GBSPLib/POLY.CPP

   1 /****************************************************************************************/\r
   2 /*  Poly.Cpp                                                                            */\r
   3 /*                                                                                      */\r
   4 /*  Author: John Pollard                                                                */\r
   5 /*  Description: Various Poly routines (clipping, splitting, etc)                       */\r
   6 /*                                                                                      */\r
   7 /*  The contents of this file are subject to the Genesis3D Public License               */\r
   8 /*  Version 1.01 (the "License"); you may not use this file except in                   */\r
   9 /*  compliance with the License. You may obtain a copy of the License at                */\r
  10 /*  http://www.genesis3d.com                                                            */\r
  11 /*                                                                                      */\r
  12 /*  Software distributed under the License is distributed on an "AS IS"                 */\r
  13 /*  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See                */\r
  14 /*  the License for the specific language governing rights and limitations              */\r
  15 /*  under the License.                                                                  */\r
  16 /*                                                                                      */\r
  17 /*  The Original Code is Genesis3D, released March 25, 1999.                            */\r
  18 /*Genesis3D Version 1.1 released November 15, 1999                            */\r
  19 /*  Copyright (C) 1999 WildTangent, Inc. All Rights Reserved           */\r
  20 /*                                                                                      */\r
  21 /****************************************************************************************/\r
  22 #include <Windows.h>\r
  23 #include <math.h>\r
  24 \r
  25 #include "BSP.h"\r
  26 #include "Mathlib.h"\r
  27 #include "Map.h"\r
  28 #include "Poly.h"\r
  29 #include "Texture.h"\r
  30 #include "GBSPFile.h"\r
  31 #include "Light.h"\r
  32 \r
  33 #include "Ram.h"\r
  34 \r
  35 int32           NumSubdivides;\r
  36 geFloat         SubdivideSize = 235.0f;\r
  37 //geFloat               SubdivideSize = ((geFloat)((16*MAX_LMAP_SIZE)-20));\r
  38 //geFloat               SubdivideSize = ((geFloat)((16*MAX_LMAP_SIZE)-32));\r
  39 \r
  40 int32           NumSubdivided;\r
  41 int32           NumMerged;\r
  42 \r
  43 //#define FREAKED_OUT\r
  44 \r
  45 geBoolean       gCountVerts;\r
  46 int32           gTotalVerts;\r
  47 int32           gPeekVerts;     \r
  48 \r
  49 //#define DEGENERATE_EPSILON            0.05f\r
  50 #define DEGENERATE_EPSILON                      0.001f\r
  51 \r
  52 //\r
  53 //      Polys\r
  54 //\r
  55 \r
  56 //====================================================================================\r
  57 //      AllocPoly\r
  58 //====================================================================================\r
  59 GBSP_Poly *AllocPoly(int32 NumVerts)\r
  60 {\r
  61         GBSP_Poly       *NewPoly;\r
  62 \r
  63         if (NumVerts > 1000)\r
  64         {\r
  65                 GHook.Error("Bogus verts: %i\n", NumVerts);\r
  66                 return NULL;\r
  67         }\r
  68         \r
  69         NewPoly = GE_RAM_ALLOCATE_STRUCT(GBSP_Poly);\r
  70 \r
  71         if (!NewPoly)\r
  72         {\r
  73                 GHook.Error("AllocPoly:  Not enough memory.\n");\r
  74                 return NULL;\r
  75         }\r
  76         \r
  77         NewPoly->Verts = GE_RAM_ALLOCATE_ARRAY(geVec3d,NumVerts);\r
  78         \r
  79         if (!NewPoly->Verts)\r
  80         {\r
  81                 GHook.Error("AllocPoly:  Not enough memory for verts: %i\n", NumVerts);\r
  82                 geRam_Free(NewPoly);\r
  83                 return NULL;\r
  84         }\r
  85 \r
  86         NewPoly->NumVerts = NumVerts;\r
  87 \r
  88 #ifdef SHOW_DEBUG_STATS\r
  89         if (gCountVerts)\r
  90         {\r
  91                 gTotalVerts += NumVerts;\r
  92                 if (gTotalVerts > gPeekVerts)\r
  93                         gPeekVerts = gTotalVerts;\r
  94         }\r
  95 #endif\r
  96 \r
  97         return NewPoly;\r
  98 }\r
  99 \r
 100 //====================================================================================\r
 101 //      FreePoly\r
 102 //====================================================================================\r
 103 void FreePoly(GBSP_Poly *Poly)\r
 104 {\r
 105         if (!Poly)\r
 106         {\r
 107                 GHook.Printf("*WARNING* FreePoly: NULL Poly.\n");\r
 108                 return;\r
 109         }\r
 110 \r
 111         if (Poly->Verts)\r
 112         {\r
 113                 geRam_Free(Poly->Verts);\r
 114 \r
 115         #ifdef SHOW_DEBUG_STATS\r
 116                 if (gCountVerts)\r
 117                 {\r
 118                         gTotalVerts -= Poly->NumVerts;\r
 119                 }\r
 120         #endif\r
 121         }\r
 122 \r
 123         geRam_Free(Poly);\r
 124 }\r
 125 \r
 126 //=====================================================================================\r
 127 //      TextureAxisFromPlane\r
 128 //=====================================================================================\r
 129 geBoolean TextureAxisFromPlane(GBSP_Plane *Pln, geVec3d *Xv, geVec3d *Yv)\r
 130 {\r
 131         int32   BestAxis;\r
 132         geFloat Dot,Best;\r
 133         int32           i;\r
 134         \r
 135         Best = 0.0f;\r
 136         BestAxis = -1;\r
 137         \r
 138         for (i=0 ; i<3 ; i++)\r
 139         {\r
 140                 Dot = (geFloat)fabs(VectorToSUB(Pln->Normal, i));\r
 141                 if (Dot > Best)\r
 142                 {\r
 143                         Best = Dot;\r
 144                         BestAxis = i;\r
 145                 }\r
 146         }\r
 147 \r
 148         switch(BestAxis)\r
 149         {\r
 150                 case 0:                                         // X\r
 151                         Xv->X = (geFloat)0;\r
 152                         Xv->Y = (geFloat)0;\r
 153                         Xv->Z = (geFloat)1;\r
 154 \r
 155                         Yv->X = (geFloat)0;\r
 156                         Yv->Y = (geFloat)-1;\r
 157                         Yv->Z = (geFloat)0;\r
 158                         break;\r
 159                 case 1:                                         // Y\r
 160                         Xv->X = (geFloat)1;\r
 161                         Xv->Y = (geFloat)0;\r
 162                         Xv->Z = (geFloat)0;\r
 163 \r
 164                         Yv->X = (geFloat)0;\r
 165                         Yv->Y = (geFloat)0;\r
 166                         Yv->Z = (geFloat)1;\r
 167                         break;\r
 168                 case 2:                                         // Z\r
 169                         Xv->X = (geFloat)1;\r
 170                         Xv->Y = (geFloat)0;\r
 171                         Xv->Z = (geFloat)0;\r
 172 \r
 173                         Yv->X = (geFloat)0;\r
 174                         Yv->Y = (geFloat)-1;\r
 175                         Yv->Z = (geFloat)0;\r
 176                         break;\r
 177                 default:\r
 178                         GHook.Error("TextureAxisFromPlane: No Axis found.\n");\r
 179                         return GE_FALSE;\r
 180                         break;\r
 181         }\r
 182 \r
 183         return GE_TRUE;\r
 184 }\r
 185 \r
 186 //====================================================================================\r
 187 //      CreatePolyFromPlane     \r
 188 //      Create a huge poly with normal pointing in same direction as Plane\r
 189 //====================================================================================\r
 190 GBSP_Poly *CreatePolyFromPlane(GBSP_Plane *Plane)\r
 191 {\r
 192         geVec3d         Normal = Plane->Normal;\r
 193         geVec3d         UpVect = {0.0f, 0.0f, 0.0f};\r
 194         geVec3d         RightVect, Org;\r
 195         GBSP_Poly       *Poly;\r
 196         \r
 197         if (!TextureAxisFromPlane(Plane, &RightVect, &UpVect))\r
 198                 return NULL;\r
 199 \r
 200         // Produce some walk vectors\r
 201         geVec3d_CrossProduct(&Normal, &UpVect, &RightVect);             // Get right vector\r
 202         geVec3d_CrossProduct(&Normal, &RightVect, &UpVect);             // Get new Up vector from correct Right vector\r
 203 \r
 204         geVec3d_Normalize(&UpVect);\r
 205         geVec3d_Normalize(&RightVect);\r
 206 \r
 207         // Create the poly with 4 verts\r
 208         Poly = AllocPoly(4);\r
 209 \r
 210         if (!Poly)\r
 211         {\r
 212                 GHook.Error("CreatePolyFromPlane:  Not enough memory for new poly!\n");\r
 213                 return NULL;\r
 214         }\r
 215 \r
 216         geVec3d_Scale(&Normal, Plane->Dist, &Org);                                              // Get the Org\r
 217         geVec3d_Scale(&UpVect, (geFloat)MIN_MAX_BOUNDS, &UpVect);                       // Scale walk vectors\r
 218         geVec3d_Scale(&RightVect, (geFloat)MIN_MAX_BOUNDS, &RightVect);\r
 219 \r
 220         geVec3d_Subtract(&Org, &RightVect, &Poly->Verts[0]);\r
 221         geVec3d_Add(&Poly->Verts[0], &UpVect, &Poly->Verts[0]);\r
 222 \r
 223         geVec3d_Add(&Org, &RightVect, &Poly->Verts[1]);\r
 224         geVec3d_Add(&Poly->Verts[1], &UpVect, &Poly->Verts[1]);\r
 225 \r
 226         geVec3d_Add(&Org, &RightVect, &Poly->Verts[2]);\r
 227         geVec3d_Subtract(&Poly->Verts[2], &UpVect, &Poly->Verts[2]);\r
 228 \r
 229         geVec3d_Subtract(&Org, &RightVect, &Poly->Verts[3]);\r
 230         geVec3d_Subtract(&Poly->Verts[3], &UpVect, &Poly->Verts[3]);\r
 231 \r
 232 #ifdef FREAKED_OUT      \r
 233         geVec3d Normal2, V1, V2;\r
 234         geVec3d_Subtract(&Poly->Verts[0], &Poly->Verts[1], &V1);\r
 235         geVec3d_Subtract(&Poly->Verts[2], &Poly->Verts[1], &V2);\r
 236         geVec3d_CrossProduct(&V1, &V2, &Normal2);\r
 237         geVec3d_Normalize(&Normal2);\r
 238         \r
 239         Normal = Plane->Normal;\r
 240         \r
 241         if (!geVec3d_Compare(&Normal, &Normal2, VCOMPARE_EPSILON))\r
 242         {\r
 243                 GHook.Error("Normal1 X:%2.2f, Y:%2.2f, Z:%2.2f\n", Normal.X, Normal.Y, Normal.Z);\r
 244                 GHook.Error("Normal2 X:%2.2f, Y:%2.2f, Z:%2.2f\n", Normal2.X, Normal2.Y, Normal2.Z);\r
 245                 GHook.Error("CreatePolyFromPlane:  Normals do not match.\n");\r
 246                 return NULL;\r
 247         }\r
 248 #endif  \r
 249 \r
 250         return Poly;\r
 251 \r
 252 }\r
 253 \r
 254 #define MAX_TEMP_VERTS  200\r
 255 \r
 256 geVec3d TempVerts[MAX_TEMP_VERTS];\r
 257 geVec3d TempVerts2[MAX_TEMP_VERTS];\r
 258 \r
 259 #define CLIP_EPSILON    (geFloat)0.001\r
 260 \r
 261 //====================================================================================\r
 262 //      ClipPoly\r
 263 //====================================================================================\r
 264 geBoolean ClipPoly(GBSP_Poly *InPoly, GBSP_Plane *Plane, geBoolean FlipTest, GBSP_Poly **OutPoly)\r
 265 {\r
 266         GBSP_Poly       *NewPoly = NULL;\r
 267         geVec3d         *pInVert, Vert1, Vert2;\r
 268         geVec3d         *pFrontVert, *Verts;\r
 269         int32           i, NextVert, NewNumVerts = 0;\r
 270         geFloat         Scale;\r
 271 \r
 272         geVec3d         Normal = Plane->Normal;\r
 273         geFloat         Dist = Plane->Dist;\r
 274         int32           NumVerts = InPoly->NumVerts;\r
 275         int32           VSides[100];\r
 276         geFloat         VDist[100];\r
 277         int32           CountSides[3];\r
 278 \r
 279         *OutPoly = NULL;\r
 280 \r
 281         if (NumVerts >= 100)\r
 282         {\r
 283                 GHook.Error("ClipPoly:  Too many verts.\n");\r
 284                 return GE_FALSE;\r
 285         }\r
 286         \r
 287         memset(CountSides, 0, sizeof(CountSides));\r
 288 \r
 289         Verts = InPoly->Verts;\r
 290         pInVert = Verts;\r
 291         pFrontVert = TempVerts;\r
 292         \r
 293         if (FlipTest)           // Flip the normal and dist\r
 294         {\r
 295                 Normal.X = -Normal.X;\r
 296                 Normal.Y = -Normal.Y;\r
 297                 Normal.Z = -Normal.Z;\r
 298                 Dist = -Dist;\r
 299         }\r
 300         \r
 301         // See what side of plane each vert is on\r
 302         for (i=0; i< NumVerts; i++)\r
 303         {\r
 304                 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;\r
 305                 if (VDist[i] > ON_EPSILON)\r
 306                         VSides[i] = 0;\r
 307                 else if (VDist[i] < -ON_EPSILON)\r
 308                         VSides[i] = 1;\r
 309                 else\r
 310                         VSides[i] = 2;\r
 311 \r
 312                 CountSides[VSides[i]]++;\r
 313         }\r
 314 \r
 315         if (!CountSides[0])\r
 316         {\r
 317                 FreePoly(InPoly);\r
 318                 *OutPoly = NULL;\r
 319                 return GE_TRUE;\r
 320         }\r
 321 \r
 322         if (!CountSides[1])\r
 323         {\r
 324                 *OutPoly = InPoly;\r
 325                 return GE_TRUE;\r
 326         }\r
 327 \r
 328         // Else we have to split this sucker\r
 329         for (i=0; i< NumVerts; i++)\r
 330         {\r
 331                 Vert1 = Verts[i];\r
 332 \r
 333                 if (VSides[i] == 2)                             // On plane, put on both sides\r
 334                 {\r
 335             *pFrontVert++ = Vert1;\r
 336                         continue;\r
 337                 }\r
 338                 \r
 339                 if (VSides[i] == 0)                             // Front side, put on front list\r
 340             *pFrontVert++ = Vert1;\r
 341 \r
 342                 NextVert = (i+1) % NumVerts;\r
 343                 \r
 344                 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])\r
 345                         continue;\r
 346 \r
 347                 Vert2 = Verts[NextVert];\r
 348                 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);\r
 349 \r
 350                 pFrontVert->X = Vert1.X + (Vert2.X - Vert1.X) * Scale;\r
 351                 pFrontVert->Y = Vert1.Y + (Vert2.Y - Vert1.Y) * Scale;\r
 352                 pFrontVert->Z = Vert1.Z + (Vert2.Z - Vert1.Z) * Scale;\r
 353 \r
 354                 pFrontVert++;\r
 355         }\r
 356 \r
 357         FreePoly(InPoly);               // Don't need this anymore\r
 358 \r
 359     NewNumVerts = pFrontVert - TempVerts;\r
 360 \r
 361         if (NewNumVerts < 3)\r
 362         {\r
 363                 *OutPoly = NULL;\r
 364                 return GE_TRUE;\r
 365         }\r
 366         \r
 367         NewPoly = AllocPoly(NewNumVerts);\r
 368 \r
 369         if (!NewPoly)\r
 370         {\r
 371                 GHook.Error("ClipPoly:  Not enough mem for new poly.\n");\r
 372                 return GE_FALSE;\r
 373         }\r
 374 \r
 375         for (i = 0; i< NewNumVerts; i++)\r
 376                 NewPoly->Verts[i] =     TempVerts[i];\r
 377 \r
 378         *OutPoly = NewPoly;\r
 379         return GE_TRUE;\r
 380 }\r
 381 \r
 382 //====================================================================================\r
 383 //      ClipPolyEpsilon\r
 384 //====================================================================================\r
 385 geBoolean ClipPolyEpsilon(GBSP_Poly *InPoly, geFloat Epsilon, GBSP_Plane *Plane, geBoolean FlipTest, GBSP_Poly **OutPoly)\r
 386 {\r
 387         GBSP_Poly       *NewPoly = NULL;\r
 388         geVec3d         *pInVert, Vert1, Vert2;\r
 389         geVec3d         *pFrontVert, *Verts;\r
 390         int32           i, NextVert, NewNumVerts = 0;\r
 391         geFloat         Scale;\r
 392 \r
 393         geVec3d         Normal = Plane->Normal;\r
 394         geFloat         Dist = Plane->Dist;\r
 395         int32           NumVerts = InPoly->NumVerts;\r
 396         int32           VSides[100];\r
 397         geFloat         VDist[100];\r
 398         int32           CountSides[3];\r
 399 \r
 400         *OutPoly = NULL;\r
 401 \r
 402         if (NumVerts >= 100)\r
 403         {\r
 404                 GHook.Error("ClipPoly:  Too many verts.\n");\r
 405                 return GE_FALSE;\r
 406         }\r
 407         \r
 408         memset(CountSides, 0, sizeof(CountSides));\r
 409 \r
 410         Verts = InPoly->Verts;\r
 411         pInVert = Verts;\r
 412         pFrontVert = TempVerts;\r
 413         \r
 414         if (FlipTest)           // Flip the normal and dist\r
 415         {\r
 416                 Normal.X = -Normal.X;\r
 417                 Normal.Y = -Normal.Y;\r
 418                 Normal.Z = -Normal.Z;\r
 419                 Dist = -Dist;\r
 420         }\r
 421         \r
 422         // See what side of plane each vert is on\r
 423         for (i=0; i< NumVerts; i++)\r
 424         {\r
 425                 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;\r
 426                 if (VDist[i] > Epsilon)\r
 427                         VSides[i] = 0;\r
 428                 else if (VDist[i] < -Epsilon)\r
 429                         VSides[i] = 1;\r
 430                 else\r
 431                         VSides[i] = 2;\r
 432 \r
 433                 CountSides[VSides[i]]++;\r
 434         }\r
 435 \r
 436         if (!CountSides[0])\r
 437         {\r
 438                 FreePoly(InPoly);\r
 439                 *OutPoly = NULL;\r
 440                 return GE_TRUE;\r
 441         }\r
 442 \r
 443         if (!CountSides[1])\r
 444         {\r
 445                 *OutPoly = InPoly;\r
 446                 return GE_TRUE;\r
 447         }\r
 448 \r
 449         // Else we have to split this sucker\r
 450         for (i=0; i< NumVerts; i++)\r
 451         {\r
 452                 Vert1 = Verts[i];\r
 453 \r
 454                 if (VSides[i] == 2)                             // On plane, put on both sides\r
 455                 {\r
 456             *pFrontVert++ = Vert1;\r
 457                         continue;\r
 458                 }\r
 459                 \r
 460                 if (VSides[i] == 0)                             // Front side, put on front list\r
 461             *pFrontVert++ = Vert1;\r
 462 \r
 463                 NextVert = (i+1) % NumVerts;\r
 464                 \r
 465                 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])\r
 466                         continue;\r
 467 \r
 468                 Vert2 = Verts[NextVert];\r
 469                 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);\r
 470 \r
 471                 pFrontVert->X = Vert1.X + (Vert2.X - Vert1.X) * Scale;\r
 472                 pFrontVert->Y = Vert1.Y + (Vert2.Y - Vert1.Y) * Scale;\r
 473                 pFrontVert->Z = Vert1.Z + (Vert2.Z - Vert1.Z) * Scale;\r
 474 \r
 475                 pFrontVert++;\r
 476         }\r
 477 \r
 478         FreePoly(InPoly);               // Don't need this anymore\r
 479 \r
 480     NewNumVerts = pFrontVert - TempVerts;\r
 481 \r
 482         if (NewNumVerts < 3)\r
 483         {\r
 484                 *OutPoly = NULL;\r
 485                 return GE_TRUE;\r
 486         }\r
 487         \r
 488         NewPoly = AllocPoly(NewNumVerts);\r
 489 \r
 490         if (!NewPoly)\r
 491         {\r
 492                 GHook.Error("ClipPoly:  Not enough mem for new poly.\n");\r
 493                 return GE_FALSE;\r
 494         }\r
 495 \r
 496         for (i = 0; i< NewNumVerts; i++)\r
 497                 NewPoly->Verts[i] =     TempVerts[i];\r
 498 \r
 499         *OutPoly = NewPoly;\r
 500         return GE_TRUE;\r
 501 }\r
 502 \r
 503 //====================================================================================\r
 504 //      SplitPoly\r
 505 //====================================================================================\r
 506 geBoolean SplitPoly(GBSP_Poly *InPoly, GBSP_Plane *Plane, GBSP_Poly **Front, GBSP_Poly **Back, \r
 507                            geBoolean FlipTest)\r
 508 {\r
 509         GBSP_Poly       *NewPoly = NULL;\r
 510         geVec3d         *pInVert, Vert1, Vert2;\r
 511         geVec3d         *pFrontVert, *pBackVert, *Verts;\r
 512         int32           i, NextVert, NewNumVerts = 0;\r
 513         geFloat         Scale;\r
 514 \r
 515         geVec3d         Normal = Plane->Normal;\r
 516         geFloat         Dist = Plane->Dist, *pDist;\r
 517         int32           NumVerts = InPoly->NumVerts;\r
 518         int32           VSides[100];\r
 519         geFloat         VDist[100];\r
 520         int32           CountSides[3];\r
 521 \r
 522         if (NumVerts >= 100)\r
 523         {\r
 524                 GHook.Error("SplitPoly:  Too many verts.\n");\r
 525                 return GE_FALSE;\r
 526         }\r
 527         \r
 528         memset(CountSides, 0, sizeof(CountSides));\r
 529 \r
 530         Verts = InPoly->Verts;\r
 531         pInVert = Verts;\r
 532         pFrontVert = TempVerts;\r
 533         pBackVert = TempVerts2;\r
 534         \r
 535         if (FlipTest)           // Flip the normal and dist\r
 536         {\r
 537                 Normal.X = -Normal.X;\r
 538                 Normal.Y = -Normal.Y;\r
 539                 Normal.Z = -Normal.Z;\r
 540                 Dist = -Dist;\r
 541         }\r
 542         \r
 543         // See what side of plane each vert is on\r
 544         if (Plane->Type < PLANE_ANYX)\r
 545         {\r
 546                 pDist = &VectorToSUB(Verts[0], Plane->Type);\r
 547 \r
 548                 for (i=0; i< NumVerts ; i++)\r
 549                 {\r
 550 \r
 551                         //VDist[i] = VectorToSUB(Verts[i], Plane->Type) - Plane->Dist;\r
 552                         VDist[i] = *pDist - Plane->Dist;\r
 553                         if (FlipTest)\r
 554                                 VDist[i] = -VDist[i];\r
 555 \r
 556                         if (VDist[i] > ON_EPSILON)\r
 557                                 VSides[i] = 0;\r
 558                         else if (VDist[i] < -ON_EPSILON)\r
 559                                 VSides[i] = 1;\r
 560                         else\r
 561                                 VSides[i] = 2;\r
 562 \r
 563                         CountSides[VSides[i]]++;\r
 564 \r
 565                         pDist += 3;\r
 566                 }\r
 567         }\r
 568         else\r
 569         {\r
 570                 for (i=0; i< NumVerts; i++)\r
 571                 {\r
 572                         VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;\r
 573                         if (VDist[i] > ON_EPSILON)\r
 574                                 VSides[i] = 0;\r
 575                         else if (VDist[i] < -ON_EPSILON)\r
 576                                 VSides[i] = 1;\r
 577                         else\r
 578                                 VSides[i] = 2;\r
 579 \r
 580                         CountSides[VSides[i]]++;\r
 581                 }\r
 582         }\r
 583 \r
 584         if (!CountSides[0] && !CountSides[1])\r
 585         {\r
 586                 *Back = NULL;\r
 587                 *Front = InPoly;\r
 588                 return GE_TRUE;\r
 589         }\r
 590 \r
 591         // Get out quick, if no splitting is neccesary\r
 592         if (!CountSides[0])\r
 593         {\r
 594                 *Front = NULL;\r
 595                 *Back = InPoly;\r
 596                 return GE_TRUE;\r
 597         }\r
 598         if (!CountSides[1])\r
 599         {\r
 600                 *Back = NULL;\r
 601                 *Front = InPoly;\r
 602                 return GE_TRUE;\r
 603         }\r
 604 \r
 605         // Else we have to split this sucker\r
 606         for (i=0; i< NumVerts; i++)\r
 607         {\r
 608                 Vert1 = Verts[i];\r
 609 \r
 610                 if (VSides[i] == 2)                             // On plane, put on both sides\r
 611                 {\r
 612             *pFrontVert++ = Vert1;\r
 613             *pBackVert++ = Vert1;\r
 614                         continue;\r
 615                 }\r
 616                 \r
 617                 if (VSides[i] == 0)                             // Front side, put on front list\r
 618             *pFrontVert++ = Vert1;\r
 619                 else if (VSides[i] == 1)                // Back side, put on back list\r
 620             *pBackVert++ = Vert1;\r
 621 \r
 622 \r
 623                 NextVert = (i+1) % NumVerts;\r
 624                 \r
 625                 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])\r
 626                         continue;\r
 627 \r
 628                 Vert2 = Verts[NextVert];\r
 629                 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);\r
 630 \r
 631                 pFrontVert->X = Vert1.X + (Vert2.X - Vert1.X) * Scale;\r
 632                 pFrontVert->Y = Vert1.Y + (Vert2.Y - Vert1.Y) * Scale;\r
 633                 pFrontVert->Z = Vert1.Z + (Vert2.Z - Vert1.Z) * Scale;\r
 634 \r
 635                 *pBackVert = *pFrontVert;\r
 636                 pFrontVert++;\r
 637                 pBackVert++;\r
 638         }\r
 639 \r
 640         FreePoly(InPoly);               // Don't need this anymore\r
 641 \r
 642     NewNumVerts = pFrontVert - TempVerts;\r
 643 \r
 644         if (NewNumVerts < 3)\r
 645                 *Front = NULL;\r
 646         else\r
 647         {\r
 648                 NewPoly = AllocPoly(NewNumVerts);\r
 649 \r
 650                 if (!NewPoly)\r
 651                 {\r
 652                         GHook.Error("SplitPoly:  Not enough mem for new poly.\n");\r
 653                         return GE_FALSE;\r
 654                 }\r
 655 \r
 656                 for (i = 0; i< NewNumVerts; i++)\r
 657                         NewPoly->Verts[i] =     TempVerts[i];\r
 658 \r
 659                 *Front = NewPoly;\r
 660         }\r
 661     \r
 662         NewNumVerts = pBackVert - TempVerts2;\r
 663         \r
 664         if (NewNumVerts < 3)\r
 665                 *Back = NULL;\r
 666         else\r
 667         {\r
 668                 NewPoly = AllocPoly(NewNumVerts);\r
 669 \r
 670                 if (!NewPoly)\r
 671                 {\r
 672                         GHook.Error("SplitPoly:  Not enough mem for new poly.\n");\r
 673                         return GE_FALSE;\r
 674                 }\r
 675 \r
 676                 for (i = 0; i< NewNumVerts; i++)\r
 677                         NewPoly->Verts[i] = TempVerts2[i];\r
 678 \r
 679                 *Back = NewPoly;\r
 680         }\r
 681 \r
 682         return GE_TRUE;\r
 683 }\r
 684 \r
 685 //====================================================================================\r
 686 //      SplitPoly\r
 687 //====================================================================================\r
 688 geBoolean SplitPolyEpsilon(GBSP_Poly *InPoly, geFloat Epsilon, GBSP_Plane *Plane, GBSP_Poly **Front, GBSP_Poly **Back, \r
 689                            geBoolean FlipTest)\r
 690 {\r
 691         GBSP_Poly       *NewPoly = NULL;\r
 692         geVec3d         *pInVert, Vert1, Vert2;\r
 693         geVec3d         *pFrontVert, *pBackVert, *Verts;\r
 694         int32           i, NextVert, NewNumVerts = 0;\r
 695         geFloat         Scale;\r
 696 \r
 697         geVec3d         Normal = Plane->Normal;\r
 698         geFloat         Dist = Plane->Dist, *pDist;\r
 699         int32           NumVerts = InPoly->NumVerts;\r
 700         int32           VSides[100];\r
 701         geFloat         VDist[100];\r
 702         int32           CountSides[3];\r
 703 \r
 704         if (NumVerts >= 100)\r
 705         {\r
 706                 GHook.Error("SplitPoly:  Too many verts.\n");\r
 707                 return GE_FALSE;\r
 708         }\r
 709         \r
 710         memset(CountSides, 0, sizeof(CountSides));\r
 711 \r
 712         Verts = InPoly->Verts;\r
 713         pInVert = Verts;\r
 714         pFrontVert = TempVerts;\r
 715         pBackVert = TempVerts2;\r
 716         \r
 717         if (FlipTest)           // Flip the normal and dist\r
 718         {\r
 719                 Normal.X = -Normal.X;\r
 720                 Normal.Y = -Normal.Y;\r
 721                 Normal.Z = -Normal.Z;\r
 722                 Dist = -Dist;\r
 723         }\r
 724         \r
 725         // See what side of plane each vert is on\r
 726         if (Plane->Type < PLANE_ANYX)\r
 727         {\r
 728                 pDist = &VectorToSUB(Verts[0], Plane->Type);\r
 729 \r
 730                 for (i=0; i< NumVerts ; i++)\r
 731                 {\r
 732 \r
 733                         //VDist[i] = VectorToSUB(Verts[i], Plane->Type) - Plane->Dist;\r
 734                         VDist[i] = *pDist - Plane->Dist;\r
 735                         if (FlipTest)\r
 736                                 VDist[i] = -VDist[i];\r
 737 \r
 738                         if (VDist[i] > Epsilon)\r
 739                                 VSides[i] = 0;\r
 740                         else if (VDist[i] < -Epsilon)\r
 741                                 VSides[i] = 1;\r
 742                         else\r
 743                                 VSides[i] = 2;\r
 744 \r
 745                         CountSides[VSides[i]]++;\r
 746 \r
 747                         pDist += 3;\r
 748                 }\r
 749         }\r
 750         else\r
 751         {\r
 752                 for (i=0; i< NumVerts; i++)\r
 753                 {\r
 754                         VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;\r
 755                         if (VDist[i] > Epsilon)\r
 756                                 VSides[i] = 0;\r
 757                         else if (VDist[i] < -Epsilon)\r
 758                                 VSides[i] = 1;\r
 759                         else\r
 760                                 VSides[i] = 2;\r
 761 \r
 762                         CountSides[VSides[i]]++;\r
 763                 }\r
 764         }\r
 765 \r
 766         // Get out quick, if no splitting is neccesary\r
 767         if (!CountSides[0])\r
 768         {\r
 769                 *Front = NULL;\r
 770                 *Back = InPoly;\r
 771                 return GE_TRUE;\r
 772         }\r
 773         if (!CountSides[1])\r
 774         {\r
 775                 *Back = NULL;\r
 776                 *Front = InPoly;\r
 777                 return GE_TRUE;\r
 778         }\r
 779 \r
 780         // Else we have to split this sucker\r
 781         for (i=0; i< NumVerts; i++)\r
 782         {\r
 783                 Vert1 = Verts[i];\r
 784 \r
 785                 if (VSides[i] == 2)                             // On plane, put on both sides\r
 786                 {\r
 787             *pFrontVert++ = Vert1;\r
 788             *pBackVert++ = Vert1;\r
 789                         continue;\r
 790                 }\r
 791                 \r
 792                 if (VSides[i] == 0)                             // Front side, put on front list\r
 793             *pFrontVert++ = Vert1;\r
 794                 else if (VSides[i] == 1)                // Back side, put on back list\r
 795             *pBackVert++ = Vert1;\r
 796 \r
 797 \r
 798                 NextVert = (i+1) % NumVerts;\r
 799                 \r
 800                 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])\r
 801                         continue;\r
 802 \r
 803                 Vert2 = Verts[NextVert];\r
 804                 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);\r
 805 \r
 806                 pFrontVert->X = Vert1.X + (Vert2.X - Vert1.X) * Scale;\r
 807                 pFrontVert->Y = Vert1.Y + (Vert2.Y - Vert1.Y) * Scale;\r
 808                 pFrontVert->Z = Vert1.Z + (Vert2.Z - Vert1.Z) * Scale;\r
 809 \r
 810                 *pBackVert = *pFrontVert;\r
 811                 pFrontVert++;\r
 812                 pBackVert++;\r
 813         }\r
 814 \r
 815         FreePoly(InPoly);               // Don't need this anymore\r
 816 \r
 817     NewNumVerts = pFrontVert - TempVerts;\r
 818 \r
 819         if (NewNumVerts < 3)\r
 820                 *Front = NULL;\r
 821         else\r
 822         {\r
 823                 NewPoly = AllocPoly(NewNumVerts);\r
 824 \r
 825                 if (!NewPoly)\r
 826                 {\r
 827                         GHook.Error("SplitPoly:  Not enough mem for new poly.\n");\r
 828                         return GE_FALSE;\r
 829                 }\r
 830 \r
 831                 for (i = 0; i< NewNumVerts; i++)\r
 832                         NewPoly->Verts[i] =     TempVerts[i];\r
 833 \r
 834                 *Front = NewPoly;\r
 835         }\r
 836     \r
 837         NewNumVerts = pBackVert - TempVerts2;\r
 838         \r
 839         if (NewNumVerts < 3)\r
 840                 *Back = NULL;\r
 841         else\r
 842         {\r
 843                 NewPoly = AllocPoly(NewNumVerts);\r
 844 \r
 845                 if (!NewPoly)\r
 846                 {\r
 847                         GHook.Error("SplitPoly:  Not enough mem for new poly.\n");\r
 848                         return GE_FALSE;\r
 849                 }\r
 850 \r
 851                 for (i = 0; i< NewNumVerts; i++)\r
 852                         NewPoly->Verts[i] = TempVerts2[i];\r
 853 \r
 854                 *Back = NewPoly;\r
 855         }\r
 856 \r
 857         return GE_TRUE;\r
 858 }\r
 859 \r
 860 //====================================================================================\r
 861 //      RemoveDegenerateEdges\r
 862 //====================================================================================\r
 863 void RemoveDegenerateEdges(GBSP_Poly *Poly)\r
 864 {\r
 865         int32           i, NumVerts;\r
 866         geVec3d         *Verts, V1, V2, NVerts[1000], Vec;\r
 867         geBoolean       Bad = GE_FALSE;\r
 868         int32           NumNVerts = 0;\r
 869 \r
 870         Verts = Poly->Verts;\r
 871         NumVerts = Poly->NumVerts;\r
 872 \r
 873         for (i=0; i< NumVerts; i++)\r
 874         {\r
 875                 V1 = Verts[i];\r
 876                 V2 = Verts[(i+1)%NumVerts];\r
 877 \r
 878                 geVec3d_Subtract(&V1, &V2, &Vec);\r
 879 \r
 880                 if (geVec3d_Length(&Vec) > DEGENERATE_EPSILON)\r
 881                 {\r
 882                         NVerts[NumNVerts++] = V1;       \r
 883                 }\r
 884                 else\r
 885                         Bad = GE_TRUE;\r
 886         }\r
 887 \r
 888         if (Bad)\r
 889         {\r
 890                 //Hook.Printf("Removing degenerate edge...\n");\r
 891 \r
 892                 Poly->NumVerts = NumNVerts;\r
 893                 for (i=0; i< NumNVerts; i++)\r
 894                 {\r
 895                         Verts[i] = NVerts[i];\r
 896                 }\r
 897         }\r
 898 }\r
 899 \r
 900 //====================================================================================\r
 901 //      RemoveDegenerateEdges2\r
 902 //====================================================================================\r
 903 geBoolean RemoveDegenerateEdges2(GBSP_Poly *Poly)\r
 904 {\r
 905         int32           i, NumVerts;\r
 906         geVec3d         *Verts, V1, V2, NVerts[1000], Vec;\r
 907         geBoolean       Bad = GE_FALSE;\r
 908         int32           NumNVerts = 0;\r
 909 \r
 910         Verts = Poly->Verts;\r
 911         NumVerts = Poly->NumVerts;\r
 912 \r
 913         for (i=0; i< NumVerts; i++)\r
 914         {\r
 915                 V1 = Verts[i];\r
 916                 V2 = Verts[(i+1)%NumVerts];\r
 917 \r
 918                 geVec3d_Subtract(&V1, &V2, &Vec);\r
 919 \r
 920                 if (geVec3d_Length(&Vec) > DEGENERATE_EPSILON)\r
 921                 {\r
 922                         NVerts[NumNVerts++] = V1;       \r
 923                 }\r
 924                 else\r
 925                         Bad = GE_TRUE;\r
 926         }\r
 927 \r
 928         if (NumNVerts < 3)\r
 929                 return GE_FALSE;\r
 930 \r
 931         if (Bad)\r
 932         {\r
 933                 Poly->NumVerts = NumNVerts;\r
 934                 for (i=0; i< NumNVerts; i++)\r
 935                 {\r
 936                         Verts[i] = NVerts[i];\r
 937                 }\r
 938         }\r
 939 \r
 940         return GE_TRUE;\r
 941 }\r
 942 \r
 943 //====================================================================================\r
 944 //      PolyArea\r
 945 //====================================================================================\r
 946 geFloat PolyArea(GBSP_Poly *Poly)\r
 947 {\r
 948         int32   i;\r
 949         geVec3d Vect1, Vect2, Cross;\r
 950         geFloat Total;\r
 951 \r
 952         Total = 0.0f;\r
 953 \r
 954         for (i=2 ; i<Poly->NumVerts ; i++)\r
 955         {\r
 956                 geVec3d_Subtract(&Poly->Verts[i-1], &Poly->Verts[0], &Vect1);\r
 957                 geVec3d_Subtract(&Poly->Verts[i]  , &Poly->Verts[0], &Vect2);\r
 958                 geVec3d_CrossProduct (&Vect1, &Vect2, &Cross);\r
 959                 Total += (geFloat)0.5 * geVec3d_Length(&Cross);\r
 960         }\r
 961 \r
 962         return (geFloat)Total;\r
 963 }\r
 964 \r
 965 #define BOGUS_VERTS             256\r
 966 //====================================================================================\r
 967 //      CopyPoly\r
 968 //====================================================================================\r
 969 geBoolean CopyPoly(GBSP_Poly *In, GBSP_Poly **Out)\r
 970 {\r
 971         GBSP_Poly       *NewPoly;\r
 972         int32           i;\r
 973 \r
 974         if (!In)\r
 975         {\r
 976                 GHook.Error("CopyPoly:  NULL Poly!!!\n");\r
 977                 return GE_FALSE;\r
 978         }\r
 979 \r
 980         if (In->NumVerts <= 0 || In->NumVerts >= BOGUS_VERTS)\r
 981         {\r
 982                 GHook.Error("CopyPoly:  Bogus number of verts:  %i\n", In->NumVerts);\r
 983                 return GE_FALSE;\r
 984         }\r
 985         \r
 986         NewPoly = AllocPoly(In->NumVerts);\r
 987         if (!NewPoly)\r
 988         {\r
 989                 return GE_FALSE;\r
 990         }\r
 991 \r
 992         for (i=0; i<In->NumVerts; i++)\r
 993                 NewPoly->Verts[i] = In->Verts[i];\r
 994         \r
 995         *Out = NewPoly;\r
 996 \r
 997         return GE_TRUE;\r
 998 }\r
 999 \r
