- build system has to use 32bit (the code is not 64bit safe)
[genesis3d.git] / GBSPLib / Fill.Cpp
1 /****************************************************************************************/\r
2 /*  Fill.cpp                                                                            */\r
3 /*                                                                                      */\r
4 /*  Author: John Pollard                                                                */\r
5 /*  Description: Does the flood filling of the leafs, and removes untouchable leafs     */\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 "Fill.h"\r
26 #include "Map.h"\r
27 #include "Portals.h"\r
28 #include "Leaf.h"\r
29 #include "Poly.h"\r
30 #include "GBSPFile.h"\r
31 #include "Bsp.h"\r
32 \r
33 int32           CurrentFill;\r
34 geBoolean       HitEntity = GE_FALSE;\r
35 int32           EntityHit = 0;\r
36 GBSP_Node       *HitNode;\r
37 \r
38 int32           NumRemovedLeafs;\r
39 \r
40 //=====================================================================================\r
41 //      PlaceEntities\r
42 //=====================================================================================\r
43 geBoolean PlaceEntities(GBSP_Node *RootNode)\r
44 {                               \r
45         int32           i;\r
46         GBSP_Node       *Node;\r
47         geBoolean       Empty;\r
48 \r
49         Empty = GE_FALSE;\r
50 \r
51         for (i=1; i< NumEntities; i++)\r
52         {\r
53                 if (!(Entities[i].Flags & ENTITY_HAS_ORIGIN))           // No "Origin" in entity\r
54                         continue;\r
55 \r
56                 Node = FindLeaf(RootNode, &Entities[i].Origin);\r
57                 if (!Node)\r
58                         return GE_FALSE;\r
59 \r
60                 if (!(Node->Contents & BSP_CONTENTS_SOLID2))\r
61                 {\r
62                         Node->Entity = i;\r
63                         Empty = GE_TRUE;\r
64                 }\r
65         }\r
66         \r
67         if (!Empty)\r
68         {\r
69                 GHook.Error("PlaceEntities:  No valid entities for operation %i.\n", NumEntities);\r
70                 return GE_FALSE;\r
71         }\r
72         \r
73         return GE_TRUE;\r
74 }\r
75 \r
76 //=====================================================================================\r
77 //      FillUnTouchedLeafs_r\r
78 //=====================================================================================\r
79 void FillUnTouchedLeafs_r(GBSP_Node *Node)\r
80 {\r
81         if (Node->PlaneNum != PLANENUM_LEAF)\r
82         {\r
83                 FillUnTouchedLeafs_r(Node->Children[0]);\r
84                 FillUnTouchedLeafs_r(Node->Children[1]);\r
85                 return;\r
86         }\r
87 \r
88         if ((Node->Contents & BSP_CONTENTS_SOLID2))\r
89                 return;         //allready solid or removed...\r
90 \r
91         if (Node->CurrentFill != CurrentFill)\r
92         {\r
93                 // Fill er in with solid so it does not show up...(Preserve user contents)\r
94                 Node->Contents &= (0xffff0000);\r
95                 Node->Contents |= BSP_CONTENTS_SOLID2;\r
96                 NumRemovedLeafs++;\r
97         }\r
98 }\r
99 \r
100 //=====================================================================================\r
101 //      FillLeafs2_r\r
102 //=====================================================================================\r
103 geBoolean FillLeafs2_r(GBSP_Node *Node)\r
104 {\r
105         GBSP_Portal             *Portal;\r
106         int32                   Side;\r
107         \r
108         if (Node->Contents & BSP_CONTENTS_SOLID2)\r
109                 return GE_TRUE;\r
110 \r
111         if (Node->CurrentFill == CurrentFill)\r
112                 return GE_TRUE;\r
113 \r
114         Node->CurrentFill = CurrentFill;\r
115 \r
116         for (Portal = Node->Portals; Portal; Portal = Portal->Next[Side])\r
117         {\r
118                 if (Portal->Nodes[0] == Node)\r
119                         Side = 0;\r
120                 else if (Portal->Nodes[1] == Node)\r
121                         Side = 1;\r
122                 else\r
123                 {\r
124                         GHook.Error("RemoveOutside2_r:  Portal does not look at either node.\n");\r
125                         return GE_FALSE;\r
126                 }\r
127 \r
128                 // Go though the portal to the node on the other side (!side)\r
129                 if (!FillLeafs2_r(Portal->Nodes[!Side]))\r
130                         return GE_FALSE;\r
131         }\r
132 \r
133         return GE_TRUE;\r
134 }\r
135 \r
136 //=====================================================================================\r
137 //      CanPassPortal\r
138 //      See if a portal can be passed through or not\r
139 //=====================================================================================\r
140 geBoolean CanPassPortal(GBSP_Portal *Portal)\r
141 {\r
142         if (Portal->Nodes[0]->PlaneNum != PLANENUM_LEAF)\r
143                 GHook.Printf("*WARNING* CanPassPortal:  Portal does not seperate leafs.\n");\r
144 \r
145         if (Portal->Nodes[1]->PlaneNum != PLANENUM_LEAF)\r
146                 GHook.Printf("*WARNING* CanPassPortal:  Portal does not seperate leafs.\n");\r
147 \r
148         if (Portal->Nodes[0]->Contents & BSP_CONTENTS_SOLID2)\r
149                 return GE_FALSE;\r
150 \r
151         if (Portal->Nodes[1]->Contents & BSP_CONTENTS_SOLID2)\r
152                 return GE_FALSE;\r
153 \r
154         return GE_TRUE;\r
155 }\r
156 \r
157 //=====================================================================================\r
158 //      FillLeafs_r\r
159 //=====================================================================================\r
160 geBoolean FillLeafs_r(GBSP_Node *Node, geBoolean Fill, int32 Dist)\r
161 {\r
162         GBSP_Portal             *Portal;\r
163         int32                   Side;\r
164         \r
165         //if (HitEntity)\r
166         //      return GE_TRUE;\r
167         \r
168         if (Node->Contents & BSP_CONTENTS_SOLID2)\r
169                 return GE_TRUE;\r
170 \r
171         if (Node->CurrentFill == CurrentFill)\r
172                 return GE_TRUE;\r
173 \r
174         Node->CurrentFill = CurrentFill;\r
175 \r
176         Node->Occupied = Dist;\r
177 \r
178         if (Fill)\r
179         {\r
180                 // Preserve user contents\r
181                 Node->Contents &= 0xffff0000;\r
182                 Node->Contents |= BSP_CONTENTS_SOLID2;\r
183         }\r
184         else \r
185         {\r
186                 if (Node->Entity)\r
187                 {\r
188                         HitEntity = GE_TRUE;\r
189                         EntityHit = Node->Entity;\r
190                         HitNode = Node;\r
191                         return GE_TRUE;\r
192                 }\r
193         }\r
194 \r
195         for (Portal = Node->Portals; Portal; Portal = Portal->Next[Side])\r
196         {\r
197                 if (Portal->Nodes[0] == Node)\r
198                         Side = 0;\r
199                 else if (Portal->Nodes[1] == Node)\r
200                         Side = 1;\r
201                 else\r
202                 {\r
203                         GHook.Error("FillLeafs_r:  Portal does not look at either node.\n");\r
204                         return GE_FALSE;\r
205                 }\r
206                 \r
207                 //if (!CanPassPortal(Portal))\r
208                 //      continue;\r
209 \r
210                 if (!FillLeafs_r(Portal->Nodes[!Side], Fill, Dist+1))\r
211                         return GE_FALSE;\r
212         }\r
213 \r
214         return GE_TRUE;\r
215 }\r
216 \r
217 //=====================================================================================\r
218 //      FillFromEntities\r
219 //=====================================================================================\r
220 geBoolean FillFromEntities(GBSP_Node *RootNode)\r
221 {\r
222         int32           i;\r
223         GBSP_Node       *Node;\r
224         geBoolean       Empty;\r
225 \r
226         Empty = GE_FALSE;\r
227         \r
228         for (i=1; i< NumEntities; i++)  // Don't use the world as an entity (skip 0)!!\r
229         {\r
230                 if (!(Entities[i].Flags & ENTITY_HAS_ORIGIN))           // No "Origin" in entity\r
231                         continue;\r
232 \r
233                 Node = FindLeaf(RootNode, &Entities[i].Origin);\r
234 \r
235                 if (Node->Contents & BSP_CONTENTS_SOLID2)\r
236                         continue;\r
237                 \r
238                 // There is at least one entity in empty space...\r
239                 Empty = GE_TRUE;\r
240 \r
241                 if (!FillLeafs2_r(Node))\r
242                         return GE_FALSE;\r
243         }\r
244 \r
245         if (!Empty)\r
246         {\r
247                 GHook.Error("FillFromEntities:  No valid entities for operation.\n");\r
248                 return GE_FALSE;\r
249         }\r
250 \r
251         return GE_TRUE;\r
252 }\r
253 \r
254 //=====================================================================================\r
255 //      LeafCenter\r
256 //=====================================================================================\r
257 void LeafCenter(GBSP_Node *Node, geVec3d *PortalMid)\r
258 {\r
259         int32           NumPortals, Side;\r
260         geVec3d         Mid;\r
261         GBSP_Portal     *Portal;\r
262 \r
263         NumPortals = 0;\r
264         geVec3d_Clear(PortalMid);\r
265 \r
266         for (Portal = Node->Portals; Portal; Portal = Portal->Next[Side])\r
267         {\r
268                 Side = Portal->Nodes[1] == Node;\r
269 \r
270                 PolyCenter(Portal->Poly, &Mid);\r
271                 geVec3d_Add(PortalMid, &Mid, PortalMid);\r
272                 NumPortals++;\r
273         }\r
274 \r
275         geVec3d_Scale(PortalMid, 1.0f/(geFloat)NumPortals, PortalMid);\r
276 }\r
277 \r
278 //=====================================================================================\r
279 //      WriteLeakFile\r
280 //=====================================================================================\r
281 geBoolean WriteLeakFile (char *FileName, GBSP_Node *Start, GBSP_Node *Outside)\r
282 {\r
283         geVec3d         Mid;\r
284         FILE            *PntFile;\r
285         char            FileName2[1024];\r
286         int32           Count;\r
287         GBSP_Node       *Node;\r
288         int                     Pos1, Pos2;\r
289         char            TAG[5];\r
290         geBoolean       Stop;\r
291 \r
292         GHook.Printf("--- WriteLeakFile ---\n");\r
293 \r
294         //\r
295         // Write the points to the file\r
296         //\r
297         sprintf (FileName2, "%s.Pnt", FileName);\r
298         PntFile = fopen (FileName2, "wb");\r
299 \r
300         if (!PntFile)\r
301                 GHook.Error ("WriteLeakFile:  Couldn't open %s\n", FileName);\r
302 \r
303         Count = 0;\r
304 \r
305         strcpy(TAG, "LEAK");\r
306         fwrite(TAG, sizeof(char), 4, PntFile);\r
307 \r
308         Pos1 = ftell(PntFile);\r
309 \r
310         fwrite(&Count, sizeof(int32), 1, PntFile);\r
311         \r
312         Node = Start;\r
313 \r
314         fwrite(&Entities[EntityHit].Origin, sizeof(geVec3d), 1, PntFile);\r
315         Count++;\r
316 \r
317         Stop = GE_FALSE;\r
318 \r
319         while (Node && Node->Occupied > 1)\r
320         {\r
321                 int32           Next;\r
322                 GBSP_Portal     *p, *NextPortal;\r
323                 GBSP_Node       *NextNode;\r
324                 int32           s;\r
325 \r
326                 // find the best portal exit\r
327                 Next = Node->Occupied;\r
328                 NextNode = NULL;\r
329                 NextPortal = NULL;\r
330 \r
331                 GHook.Printf("Occupied   : %5i\n", Node->Occupied);\r
332 \r
333                 for (p=Node->Portals ; p ; p = p->Next[!s])\r
334                 {\r
335                         s = (p->Nodes[0] == Node);\r
336 \r
337                         if (p->Nodes[s] == Outside)\r
338                         {\r
339                                 Stop = GE_TRUE;\r
340                                 break;\r
341                         }\r
342 \r
343                         if (p->Nodes[s]->Occupied && p->Nodes[s]->Occupied < Next)\r
344                         {\r
345                                 NextPortal = p;\r
346                                 NextNode = p->Nodes[s];\r
347                                 Next = NextNode->Occupied;\r
348                         }\r
349                 }\r
350 \r
351                 Node = NextNode;\r
352                 \r
353                 if (Stop)\r
354                         break;\r
355 \r
356                 if (NextPortal && Node && Node != Outside)\r
357                 {\r
358                         // Write out the center of the portal\r
359                         PolyCenter(NextPortal->Poly, &Mid);\r
360                         fwrite(&Mid, sizeof(geVec3d), 1, PntFile);\r
361                         Count++;\r
362                         // Then writer out the center of the leaf it goes too\r
363                         LeafCenter(Node, &Mid);\r
364                         fwrite(&Mid, sizeof(geVec3d), 1, PntFile);\r
365                         Count++;\r
366                 }\r
367         }\r
368 \r
369         GHook.Printf("Num Points    : %5i\n", Count);\r
370 \r
371         // HACK!!!!\r
372         Pos2 = ftell(PntFile);\r
373 \r
374         GHook.Printf("Pos1 = %5i\n", Pos1);\r
375         GHook.Printf("Pos2 = %5i\n", Pos2);\r
376 \r
377         fseek(PntFile, Pos1, SEEK_SET);\r
378         //Count-=2;\r
379         fwrite(&Count, sizeof(int32), 1, PntFile);\r
380 \r
381         fseek(PntFile, Pos2, SEEK_SET);\r
382 \r
383         fclose (PntFile);\r
384 \r
385         return GE_TRUE;\r
386 }\r
387 \r
388 //=====================================================================================\r
389 //      RemoveHiddenLeafs\r
390 //=====================================================================================\r
391 int32 RemoveHiddenLeafs(GBSP_Node *RootNode, GBSP_Node *ONode)\r
392 {\r
393         int32   Side;\r
394 \r
395         GHook.Printf(" --- Remove Hidden Leafs --- \n");\r
396 \r
397         OutsideNode = ONode;\r
398         \r
399         Side = OutsideNode->Portals->Nodes[0] == OutsideNode;\r
400 \r
401         NumRemovedLeafs = 0;\r
402 \r
403         if (!PlaceEntities(RootNode))\r
404                 return -1;\r
405 \r
406         HitEntity = GE_FALSE;\r
407         HitNode = NULL;\r
408 \r
409         CurrentFill = 1;\r
410         if (!FillLeafs_r(OutsideNode->Portals->Nodes[Side], GE_FALSE, 1))\r
411                 return -1;\r
412 \r
413         if (HitEntity)\r
414         {\r
415                 GHook.Printf("*****************************************\n");\r
416                 GHook.Printf("*           *** LEAK ***                *\n");\r
417                 GHook.Printf("* Level is NOT sealed.                  *\n");\r
418                 GHook.Printf("* Optimal removal will not be performed.*\n");\r
419                 GHook.Printf("*****************************************\n");\r
420 \r
421                 WriteLeakFile("Test", HitNode, ONode);\r
422                 return -1;\r
423         }\r
424 \r
425         CurrentFill = 2;\r
426         \r
427         if (!FillFromEntities(RootNode))\r
428                 return -1;\r
429         \r
430         FillUnTouchedLeafs_r(RootNode);\r
431 \r
432         if (Verbose)\r
433                 GHook.Printf("Removed Leafs          : %5i\n", NumRemovedLeafs);\r
434 \r
435         return NumRemovedLeafs;\r
436 }\r