neo/tools/compilers/dmap/facebsp.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../../../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "dmap.h"
  33
  34 int                     c_faceLeafs;
  35
  36
  37 extern  int     c_nodes;
  38
  39 void RemovePortalFromNode( uPortal_t *portal, node_t *l );
  40
  41 node_t *NodeForPoint( node_t *node, idVec3 origin ) {
  42         float   d;
  43
  44         while( node->planenum != PLANENUM_LEAF ) {
  45                 idPlane &plane = dmapGlobals.mapPlanes[node->planenum];
  46                 d = plane.Distance( origin );
  47                 if ( d >= 0 ) {
  48                         node = node->children[0];
  49                 } else {
  50                         node = node->children[1];
  51                 }
  52         }
  53
  54         return node;
  55 }
  56
  57
  58
  59 /*
  60 =============
  61 FreeTreePortals_r
  62 =============
  63 */
  64 void FreeTreePortals_r (node_t *node)
  65 {
  66         uPortal_t       *p, *nextp;
  67         int                     s;
  68
  69         // free children
  70         if (node->planenum != PLANENUM_LEAF)
  71         {
  72                 FreeTreePortals_r (node->children[0]);
  73                 FreeTreePortals_r (node->children[1]);
  74         }
  75
  76         // free portals
  77         for (p=node->portals ; p ; p=nextp)
  78         {
  79                 s = (p->nodes[1] == node);
  80                 nextp = p->next[s];
  81
  82                 RemovePortalFromNode (p, p->nodes[!s]);
  83                 FreePortal (p);
  84         }
  85         node->portals = NULL;
  86 }
  87
  88 /*
  89 =============
  90 FreeTree_r
  91 =============
  92 */
  93 void FreeTree_r (node_t *node)
  94 {
  95         // free children
  96         if (node->planenum != PLANENUM_LEAF)
  97         {
  98                 FreeTree_r (node->children[0]);
  99                 FreeTree_r (node->children[1]);
 100         }
 101
 102         // free brushes
 103         FreeBrushList (node->brushlist);
 104
 105         // free the node
 106         c_nodes--;
 107         Mem_Free (node);
 108 }
 109
 110
 111 /*
 112 =============
 113 FreeTree
 114 =============
 115 */
 116 void FreeTree( tree_t *tree ) {
 117         if ( !tree ) {
 118                 return;
 119         }
 120         FreeTreePortals_r (tree->headnode);
 121         FreeTree_r (tree->headnode);
 122         Mem_Free (tree);
 123 }
 124
 125 //===============================================================
 126
 127 void PrintTree_r (node_t *node, int depth)
 128 {
 129         int                     i;
 130         uBrush_t        *bb;
 131
 132         for (i=0 ; i<depth ; i++)
 133                 common->Printf("  ");
 134         if (node->planenum == PLANENUM_LEAF)
 135         {
 136                 if (!node->brushlist)
 137                         common->Printf("NULL\n");
 138                 else
 139                 {
 140                         for (bb=node->brushlist ; bb ; bb=bb->next)
 141                                 common->Printf("%i ", bb->original->brushnum);
 142                         common->Printf("\n");
 143                 }
 144                 return;
 145         }
 146
 147         idPlane &plane = dmapGlobals.mapPlanes[node->planenum];
 148         common->Printf( "#%i (%5.2f %5.2f %5.2f %5.2f)\n", node->planenum,
 149                                         plane[0], plane[1], plane[2], plane[3] );
 150         PrintTree_r( node->children[0], depth+1 );
 151         PrintTree_r( node->children[1], depth+1 );
 152 }
 153
 154 /*
 155 ================
 156 AllocBspFace
 157 ================
 158 */
 159 bspface_t       *AllocBspFace( void ) {
 160         bspface_t       *f;
 161
 162         f = (bspface_t *)Mem_Alloc(sizeof(*f));
 163         memset( f, 0, sizeof(*f) );
 164
 165         return f;
 166 }
 167
 168 /*
 169 ================
 170 FreeBspFace
 171 ================
 172 */
 173 void    FreeBspFace( bspface_t *f ) {
 174         if ( f->w ) {
 175                 delete f->w;
 176         }
 177         Mem_Free( f );
 178 }
 179
 180
 181 /*
 182 ================
 183 SelectSplitPlaneNum
 184 ================
 185 */
 186 #define BLOCK_SIZE      1024
 187 int SelectSplitPlaneNum( node_t *node, bspface_t *list ) {
 188         bspface_t       *split;
 189         bspface_t       *check;
 190         bspface_t       *bestSplit;
 191         int                     splits, facing, front, back;
 192         int                     side;
 193         idPlane         *mapPlane;
 194         int                     value, bestValue;
 195         idPlane         plane;
 196         int                     planenum;
 197         bool    havePortals;
 198         float           dist;
 199         idVec3          halfSize;
 200
 201         // if it is crossing a 1k block boundary, force a split
 202         // this prevents epsilon problems from extending an
 203         // arbitrary distance across the map
 204
 205         halfSize = ( node->bounds[1] - node->bounds[0] ) * 0.5f;
 206         for ( int axis = 0; axis < 3; axis++ ) {
 207                 if ( halfSize[axis] > BLOCK_SIZE ) {
 208                         dist = BLOCK_SIZE * ( floor( ( node->bounds[0][axis] + halfSize[axis] ) / BLOCK_SIZE ) + 1.0f );
 209                 } else {
 210                         dist = BLOCK_SIZE * ( floor( node->bounds[0][axis] / BLOCK_SIZE ) + 1.0f );
 211                 }
 212                 if ( dist > node->bounds[0][axis] + 1.0f && dist < node->bounds[1][axis] - 1.0f ) {
 213                         plane[0] = plane[1] = plane[2] = 0.0f;
 214                         plane[axis] = 1.0f;
 215                         plane[3] = -dist;
 216                         planenum = FindFloatPlane( plane );
 217                         return planenum;
 218                 }
 219         }
 220
 221         // pick one of the face planes
 222         // if we have any portal faces at all, only
 223         // select from them, otherwise select from
 224         // all faces
 225         bestValue = -999999;
 226         bestSplit = list;
 227
 228         havePortals = false;
 229         for ( split = list ; split ; split = split->next ) {
 230                 split->checked = false;
 231                 if ( split->portal ) {
 232                         havePortals = true;
 233                 }
 234         }
 235
 236         for ( split = list ; split ; split = split->next ) {
 237                 if ( split->checked ) {
 238                         continue;
 239                 }
 240                 if ( havePortals != split->portal ) {
 241                         continue;
 242                 }
 243                 mapPlane = &dmapGlobals.mapPlanes[ split->planenum ];
 244                 splits = 0;
 245                 facing = 0;
 246                 front = 0;
 247                 back = 0;
 248                 for ( check = list ; check ; check = check->next ) {
 249                         if ( check->planenum == split->planenum ) {
 250                                 facing++;
 251                                 check->checked = true;  // won't need to test this plane again
 252                                 continue;
 253                         }
 254                         side = check->w->PlaneSide( *mapPlane );
 255                         if ( side == SIDE_CROSS ) {
 256                                 splits++;
 257                         } else if ( side == SIDE_FRONT ) {
 258                                 front++;
 259                         } else if ( side == SIDE_BACK ) {
 260                                 back++;
 261                         }
 262                 }
 263                 value =  5*facing - 5*splits; // - abs(front-back);
 264                 if ( mapPlane->Type() < PLANETYPE_TRUEAXIAL ) {
 265                         value+=5;               // axial is better
 266                 }
 267
 268                 if ( value > bestValue ) {
 269                         bestValue = value;
 270                         bestSplit = split;
 271                 }
 272         }
 273
 274         if ( bestValue == -999999 ) {
 275                 return -1;
 276         }
 277
 278         return bestSplit->planenum;
 279 }
 280
 281 /*
 282 ================
 283 BuildFaceTree_r
 284 ================
 285 */
 286 void    BuildFaceTree_r( node_t *node, bspface_t *list ) {
 287         bspface_t       *split;
 288         bspface_t       *next;
 289         int                     side;
 290         bspface_t       *newFace;
 291         bspface_t       *childLists[2];
 292         idWinding       *frontWinding, *backWinding;
 293         int                     i;
 294         int                     splitPlaneNum;
 295
 296         splitPlaneNum = SelectSplitPlaneNum( node, list );
 297         // if we don't have any more faces, this is a node
 298         if ( splitPlaneNum == -1 ) {
 299                 node->planenum = PLANENUM_LEAF;
 300                 c_faceLeafs++;
 301                 return;
 302         }
 303
 304         // partition the list
 305         node->planenum = splitPlaneNum;
 306         idPlane &plane = dmapGlobals.mapPlanes[ splitPlaneNum ];
 307         childLists[0] = NULL;
 308         childLists[1] = NULL;
 309         for ( split = list ; split ; split = next ) {
 310                 next = split->next;
 311
 312                 if ( split->planenum == node->planenum ) {
 313                         FreeBspFace( split );
 314                         continue;
 315                 }
 316
 317                 side = split->w->PlaneSide( plane );
 318
 319                 if ( side == SIDE_CROSS ) {
 320                         split->w->Split( plane, CLIP_EPSILON * 2, &frontWinding, &backWinding );
 321                         if ( frontWinding ) {
 322                                 newFace = AllocBspFace();
 323                                 newFace->w = frontWinding;
 324                                 newFace->next = childLists[0];
 325                                 newFace->planenum = split->planenum;
 326                                 childLists[0] = newFace;
 327                         }
 328                         if ( backWinding ) {
 329                                 newFace = AllocBspFace();
 330                                 newFace->w = backWinding;
 331                                 newFace->next = childLists[1];
 332                                 newFace->planenum = split->planenum;
 333                                 childLists[1] = newFace;
 334                         }
 335                         FreeBspFace( split );
 336                 } else if ( side == SIDE_FRONT ) {
 337                         split->next = childLists[0];
 338                         childLists[0] = split;
 339                 } else if ( side == SIDE_BACK ) {
 340                         split->next = childLists[1];
 341                         childLists[1] = split;
 342                 }
 343         }
 344
 345
 346         // recursively process children
 347         for ( i = 0 ; i < 2 ; i++ ) {
 348                 node->children[i] = AllocNode();
 349                 node->children[i]->parent = node;
 350                 node->children[i]->bounds = node->bounds;
 351         }
 352
 353         // split the bounds if we have a nice axial plane
 354         for ( i = 0 ; i < 3 ; i++ ) {
 355                 if ( idMath::Fabs( plane[i] - 1.0 ) < 0.001 ) {
 356                         node->children[0]->bounds[0][i] = plane.Dist();
 357                         node->children[1]->bounds[1][i] = plane.Dist();
 358                         break;
 359                 }
 360         }
 361
 362         for ( i = 0 ; i < 2 ; i++ ) {
 363                 BuildFaceTree_r ( node->children[i], childLists[i]);
 364         }
 365 }
 366
 367
 368 /*
 369 ================
 370 FaceBSP
 371
 372 List will be freed before returning
 373 ================
 374 */
 375 tree_t *FaceBSP( bspface_t *list ) {
 376         tree_t          *tree;
 377         bspface_t       *face;
 378         int                     i;
 379         int                     count;
 380         int                     start, end;
 381
 382         start = Sys_Milliseconds();
 383
 384         common->Printf( "--- FaceBSP ---\n" );
 385
 386         tree = AllocTree ();
 387
 388         count = 0;
 389         tree->bounds.Clear();
 390         for ( face = list ; face ; face = face->next ) {
 391                 count++;
 392                 for ( i = 0 ; i < face->w->GetNumPoints() ; i++ ) {
 393                         tree->bounds.AddPoint( (*face->w)[i].ToVec3() );
 394                 }
 395         }
 396         common->Printf( "%5i faces\n", count );
 397
 398         tree->headnode = AllocNode();
 399         tree->headnode->bounds = tree->bounds;
 400         c_faceLeafs = 0;
 401
 402         BuildFaceTree_r ( tree->headnode, list );
 403
 404         common->Printf( "%5i leafs\n", c_faceLeafs );
 405
 406         end = Sys_Milliseconds();
 407
 408         common->Printf( "%5.1f seconds faceBsp\n", ( end - start ) / 1000.0 );
 409
 410         return tree;
 411 }
 412
 413 //==========================================================================
 414
 415 /*
 416 =================
 417 MakeStructuralBspFaceList
 418 =================
 419 */
 420 bspface_t       *MakeStructuralBspFaceList( primitive_t *list ) {
 421         uBrush_t        *b;
 422         int                     i;
 423         side_t          *s;
 424         idWinding       *w;
 425         bspface_t       *f, *flist;
 426
 427         flist = NULL;
 428         for ( ; list ; list = list->next ) {
 429                 b = list->brush;
 430                 if ( !b ) {
 431                         continue;
 432                 }
 433                 if ( !b->opaque && !( b->contents & CONTENTS_AREAPORTAL ) ) {
 434                         continue;
 435                 }
 436                 for ( i = 0 ; i < b->numsides ; i++ ) {
 437                         s = &b->sides[i];
 438                         w = s->winding;
 439                         if ( !w ) {
 440                                 continue;
 441                         }
 442                         if ( ( b->contents & CONTENTS_AREAPORTAL ) && ! ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
 443                                 continue;
 444                         }
 445                         f = AllocBspFace();
 446                         if ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) {
 447                                 f->portal = true;
 448                         }
 449                         f->w = w->Copy();
 450                         f->planenum = s->planenum & ~1;
 451                         f->next = flist;
 452                         flist = f;
 453                 }
 454         }
 455
 456         return flist;
 457 }
 458
 459 /*
 460 =================
 461 MakeVisibleBspFaceList
 462 =================
 463 */
 464 bspface_t       *MakeVisibleBspFaceList( primitive_t *list ) {
 465         uBrush_t        *b;
 466         int                     i;
 467         side_t          *s;
 468         idWinding       *w;
 469         bspface_t       *f, *flist;
 470
 471         flist = NULL;
 472         for ( ; list ; list = list->next ) {
 473                 b = list->brush;
 474                 if ( !b ) {
 475                         continue;
 476                 }
 477                 if ( !b->opaque && !( b->contents & CONTENTS_AREAPORTAL ) ) {
 478                         continue;
 479                 }
 480                 for ( i = 0 ; i < b->numsides ; i++ ) {
 481                         s = &b->sides[i];
 482                         w = s->visibleHull;
 483                         if ( !w ) {
 484                                 continue;
 485                         }
 486                         f = AllocBspFace();
 487                         if ( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) {
 488                                 f->portal = true;
 489                         }
 490                         f->w = w->Copy();
 491                         f->planenum = s->planenum & ~1;
 492                         f->next = flist;
 493                         flist = f;
 494                 }
 495         }
 496
 497         return flist;
 498 }
 499