1000 //====================================================================================\r
1001 //      CopyPoly2\r
1002 //====================================================================================\r
1003 GBSP_Poly *CopyPoly2(GBSP_Poly *In)\r
1004 {\r
1005         GBSP_Poly       *NewPoly;\r
1006         int32           i;\r
1007 \r
1008         if (!In)\r
1009         {\r
1010                 GHook.Error("CopyPoly:  NULL Poly!!!\n");\r
1011                 return NULL;\r
1012         }\r
1013 \r
1014         if (In->NumVerts <= 0 || In->NumVerts >= BOGUS_VERTS)\r
1015         {\r
1016                 GHook.Error("CopyPoly:  Bogus number of verts:  %i\n", In->NumVerts);\r
1017                 return NULL;\r
1018         }\r
1019         \r
1020         NewPoly = AllocPoly(In->NumVerts);\r
1021 \r
1022         if (!NewPoly)\r
1023                 return NULL;\r
1024 \r
1025         for (i=0; i<In->NumVerts; i++)\r
1026                 NewPoly->Verts[i] = In->Verts[i];\r
1027         \r
1028         return NewPoly;\r
1029 }\r
1030 \r
1031 //====================================================================================\r
1032 //      ReversePoly\r
1033 //====================================================================================\r
1034 geBoolean ReversePoly(GBSP_Poly *In, GBSP_Poly **Out)\r
1035 {\r
1036         GBSP_Poly       *NewPoly;\r
1037         int32           i;\r
1038 \r
1039         NewPoly = AllocPoly(In->NumVerts);\r
1040         if (!NewPoly)\r
1041         {\r
1042                 return GE_FALSE;\r
1043         }\r
1044 \r
1045         for (i=0; i<In->NumVerts; i++)\r
1046                 NewPoly->Verts[i] = In->Verts[In->NumVerts-i-1];\r
1047         \r
1048         *Out = NewPoly;\r
1049 \r
1050         return GE_TRUE;\r
1051 }\r
1052 \r
1053 //====================================================================================\r
1054 //      PolyCenter\r
1055 //====================================================================================\r
1056 void PolyCenter(GBSP_Poly *Poly, geVec3d *Center)\r
1057 {\r
1058         int32   i;\r
1059 \r
1060         geVec3d_Clear(Center);\r
1061 \r
1062         for (i=0; i< Poly->NumVerts; i++)\r
1063                 geVec3d_Add(Center, &Poly->Verts[i], Center);\r
1064 \r
1065         geVec3d_Scale(Center, (geFloat)1.0/(geFloat)Poly->NumVerts, Center);\r
1066 }\r
1067 \r
1068 #define EDGE_LENGTH                     (geFloat)0.1\r
1069 \r
1070 //====================================================================================\r
1071 //      PolyIsTiny\r
1072 //====================================================================================\r
1073 geBoolean PolyIsTiny (GBSP_Poly *Poly)\r
1074 {\r
1075         int32   i, j;\r
1076         geFloat Len;\r
1077         geVec3d Delta;\r
1078         int32   Edges;\r
1079 \r
1080         Edges = 0;\r
1081 \r
1082         //return GE_FALSE;\r
1083 \r
1084         for (i=0 ; i<Poly->NumVerts ; i++)\r
1085         {\r
1086                 j = i == Poly->NumVerts - 1 ? 0 : i+1;\r
1087 \r
1088                 geVec3d_Subtract(&Poly->Verts[j], &Poly->Verts[i], &Delta);\r
1089 \r
1090                 Len = geVec3d_Length(&Delta);\r
1091 \r
1092                 if (Len > EDGE_LENGTH)\r
1093                 {\r
1094                         if (++Edges == 3)\r
1095                                 return GE_FALSE;\r
1096                 }\r
1097         }\r
1098 \r
1099         //GHook.Printf("Poly is tiny...\n");\r
1100 \r
1101         return GE_TRUE;\r
1102 }\r
1103 \r
1104 //\r
1105 //      Faces\r
1106 //\r
1107 \r
1108 //====================================================================================\r
1109 //      AllocFace\r
1110 //====================================================================================\r
1111 GBSP_Face *AllocFace(int32 NumVerts)\r
1112 {\r
1113         GBSP_Face *Face;\r
1114 \r
1115         Face = GE_RAM_ALLOCATE_STRUCT(GBSP_Face);\r
1116 \r
1117         if (!Face)\r
1118                 return NULL;\r
1119 \r
1120         memset(Face, 0, sizeof(GBSP_Face));\r
1121 \r
1122         if (NumVerts)\r
1123         {\r
1124                 Face->Poly = AllocPoly(NumVerts);\r
1125                 if (!Face->Poly)\r
1126                 {\r
1127                         FreeFace(Face);\r
1128                         return NULL;\r
1129                 }\r
1130         }\r
1131         else\r
1132                 Face->Poly = NULL;\r
1133 \r
1134         return Face;\r
1135 }\r
1136 \r
1137 //====================================================================================\r
1138 //      FreeFace\r
1139 //====================================================================================\r
1140 void FreeFace(GBSP_Face *Face)\r
1141 {\r
1142         if (!Face)\r
1143         {\r
1144                 GHook.Printf("*WARNING* FreeFace: NULL Face.\n");\r
1145                 return;\r
1146         }\r
1147 \r
1148         //if (!Face->Poly)\r
1149         //      Hook.Error("FreeFace: NULL Poly.\n");\r
1150         if (Face->Poly)\r
1151                 FreePoly(Face->Poly);\r
1152         Face->Poly = NULL;\r
1153 \r
1154         if (Face->IndexVerts)\r
1155                 geRam_Free(Face->IndexVerts);\r
1156         Face->IndexVerts = NULL;\r
1157         \r
1158         geRam_Free(Face);\r
1159 }\r
1160 \r
1161 //====================================================================================\r
1162 //      void SplitFace\r
1163 //====================================================================================\r
1164 geBoolean SplitFace(GBSP_Face *In, GBSP_Plane *Split, GBSP_Face **Front, GBSP_Face **Back, geBoolean FlipTest)\r
1165 {\r
1166         GBSP_Poly       *F, *B;\r
1167         GBSP_Face       *NewFace;\r
1168 \r
1169         if (!SplitPoly(In->Poly, Split, &F, &B, FlipTest))\r
1170                 return GE_FALSE;\r
1171 \r
1172         if (!F && !B)\r
1173         {\r
1174                 GHook.Error("SplitFace:  Poly was clipped away.\n");\r
1175                 return GE_FALSE;\r
1176         }\r
1177 \r
1178         if (!F)\r
1179         {\r
1180                 In->Poly = B;\r
1181                 *Back = In;\r
1182                 *Front = NULL;\r
1183                 return GE_TRUE;\r
1184         }\r
1185         if (!B)\r
1186         {\r
1187                 In->Poly = F;\r
1188                 *Front = In;\r
1189                 *Back = NULL;\r
1190                 return GE_TRUE;\r
1191         }\r
1192 \r
1193         NewFace = GE_RAM_ALLOCATE_STRUCT(GBSP_Face);\r
1194         if (!NewFace)\r
1195         {\r
1196                 GHook.Error("SplitFace:  Out of memory for new face.\n");\r
1197                 return GE_FALSE;\r
1198         }\r
1199 \r
1200         *NewFace = *In;\r
1201 \r
1202         In->Poly = F;\r
1203         NewFace->Poly = B;\r
1204 \r
1205         *Front = In;\r
1206         *Back = NewFace;\r
1207 \r
1208         return GE_TRUE;\r
1209 }\r
1210 \r
1211 //====================================================================================\r
1212 //      CopyFace\r
1213 //====================================================================================\r
1214 geBoolean CopyFace(GBSP_Face *In, GBSP_Face **Out)\r
1215 {\r
1216         GBSP_Face       *NewFace;\r
1217         GBSP_Poly       *NewPoly;\r
1218         int32           i;\r
1219 \r
1220         NewFace = AllocFace(0);\r
1221 \r
1222         if (!NewFace)\r
1223         {\r
1224                 GHook.Error("CopyFaceList:  Out of memory for new face.\n");\r
1225                 return GE_FALSE;\r
1226         }\r
1227 \r
1228         *NewFace = *In;\r
1229         NewPoly = AllocPoly(In->Poly->NumVerts);\r
1230 \r
1231         if (!NewPoly)\r
1232         {\r
1233                 GHook.Error("CopyFaceList:  Out of memory for newpoly.\n");\r
1234                 return GE_FALSE;\r
1235         }\r
1236                 \r
1237         NewFace->Poly = NewPoly;\r
1238 \r
1239         for (i=0; i< In->Poly->NumVerts; i++)\r
1240                 NewFace->Poly->Verts[i] = In->Poly->Verts[i];\r
1241 \r
1242         return GE_TRUE;\r
1243 }\r
1244 \r
1245 //====================================================================================\r
1246 //      MergeFaceList2\r
1247 //====================================================================================\r
1248 geBoolean MergeFaceList2(GBSP_Face *Faces)\r
1249 {\r
1250         GBSP_Face       *Face1, *Face2, *End, *Merged;\r
1251 \r
1252         for (Face1 = Faces ; Face1 ; Face1 = Face1->Next)\r
1253         {\r
1254                 if (Face1->Poly->NumVerts == -1)\r
1255                         continue;\r
1256 \r
1257                 if (Face1->Merged || Face1->Split[0] || Face1->Split[1])\r
1258                         continue;\r
1259 \r
1260                 for (Face2 = Faces ; Face2 != Face1 ; Face2 = Face2->Next)\r
1261                 {\r
1262                         if (Face2->Poly->NumVerts == -1)\r
1263                                 continue;\r
1264 \r
1265                         if (Face2->Merged || Face2->Split[0] || Face2->Split[1])\r
1266                                 continue;\r
1267                         \r
1268                         Merged = MergeFace(Face1, Face2);\r
1269 \r
1270                         if (!Merged)\r
1271                                 continue;\r
1272 \r
1273                         RemoveDegenerateEdges(Merged->Poly);\r
1274                         \r
1275                         if (!CheckFace(Merged, GE_FALSE))\r
1276                         {\r
1277                                 FreeFace(Merged);\r
1278                                 Face1->Merged = NULL;\r
1279                                 Face2->Merged = NULL;\r
1280                                 continue;\r
1281                         }\r
1282 \r
1283                         NumMerged++;\r
1284 \r
1285                         // Add the Merged to the end of the face list \r
1286                         // so it will be checked against all the faces again\r
1287                         for (End = Faces ; End->Next ; End = End->Next);\r
1288                                 \r
1289                         Merged->Next = NULL;\r
1290                         End->Next = Merged;\r
1291                         break;\r
1292                 }\r
1293         }\r
1294 \r
1295         return GE_TRUE;\r
1296 }\r
1297 \r
1298 //====================================================================================\r
1299 //      FreeFaceList\r
1300 //====================================================================================\r
1301 void FreeFaceList(GBSP_Face *List)\r
1302 {                       \r
1303         GBSP_Face       *Next;\r
1304 \r
1305         while(List)\r
1306         {\r
1307                 Next = List->Next;\r
1308                 FreeFace(List);\r
1309                 List = Next;\r
1310         }\r
1311 }\r
1312 \r
1313 //====================================================================================\r
1314 //      EdgeExist\r
1315 //====================================================================================\r
1316 int32 EdgeExist(geVec3d *Edge1, GBSP_Poly *Poly, int32 *EdgeIndexOut)\r
1317 {\r
1318         int32           i;\r
1319         geVec3d         Edge2[2], *Verts;\r
1320         int32           NumVerts;\r
1321 \r
1322         Verts = Poly->Verts;\r
1323         NumVerts = Poly->NumVerts;\r
1324 \r
1325         for (i=0; i< NumVerts; i++)\r
1326         {\r
1327                 Edge2[0] = Verts[i];\r
1328                 Edge2[1] = Verts[(i+1)%NumVerts];\r
1329 \r
1330                 if (geVec3d_Compare(Edge1, Edge2, VCOMPARE_EPSILON))\r
1331                 if (geVec3d_Compare(Edge1+1, Edge2+1, VCOMPARE_EPSILON))\r
1332                 {\r
1333                         EdgeIndexOut[0] = i;\r
1334                         EdgeIndexOut[1] = (i+1)%NumVerts;\r
1335                         return GE_TRUE;\r
1336                 }\r
1337         }\r
1338 \r
1339         return GE_FALSE;\r
1340 }\r
1341 \r
1342 #define COLINEAR_EPSILON                0.0001f\r
1343 \r
1344 //====================================================================================\r
1345 //      MergeFace\r
1346 //====================================================================================\r
1347 GBSP_Face *MergeFace(GBSP_Face *Face1, GBSP_Face *Face2)\r
1348 {\r
1349         geVec3d         Edge1[2], *Verts1, *Verts2;\r
1350         int32           i, k, NumVerts, NumVerts2, EdgeIndex[2], NumNewVerts;\r
1351         GBSP_Poly       *NewPoly = NULL, *Poly1, *Poly2;\r
1352         geVec3d         Normal1, Normal2, Vec1, Vec2;\r
1353         GBSP_Face       *NewFace = NULL;\r
1354         geFloat         Dot;\r
1355         //int32         Start, End;\r
1356         geBoolean       Keep1 = GE_TRUE, Keep2 = GE_TRUE;\r
1357 \r
1358         //\r
1359         // Planes and Sides MUST match before even trying to merge\r
1360         //\r
1361         if (Face1->PlaneNum != Face2->PlaneNum)\r
1362                 return NULL;\r
1363         if (Face1->PlaneSide != Face2->PlaneSide)\r
1364                 return NULL;\r
1365 \r
1366 #if 1\r
1367         if ((Face1->Contents[0]&BSP_MERGE_SEP_CONTENTS) != (Face2->Contents[0]&BSP_MERGE_SEP_CONTENTS))\r
1368                 return NULL;\r
1369         if ((Face1->Contents[1]&BSP_MERGE_SEP_CONTENTS) != (Face2->Contents[1]&BSP_MERGE_SEP_CONTENTS))\r
1370                 return NULL;\r
1371 #endif\r
1372 \r
1373         if (Face1->TexInfo != Face2->TexInfo)\r
1374                 return NULL;\r
1375         \r
1376         Poly1 = Face1->Poly;\r
1377         Poly2 = Face2->Poly;\r
1378 \r
1379         if (Poly1->NumVerts == -1 || Poly2->NumVerts == -1)\r
1380                 return NULL;\r
1381 \r
1382         Verts1 = Poly1->Verts;\r
1383         NumVerts = Poly1->NumVerts;\r
1384 \r
1385         //\r
1386         // Go through each edge of Poly1, and see if the reverse of it exist in Poly2\r
1387         //\r
1388         for (i=0; i< NumVerts; i++)             \r
1389         {\r
1390                 Edge1[1] = Verts1[i];\r
1391                 Edge1[0] = Verts1[(i+1)%NumVerts];\r
1392 \r
1393                 if (EdgeExist(Edge1, Poly2, EdgeIndex)) // Found one, break out\r
1394                         break;\r
1395         }\r
1396 \r
1397         if (i >= NumVerts)                                                      // Did'nt find an edge, return nothing\r
1398                 return NULL;\r
1399 \r
1400         Verts2 = Poly2->Verts;\r
1401         NumVerts2 = Poly2->NumVerts;\r
1402 \r
1403         //\r
1404         //      See if the 2 joined make a convex poly, connect them, and return new one\r
1405         //\r
1406         Normal1 = Planes[Face1->PlaneNum].Normal;       // Get the normal\r
1407         if (Face1->PlaneSide)\r
1408                 geVec3d_Subtract(&VecOrigin, &Normal1, &Normal1);\r
1409 \r
1410         Vec1 = Verts1[(i+NumVerts-1)%NumVerts];         // Get the normal of the edge just behind edge1\r
1411         geVec3d_Subtract(&Vec1, Edge1+1, &Vec1);\r
1412         geVec3d_CrossProduct(&Normal1, &Vec1, &Normal2);\r
1413         geVec3d_Normalize(&Normal2);\r
1414         geVec3d_Subtract(&Verts2[(EdgeIndex[1]+1)%NumVerts2], &Verts2[EdgeIndex[1]], &Vec2);\r
1415         Dot = geVec3d_DotProduct(&Vec2, &Normal2);\r
1416         if (Dot > COLINEAR_EPSILON)\r
1417                 return NULL;                                                    // Edge makes a non-convex poly\r
1418         if (Dot >=-COLINEAR_EPSILON)                            // Drop point, on colinear edge\r
1419                 Keep1 = GE_FALSE;\r
1420 \r
1421         Vec1 = Verts1[(i+2)%NumVerts];                          // Get the normal of the edge just behind edge1\r
1422         geVec3d_Subtract(&Vec1, Edge1, &Vec1);\r
1423         geVec3d_CrossProduct(&Normal1, &Vec1, &Normal2);\r
1424         geVec3d_Normalize(&Normal2);\r
1425         geVec3d_Subtract(&Verts2[(EdgeIndex[0]+NumVerts2-1)%NumVerts2], &Verts2[EdgeIndex[0]], &Vec2);\r
1426         Dot = geVec3d_DotProduct(&Vec2, &Normal2);\r
1427         if (Dot > COLINEAR_EPSILON)\r
1428                 return NULL;                                                    // Edge makes a non-convex poly\r
1429         if (Dot >=-COLINEAR_EPSILON)                            // Drop point, on colinear edge\r
1430                 Keep2 = GE_FALSE;\r
1431 \r
1432         //if (NumVerts+NumVerts2 > 30)\r
1433         //      return NULL;\r
1434         \r
1435         NewFace = AllocFace(NumVerts+NumVerts2);\r
1436         NewPoly = NewFace->Poly;\r
1437         if (!NewFace)\r
1438         {\r
1439                 GHook.Error("*WARNING* MergeFace:  Out of memory for new face!\n");\r
1440                 return NULL;\r
1441         }\r
1442 \r
1443         //\r
1444         // Make a new poly, free the old ones...\r
1445         //\r
1446         NumNewVerts = 0;\r
1447 \r
1448         for (k = (i+1)%NumVerts; k != i ; k = (k+1)%NumVerts)\r
1449         {\r
1450                 if (k == (i+1)%NumVerts && ! Keep2)\r
1451                         continue;\r
1452                 NewPoly->Verts[NumNewVerts++] = Verts1[k];\r
1453         }\r
1454 \r
1455         i = EdgeIndex[0];\r
1456 \r
1457         for (k = (i+1)%NumVerts2; k != i ; k = (k+1)%NumVerts2)\r
1458         {\r
1459                 if (k == (i+1)%NumVerts2 && ! Keep1)\r
1460                         continue;\r
1461                 NewPoly->Verts[NumNewVerts++] = Verts2[k];\r
1462         }\r
1463 \r
1464         *NewFace = *Face2;\r
1465 \r
1466         NewPoly->NumVerts = NumNewVerts;\r
1467         NewFace->Poly = NewPoly;\r
1468 \r
1469         //Hook.Printf("Merged face: %i\n", NumNewVerts);\r
1470 \r
1471         Face1->Merged = NewFace;\r
1472         Face2->Merged = NewFace;\r
1473 \r
1474         return NewFace;\r
1475 }\r
1476 \r
1477 //====================================================================================\r
1478 //      NewFaceFromFace\r
1479 //====================================================================================\r
1480 GBSP_Face *NewFaceFromFace (GBSP_Face *f)\r
1481 {\r
1482         GBSP_Face       *Newf;\r
1483 \r
1484         Newf = AllocFace (0);\r
1485         *Newf = *f;\r
1486         //Newf->merged = NULL;\r
1487         Newf->Split[0] = Newf->Split[1] = NULL;\r
1488         Newf->Poly = NULL;\r
1489         \r
1490         return Newf;\r
1491 }\r
1492 \r
1493 //====================================================================================\r
1494 //      FanFace_r\r
1495 //====================================================================================\r
1496 void FanFace_r(GBSP_Node *Node, GBSP_Face *Face)\r
1497 {\r
1498         GBSP_Poly       *Poly, *NewPoly;\r
1499         geVec3d         *pVert;\r
1500         int32           i;\r
1501 \r
1502         Poly = Face->Poly;\r
1503 \r
1504         if (Poly->NumVerts == 3)                // Don't need to fan...\r
1505                 return;                 \r
1506 \r
1507         // Split this poly at the firsdt fan point into 2 more polys, and fan those...\r
1508         NewPoly = AllocPoly(3);\r
1509 \r
1510         NewPoly->Verts[0] = Poly->Verts[0];\r
1511         NewPoly->Verts[1] = Poly->Verts[1];\r
1512         NewPoly->Verts[2] = Poly->Verts[2];\r
1513 \r
1514         Face->Split[0] = NewFaceFromFace(Face); \r
1515         Face->Split[0]->Poly = NewPoly;\r
1516         Face->Split[0]->Next = Node->Faces;\r
1517         Node->Faces = Face->Split[0];\r
1518                 \r
1519         // Now make the rest of the polys\r
1520         NewPoly = AllocPoly(Poly->NumVerts-1);\r
1521 \r
1522         pVert = NewPoly->Verts;\r
1523 \r
1524         for (i=0; i<Poly->NumVerts; i++)\r
1525         {\r
1526                 if (i==1)\r
1527                         continue;\r
1528 \r
1529                 *pVert++ = Poly->Verts[i];\r
1530         }\r
1531         \r
1532         Face->Split[1] = NewFaceFromFace(Face); \r
1533         Face->Split[1]->Poly = NewPoly;\r
1534         Face->Split[1]->Next = Node->Faces;\r
1535         Node->Faces = Face->Split[1];\r
1536         \r
1537         FanFace_r(Node, Face->Split[1]);\r
1538 }\r
1539 \r
1540 //====================================================================================\r
1541 //      GetLog\r
1542 //====================================================================================\r
1543 uint32 GetLog(uint32 P2)\r
1544 {\r
1545         U32             p = 0;\r
1546         S32             i = 0;\r
1547 \r
1548         if (!P2)\r
1549         {\r
1550                 GHook.Printf("*WARNING* GetLog:  Bad input.\n");\r
1551                 return 0;\r
1552         }\r
1553         \r
1554         for (i = P2; i > 0; i>>=1)\r
1555                 p++;\r
1556 \r
1557         return (p-1);\r
1558 }\r
1559 \r
1560 \r
1561 //====================================================================================\r
1562 //      Snaps a number to a power of 2\r
1563 //====================================================================================\r
1564 int32 SnapToPower2(int32 Width)\r
1565 {\r
1566         int RetWidth;\r
1567 \r
1568         for ( RetWidth = 1; RetWidth < Width; RetWidth <<= 1 ) ;\r
1569         \r
1570         //assert( RetWidth <= 256 );\r
1571 \r
1572         return RetWidth;\r
1573 }\r
1574 \r
1575 //====================================================================================\r
1576 //      SubdivideFace\r
1577 //====================================================================================\r
1578 void SubdivideFace(GBSP_Node *Node, GBSP_Face *Face)\r
1579 {\r
1580         geFloat         Mins, Maxs;\r
1581         geFloat         v;\r
1582         int32           Axis, i;\r
1583         GFX_TexInfo     *Tex;\r
1584         geVec3d         Temp;\r
1585         geFloat         Dist;\r
1586         GBSP_Poly       *p, *Frontp, *Backp;\r
1587         GBSP_Plane      Plane;\r
1588 \r
1589         if (Face->Merged)\r
1590                 return;\r
1591 \r
1592         // Special (non-surface cached) faces don't need subdivision\r
1593         Tex = &TexInfo[Face->TexInfo];\r
1594 \r
1595         //if ( Tex->Flags & TEXINFO_GOURAUD)\r
1596         //      FanFace_r(Node, Face);\r
1597 \r
1598         if ( Tex->Flags & TEXINFO_NO_LIGHTMAP)\r
1599                 return;\r
1600 \r
1601         for (Axis = 0 ; Axis < 2 ; Axis++)\r
1602         {\r
1603                 while (1)\r
1604                 {\r
1605                         geFloat         TexSize, SplitDist;\r
1606                         geFloat         Mins16, Maxs16;\r
1607 \r
1608                         Mins = 999999.0f;\r
1609                         Maxs = -999999.0f;\r
1610                         \r
1611                         geVec3d_Copy(&Tex->Vecs[Axis], &Temp);\r
1612 \r
1613                         for (i=0 ; i<Face->Poly->NumVerts ; i++)\r
1614                         {\r
1615                                 v = geVec3d_DotProduct (&Face->Poly->Verts[i], &Temp);\r
1616                                 if (v < Mins)\r
1617                                         Mins = v;\r
1618                                 if (v > Maxs)\r
1619                                         Maxs = v;\r
1620                         }\r
1621                         \r
1622                         Mins16 = (geFloat)floor(Mins/16.0f)*16.0f;\r
1623                         Maxs16 = (geFloat)ceil(Maxs/16.0f)*16.0f;\r
1624 \r
1625                         TexSize = Maxs - Mins;\r
1626                         //TexSize = Maxs16 - Mins16;\r
1627 \r
1628                         // Default to the Subdivide size\r
1629                         SplitDist = SubdivideSize;\r
1630 \r
1631                 #if 0\r
1632                         if (TexSize <= SubdivideSize)\r
1633                         {\r
1634                                 int32           Log, LogSize;\r
1635                                 geFloat         Ratio;\r
1636 \r
1637                                 LogSize = SnapToPower2((int32)TexSize);\r
1638                                 Log = GetLog(LogSize);\r
1639 \r
1640                                 if (LogSize <= 16)\r
1641                                         break;                                          // Don't bother with small lmaps\r
1642 \r
1643                                 Ratio = TexSize / (geFloat)LogSize;     // Get the percentage of the space being taken advantage of if it were to be snapped to power of 2 texture in drivers\r
1644 \r
1645                                 if (Ratio >= 0.75f)\r
1646                                         break;                  // No need to split, if going to use at least 50% of the space\r
1647 \r
1648                                 // The lmap is not going to use a big enough percentage of the size it's currently going to be snapped to\r
1649                                 // So, cut it along the next size down...\r
1650                                 Log--;                          // Split along next log down\r
1651 \r
1652                                 // Overide the subdivide size with the next size down\r
1653                                 SplitDist = (geFloat)(1<<Log);\r
1654                         }\r
1655                 #else\r
1656                         if (TexSize <= SubdivideSize)\r
1657                                 break;\r
1658                 #endif\r
1659                         \r
1660                         // Make a copy\r
1661                         CopyPoly(Face->Poly, &p);\r
1662 \r
1663                         // Split it\r
1664                         NumSubdivided++;\r
1665                         \r
1666                         v = geVec3d_Normalize (&Temp);  \r
1667 \r
1668                         Dist = (Mins + SplitDist - 16)/v;\r
1669                         //Dist = (Mins16 + SplitDist)/v;\r
1670 \r
1671                         Plane.Normal = Temp;\r
1672                         Plane.Dist = Dist;\r
1673                         Plane.Type = PLANE_ANY;\r
1674                         \r
1675                         SplitPoly(p, &Plane, &Frontp, &Backp, GE_FALSE);\r
1676 \r
1677                         if (!Frontp || !Backp)\r
1678                         {\r
1679                                 GHook.Printf("*WARNING* SubdivideFace: didn't split the polygon: %f, %f, %f\n", Mins, Maxs, SplitDist);\r
1680                                 break;\r
1681                         }\r
1682 \r
1683                         Face->Split[0] = NewFaceFromFace (Face);\r
1684                         Face->Split[0]->Poly = Frontp;\r
1685                         Face->Split[0]->Next = Node->Faces;\r
1686                         Node->Faces = Face->Split[0];\r
1687 \r
1688                         Face->Split[1] = NewFaceFromFace (Face);\r
1689                         Face->Split[1]->Poly = Backp;\r
1690                         Face->Split[1]->Next = Node->Faces;\r
1691                         Node->Faces = Face->Split[1];\r
1692 \r
1693                         SubdivideFace (Node, Face->Split[0]);\r
1694                         SubdivideFace (Node, Face->Split[1]);\r
1695                         return;\r
1696                 }\r
1697         }\r
1698 }\r
1699 \r
1700 //====================================================================================\r
1701 //      SubdivideNodeFaces\r
1702 //====================================================================================\r
1703 void SubdivideNodeFaces (GBSP_Node *Node)\r
1704 {\r
1705         GBSP_Face       *f;\r
1706 \r
1707         for (f = Node->Faces ; f ; f=f->Next)\r
1708         {\r
1709                 SubdivideFace (Node, f);\r
1710         }\r
1711 }\r
1712 \r
1713 //====================================================================================\r
1714 //      CheckFace\r
1715 //====================================================================================\r
1716 geBoolean CheckFace(GBSP_Face *Face, geBoolean Verb)\r
1717 {\r
1718         int32           i, j, NumVerts;\r
1719         geVec3d         Vect1, *Verts, Normal, V1, V2, EdgeNormal;\r
1720         GBSP_Poly       *Poly;\r
1721         geFloat         Dist, PDist, EdgeDist;\r
1722         \r
1723         Poly = Face->Poly;\r
1724         Verts = Poly->Verts;\r
1725         NumVerts = Poly->NumVerts;\r
1726 \r
1727         if (NumVerts < 3)\r
1728         {\r
1729                 if (Verb)\r
1730                         GHook.Printf("CheckFace:  NumVerts < 3.\n");\r
1731                 return GE_FALSE;\r
1732         }\r
1733         \r
1734         Normal = Planes[Face->PlaneNum].Normal;\r
1735         PDist = Planes[Face->PlaneNum].Dist;\r
1736         if (Face->PlaneSide)\r
1737         {\r
1738                 geVec3d_Subtract(&VecOrigin, &Normal, &Normal);\r
1739                 PDist = -PDist;\r
1740         }\r
1741 \r
1742         //\r
1743         //      Check for degenerate edges, convexity, and make sure it's planar\r
1744         //\r
1745         for (i=0; i< NumVerts; i++)\r
1746         {\r
1747                 V1 = Verts[i];\r
1748                 V2 = Verts[(i+1)%NumVerts];\r
1749 \r
1750                 //      Check for degenreate edge\r
1751                 geVec3d_Subtract(&V2, &V1, &Vect1);\r
1752                 Dist = geVec3d_Length(&Vect1);\r
1753                 if (fabs(Dist) < DEGENERATE_EPSILON)\r
1754                 {\r
1755                         if (Verb)\r
1756                                 GHook.Printf("WARNING CheckFace:  Degenerate Edge.\n");\r
1757                         return GE_FALSE;\r
1758                 }\r
1759 \r
1760                 // Check for planar\r
1761                 Dist = geVec3d_DotProduct(&V1, &Normal) - PDist;\r
1762                 if (Dist > ON_EPSILON || Dist <-ON_EPSILON)\r
1763                 {\r
1764                         if (Verb)\r
1765                                 GHook.Printf("WARNING CheckFace:  Non planar: %f.\n", Dist);\r
1766                         return GE_FALSE;\r
1767                 }\r
1768 \r
1769                 geVec3d_CrossProduct(&Normal, &Vect1, &EdgeNormal);\r
1770                 geVec3d_Normalize(&EdgeNormal);\r
1771                 EdgeDist = geVec3d_DotProduct(&V1, &EdgeNormal);\r
1772                 \r
1773                 // Check for convexity\r
1774                 for (j=0; j< NumVerts; j++)\r
1775                 {\r
1776                         Dist = geVec3d_DotProduct(&Verts[j], &EdgeNormal) - EdgeDist;\r
1777                         if (Dist > ON_EPSILON)\r
1778                         {\r
1779                                 if (Verb)\r
1780                                         GHook.Printf("CheckFace:  Face not convex.\n");\r
1781                                 return GE_FALSE;\r
1782                         }\r
1783                 }\r
1784         }\r
1785 \r
1786         return GE_TRUE;\r
1787 }\r
1788 \r
1789 //====================================================================================\r
1790 //      GetFaceListBOX\r
1791 //====================================================================================\r
1792 void GetFaceListBOX(GBSP_Face *Faces, geVec3d *Mins, geVec3d *Maxs)\r
1793 {\r
1794         GBSP_Face       *Face;\r
1795         GBSP_Poly       *Poly;\r
1796         geVec3d         Vert;\r
1797         int32           i;\r
1798 \r
1799         ClearBounds(Mins, Maxs);\r
1800 \r
1801         // Go through each face in this brush...\r
1802         for (Face = Faces; Face; Face = Face->Next)\r
1803         {\r
1804                 Poly = Face->Poly;\r
1805                 for (i=0; i< Poly->NumVerts; i++)\r
1806                 {\r
1807                         Vert = Poly->Verts[i];\r
1808 \r
1809                         // First get maxs\r
1810                         if (Vert.X > Maxs->X)\r
1811                                 Maxs->X = Vert.X;\r
1812                         if (Vert.Y > Maxs->Y)\r
1813                                 Maxs->Y = Vert.Y;\r
1814                         if (Vert.Z > Maxs->Z)\r
1815                                 Maxs->Z = Vert.Z;\r
1816 \r
1817                         // Then check mins\r
1818                         if (Vert.X < Mins->X)\r
1819                                 Mins->X = Vert.X;\r
1820                         if (Vert.Y < Mins->Y)\r
1821                                 Mins->Y = Vert.Y;\r
1822                         if (Vert.Z < Mins->Z)\r
1823                                 Mins->Z = Vert.Z;\r
1824                 }\r
1825         }\r
1826 }\r
1827 \r