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