1 /****************************************************************************************/
\r
4 /* Author: John Pollard */
\r
5 /* Description: Vises a BSP */
\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
27 #include "GBSPFile.h"
\r
33 extern int32 NumVisPortals; // Total portals
\r
34 extern int32 NumVisPortalBytes; // Total portals / 8
\r
35 extern int32 NumVisPortalLongs; // Total portalbytes / 4
\r
36 extern VIS_Portal *VisPortals; // NumVisPortals
\r
37 extern pVIS_Portal *VisSortedPortals; // Pointers to portals sorted by MightSee
\r
38 extern uint8 *PortalSeen; // Temp vis array
\r
40 extern int32 NumVisLeafs; // Total VisLeafs
\r
41 extern int32 NumVisLeafBytes; // NumVisLeaf / 8
\r
42 extern int32 NumVisLeafLongs; // NumVisBytes / sizeof(uint32)
\r
43 extern uint8 *LeafVisBits; // Should be NumVisLeafs * (NumVisLeafs / 8)
\r
44 extern VIS_Leaf *VisLeafs; // NumVisLeafs
\r
50 extern geBoolean VisVerbose;
\r
51 extern geBoolean NoSort;
\r
52 extern geBoolean FullVis;
\r
54 //=======================================================================================
\r
55 // FloodPortalsFast_r
\r
56 //=======================================================================================
\r
57 void FloodPortalsFast_r(VIS_Portal *SrcPortal, VIS_Portal *DestPortal)
\r
64 PNum = (int32)(DestPortal - VisPortals);
\r
69 if (PortalSeen[PNum])
\r
72 PortalSeen[PNum] = 1;
\r
74 // Add the portal that we are Flooding into, to the original portals visbits
\r
75 LeafNum = DestPortal->Leaf;
\r
77 int32 Bit = 1<<(PNum&7);
\r
78 if (!(SrcPortal->VisBits[PNum>>3] & Bit))
\r
80 SrcPortal->VisBits[PNum>>3] |= Bit;
\r
81 SrcPortal->MightSee++;
\r
82 VisLeafs[SrcLeaf].MightSee++;
\r
86 Leaf = &VisLeafs[LeafNum];
\r
87 // Now, try and Flood into the leafs that this portal touches
\r
88 for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)
\r
90 // If SrcPortal can see this Portal, flood into it...
\r
91 if (PortalCanSeePortal(SrcPortal, Portal))
\r
92 FloodPortalsFast_r(SrcPortal, Portal);
\r
96 //=======================================================================================
\r
97 // FloodLeafPortalsFast
\r
98 //=======================================================================================
\r
99 void FloodLeafPortalsFast(int32 LeafNum)
\r
102 VIS_Portal *Portal;
\r
105 Leaf = &VisLeafs[LeafNum];
\r
107 if (!Leaf->Portals)
\r
109 //GHook.Printf("*WARNING* FloodLeafPortalsFast: Leaf with no portals.\n");
\r
115 for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)
\r
117 Portal->VisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);
\r
119 // This portal can't see anyone yet...
\r
120 memset(Portal->VisBits, 0, NumVisPortalBytes);
\r
121 memset(PortalSeen, 0, NumVisPortals);
\r
125 FloodPortalsFast_r(Portal, Portal);
\r
127 PNum = (int32)(Portal - VisPortals);
\r
129 //Hook.Printf("Portal: %5i - MightSee: %5i\n", PNum, MightSee);
\r
135 geFloat PlaneDistanceFastP(geVec3d *Point, GBSP_Plane *Plane)
\r
137 geFloat Dist,Dist2;
\r
138 Dist2 = Plane->Dist;
\r
140 switch (Plane->Type)
\r
143 //Dist = (Point->X - Dist2);
\r
146 //Dist = (Point->Y - Dist2);
\r
149 //Dist = (Point->Z - Dist2);
\r
152 Dist = geVec3d_DotProduct(Point, &Plane->Normal) - Dist2;
\r
159 //=======================================================================================
\r
160 // PortalCanSeePortal
\r
161 // See if Portal1 can see into Portal2
\r
162 // (Quick, does not take into acount of other leafs blocking path)
\r
163 //=======================================================================================
\r
164 geBoolean PortalCanSeePortal(VIS_Portal *Portal1, VIS_Portal *Portal2)
\r
168 GBSP_Plane *pPlane;
\r
172 // Check first portal
\r
173 Poly = Portal1->Poly;
\r
174 pVert = Poly->Verts;
\r
175 pPlane = &Portal2->Plane;
\r
177 for (i=0; i< Poly->NumVerts; i++)
\r
179 Dist = PlaneDistanceFastP(pVert, pPlane);
\r
181 if (Dist < -ON_EPSILON)
\r
187 if (i == Poly->NumVerts)
\r
188 return GE_FALSE; // No points of Portal1 behind Portal2, can't possibly see
\r
190 // Check second portal
\r
191 Poly = Portal2->Poly;
\r
192 pVert = Poly->Verts;
\r
194 pPlane = &Portal1->Plane;
\r
196 for (i=0; i< Poly->NumVerts; i++)
\r
198 Dist = PlaneDistanceFastP(pVert, pPlane);
\r
200 if (Dist > ON_EPSILON)
\r
206 if (i == Poly->NumVerts)
\r
207 return GE_FALSE; // No points of Portal2 in front of Portal1, can't possibly see
\r
209 return GE_TRUE; // It can see through it!!!
\r
213 //=======================================================================================
\r
214 // ClipToSeperators
\r
215 //=======================================================================================
\r
216 geBoolean ClipToSeperators (GBSP_Poly *Source, GBSP_Poly *Pass, GBSP_Poly *Target, geBoolean FlipClip, GBSP_Poly **Dest)
\r
224 geBoolean FlipTest;
\r
226 for (i=0 ; i<Source->NumVerts ; i++)
\r
228 l = (i+1)%Source->NumVerts;
\r
229 geVec3d_Subtract(&Source->Verts[l] , &Source->Verts[i], &v1);
\r
231 for (j=0 ; j<Pass->NumVerts ; j++)
\r
233 geVec3d_Subtract(&Pass->Verts[j], &Source->Verts[i], &v2);
\r
235 geVec3d_CrossProduct(&v1, &v2, &Plane.Normal);
\r
237 Length = geVec3d_Normalize(&Plane.Normal);
\r
239 if (Length < ON_EPSILON)
\r
242 Plane.Dist = geVec3d_DotProduct(&Pass->Verts[j], &Plane.Normal);
\r
245 FlipTest = GE_FALSE;
\r
246 for (k=0 ; k<Source->NumVerts ; k++)
\r
248 if (k == i || k == l)
\r
251 d = geVec3d_DotProduct(&Source->Verts[k], &Plane.Normal) - Plane.Dist;
\r
252 if (d < -ON_EPSILON)
\r
254 FlipTest = GE_FALSE;
\r
257 else if (d > ON_EPSILON)
\r
259 FlipTest = GE_TRUE;
\r
263 if (k == Source->NumVerts)
\r
266 FlipTest = FlipClip;
\r
270 geVec3d_Inverse(&Plane.Normal);
\r
271 Plane.Dist = -Plane.Dist;
\r
274 Counts[0] = Counts[1] = Counts[2] = 0;
\r
276 for (k=0 ; k<Pass->NumVerts ; k++)
\r
280 d = geVec3d_DotProduct(&Pass->Verts[k], &Plane.Normal) - Plane.Dist;
\r
281 if (d < -ON_EPSILON)
\r
283 else if (d > ON_EPSILON)
\r
288 if (k != Pass->NumVerts)
\r
294 k = (j+1)%Pass->NumVerts;
\r
295 d = geVec3d_DotProduct(&Pass->Verts[k], &Plane.Normal) - Plane.Dist;
\r
296 if (d < -ON_EPSILON)
\r
298 k = (j+Pass->NumVerts-1)%Pass->NumVerts;
\r
299 d = geVec3d_DotProduct(&Pass->Verts[k], &Plane.Normal) - Plane.Dist;
\r
300 if (d < -ON_EPSILON)
\r
303 if (!ClipPoly(Target, &Plane, FlipClip, &Target))
\r
305 GHook.Error("ClipToPortals: Error clipping portal.\n");
\r
321 //=======================================================================================
\r
322 // FloodPortalsSlow_r
\r
323 //=======================================================================================
\r
324 geBoolean FloodPortalsSlow_r(VIS_Portal *SrcPortal, VIS_Portal *DestPortal, VIS_PStack *PrevStack)
\r
327 VIS_Portal *Portal;
\r
330 uint32 *Test, *Might, *Vis, More;
\r
333 PNum = (int32)(DestPortal - VisPortals);
\r
337 GHook.Printf("Cancel requested...\n");
\r
341 //if (PortalSeen[PNum])
\r
343 //PortalSeen[PNum] = 1;
\r
345 // Add the portal that we are Flooding into, to the original portals visbits
\r
346 int32 Bit = 1<<(PNum&7);
\r
347 if (!(SrcPortal->FinalVisBits[PNum>>3] & Bit))
\r
349 SrcPortal->FinalVisBits[PNum>>3] |= Bit;
\r
350 SrcPortal->CanSee++;
\r
351 VisLeafs[SrcLeaf].CanSee++;
\r
355 // Get the leaf that this portal looks into, and flood from there
\r
356 LeafNum = DestPortal->Leaf;
\r
357 Leaf = &VisLeafs[LeafNum];
\r
359 Might = (uint32*)Stack.VisBits;
\r
360 Vis = (uint32*)SrcPortal->FinalVisBits;
\r
362 // Now, try and Flood into the leafs that this portal touches
\r
363 for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)
\r
365 PNum = (int32)(Portal - VisPortals);
\r
368 //GHook.Printf("PrevStack VisBits: %i\n", PrevStack->VisBits[PNum>>3]);
\r
370 // If might see could'nt see it, then don't worry about it
\r
371 if (!(SrcPortal->VisBits[PNum>>3] & Bit))
\r
374 if (!(PrevStack->VisBits[PNum>>3] & Bit))
\r
375 continue; // Can't possibly see it
\r
377 // If the portal can't see anything we haven't allready seen, skip it
\r
379 Test = (uint32*)Portal->FinalVisBits;
\r
381 Test = (uint32*)Portal->VisBits;
\r
384 for (j=0 ; j<NumVisPortalLongs ; j++)
\r
386 Might[j] = ((uint32*)PrevStack->VisBits)[j] & Test[j];
\r
387 More |= (Might[j] & ~Vis[j]);
\r
390 if (!More && (SrcPortal->FinalVisBits[PNum>>3] & Bit) ) // Can't see anything new
\r
393 // Setup Source/Pass
\r
394 if (!CopyPoly(Portal->Poly, &Stack.Pass))
\r
400 Dist = geVec3d_DotProduct(&Portal->Center, &SrcPortal->Plane.Normal) - SrcPortal->Plane.Dist;
\r
402 if (Dist < -Portal->Radius) // Totally behind
\r
404 else if (Dist < Portal->Radius)
\r
406 if (!ClipPoly(Stack.Pass, &SrcPortal->Plane, GE_FALSE, &Stack.Pass))
\r
412 // Cut away portion of pass portal we can't see through
\r
413 if (!ClipPoly(Stack.Pass, &SrcPortal->Plane, GE_FALSE, &Stack.Pass))
\r
419 if (!CopyPoly(PrevStack->Source, &Stack.Source))
\r
423 Dist = geVec3d_DotProduct(&SrcPortal->Center, &Portal->Plane.Normal) - Portal->Plane.Dist;
\r
425 if (Dist > Portal->Radius) // Totally behind
\r
427 else if (Dist > -Portal->Radius)
\r
429 if (!ClipPoly(Stack.Source, &Portal->Plane, GE_TRUE, &Stack.Source))
\r
433 FreePoly(Stack.Pass);
\r
438 // Also, Cut away portion of source portal that can't be seen through pass
\r
439 if (!ClipPoly(Stack.Source, &Portal->Plane, GE_TRUE, &Stack.Source))
\r
443 FreePoly(Stack.Pass);
\r
448 // If we don't have a PrevStack->Pass, then we don't have enough to look through.
\r
449 // This portal can only be blocked by VisBits (Above test)...
\r
450 if (!PrevStack->Pass)
\r
452 if (!FloodPortalsSlow_r(SrcPortal, Portal, &Stack))
\r
455 FreePoly(Stack.Source);
\r
456 FreePoly(Stack.Pass);
\r
460 if (!ClipToSeperators(Stack.Source, PrevStack->Pass, Stack.Pass, GE_FALSE, &Stack.Pass))
\r
465 FreePoly(Stack.Source);
\r
470 if (!ClipToSeperators(PrevStack->Pass, Stack.Source, Stack.Pass, GE_TRUE, &Stack.Pass))
\r
474 FreePoly(Stack.Source);
\r
479 if (!ClipToSeperators(Stack.Source, PrevStack->Pass, Stack.Source, GE_TRUE, &Stack.Source))
\r
484 FreePoly(Stack.Pass);
\r
489 // Flood into it...
\r
490 if (!FloodPortalsSlow_r(SrcPortal, Portal, &Stack))
\r
493 FreePoly(Stack.Source);
\r
494 FreePoly(Stack.Pass);
\r
500 //=======================================================================================
\r
501 // FloodLeafPortalsSlow
\r
502 //=======================================================================================
\r
503 geBoolean FloodLeafPortalsSlow(int32 LeafNum)
\r
506 VIS_Portal *Portal;
\r
511 Leaf = &VisLeafs[LeafNum];
\r
513 if (!Leaf->Portals)
\r
515 //GHook.Printf("*WARNING* FloodLeafPortalsFast: Leaf with no portals.\n");
\r
520 for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)
\r
522 Portal->FinalVisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);
\r
524 // This portal can't see anyone yet...
\r
525 memset(Portal->FinalVisBits, 0, NumVisPortalBytes);
\r
526 memset(PortalSeen, 0, NumVisPortals);
\r
530 for (i=0; i< NumVisPortalBytes; i++)
\r
531 PStack.VisBits[i] = Portal->VisBits[i];
\r
533 // Setup Source/Pass
\r
534 if (!CopyPoly(Portal->Poly, &PStack.Source))
\r
536 PStack.Pass = NULL;
\r
538 if (!FloodPortalsSlow_r(Portal, Portal, &PStack))
\r
541 Portal->Done = GE_TRUE;
\r
543 PNum = (int32)(Portal - VisPortals);
\r
544 //Hook.Printf("Portal: %5i - MightSee: %5i\n", PNum, MightSee);
\r
550 //=======================================================================================
\r
551 // FloodPortalsSlow
\r
552 //=======================================================================================
\r
553 geBoolean FloodPortalsSlow(void)
\r
555 VIS_Portal *Portal;
\r
560 for (k=0; k< NumVisPortals; k++)
\r
561 VisPortals[k].Done = GE_FALSE;
\r
563 for (k=0; k< NumVisPortals; k++)
\r
565 Portal = VisSortedPortals[k];
\r
567 Portal->FinalVisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);
\r
569 // This portal can't see anyone yet...
\r
570 memset(Portal->FinalVisBits, 0, NumVisPortalBytes);
\r
571 memset(PortalSeen, 0, NumVisPortals);
\r
575 for (i=0; i< NumVisPortalBytes; i++)
\r
576 PStack.VisBits[i] = Portal->VisBits[i];
\r
578 // Setup Source/Pass
\r
579 if (!CopyPoly(Portal->Poly, &PStack.Source))
\r
581 PStack.Pass = NULL;
\r
583 if (!FloodPortalsSlow_r(Portal, Portal, &PStack))
\r
586 FreePoly(PStack.Source);
\r
588 Portal->Done = GE_TRUE;
\r
590 PNum = (int32)(Portal - VisPortals);
\r
592 GHook.Printf("Portal: %4i - Fast Vis: %4i, Full Vis: %4i\n", k+1, Portal->MightSee, Portal->CanSee);
\r