1 /****************************************************************************************/
\r
4 /* Author: John Pollard */
\r
5 /* Description: Various Poly routines (clipping, splitting, etc) */
\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
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
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
21 /****************************************************************************************/
\r
22 #include <Windows.h>
\r
26 #include "Mathlib.h"
\r
29 #include "Texture.h"
\r
30 #include "GBSPFile.h"
\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
40 int32 NumSubdivided;
\r
43 //#define FREAKED_OUT
\r
45 geBoolean gCountVerts;
\r
49 //#define DEGENERATE_EPSILON 0.05f
\r
50 #define DEGENERATE_EPSILON 0.001f
\r
56 //====================================================================================
\r
58 //====================================================================================
\r
59 GBSP_Poly *AllocPoly(int32 NumVerts)
\r
63 if (NumVerts > 1000)
\r
65 GHook.Error("Bogus verts: %i\n", NumVerts);
\r
69 NewPoly = GE_RAM_ALLOCATE_STRUCT(GBSP_Poly);
\r
73 GHook.Error("AllocPoly: Not enough memory.\n");
\r
77 NewPoly->Verts = GE_RAM_ALLOCATE_ARRAY(geVec3d,NumVerts);
\r
79 if (!NewPoly->Verts)
\r
81 GHook.Error("AllocPoly: Not enough memory for verts: %i\n", NumVerts);
\r
82 geRam_Free(NewPoly);
\r
86 NewPoly->NumVerts = NumVerts;
\r
88 #ifdef SHOW_DEBUG_STATS
\r
91 gTotalVerts += NumVerts;
\r
92 if (gTotalVerts > gPeekVerts)
\r
93 gPeekVerts = gTotalVerts;
\r
100 //====================================================================================
\r
102 //====================================================================================
\r
103 void FreePoly(GBSP_Poly *Poly)
\r
107 GHook.Printf("*WARNING* FreePoly: NULL Poly.\n");
\r
113 geRam_Free(Poly->Verts);
\r
115 #ifdef SHOW_DEBUG_STATS
\r
118 gTotalVerts -= Poly->NumVerts;
\r
126 //=====================================================================================
\r
127 // TextureAxisFromPlane
\r
128 //=====================================================================================
\r
129 geBoolean TextureAxisFromPlane(GBSP_Plane *Pln, geVec3d *Xv, geVec3d *Yv)
\r
138 for (i=0 ; i<3 ; i++)
\r
140 Dot = (geFloat)fabs(VectorToSUB(Pln->Normal, i));
\r
151 Xv->X = (geFloat)0;
\r
152 Xv->Y = (geFloat)0;
\r
153 Xv->Z = (geFloat)1;
\r
155 Yv->X = (geFloat)0;
\r
156 Yv->Y = (geFloat)-1;
\r
157 Yv->Z = (geFloat)0;
\r
160 Xv->X = (geFloat)1;
\r
161 Xv->Y = (geFloat)0;
\r
162 Xv->Z = (geFloat)0;
\r
164 Yv->X = (geFloat)0;
\r
165 Yv->Y = (geFloat)0;
\r
166 Yv->Z = (geFloat)1;
\r
169 Xv->X = (geFloat)1;
\r
170 Xv->Y = (geFloat)0;
\r
171 Xv->Z = (geFloat)0;
\r
173 Yv->X = (geFloat)0;
\r
174 Yv->Y = (geFloat)-1;
\r
175 Yv->Z = (geFloat)0;
\r
178 GHook.Error("TextureAxisFromPlane: No Axis found.\n");
\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
192 geVec3d Normal = Plane->Normal;
\r
193 geVec3d UpVect = {0.0f, 0.0f, 0.0f};
\r
194 geVec3d RightVect, Org;
\r
197 if (!TextureAxisFromPlane(Plane, &RightVect, &UpVect))
\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
204 geVec3d_Normalize(&UpVect);
\r
205 geVec3d_Normalize(&RightVect);
\r
207 // Create the poly with 4 verts
\r
208 Poly = AllocPoly(4);
\r
212 GHook.Error("CreatePolyFromPlane: Not enough memory for new poly!\n");
\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
220 geVec3d_Subtract(&Org, &RightVect, &Poly->Verts[0]);
\r
221 geVec3d_Add(&Poly->Verts[0], &UpVect, &Poly->Verts[0]);
\r
223 geVec3d_Add(&Org, &RightVect, &Poly->Verts[1]);
\r
224 geVec3d_Add(&Poly->Verts[1], &UpVect, &Poly->Verts[1]);
\r
226 geVec3d_Add(&Org, &RightVect, &Poly->Verts[2]);
\r
227 geVec3d_Subtract(&Poly->Verts[2], &UpVect, &Poly->Verts[2]);
\r
229 geVec3d_Subtract(&Org, &RightVect, &Poly->Verts[3]);
\r
230 geVec3d_Subtract(&Poly->Verts[3], &UpVect, &Poly->Verts[3]);
\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
239 Normal = Plane->Normal;
\r
241 if (!geVec3d_Compare(&Normal, &Normal2, VCOMPARE_EPSILON))
\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
254 #define MAX_TEMP_VERTS 200
\r
256 geVec3d TempVerts[MAX_TEMP_VERTS];
\r
257 geVec3d TempVerts2[MAX_TEMP_VERTS];
\r
259 #define CLIP_EPSILON (geFloat)0.001
\r
261 //====================================================================================
\r
263 //====================================================================================
\r
264 geBoolean ClipPoly(GBSP_Poly *InPoly, GBSP_Plane *Plane, geBoolean FlipTest, GBSP_Poly **OutPoly)
\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
272 geVec3d Normal = Plane->Normal;
\r
273 geFloat Dist = Plane->Dist;
\r
274 int32 NumVerts = InPoly->NumVerts;
\r
276 geFloat VDist[100];
\r
277 int32 CountSides[3];
\r
281 if (NumVerts >= 100)
\r
283 GHook.Error("ClipPoly: Too many verts.\n");
\r
287 memset(CountSides, 0, sizeof(CountSides));
\r
289 Verts = InPoly->Verts;
\r
291 pFrontVert = TempVerts;
\r
293 if (FlipTest) // Flip the normal and dist
\r
295 Normal.X = -Normal.X;
\r
296 Normal.Y = -Normal.Y;
\r
297 Normal.Z = -Normal.Z;
\r
301 // See what side of plane each vert is on
\r
302 for (i=0; i< NumVerts; i++)
\r
304 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;
\r
305 if (VDist[i] > ON_EPSILON)
\r
307 else if (VDist[i] < -ON_EPSILON)
\r
312 CountSides[VSides[i]]++;
\r
315 if (!CountSides[0])
\r
322 if (!CountSides[1])
\r
328 // Else we have to split this sucker
\r
329 for (i=0; i< NumVerts; i++)
\r
333 if (VSides[i] == 2) // On plane, put on both sides
\r
335 *pFrontVert++ = Vert1;
\r
339 if (VSides[i] == 0) // Front side, put on front list
\r
340 *pFrontVert++ = Vert1;
\r
342 NextVert = (i+1) % NumVerts;
\r
344 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])
\r
347 Vert2 = Verts[NextVert];
\r
348 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);
\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
357 FreePoly(InPoly); // Don't need this anymore
\r
359 NewNumVerts = pFrontVert - TempVerts;
\r
361 if (NewNumVerts < 3)
\r
367 NewPoly = AllocPoly(NewNumVerts);
\r
371 GHook.Error("ClipPoly: Not enough mem for new poly.\n");
\r
375 for (i = 0; i< NewNumVerts; i++)
\r
376 NewPoly->Verts[i] = TempVerts[i];
\r
378 *OutPoly = NewPoly;
\r
382 //====================================================================================
\r
384 //====================================================================================
\r
385 geBoolean ClipPolyEpsilon(GBSP_Poly *InPoly, geFloat Epsilon, GBSP_Plane *Plane, geBoolean FlipTest, GBSP_Poly **OutPoly)
\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
393 geVec3d Normal = Plane->Normal;
\r
394 geFloat Dist = Plane->Dist;
\r
395 int32 NumVerts = InPoly->NumVerts;
\r
397 geFloat VDist[100];
\r
398 int32 CountSides[3];
\r
402 if (NumVerts >= 100)
\r
404 GHook.Error("ClipPoly: Too many verts.\n");
\r
408 memset(CountSides, 0, sizeof(CountSides));
\r
410 Verts = InPoly->Verts;
\r
412 pFrontVert = TempVerts;
\r
414 if (FlipTest) // Flip the normal and dist
\r
416 Normal.X = -Normal.X;
\r
417 Normal.Y = -Normal.Y;
\r
418 Normal.Z = -Normal.Z;
\r
422 // See what side of plane each vert is on
\r
423 for (i=0; i< NumVerts; i++)
\r
425 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;
\r
426 if (VDist[i] > Epsilon)
\r
428 else if (VDist[i] < -Epsilon)
\r
433 CountSides[VSides[i]]++;
\r
436 if (!CountSides[0])
\r
443 if (!CountSides[1])
\r
449 // Else we have to split this sucker
\r
450 for (i=0; i< NumVerts; i++)
\r
454 if (VSides[i] == 2) // On plane, put on both sides
\r
456 *pFrontVert++ = Vert1;
\r
460 if (VSides[i] == 0) // Front side, put on front list
\r
461 *pFrontVert++ = Vert1;
\r
463 NextVert = (i+1) % NumVerts;
\r
465 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])
\r
468 Vert2 = Verts[NextVert];
\r
469 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);
\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
478 FreePoly(InPoly); // Don't need this anymore
\r
480 NewNumVerts = pFrontVert - TempVerts;
\r
482 if (NewNumVerts < 3)
\r
488 NewPoly = AllocPoly(NewNumVerts);
\r
492 GHook.Error("ClipPoly: Not enough mem for new poly.\n");
\r
496 for (i = 0; i< NewNumVerts; i++)
\r
497 NewPoly->Verts[i] = TempVerts[i];
\r
499 *OutPoly = NewPoly;
\r
503 //====================================================================================
\r
505 //====================================================================================
\r
506 geBoolean SplitPoly(GBSP_Poly *InPoly, GBSP_Plane *Plane, GBSP_Poly **Front, GBSP_Poly **Back,
\r
507 geBoolean FlipTest)
\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
515 geVec3d Normal = Plane->Normal;
\r
516 geFloat Dist = Plane->Dist, *pDist;
\r
517 int32 NumVerts = InPoly->NumVerts;
\r
519 geFloat VDist[100];
\r
520 int32 CountSides[3];
\r
522 if (NumVerts >= 100)
\r
524 GHook.Error("SplitPoly: Too many verts.\n");
\r
528 memset(CountSides, 0, sizeof(CountSides));
\r
530 Verts = InPoly->Verts;
\r
532 pFrontVert = TempVerts;
\r
533 pBackVert = TempVerts2;
\r
535 if (FlipTest) // Flip the normal and dist
\r
537 Normal.X = -Normal.X;
\r
538 Normal.Y = -Normal.Y;
\r
539 Normal.Z = -Normal.Z;
\r
543 // See what side of plane each vert is on
\r
544 if (Plane->Type < PLANE_ANYX)
\r
546 pDist = &VectorToSUB(Verts[0], Plane->Type);
\r
548 for (i=0; i< NumVerts ; i++)
\r
551 //VDist[i] = VectorToSUB(Verts[i], Plane->Type) - Plane->Dist;
\r
552 VDist[i] = *pDist - Plane->Dist;
\r
554 VDist[i] = -VDist[i];
\r
556 if (VDist[i] > ON_EPSILON)
\r
558 else if (VDist[i] < -ON_EPSILON)
\r
563 CountSides[VSides[i]]++;
\r
570 for (i=0; i< NumVerts; i++)
\r
572 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;
\r
573 if (VDist[i] > ON_EPSILON)
\r
575 else if (VDist[i] < -ON_EPSILON)
\r
580 CountSides[VSides[i]]++;
\r
584 if (!CountSides[0] && !CountSides[1])
\r
591 // Get out quick, if no splitting is neccesary
\r
592 if (!CountSides[0])
\r
598 if (!CountSides[1])
\r
605 // Else we have to split this sucker
\r
606 for (i=0; i< NumVerts; i++)
\r
610 if (VSides[i] == 2) // On plane, put on both sides
\r
612 *pFrontVert++ = Vert1;
\r
613 *pBackVert++ = Vert1;
\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
623 NextVert = (i+1) % NumVerts;
\r
625 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])
\r
628 Vert2 = Verts[NextVert];
\r
629 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);
\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
635 *pBackVert = *pFrontVert;
\r
640 FreePoly(InPoly); // Don't need this anymore
\r
642 NewNumVerts = pFrontVert - TempVerts;
\r
644 if (NewNumVerts < 3)
\r
648 NewPoly = AllocPoly(NewNumVerts);
\r
652 GHook.Error("SplitPoly: Not enough mem for new poly.\n");
\r
656 for (i = 0; i< NewNumVerts; i++)
\r
657 NewPoly->Verts[i] = TempVerts[i];
\r
662 NewNumVerts = pBackVert - TempVerts2;
\r
664 if (NewNumVerts < 3)
\r
668 NewPoly = AllocPoly(NewNumVerts);
\r
672 GHook.Error("SplitPoly: Not enough mem for new poly.\n");
\r
676 for (i = 0; i< NewNumVerts; i++)
\r
677 NewPoly->Verts[i] = TempVerts2[i];
\r
685 //====================================================================================
\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
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
697 geVec3d Normal = Plane->Normal;
\r
698 geFloat Dist = Plane->Dist, *pDist;
\r
699 int32 NumVerts = InPoly->NumVerts;
\r
701 geFloat VDist[100];
\r
702 int32 CountSides[3];
\r
704 if (NumVerts >= 100)
\r
706 GHook.Error("SplitPoly: Too many verts.\n");
\r
710 memset(CountSides, 0, sizeof(CountSides));
\r
712 Verts = InPoly->Verts;
\r
714 pFrontVert = TempVerts;
\r
715 pBackVert = TempVerts2;
\r
717 if (FlipTest) // Flip the normal and dist
\r
719 Normal.X = -Normal.X;
\r
720 Normal.Y = -Normal.Y;
\r
721 Normal.Z = -Normal.Z;
\r
725 // See what side of plane each vert is on
\r
726 if (Plane->Type < PLANE_ANYX)
\r
728 pDist = &VectorToSUB(Verts[0], Plane->Type);
\r
730 for (i=0; i< NumVerts ; i++)
\r
733 //VDist[i] = VectorToSUB(Verts[i], Plane->Type) - Plane->Dist;
\r
734 VDist[i] = *pDist - Plane->Dist;
\r
736 VDist[i] = -VDist[i];
\r
738 if (VDist[i] > Epsilon)
\r
740 else if (VDist[i] < -Epsilon)
\r
745 CountSides[VSides[i]]++;
\r
752 for (i=0; i< NumVerts; i++)
\r
754 VDist[i] = geVec3d_DotProduct(&Verts[i], &Normal) - Dist;
\r
755 if (VDist[i] > Epsilon)
\r
757 else if (VDist[i] < -Epsilon)
\r
762 CountSides[VSides[i]]++;
\r
766 // Get out quick, if no splitting is neccesary
\r
767 if (!CountSides[0])
\r
773 if (!CountSides[1])
\r
780 // Else we have to split this sucker
\r
781 for (i=0; i< NumVerts; i++)
\r
785 if (VSides[i] == 2) // On plane, put on both sides
\r
787 *pFrontVert++ = Vert1;
\r
788 *pBackVert++ = Vert1;
\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
798 NextVert = (i+1) % NumVerts;
\r
800 if (VSides[NextVert] == 2 || VSides[NextVert] == VSides[i])
\r
803 Vert2 = Verts[NextVert];
\r
804 Scale = VDist[i] / (VDist[i] - VDist[NextVert]);
\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
810 *pBackVert = *pFrontVert;
\r
815 FreePoly(InPoly); // Don't need this anymore
\r
817 NewNumVerts = pFrontVert - TempVerts;
\r
819 if (NewNumVerts < 3)
\r
823 NewPoly = AllocPoly(NewNumVerts);
\r
827 GHook.Error("SplitPoly: Not enough mem for new poly.\n");
\r
831 for (i = 0; i< NewNumVerts; i++)
\r
832 NewPoly->Verts[i] = TempVerts[i];
\r
837 NewNumVerts = pBackVert - TempVerts2;
\r
839 if (NewNumVerts < 3)
\r
843 NewPoly = AllocPoly(NewNumVerts);
\r
847 GHook.Error("SplitPoly: Not enough mem for new poly.\n");
\r
851 for (i = 0; i< NewNumVerts; i++)
\r
852 NewPoly->Verts[i] = TempVerts2[i];
\r
860 //====================================================================================
\r
861 // RemoveDegenerateEdges
\r
862 //====================================================================================
\r
863 void RemoveDegenerateEdges(GBSP_Poly *Poly)
\r
866 geVec3d *Verts, V1, V2, NVerts[1000], Vec;
\r
867 geBoolean Bad = GE_FALSE;
\r
868 int32 NumNVerts = 0;
\r
870 Verts = Poly->Verts;
\r
871 NumVerts = Poly->NumVerts;
\r
873 for (i=0; i< NumVerts; i++)
\r
876 V2 = Verts[(i+1)%NumVerts];
\r
878 geVec3d_Subtract(&V1, &V2, &Vec);
\r
880 if (geVec3d_Length(&Vec) > DEGENERATE_EPSILON)
\r
882 NVerts[NumNVerts++] = V1;
\r
890 //Hook.Printf("Removing degenerate edge...\n");
\r
892 Poly->NumVerts = NumNVerts;
\r
893 for (i=0; i< NumNVerts; i++)
\r
895 Verts[i] = NVerts[i];
\r
900 //====================================================================================
\r
901 // RemoveDegenerateEdges2
\r
902 //====================================================================================
\r
903 geBoolean RemoveDegenerateEdges2(GBSP_Poly *Poly)
\r
906 geVec3d *Verts, V1, V2, NVerts[1000], Vec;
\r
907 geBoolean Bad = GE_FALSE;
\r
908 int32 NumNVerts = 0;
\r
910 Verts = Poly->Verts;
\r
911 NumVerts = Poly->NumVerts;
\r
913 for (i=0; i< NumVerts; i++)
\r
916 V2 = Verts[(i+1)%NumVerts];
\r
918 geVec3d_Subtract(&V1, &V2, &Vec);
\r
920 if (geVec3d_Length(&Vec) > DEGENERATE_EPSILON)
\r
922 NVerts[NumNVerts++] = V1;
\r
933 Poly->NumVerts = NumNVerts;
\r
934 for (i=0; i< NumNVerts; i++)
\r
936 Verts[i] = NVerts[i];
\r
943 //====================================================================================
\r
945 //====================================================================================
\r
946 geFloat PolyArea(GBSP_Poly *Poly)
\r
949 geVec3d Vect1, Vect2, Cross;
\r
954 for (i=2 ; i<Poly->NumVerts ; i++)
\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
962 return (geFloat)Total;
\r
965 #define BOGUS_VERTS 256
\r
966 //====================================================================================
\r
968 //====================================================================================
\r
969 geBoolean CopyPoly(GBSP_Poly *In, GBSP_Poly **Out)
\r
971 GBSP_Poly *NewPoly;
\r
976 GHook.Error("CopyPoly: NULL Poly!!!\n");
\r
980 if (In->NumVerts <= 0 || In->NumVerts >= BOGUS_VERTS)
\r
982 GHook.Error("CopyPoly: Bogus number of verts: %i\n", In->NumVerts);
\r
986 NewPoly = AllocPoly(In->NumVerts);
\r
992 for (i=0; i<In->NumVerts; i++)
\r
993 NewPoly->Verts[i] = In->Verts[i];
\r
1000 //====================================================================================
\r
1002 //====================================================================================
\r
1003 GBSP_Poly *CopyPoly2(GBSP_Poly *In)
\r
1005 GBSP_Poly *NewPoly;
\r
1010 GHook.Error("CopyPoly: NULL Poly!!!\n");
\r
1014 if (In->NumVerts <= 0 || In->NumVerts >= BOGUS_VERTS)
\r
1016 GHook.Error("CopyPoly: Bogus number of verts: %i\n", In->NumVerts);
\r
1020 NewPoly = AllocPoly(In->NumVerts);
\r
1025 for (i=0; i<In->NumVerts; i++)
\r
1026 NewPoly->Verts[i] = In->Verts[i];
\r
1031 //====================================================================================
\r
1033 //====================================================================================
\r
1034 geBoolean ReversePoly(GBSP_Poly *In, GBSP_Poly **Out)
\r
1036 GBSP_Poly *NewPoly;
\r
1039 NewPoly = AllocPoly(In->NumVerts);
\r
1045 for (i=0; i<In->NumVerts; i++)
\r
1046 NewPoly->Verts[i] = In->Verts[In->NumVerts-i-1];
\r
1053 //====================================================================================
\r
1055 //====================================================================================
\r
1056 void PolyCenter(GBSP_Poly *Poly, geVec3d *Center)
\r
1060 geVec3d_Clear(Center);
\r
1062 for (i=0; i< Poly->NumVerts; i++)
\r
1063 geVec3d_Add(Center, &Poly->Verts[i], Center);
\r
1065 geVec3d_Scale(Center, (geFloat)1.0/(geFloat)Poly->NumVerts, Center);
\r
1068 #define EDGE_LENGTH (geFloat)0.1
\r
1070 //====================================================================================
\r
1072 //====================================================================================
\r
1073 geBoolean PolyIsTiny (GBSP_Poly *Poly)
\r
1082 //return GE_FALSE;
\r
1084 for (i=0 ; i<Poly->NumVerts ; i++)
\r
1086 j = i == Poly->NumVerts - 1 ? 0 : i+1;
\r
1088 geVec3d_Subtract(&Poly->Verts[j], &Poly->Verts[i], &Delta);
\r
1090 Len = geVec3d_Length(&Delta);
\r
1092 if (Len > EDGE_LENGTH)
\r
1099 //GHook.Printf("Poly is tiny...\n");
\r
1108 //====================================================================================
\r
1110 //====================================================================================
\r
1111 GBSP_Face *AllocFace(int32 NumVerts)
\r
1115 Face = GE_RAM_ALLOCATE_STRUCT(GBSP_Face);
\r
1120 memset(Face, 0, sizeof(GBSP_Face));
\r
1124 Face->Poly = AllocPoly(NumVerts);
\r
1132 Face->Poly = NULL;
\r
1137 //====================================================================================
\r
1139 //====================================================================================
\r
1140 void FreeFace(GBSP_Face *Face)
\r
1144 GHook.Printf("*WARNING* FreeFace: NULL Face.\n");
\r
1148 //if (!Face->Poly)
\r
1149 // Hook.Error("FreeFace: NULL Poly.\n");
\r
1151 FreePoly(Face->Poly);
\r
1152 Face->Poly = NULL;
\r
1154 if (Face->IndexVerts)
\r
1155 geRam_Free(Face->IndexVerts);
\r
1156 Face->IndexVerts = NULL;
\r
1161 //====================================================================================
\r
1163 //====================================================================================
\r
1164 geBoolean SplitFace(GBSP_Face *In, GBSP_Plane *Split, GBSP_Face **Front, GBSP_Face **Back, geBoolean FlipTest)
\r
1167 GBSP_Face *NewFace;
\r
1169 if (!SplitPoly(In->Poly, Split, &F, &B, FlipTest))
\r
1174 GHook.Error("SplitFace: Poly was clipped away.\n");
\r
1193 NewFace = GE_RAM_ALLOCATE_STRUCT(GBSP_Face);
\r
1196 GHook.Error("SplitFace: Out of memory for new face.\n");
\r
1203 NewFace->Poly = B;
\r
1211 //====================================================================================
\r
1213 //====================================================================================
\r
1214 geBoolean CopyFace(GBSP_Face *In, GBSP_Face **Out)
\r
1216 GBSP_Face *NewFace;
\r
1217 GBSP_Poly *NewPoly;
\r
1220 NewFace = AllocFace(0);
\r
1224 GHook.Error("CopyFaceList: Out of memory for new face.\n");
\r
1229 NewPoly = AllocPoly(In->Poly->NumVerts);
\r
1233 GHook.Error("CopyFaceList: Out of memory for newpoly.\n");
\r
1237 NewFace->Poly = NewPoly;
\r
1239 for (i=0; i< In->Poly->NumVerts; i++)
\r
1240 NewFace->Poly->Verts[i] = In->Poly->Verts[i];
\r
1245 //====================================================================================
\r
1247 //====================================================================================
\r
1248 geBoolean MergeFaceList2(GBSP_Face *Faces)
\r
1250 GBSP_Face *Face1, *Face2, *End, *Merged;
\r
1252 for (Face1 = Faces ; Face1 ; Face1 = Face1->Next)
\r
1254 if (Face1->Poly->NumVerts == -1)
\r
1257 if (Face1->Merged || Face1->Split[0] || Face1->Split[1])
\r
1260 for (Face2 = Faces ; Face2 != Face1 ; Face2 = Face2->Next)
\r
1262 if (Face2->Poly->NumVerts == -1)
\r
1265 if (Face2->Merged || Face2->Split[0] || Face2->Split[1])
\r
1268 Merged = MergeFace(Face1, Face2);
\r
1273 RemoveDegenerateEdges(Merged->Poly);
\r
1275 if (!CheckFace(Merged, GE_FALSE))
\r
1278 Face1->Merged = NULL;
\r
1279 Face2->Merged = NULL;
\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
1289 Merged->Next = NULL;
\r
1290 End->Next = Merged;
\r
1298 //====================================================================================
\r
1300 //====================================================================================
\r
1301 void FreeFaceList(GBSP_Face *List)
\r
1307 Next = List->Next;
\r
1313 //====================================================================================
\r
1315 //====================================================================================
\r
1316 int32 EdgeExist(geVec3d *Edge1, GBSP_Poly *Poly, int32 *EdgeIndexOut)
\r
1319 geVec3d Edge2[2], *Verts;
\r
1322 Verts = Poly->Verts;
\r
1323 NumVerts = Poly->NumVerts;
\r
1325 for (i=0; i< NumVerts; i++)
\r
1327 Edge2[0] = Verts[i];
\r
1328 Edge2[1] = Verts[(i+1)%NumVerts];
\r
1330 if (geVec3d_Compare(Edge1, Edge2, VCOMPARE_EPSILON))
\r
1331 if (geVec3d_Compare(Edge1+1, Edge2+1, VCOMPARE_EPSILON))
\r
1333 EdgeIndexOut[0] = i;
\r
1334 EdgeIndexOut[1] = (i+1)%NumVerts;
\r
1342 #define COLINEAR_EPSILON 0.0001f
\r
1344 //====================================================================================
\r
1346 //====================================================================================
\r
1347 GBSP_Face *MergeFace(GBSP_Face *Face1, GBSP_Face *Face2)
\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
1355 //int32 Start, End;
\r
1356 geBoolean Keep1 = GE_TRUE, Keep2 = GE_TRUE;
\r
1359 // Planes and Sides MUST match before even trying to merge
\r
1361 if (Face1->PlaneNum != Face2->PlaneNum)
\r
1363 if (Face1->PlaneSide != Face2->PlaneSide)
\r
1367 if ((Face1->Contents[0]&BSP_MERGE_SEP_CONTENTS) != (Face2->Contents[0]&BSP_MERGE_SEP_CONTENTS))
\r
1369 if ((Face1->Contents[1]&BSP_MERGE_SEP_CONTENTS) != (Face2->Contents[1]&BSP_MERGE_SEP_CONTENTS))
\r
1373 if (Face1->TexInfo != Face2->TexInfo)
\r
1376 Poly1 = Face1->Poly;
\r
1377 Poly2 = Face2->Poly;
\r
1379 if (Poly1->NumVerts == -1 || Poly2->NumVerts == -1)
\r
1382 Verts1 = Poly1->Verts;
\r
1383 NumVerts = Poly1->NumVerts;
\r
1386 // Go through each edge of Poly1, and see if the reverse of it exist in Poly2
\r
1388 for (i=0; i< NumVerts; i++)
\r
1390 Edge1[1] = Verts1[i];
\r
1391 Edge1[0] = Verts1[(i+1)%NumVerts];
\r
1393 if (EdgeExist(Edge1, Poly2, EdgeIndex)) // Found one, break out
\r
1397 if (i >= NumVerts) // Did'nt find an edge, return nothing
\r
1400 Verts2 = Poly2->Verts;
\r
1401 NumVerts2 = Poly2->NumVerts;
\r
1404 // See if the 2 joined make a convex poly, connect them, and return new one
\r
1406 Normal1 = Planes[Face1->PlaneNum].Normal; // Get the normal
\r
1407 if (Face1->PlaneSide)
\r
1408 geVec3d_Subtract(&VecOrigin, &Normal1, &Normal1);
\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
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
1432 //if (NumVerts+NumVerts2 > 30)
\r
1435 NewFace = AllocFace(NumVerts+NumVerts2);
\r
1436 NewPoly = NewFace->Poly;
\r
1439 GHook.Error("*WARNING* MergeFace: Out of memory for new face!\n");
\r
1444 // Make a new poly, free the old ones...
\r
1448 for (k = (i+1)%NumVerts; k != i ; k = (k+1)%NumVerts)
\r
1450 if (k == (i+1)%NumVerts && ! Keep2)
\r
1452 NewPoly->Verts[NumNewVerts++] = Verts1[k];
\r
1457 for (k = (i+1)%NumVerts2; k != i ; k = (k+1)%NumVerts2)
\r
1459 if (k == (i+1)%NumVerts2 && ! Keep1)
\r
1461 NewPoly->Verts[NumNewVerts++] = Verts2[k];
\r
1464 *NewFace = *Face2;
\r
1466 NewPoly->NumVerts = NumNewVerts;
\r
1467 NewFace->Poly = NewPoly;
\r
1469 //Hook.Printf("Merged face: %i\n", NumNewVerts);
\r
1471 Face1->Merged = NewFace;
\r
1472 Face2->Merged = NewFace;
\r
1477 //====================================================================================
\r
1478 // NewFaceFromFace
\r
1479 //====================================================================================
\r
1480 GBSP_Face *NewFaceFromFace (GBSP_Face *f)
\r
1484 Newf = AllocFace (0);
\r
1486 //Newf->merged = NULL;
\r
1487 Newf->Split[0] = Newf->Split[1] = NULL;
\r
1488 Newf->Poly = NULL;
\r
1493 //====================================================================================
\r
1495 //====================================================================================
\r
1496 void FanFace_r(GBSP_Node *Node, GBSP_Face *Face)
\r
1498 GBSP_Poly *Poly, *NewPoly;
\r
1502 Poly = Face->Poly;
\r
1504 if (Poly->NumVerts == 3) // Don't need to fan...
\r
1507 // Split this poly at the firsdt fan point into 2 more polys, and fan those...
\r
1508 NewPoly = AllocPoly(3);
\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
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
1519 // Now make the rest of the polys
\r
1520 NewPoly = AllocPoly(Poly->NumVerts-1);
\r
1522 pVert = NewPoly->Verts;
\r
1524 for (i=0; i<Poly->NumVerts; i++)
\r
1529 *pVert++ = Poly->Verts[i];
\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
1537 FanFace_r(Node, Face->Split[1]);
\r
1540 //====================================================================================
\r
1542 //====================================================================================
\r
1543 uint32 GetLog(uint32 P2)
\r
1550 GHook.Printf("*WARNING* GetLog: Bad input.\n");
\r
1554 for (i = P2; i > 0; i>>=1)
\r
1561 //====================================================================================
\r
1562 // Snaps a number to a power of 2
\r
1563 //====================================================================================
\r
1564 int32 SnapToPower2(int32 Width)
\r
1568 for ( RetWidth = 1; RetWidth < Width; RetWidth <<= 1 ) ;
\r
1570 //assert( RetWidth <= 256 );
\r
1575 //====================================================================================
\r
1577 //====================================================================================
\r
1578 void SubdivideFace(GBSP_Node *Node, GBSP_Face *Face)
\r
1580 geFloat Mins, Maxs;
\r
1586 GBSP_Poly *p, *Frontp, *Backp;
\r
1592 // Special (non-surface cached) faces don't need subdivision
\r
1593 Tex = &TexInfo[Face->TexInfo];
\r
1595 //if ( Tex->Flags & TEXINFO_GOURAUD)
\r
1596 // FanFace_r(Node, Face);
\r
1598 if ( Tex->Flags & TEXINFO_NO_LIGHTMAP)
\r
1601 for (Axis = 0 ; Axis < 2 ; Axis++)
\r
1605 geFloat TexSize, SplitDist;
\r
1606 geFloat Mins16, Maxs16;
\r
1609 Maxs = -999999.0f;
\r
1611 geVec3d_Copy(&Tex->Vecs[Axis], &Temp);
\r
1613 for (i=0 ; i<Face->Poly->NumVerts ; i++)
\r
1615 v = geVec3d_DotProduct (&Face->Poly->Verts[i], &Temp);
\r
1622 Mins16 = (geFloat)floor(Mins/16.0f)*16.0f;
\r
1623 Maxs16 = (geFloat)ceil(Maxs/16.0f)*16.0f;
\r
1625 TexSize = Maxs - Mins;
\r
1626 //TexSize = Maxs16 - Mins16;
\r
1628 // Default to the Subdivide size
\r
1629 SplitDist = SubdivideSize;
\r
1632 if (TexSize <= SubdivideSize)
\r
1634 int32 Log, LogSize;
\r
1637 LogSize = SnapToPower2((int32)TexSize);
\r
1638 Log = GetLog(LogSize);
\r
1640 if (LogSize <= 16)
\r
1641 break; // Don't bother with small lmaps
\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
1645 if (Ratio >= 0.75f)
\r
1646 break; // No need to split, if going to use at least 50% of the space
\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
1652 // Overide the subdivide size with the next size down
\r
1653 SplitDist = (geFloat)(1<<Log);
\r
1656 if (TexSize <= SubdivideSize)
\r
1661 CopyPoly(Face->Poly, &p);
\r
1666 v = geVec3d_Normalize (&Temp);
\r
1668 Dist = (Mins + SplitDist - 16)/v;
\r
1669 //Dist = (Mins16 + SplitDist)/v;
\r
1671 Plane.Normal = Temp;
\r
1672 Plane.Dist = Dist;
\r
1673 Plane.Type = PLANE_ANY;
\r
1675 SplitPoly(p, &Plane, &Frontp, &Backp, GE_FALSE);
\r
1677 if (!Frontp || !Backp)
\r
1679 GHook.Printf("*WARNING* SubdivideFace: didn't split the polygon: %f, %f, %f\n", Mins, Maxs, SplitDist);
\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
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
1693 SubdivideFace (Node, Face->Split[0]);
\r
1694 SubdivideFace (Node, Face->Split[1]);
\r
1700 //====================================================================================
\r
1701 // SubdivideNodeFaces
\r
1702 //====================================================================================
\r
1703 void SubdivideNodeFaces (GBSP_Node *Node)
\r
1707 for (f = Node->Faces ; f ; f=f->Next)
\r
1709 SubdivideFace (Node, f);
\r
1713 //====================================================================================
\r
1715 //====================================================================================
\r
1716 geBoolean CheckFace(GBSP_Face *Face, geBoolean Verb)
\r
1718 int32 i, j, NumVerts;
\r
1719 geVec3d Vect1, *Verts, Normal, V1, V2, EdgeNormal;
\r
1721 geFloat Dist, PDist, EdgeDist;
\r
1723 Poly = Face->Poly;
\r
1724 Verts = Poly->Verts;
\r
1725 NumVerts = Poly->NumVerts;
\r
1730 GHook.Printf("CheckFace: NumVerts < 3.\n");
\r
1734 Normal = Planes[Face->PlaneNum].Normal;
\r
1735 PDist = Planes[Face->PlaneNum].Dist;
\r
1736 if (Face->PlaneSide)
\r
1738 geVec3d_Subtract(&VecOrigin, &Normal, &Normal);
\r
1743 // Check for degenerate edges, convexity, and make sure it's planar
\r
1745 for (i=0; i< NumVerts; i++)
\r
1748 V2 = Verts[(i+1)%NumVerts];
\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
1756 GHook.Printf("WARNING CheckFace: Degenerate Edge.\n");
\r
1760 // Check for planar
\r
1761 Dist = geVec3d_DotProduct(&V1, &Normal) - PDist;
\r
1762 if (Dist > ON_EPSILON || Dist <-ON_EPSILON)
\r
1765 GHook.Printf("WARNING CheckFace: Non planar: %f.\n", Dist);
\r
1769 geVec3d_CrossProduct(&Normal, &Vect1, &EdgeNormal);
\r
1770 geVec3d_Normalize(&EdgeNormal);
\r
1771 EdgeDist = geVec3d_DotProduct(&V1, &EdgeNormal);
\r
1773 // Check for convexity
\r
1774 for (j=0; j< NumVerts; j++)
\r
1776 Dist = geVec3d_DotProduct(&Verts[j], &EdgeNormal) - EdgeDist;
\r
1777 if (Dist > ON_EPSILON)
\r
1780 GHook.Printf("CheckFace: Face not convex.\n");
\r
1789 //====================================================================================
\r
1791 //====================================================================================
\r
1792 void GetFaceListBOX(GBSP_Face *Faces, geVec3d *Mins, geVec3d *Maxs)
\r
1799 ClearBounds(Mins, Maxs);
\r
1801 // Go through each face in this brush...
\r
1802 for (Face = Faces; Face; Face = Face->Next)
\r
1804 Poly = Face->Poly;
\r
1805 for (i=0; i< Poly->NumVerts; i++)
\r
1807 Vert = Poly->Verts[i];
\r
1810 if (Vert.X > Maxs->X)
\r
1812 if (Vert.Y > Maxs->Y)
\r
1814 if (Vert.Z > Maxs->Z)
\r
1817 // Then check mins
\r
1818 if (Vert.X < Mins->X)
\r
1820 if (Vert.Y < Mins->Y)
\r
1822 if (Vert.Z < Mins->Z)
\r