- build system has to use 32bit (the code is not 64bit safe)
[genesis3d.git] / GBSPLib / VISFLOOD.CPP
1 /****************************************************************************************/\r
2 /*  VisFlood.cpp                                                                        */\r
3 /*                                                                                      */\r
4 /*  Author: John Pollard                                                                */\r
5 /*  Description: Vises a BSP                                                            */\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 <Stdio.h>\r
24 \r
25 #include "Utils.h"\r
26 #include "Vis.h"\r
27 #include "GBSPFile.h"\r
28 #include "Poly.h"\r
29 #include "Bsp.h"\r
30 \r
31 #include "Ram.h"\r
32 \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
39 \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
45 \r
46 int32   CanSee;\r
47 int32   SrcLeaf;\r
48 int32   MightSee;\r
49 \r
50 extern geBoolean        VisVerbose;\r
51 extern geBoolean        NoSort;\r
52 extern geBoolean        FullVis;\r
53 \r
54 //=======================================================================================\r
55 //      FloodPortalsFast_r\r
56 //=======================================================================================\r
57 void FloodPortalsFast_r(VIS_Portal *SrcPortal, VIS_Portal *DestPortal)\r
58 {\r
59         VIS_Leaf        *Leaf;\r
60         VIS_Portal      *Portal;\r
61         int32           LeafNum;\r
62         int32           PNum;\r
63 \r
64         PNum = (int32)(DestPortal - VisPortals);\r
65         \r
66         if (CancelRequest)\r
67                 return;\r
68 \r
69         if (PortalSeen[PNum])\r
70                 return;\r
71 \r
72         PortalSeen[PNum] = 1;\r
73 \r
74         // Add the portal that we are Flooding into, to the original portals visbits\r
75         LeafNum = DestPortal->Leaf;\r
76         \r
77         int32   Bit = 1<<(PNum&7);\r
78         if (!(SrcPortal->VisBits[PNum>>3] & Bit))\r
79         {\r
80                 SrcPortal->VisBits[PNum>>3] |= Bit;\r
81                 SrcPortal->MightSee++;\r
82                 VisLeafs[SrcLeaf].MightSee++;\r
83                 MightSee++;\r
84         }\r
85 \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
89         {\r
90                 // If SrcPortal can see this Portal, flood into it...\r
91                 if (PortalCanSeePortal(SrcPortal, Portal))\r
92                         FloodPortalsFast_r(SrcPortal, Portal);\r
93         }\r
94 }\r
95 \r
96 //=======================================================================================\r
97 // FloodLeafPortalsFast\r
98 //=======================================================================================\r
99 void FloodLeafPortalsFast(int32 LeafNum)\r
100 {\r
101         VIS_Leaf        *Leaf;\r
102         VIS_Portal      *Portal;\r
103         int32           PNum;\r
104 \r
105         Leaf = &VisLeafs[LeafNum];\r
106 \r
107         if (!Leaf->Portals)\r
108         {\r
109                 //GHook.Printf("*WARNING* FloodLeafPortalsFast:  Leaf with no portals.\n");\r
110                 return;\r
111         }\r
112         \r
113         SrcLeaf = LeafNum;\r
114 \r
115         for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)\r
116         {\r
117                 Portal->VisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);\r
118 \r
119                 // This portal can't see anyone yet...\r
120                 memset(Portal->VisBits, 0, NumVisPortalBytes);\r
121                 memset(PortalSeen, 0, NumVisPortals);\r
122 \r
123                 MightSee = 0;\r
124                 \r
125                 FloodPortalsFast_r(Portal, Portal);\r
126 \r
127                 PNum = (int32)(Portal - VisPortals);\r
128                 \r
129                 //Hook.Printf("Portal: %5i - MightSee: %5i\n", PNum, MightSee);\r
130                 if (CancelRequest)\r
131                         return;\r
132         }\r
133 }\r
134 \r
135 geFloat PlaneDistanceFastP(geVec3d *Point, GBSP_Plane *Plane)\r
136 {\r
137    geFloat      Dist,Dist2;\r
138    Dist2 = Plane->Dist;\r
139 \r
140    switch (Plane->Type)\r
141    {\r
142            case PLANE_X:\r
143            //Dist = (Point->X - Dist2);\r
144            //break;\r
145            case PLANE_Y:\r
146            //Dist = (Point->Y - Dist2);\r
147            //break;\r
148            case PLANE_Z:\r
149            //Dist = (Point->Z - Dist2);\r
150            //break;\r
151        default:\r
152            Dist = geVec3d_DotProduct(Point, &Plane->Normal) - Dist2;\r
153            break;\r
154     }\r
155 \r
156     return Dist;\r
157 }\r
158 \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
165 {\r
166         int32           i;\r
167         GBSP_Poly       *Poly;\r
168         GBSP_Plane      *pPlane;\r
169         geVec3d         *pVert;\r
170         geFloat         Dist;\r
171 \r
172         // Check first portal\r
173         Poly = Portal1->Poly;\r
174         pVert = Poly->Verts;\r
175         pPlane = &Portal2->Plane;\r
176 \r
177         for (i=0; i< Poly->NumVerts; i++)\r
178         {\r
179                 Dist = PlaneDistanceFastP(pVert, pPlane);\r
180 \r
181                 if (Dist < -ON_EPSILON)\r
182                         break;\r
183         \r
184                 pVert++;\r
185         }\r
186 \r
187         if (i == Poly->NumVerts)\r
188                 return GE_FALSE;                                // No points of Portal1 behind Portal2, can't possibly see\r
189 \r
190         // Check second portal\r
191         Poly = Portal2->Poly;\r
192         pVert = Poly->Verts;\r
193 \r
194         pPlane = &Portal1->Plane;\r
195 \r
196         for (i=0; i< Poly->NumVerts; i++)\r
197         {\r
198                 Dist = PlaneDistanceFastP(pVert, pPlane);\r
199 \r
200                 if (Dist > ON_EPSILON)\r
201                         break;\r
202 \r
203                 pVert++;\r
204         }\r
205 \r
206         if (i == Poly->NumVerts)\r
207                 return GE_FALSE;                                // No points of Portal2 in front of Portal1, can't possibly see\r
208 \r
209         return GE_TRUE;                                         // It can see through it!!!\r
210 }\r
211 \r
212 \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
217 {\r
218         int32           i, j, k, l;\r
219         GBSP_Plane      Plane;\r
220         geVec3d         v1, v2;\r
221         geFloat         d;\r
222         geFloat         Length;\r
223         int32           Counts[3];\r
224         geBoolean       FlipTest;\r
225 \r
226         for (i=0 ; i<Source->NumVerts ; i++)\r
227         {\r
228                 l = (i+1)%Source->NumVerts;\r
229                 geVec3d_Subtract(&Source->Verts[l] , &Source->Verts[i], &v1);\r
230 \r
231                 for (j=0 ; j<Pass->NumVerts ; j++)\r
232                 {\r
233                         geVec3d_Subtract(&Pass->Verts[j], &Source->Verts[i], &v2);\r
234 \r
235                         geVec3d_CrossProduct(&v1, &v2, &Plane.Normal);\r
236                         \r
237                         Length = geVec3d_Normalize(&Plane.Normal);\r
238 \r
239                         if (Length < ON_EPSILON)\r
240                                 continue;\r
241                         \r
242                         Plane.Dist = geVec3d_DotProduct(&Pass->Verts[j], &Plane.Normal);\r
243 \r
244                 #if 1\r
245                         FlipTest = GE_FALSE;\r
246                         for (k=0 ; k<Source->NumVerts ; k++)\r
247                         {\r
248                                 if (k == i || k == l)\r
249                                         continue;\r
250 \r
251                                 d = geVec3d_DotProduct(&Source->Verts[k], &Plane.Normal) - Plane.Dist;\r
252                                 if (d < -ON_EPSILON)\r
253                                 {\r
254                                         FlipTest = GE_FALSE;\r
255                                         break;\r
256                                 }\r
257                                 else if (d > ON_EPSILON)\r
258                                 {       \r
259                                         FlipTest = GE_TRUE;\r
260                                         break;\r
261                                 }\r
262                         }\r
263                         if (k == Source->NumVerts)\r
264                                 continue;               \r
265 #else\r
266                         FlipTest = FlipClip;\r
267 #endif\r
268                         if (FlipTest)\r
269                         {\r
270                                 geVec3d_Inverse(&Plane.Normal);\r
271                                 Plane.Dist = -Plane.Dist;\r
272                         }\r
273 #if 1\r
274                         Counts[0] = Counts[1] = Counts[2] = 0;\r
275 \r
276                         for (k=0 ; k<Pass->NumVerts ; k++)\r
277                         {\r
278                                 if (k==j)\r
279                                         continue;\r
280                                 d = geVec3d_DotProduct(&Pass->Verts[k], &Plane.Normal) - Plane.Dist;\r
281                                 if (d < -ON_EPSILON)\r
282                                         break;\r
283                                 else if (d > ON_EPSILON)\r
284                                         Counts[0]++;\r
285                                 else\r
286                                         Counts[2]++;\r
287                         }\r
288                         if (k != Pass->NumVerts)\r
289                                 continue;       \r
290                                 \r
291                         if (!Counts[0])\r
292                                 continue;\r
293 #else\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
297                                 continue;\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
301                                 continue;                       \r
302 #endif\r
303                         if (!ClipPoly(Target, &Plane, FlipClip, &Target))\r
304                         {\r
305                                 GHook.Error("ClipToPortals:  Error clipping portal.\n");\r
306                                 return GE_FALSE;\r
307                         }\r
308 \r
309                         if (!Target)\r
310                         {\r
311                                 *Dest = NULL;\r
312                                 return GE_TRUE; \r
313                         }\r
314                 }\r
315         }\r
316         \r
317         *Dest = Target;\r
318         return GE_TRUE;\r
319 }\r
320 \r
321 //=======================================================================================\r
322 //      FloodPortalsSlow_r\r
323 //=======================================================================================\r
324 geBoolean FloodPortalsSlow_r(VIS_Portal *SrcPortal, VIS_Portal *DestPortal, VIS_PStack *PrevStack)\r
325 {\r
326         VIS_Leaf        *Leaf;\r
327         VIS_Portal      *Portal;\r
328         int32           LeafNum, j;\r
329         int32           PNum;\r
330         uint32          *Test, *Might, *Vis, More;\r
331         VIS_PStack      Stack;\r
332 \r
333         PNum = (int32)(DestPortal - VisPortals);\r
334         \r
335         if (CancelRequest)\r
336         {\r
337                 GHook.Printf("Cancel requested...\n");\r
338                 return GE_FALSE;\r
339         }\r
340 \r
341         //if (PortalSeen[PNum])\r
342         //      return GE_TRUE;\r
343         //PortalSeen[PNum] = 1;\r
344 \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
348         {\r
349                 SrcPortal->FinalVisBits[PNum>>3] |= Bit;\r
350                 SrcPortal->CanSee++;\r
351                 VisLeafs[SrcLeaf].CanSee++;\r
352                 CanSee++;\r
353         }\r
354 \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
358 \r
359         Might = (uint32*)Stack.VisBits;\r
360         Vis = (uint32*)SrcPortal->FinalVisBits;\r
361 \r
362         // Now, try and Flood into the leafs that this portal touches\r
363         for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)\r
364         {\r
365                 PNum = (int32)(Portal - VisPortals);\r
366                 Bit = 1<<(PNum&7);\r
367 \r
368                 //GHook.Printf("PrevStack VisBits:  %i\n", PrevStack->VisBits[PNum>>3]);\r
369 \r
370                 // If might see could'nt see it, then don't worry about it\r
371                 if (!(SrcPortal->VisBits[PNum>>3] & Bit))\r
372                         continue;\r
373 \r
374                 if (!(PrevStack->VisBits[PNum>>3] & Bit))\r
375                         continue;       // Can't possibly see it\r
376 \r
377                 // If the portal can't see anything we haven't allready seen, skip it\r
378                 if (Portal->Done)\r
379                         Test = (uint32*)Portal->FinalVisBits;\r
380                 else\r
381                         Test = (uint32*)Portal->VisBits;\r
382 \r
383                 More = 0;\r
384                 for (j=0 ; j<NumVisPortalLongs ; j++)\r
385                 {\r
386                         Might[j] = ((uint32*)PrevStack->VisBits)[j] & Test[j];\r
387                         More |= (Might[j] & ~Vis[j]);\r
388                 }\r
389                 \r
390                 if (!More && (SrcPortal->FinalVisBits[PNum>>3] & Bit) ) // Can't see anything new\r
391                         continue;\r
392                 \r
393                 // Setup Source/Pass\r
394                 if (!CopyPoly(Portal->Poly, &Stack.Pass))\r
395                         return GE_FALSE;\r
396 \r
397         #if 0\r
398                 geFloat Dist;\r
399 \r
400                 Dist = geVec3d_DotProduct(&Portal->Center, &SrcPortal->Plane.Normal) - SrcPortal->Plane.Dist;\r
401 \r
402                 if (Dist < -Portal->Radius)                     // Totally behind\r
403                         continue;\r
404                 else if (Dist < Portal->Radius) \r
405                 {\r
406                         if (!ClipPoly(Stack.Pass, &SrcPortal->Plane, GE_FALSE, &Stack.Pass))\r
407                                 return GE_FALSE;\r
408                         if (!Stack.Pass)\r
409                                 continue;\r
410                 }\r
411         #else\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
414                         return GE_FALSE;\r
415                 if (!Stack.Pass)\r
416                         continue;\r
417         #endif\r
418 \r
419                 if (!CopyPoly(PrevStack->Source, &Stack.Source))\r
420                         return GE_FALSE;\r
421 \r
422         #if 0\r
423                 Dist = geVec3d_DotProduct(&SrcPortal->Center, &Portal->Plane.Normal) - Portal->Plane.Dist;\r
424 \r
425                 if (Dist > Portal->Radius)                      // Totally behind\r
426                         continue;\r
427                 else if (Dist > -Portal->Radius)        \r
428                 {\r
429                         if (!ClipPoly(Stack.Source, &Portal->Plane, GE_TRUE, &Stack.Source))\r
430                                 return GE_FALSE;\r
431                         if (!Stack.Source)\r
432                         {\r
433                                 FreePoly(Stack.Pass);\r
434                                 continue;\r
435                         }\r
436                 }\r
437         #else\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
440                         return GE_FALSE;\r
441                 if (!Stack.Source)\r
442                 {\r
443                         FreePoly(Stack.Pass);\r
444                         continue;\r
445                 }\r
446         #endif\r
447 \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
451                 {\r
452                         if (!FloodPortalsSlow_r(SrcPortal, Portal, &Stack))\r
453                                 return GE_FALSE;\r
454 \r
455                         FreePoly(Stack.Source);\r
456                         FreePoly(Stack.Pass);\r
457                         continue;\r
458                 }\r
459 \r
460                 if (!ClipToSeperators(Stack.Source, PrevStack->Pass, Stack.Pass, GE_FALSE, &Stack.Pass))\r
461                         return GE_FALSE;\r
462 \r
463                 if (!Stack.Pass)\r
464                 {\r
465                         FreePoly(Stack.Source);\r
466                         continue;\r
467                 }\r
468                 \r
469         #if 1\r
470                 if (!ClipToSeperators(PrevStack->Pass, Stack.Source, Stack.Pass, GE_TRUE, &Stack.Pass))\r
471                         return GE_FALSE;\r
472                 if (!Stack.Pass)\r
473                 {\r
474                         FreePoly(Stack.Source);\r
475                         continue;\r
476                 }\r
477         #else\r
478         /*\r
479                 if (!ClipToSeperators(Stack.Source, PrevStack->Pass, Stack.Source, GE_TRUE, &Stack.Source))\r
480                         return GE_FALSE;\r
481 \r
482                 if (!Stack.Source)\r
483                 {\r
484                         FreePoly(Stack.Pass);\r
485                         continue;\r
486                 }\r
487         */\r
488         #endif          \r
489                 // Flood into it...\r
490                 if (!FloodPortalsSlow_r(SrcPortal, Portal, &Stack))\r
491                         return GE_FALSE;\r
492 \r
493                 FreePoly(Stack.Source);\r
494                 FreePoly(Stack.Pass);\r
495         }\r
496 \r
497         return GE_TRUE;\r
498 }\r
499 \r
500 //=======================================================================================\r
501 // FloodLeafPortalsSlow\r
502 //=======================================================================================\r
503 geBoolean FloodLeafPortalsSlow(int32 LeafNum)\r
504 {\r
505         VIS_Leaf        *Leaf;\r
506         VIS_Portal      *Portal;\r
507         int32           PNum;\r
508         VIS_PStack      PStack;\r
509         int32           i;\r
510 \r
511         Leaf = &VisLeafs[LeafNum];\r
512 \r
513         if (!Leaf->Portals)\r
514         {\r
515                 //GHook.Printf("*WARNING* FloodLeafPortalsFast:  Leaf with no portals.\n");\r
516                 return GE_TRUE;\r
517         }\r
518         \r
519         SrcLeaf = LeafNum;\r
520         for (Portal = Leaf->Portals; Portal; Portal = Portal->Next)\r
521         {\r
522                 Portal->FinalVisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);\r
523 \r
524                 // This portal can't see anyone yet...\r
525                 memset(Portal->FinalVisBits, 0, NumVisPortalBytes);\r
526                 memset(PortalSeen, 0, NumVisPortals);\r
527 \r
528                 CanSee = 0;\r
529                 \r
530                 for (i=0; i< NumVisPortalBytes; i++)\r
531                         PStack.VisBits[i] = Portal->VisBits[i];\r
532 \r
533                 // Setup Source/Pass\r
534                 if (!CopyPoly(Portal->Poly, &PStack.Source))\r
535                         return GE_FALSE;\r
536                 PStack.Pass = NULL;\r
537 \r
538                 if (!FloodPortalsSlow_r(Portal, Portal, &PStack))\r
539                         return GE_FALSE;\r
540 \r
541                 Portal->Done = GE_TRUE;\r
542 \r
543                 PNum = (int32)(Portal - VisPortals);\r
544                 //Hook.Printf("Portal: %5i - MightSee: %5i\n", PNum, MightSee);\r
545         }\r
546 \r
547         return GE_TRUE;\r
548 }\r
549 \r
550 //=======================================================================================\r
551 //      FloodPortalsSlow\r
552 //=======================================================================================\r
553 geBoolean FloodPortalsSlow(void)\r
554 {\r
555         VIS_Portal      *Portal;\r
556         int32           PNum;\r
557         VIS_PStack      PStack;\r
558         int32           i, k;\r
559 \r
560         for (k=0; k< NumVisPortals; k++)\r
561                 VisPortals[k].Done = GE_FALSE;\r
562 \r
563         for (k=0; k< NumVisPortals; k++)\r
564         {\r
565                 Portal = VisSortedPortals[k];\r
566                 \r
567                 Portal->FinalVisBits = GE_RAM_ALLOCATE_ARRAY(uint8,NumVisPortalBytes);\r
568 \r
569                 // This portal can't see anyone yet...\r
570                 memset(Portal->FinalVisBits, 0, NumVisPortalBytes);\r
571                 memset(PortalSeen, 0, NumVisPortals);\r
572 \r
573                 CanSee = 0;\r
574                 \r
575                 for (i=0; i< NumVisPortalBytes; i++)\r
576                         PStack.VisBits[i] = Portal->VisBits[i];\r
577 \r
578                 // Setup Source/Pass\r
579                 if (!CopyPoly(Portal->Poly, &PStack.Source))\r
580                         return GE_FALSE;\r
581                 PStack.Pass = NULL;\r
582 \r
583                 if (!FloodPortalsSlow_r(Portal, Portal, &PStack))\r
584                         return GE_FALSE;\r
585 \r
586                 FreePoly(PStack.Source);\r
587 \r
588                 Portal->Done = GE_TRUE;\r
589 \r
590                 PNum = (int32)(Portal - VisPortals);\r
591                 if (VisVerbose)\r
592                         GHook.Printf("Portal: %4i - Fast Vis: %4i, Full Vis: %4i\n", k+1, Portal->MightSee, Portal->CanSee);\r
593         }\r
594 \r
595         return GE_TRUE;\r
596 }\r