GBSPLib/BSP.CPP

   1 /****************************************************************************************/\r
   2 /*  BSP.cpp                                                                             */\r
   3 /*                                                                                      */\r
   4 /*  Author: John Pollard                                                                */\r
   5 /*  Description: Module distributes code to all the other modules                       */\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 #include <Math.h>\r
  25 \r
  26 #include "GBSPPrep.h"\r
  27 #include "BSP.h"\r
  28 #include "Map.h"\r
  29 #include "Poly.h"\r
  30 #include "Portals.h"\r
  31 #include "Brush2.h"\r
  32 #include "Vis.h"\r
  33 #include "Leaf.h"\r
  34 #include "Fill.h"\r
  35 #include "Utils.h"\r
  36 #include "Light.h"\r
  37 #include "GBSPFile.h"\r
  38 \r
  39 #include "Ram.h"\r
  40 \r
  41 // Globals\r
  42 GBSP_Model      BSPModels[MAX_BSP_MODELS];\r
  43 int32           NumBSPModels;\r
  44 \r
  45 geBoolean       Verbose = GE_TRUE;\r
  46 geBoolean       OriginalVerbose;\r
  47 geBoolean       EntityVerbose = GE_FALSE;\r
  48 \r
  49 //\r
  50 // BSP2.cpp defs\r
  51 //\r
  52 geBoolean       ProcessEntities(void);                          \r
  53 void            FreeBSP_r(GBSP_Node *Node);     \r
  54 \r
  55 //=======================================================================================\r
  56 //      InsertModelNumbers\r
  57 //=======================================================================================\r
  58 geBoolean InsertModelNumbers(void)\r
  59 {\r
  60         int32   i, NumModels;\r
  61         char    ModelNum[128];\r
  62 \r
  63         NumModels = 0;\r
  64 \r
  65         for (i=0; i< NumEntities; i++)\r
  66         {\r
  67                 if (CancelRequest)\r
  68                         return GE_FALSE;\r
  69                 \r
  70                 if (!Entities[i].Brushes2)              // No model if no brushes\r
  71                         continue;\r
  72                 \r
  73                 Entities[i].ModelNum = NumModels;\r
  74 \r
  75                 if (i != 0)\r
  76                 {\r
  77                         sprintf(ModelNum, "%i", NumModels);\r
  78                         SetKeyValue(&Entities[i], "Model", ModelNum);\r
  79                 }\r
  80                 NumModels++;\r
  81         }\r
  82         return GE_TRUE;\r
  83 }\r
  84 \r
  85 //========================================================================================\r
  86 //      CreateBSP\r
  87 //========================================================================================\r
  88 geBoolean CreateBSP(char *FileName, BspParms *Parms)\r
  89 {\r
  90         OriginalVerbose = Verbose = Parms->Verbose;\r
  91         EntityVerbose = Parms->EntityVerbose;\r
  92                 \r
  93         gCountVerts = GE_TRUE;\r
  94 \r
  95         NumLeafSides = 0;\r
  96         NumLeafClusters = 0;\r
  97         NumLeafBevels = 0;\r
  98         NumPlanes = 0;\r
  99 \r
 100         if (!LoadBrushFile(FileName))\r
 101         {\r
 102                 FreeAllEntities();\r
 103                 return GE_FALSE;\r
 104         }\r
 105         \r
 106         InsertModelNumbers();\r
 107 \r
 108         BeginGBSPModels();\r
 109         \r
 110         if (!ProcessEntities())\r
 111         {\r
 112                 FreeAllGBSPData();\r
 113                 FreeAllEntities();\r
 114                 return GE_FALSE;\r
 115         }\r
 116 \r
 117         return GE_TRUE;\r
 118 }\r
 119 \r
 120 //========================================================================================\r
 121 //      UpdateEntities\r
 122 //      Updates the entities only...\r
 123 //========================================================================================\r
 124 geBoolean UpdateEntities(char *MapName, char *BSPName)\r
 125 {\r
 126         GHook.Printf("--- Update Entities --- \n");\r
 127 \r
 128         if (!LoadBrushFile(MapName))\r
 129                 goto ExitWithError;\r
 130 \r
 131         InsertModelNumbers();\r
 132 \r
 133         // Load the old .BSP\r
 134         if (!LoadGBSPFile(BSPName))\r
 135         {\r
 136                 GHook.Error("UpdateEntities:  Could not load .bsp file.\n");\r
 137                 goto ExitWithError;\r
 138         }\r
 139 \r
 140         // Destroy any old GFXEntData in the .BSP file\r
 141         if (GFXEntData)\r
 142         {\r
 143                 geRam_Free(GFXEntData);\r
 144                 GFXEntData = NULL;\r
 145         }\r
 146         NumGFXEntData = 0;\r
 147 \r
 148         if (!ConvertEntitiesToGFXEntData())\r
 149         {\r
 150                 GHook.Error("UpdateEntities:  ConvertEntitiesToGFXEntData failed.\n");\r
 151                 return GE_FALSE;\r
 152         }\r
 153 \r
 154         // Save it!!!\r
 155         if (!SaveGBSPFile(BSPName))\r
 156         {\r
 157                 GHook.Error("UpdateEntities:  SaveGBSPFile failed.\n");\r
 158                 goto ExitWithError;\r
 159         }\r
 160 \r
 161         FreeAllEntities();                                      // Free any entities that might be left behind\r
 162         FreeGBSPFile();                                         // Free any GFX BSP data left over\r
 163         return GE_TRUE;\r
 164         \r
 165         ExitWithError:\r
 166                 FreeAllEntities();                              // Free any entities that might be left behind\r
 167                 FreeGBSPFile();                                 // Free any GFX BSP data left over\r
 168                 return GE_FALSE;\r
 169 }\r
 170 \r
 171 //========================================================================================\r
 172 //      AllocNode\r
 173 //========================================================================================\r
 174 GBSP_Node *AllocNode(void)\r
 175 {\r
 176         GBSP_Node       *Node;\r
 177 \r
 178         Node = GE_RAM_ALLOCATE_STRUCT(GBSP_Node);\r
 179 \r
 180         if (Node == NULL)\r
 181         {\r
 182                 GHook.Error("AllocNode:  Out of memory!\n");\r
 183                 return NULL;\r
 184         }\r
 185 \r
 186         memset(Node, 0, sizeof(GBSP_Node));\r
 187 \r
 188         return Node;\r
 189 }\r
 190 \r
 191 //========================================================================================\r
 192 //      FreeNode\r
 193 //========================================================================================\r
 194 void FreeNode(GBSP_Node *Node)\r
 195 {\r
 196         GBSP_Face       *Face, *Next;\r
 197         GBSP_Brush      *Brush, *NextB;\r
 198 \r
 199         if (Node->LeafFaces)\r
 200                 geRam_Free(Node->LeafFaces);\r
 201 \r
 202         for (Face = Node->Faces; Face; Face = Next)\r
 203         {\r
 204                 Next = Face->Next;\r
 205                 FreeFace(Face);\r
 206         }\r
 207 \r
 208         for (Brush = Node->BrushList; Brush; Brush = NextB)\r
 209         {\r
 210                 NextB = Brush->Next;\r
 211 \r
 212                 FreeBrush(Brush);\r
 213         }\r
 214 \r
 215         geRam_Free(Node);\r
 216 }\r
 217 \r
 218 //========================================================================================\r
 219 //      FreeAllGBSPData\r
 220 //========================================================================================\r
 221 geBoolean FreeAllGBSPData(void)\r
 222 {\r
 223         int32   i;\r
 224 \r
 225         for (i=0; i< NumBSPModels; i++)\r
 226         {\r
 227                 if (!FreePortals(BSPModels[i].RootNode[0]))\r
 228                 {\r
 229                         GHook.Error("FreeAllGBSPData:  Could not free portals.\n");\r
 230                         return GE_FALSE;\r
 231                 }\r
 232                 FreeBSP_r(BSPModels[i].RootNode[0]);\r
 233                 \r
 234                 memset(&BSPModels[i], 0, sizeof(GBSP_Model));\r
 235         }\r
 236 \r
 237         return GE_TRUE;\r
 238 }\r
 239 \r
 240 //========================================================================================\r
 241 //      CleanupGBSP\r
 242 //========================================================================================\r
 243 void CleanupGBSP(void)\r
 244 {\r
 245         FreeAllGBSPData();\r
 246         FreeAllEntities();\r
 247 }\r
 248 \r
 249 //\r
 250 //      Planes\r
 251 //\r
 252 \r
 253 GBSP_Plane      Planes[MAX_BSP_PLANES];\r
 254 int32           NumPlanes = 0;\r
 255 \r
 256 //====================================================================================\r
 257 //      PlaneFromVerts\r
 258 //      Expects at least 3 verts\r
 259 //====================================================================================\r
 260 void PlaneFromVerts(geVec3d *Verts, GBSP_Plane *Plane)\r
 261 {\r
 262         geVec3d         Vect1, Vect2;\r
 263         \r
 264         geVec3d_Subtract(&Verts[0], &Verts[1], &Vect1);\r
 265         geVec3d_Subtract(&Verts[2], &Verts[1], &Vect2);\r
 266         \r
 267         geVec3d_CrossProduct(&Vect1, &Vect2, &Plane->Normal);\r
 268         geVec3d_Normalize(&Plane->Normal);\r
 269 \r
 270         Plane->Dist = geVec3d_DotProduct(&Verts[0], &Plane->Normal);\r
 271 \r
 272         Plane->Type = geVec3d_PlaneType(&Plane->Normal);\r
 273 }\r
 274 \r
 275 //====================================================================================\r
 276 //      SidePlane\r
 277 //====================================================================================\r
 278 void SidePlane(GBSP_Plane *Plane, int32 *Side)\r
 279 {\r
 280         int32           Type;\r
 281 \r
 282         *Side = 0;                                      // Default to same direction\r
 283 \r
 284         Plane->Type = geVec3d_PlaneType(&Plane->Normal);\r
 285 \r
 286         Type = Plane->Type % PLANE_ANYX;\r
 287 \r
 288         // Point the major axis in the positive direction\r
 289         if (VectorToSUB(Plane->Normal, Type) < 0)\r
 290         {\r
 291                 geVec3d_Inverse(&Plane->Normal);\r
 292                 Plane->Dist = -Plane->Dist;\r
 293                 *Side = 1;                                                                      // Flip if direction is opposite match\r
 294         }\r
 295 }\r
 296 \r
 297 #define NORMAL_EPSILON          (geFloat)0.00001\r
 298 \r
 299 //====================================================================================\r
 300 //      PlaneEqual\r
 301 //====================================================================================\r
 302 geBoolean PlaneEqual(GBSP_Plane *Plane1, GBSP_Plane *Plane2)\r
 303 {\r
 304         if (fabs(Plane1->Normal.X - Plane2->Normal.X) < NORMAL_EPSILON && \r
 305                 fabs(Plane1->Normal.Y - Plane2->Normal.Y) < NORMAL_EPSILON && \r
 306                 fabs(Plane1->Normal.Z - Plane2->Normal.Z) < NORMAL_EPSILON && \r
 307                 fabs(Plane1->Dist - Plane2->Dist) < DIST_EPSILON )\r
 308                         return GE_TRUE;\r
 309 \r
 310         return GE_FALSE;\r
 311 }\r
 312 \r
 313 //====================================================================================\r
 314 //      SnapVector\r
 315 //====================================================================================\r
 316 void SnapVector(geVec3d *Normal)\r
 317 {\r
 318         int             i;\r
 319 \r
 320         for (i=0 ; i<3 ; i++)\r
 321         {\r
 322                 if ( fabs(VectorToSUB(*Normal,i) - (geFloat)1) < ANGLE_EPSILON )\r
 323                 {\r
 324                         geVec3d_Clear(Normal);\r
 325                         VectorToSUB(*Normal,i) = (geFloat)1;\r
 326                         break;\r
 327                 }\r
 328 \r
 329                 if ( fabs(VectorToSUB(*Normal,i) - (geFloat)-1) < ANGLE_EPSILON )\r
 330                 {\r
 331                         geVec3d_Clear(Normal);\r
 332                         VectorToSUB(*Normal,i) = (geFloat)-1;\r
 333                         break;\r
 334                 }\r
 335         }\r
 336 }\r
 337 \r
 338 //====================================================================================\r
 339 //      RoundInt\r
 340 //====================================================================================\r
 341 geFloat RoundInt(geFloat In)\r
 342 {\r
 343         return (geFloat)floor(In + (geFloat)0.5);\r
 344 }\r
 345 \r
 346 //====================================================================================\r
 347 //      SnapPlane\r
 348 //====================================================================================\r
 349 void SnapPlane(geVec3d *Normal, geFloat *Dist)\r
 350 {\r
 351         SnapVector (Normal);\r
 352 \r
 353         if (fabs(*Dist-RoundInt(*Dist)) < DIST_EPSILON)\r
 354                 *Dist = RoundInt(*Dist);\r
 355 }\r
 356 \r
 357 \r
 358 //=======================================================================================\r
 359 //      PlaneInverse\r
 360 //=======================================================================================\r
 361 void PlaneInverse(GBSP_Plane *Plane)\r
 362 {\r
 363         geVec3d_Inverse(&Plane->Normal);\r
 364         Plane->Dist = -Plane->Dist;\r
 365 \r
 366 }\r
 367 \r
 368 //====================================================================================\r
 369 //      FindPlane\r
 370 //====================================================================================\r
 371 int32 FindPlane(GBSP_Plane *Plane, int32 *Side)\r
 372 {\r
 373         GBSP_Plane      Plane1;\r
 374         GBSP_Plane      *Plane2;\r
 375         //geFloat               Dot;\r
 376         int32           i;\r
 377 \r
 378         SnapPlane(&Plane->Normal, &Plane->Dist);\r
 379 \r
 380         Plane1 = *Plane;\r
 381 \r
 382         SidePlane(&Plane1, Side);               // Find axis, and flip if necessary, to make major axis positive\r
 383 \r
 384         Plane2 = Planes;        \r
 385 \r
 386         for (i=0; i< NumPlanes; i++)    // Try to return a plane allready in the list\r
 387         {\r
 388                 if (PlaneEqual(&Plane1, Plane2))\r
 389                         return i;\r
 390 \r
 391                 Plane2++;\r
 392         }\r
 393 \r
 394         if (NumPlanes >= MAX_BSP_PLANES)\r
 395         {\r
 396                 GHook.Error("Max BSP Planes.\n");\r
 397                 return -1;\r
 398         }\r
 399         \r
 400         Planes[NumPlanes++] = Plane1;\r
 401 \r
 402         return i;\r
 403 }\r
 404 \r
 405 //=======================================================================================\r
 406 //=======================================================================================\r
 407 geFloat _fastcall Plane_PointDistanceFast(GBSP_Plane *Plane, geVec3d *Point)\r
 408 {\r
 409    geFloat      Dist,Dist2;\r
 410 \r
 411    Dist2 = Plane->Dist;\r
 412 \r
 413    switch (Plane->Type)\r
 414    {\r
 415            \r
 416            case PLANE_X:\r
 417            Dist = (Point->X - Dist2);\r
 418            break;\r
 419            case PLANE_Y:\r
 420            Dist = (Point->Y - Dist2);\r
 421            break;\r
 422            case PLANE_Z:\r
 423            Dist = (Point->Z - Dist2);\r
 424            break;\r
 425               \r
 426        default:\r
 427            Dist = geVec3d_DotProduct(Point, &Plane->Normal) - Dist2;\r
 428            break;\r
 429     }\r
 430 \r
 431     return Dist;\r
 432 }\r