tools/quake3/q3map2/facebsp.c

   1 /* -------------------------------------------------------------------------------
   2
   3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4    For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6    This file is part of GtkRadiant.
   7
   8    GtkRadiant is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    GtkRadiant is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GtkRadiant; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22    ----------------------------------------------------------------------------------
  23
  24    This code has been altered significantly from its original form, to support
  25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27    ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define FACEBSP_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41 int c_faceLeafs;
  42
  43
  44 /*
  45    ================
  46    AllocBspFace
  47    ================
  48  */
  49 face_t  *AllocBspFace( void ) {
  50         face_t  *f;
  51
  52         f = safe_malloc( sizeof( *f ) );
  53         memset( f, 0, sizeof( *f ) );
  54
  55         return f;
  56 }
  57
  58
  59
  60 /*
  61    ================
  62    FreeBspFace
  63    ================
  64  */
  65 void    FreeBspFace( face_t *f ) {
  66         if ( f->w ) {
  67                 FreeWinding( f->w );
  68         }
  69         free( f );
  70 }
  71
  72
  73
  74 /*
  75    SelectSplitPlaneNum()
  76    finds the best split plane for this node
  77  */
  78
  79 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ){
  80         face_t      *split;
  81         face_t      *check;
  82         face_t      *bestSplit;
  83         int splits, facing, front, back;
  84         int side;
  85         plane_t     *plane;
  86         int value, bestValue;
  87         int i;
  88         vec3_t normal;
  89         float dist;
  90         int planenum;
  91         float sizeBias;
  92
  93         //int frontC,backC,splitsC,facingC;
  94
  95
  96         /* ydnar: set some defaults */
  97         *splitPlaneNum = -1; /* leaf */
  98         *compileFlags = 0;
  99
 100         /* ydnar 2002-06-24: changed this to split on z-axis as well */
 101         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
 102
 103         /* if it is crossing a block boundary, force a split */
 104         for ( i = 0; i < 3; i++ )
 105         {
 106                 if ( blockSize[ i ] <= 0 ) {
 107                         continue;
 108                 }
 109                 dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
 110                 if ( node->maxs[ i ] > dist ) {
 111                         VectorClear( normal );
 112                         normal[ i ] = 1;
 113                         planenum = FindFloatPlane( normal, dist, 0, NULL );
 114                         *splitPlaneNum = planenum;
 115                         return;
 116                 }
 117         }
 118
 119         /* pick one of the face planes */
 120         bestValue = -99999;
 121         bestSplit = list;
 122
 123
 124         // div0: this check causes detail/structural mixes
 125         //for( split = list; split; split = split->next )
 126         //      split->checked = qfalse;
 127
 128         for ( split = list; split; split = split->next )
 129         {
 130                 //if ( split->checked )
 131                 //      continue;
 132
 133                 plane = &mapplanes[ split->planenum ];
 134                 splits = 0;
 135                 facing = 0;
 136                 front = 0;
 137                 back = 0;
 138                 for ( check = list ; check ; check = check->next ) {
 139                         if ( check->planenum == split->planenum ) {
 140                                 facing++;
 141                                 //check->checked = qtrue;       // won't need to test this plane again
 142                                 continue;
 143                         }
 144                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
 145                         if ( side == SIDE_CROSS ) {
 146                                 splits++;
 147                         }
 148                         else if ( side == SIDE_FRONT ) {
 149                                 front++;
 150                         }
 151                         else if ( side == SIDE_BACK ) {
 152                                 back++;
 153                         }
 154                 }
 155
 156                 if ( bspAlternateSplitWeights ) {
 157                         // from 27
 158
 159                         //Bigger is better
 160                         sizeBias = WindingArea( split->w );
 161
 162                         //Base score = 20000 perfectly balanced
 163                         value = 20000 - ( abs( front - back ) );
 164                         value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again
 165                         value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
 166                         value -= splits * 5;        //more splits = bad
 167                         value +=  sizeBias * 10; //We want a huge score bias based on plane size
 168                 }
 169                 else
 170                 {
 171                         value =  5 * facing - 5 * splits; // - abs(front-back);
 172                         if ( plane->type < 3 ) {
 173                                 value += 5;       // axial is better
 174                         }
 175                 }
 176
 177                 value += split->priority;       // prioritize hints higher
 178
 179                 if ( value > bestValue ) {
 180                         bestValue = value;
 181                         bestSplit = split;
 182                         //frontC=front;
 183                         //backC=back;
 184                         //splitsC=splits;
 185                         //facingC=facing;
 186                 }
 187         }
 188
 189         /* nothing, we have a leaf */
 190         if ( bestValue == -99999 ) {
 191                 return;
 192         }
 193
 194         //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
 195
 196         /* set best split data */
 197         *splitPlaneNum = bestSplit->planenum;
 198         *compileFlags = bestSplit->compileFlags;
 199
 200 #if 0
 201         if ( bestSplit->compileFlags & C_DETAIL ) {
 202                 for ( split = list; split; split = split->next )
 203                         if ( !( split->compileFlags & C_DETAIL ) ) {
 204                                 Sys_FPrintf( SYS_ERR, "DON'T DO SUCH SPLITS (1)\n" );
 205                         }
 206         }
 207         if ( ( node->compileFlags & C_DETAIL ) && !( bestSplit->compileFlags & C_DETAIL ) ) {
 208                 Sys_FPrintf( SYS_ERR, "DON'T DO SUCH SPLITS (2)\n" );
 209         }
 210 #endif
 211
 212         if ( *splitPlaneNum > -1 ) {
 213                 mapplanes[ *splitPlaneNum ].counter++;
 214         }
 215 }
 216
 217
 218
 219 /*
 220    CountFaceList()
 221    counts bsp faces in the linked list
 222  */
 223
 224 int CountFaceList( face_t *list ){
 225         int c;
 226
 227
 228         c = 0;
 229         for ( ; list != NULL; list = list->next )
 230                 c++;
 231         return c;
 232 }
 233
 234
 235
 236 /*
 237    BuildFaceTree_r()
 238    recursively builds the bsp, splitting on face planes
 239  */
 240
 241 void BuildFaceTree_r( node_t *node, face_t *list ){
 242         face_t      *split;
 243         face_t      *next;
 244         int side;
 245         plane_t     *plane;
 246         face_t      *newFace;
 247         face_t      *childLists[2];
 248         winding_t   *frontWinding, *backWinding;
 249         int i;
 250         int splitPlaneNum, compileFlags;
 251 #if 0
 252         qboolean isstruct = qfalse;
 253 #endif
 254
 255
 256         /* count faces left */
 257         i = CountFaceList( list );
 258
 259         /* select the best split plane */
 260         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
 261
 262         /* if we don't have any more faces, this is a node */
 263         if ( splitPlaneNum == -1 ) {
 264                 node->planenum = PLANENUM_LEAF;
 265                 node->has_structural_children = qfalse;
 266                 c_faceLeafs++;
 267                 return;
 268         }
 269
 270         /* partition the list */
 271         node->planenum = splitPlaneNum;
 272         node->compileFlags = compileFlags;
 273         node->has_structural_children = !( compileFlags & C_DETAIL ) && !node->opaque;
 274         plane = &mapplanes[ splitPlaneNum ];
 275         childLists[0] = NULL;
 276         childLists[1] = NULL;
 277
 278         for ( split = list; split; split = next )
 279         {
 280                 /* set next */
 281                 next = split->next;
 282
 283                 /* don't split by identical plane */
 284                 if ( split->planenum == node->planenum ) {
 285                         FreeBspFace( split );
 286                         continue;
 287                 }
 288
 289 #if 0
 290                 if ( !( split->compileFlags & C_DETAIL ) ) {
 291                         isstruct = 1;
 292                 }
 293 #endif
 294
 295                 /* determine which side the face falls on */
 296                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
 297
 298                 /* switch on side */
 299                 if ( side == SIDE_CROSS ) {
 300                         ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
 301                                                                           &frontWinding, &backWinding ); /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
 302                         if ( frontWinding ) {
 303                                 newFace = AllocBspFace();
 304                                 newFace->w = frontWinding;
 305                                 newFace->next = childLists[0];
 306                                 newFace->planenum = split->planenum;
 307                                 newFace->priority = split->priority;
 308                                 newFace->compileFlags = split->compileFlags;
 309                                 childLists[0] = newFace;
 310                         }
 311                         if ( backWinding ) {
 312                                 newFace = AllocBspFace();
 313                                 newFace->w = backWinding;
 314                                 newFace->next = childLists[1];
 315                                 newFace->planenum = split->planenum;
 316                                 newFace->priority = split->priority;
 317                                 newFace->compileFlags = split->compileFlags;
 318                                 childLists[1] = newFace;
 319                         }
 320                         FreeBspFace( split );
 321                 }
 322                 else if ( side == SIDE_FRONT ) {
 323                         split->next = childLists[0];
 324                         childLists[0] = split;
 325                 }
 326                 else if ( side == SIDE_BACK ) {
 327                         split->next = childLists[1];
 328                         childLists[1] = split;
 329                 }
 330         }
 331
 332
 333         // recursively process children
 334         for ( i = 0 ; i < 2 ; i++ ) {
 335                 node->children[i] = AllocNode();
 336                 node->children[i]->parent = node;
 337                 VectorCopy( node->mins, node->children[i]->mins );
 338                 VectorCopy( node->maxs, node->children[i]->maxs );
 339         }
 340
 341         for ( i = 0 ; i < 3 ; i++ ) {
 342                 if ( plane->normal[i] == 1 ) {
 343                         node->children[0]->mins[i] = plane->dist;
 344                         node->children[1]->maxs[i] = plane->dist;
 345                         break;
 346                 }
 347                 if ( plane->normal[i] == -1 ) {
 348                         node->children[0]->maxs[i] = -plane->dist;
 349                         node->children[1]->mins[i] = -plane->dist;
 350                         break;
 351                 }
 352         }
 353
 354 #if 0
 355         if ( ( node->compileFlags & C_DETAIL ) && isstruct ) {
 356                 Sys_FPrintf( SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children );
 357         }
 358 #endif
 359
 360         for ( i = 0 ; i < 2 ; i++ ) {
 361                 BuildFaceTree_r( node->children[i], childLists[i] );
 362                 node->has_structural_children |= node->children[i]->has_structural_children;
 363         }
 364
 365 #if 0
 366         if ( ( node->compileFlags & C_DETAIL ) && !( node->children[0]->compileFlags & C_DETAIL ) && node->children[0]->planenum != PLANENUM_LEAF ) {
 367                 Sys_FPrintf( SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children );
 368         }
 369         if ( ( node->compileFlags & C_DETAIL ) && isstruct ) {
 370                 Sys_FPrintf( SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children );
 371         }
 372 #endif
 373 }
 374
 375
 376 /*
 377    ================
 378    FaceBSP
 379
 380    List will be freed before returning
 381    ================
 382  */
 383 tree_t *FaceBSP( face_t *list ) {
 384         tree_t      *tree;
 385         face_t  *face;
 386         int i;
 387         int count;
 388
 389         Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
 390
 391         tree = AllocTree();
 392
 393         count = 0;
 394         for ( face = list; face != NULL; face = face->next )
 395         {
 396                 count++;
 397                 for ( i = 0; i < face->w->numpoints; i++ )
 398                 {
 399                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
 400                 }
 401         }
 402         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
 403
 404         for ( i = 0; i < nummapplanes; i++ )
 405         {
 406                 mapplanes[ i ].counter = 0;
 407         }
 408
 409         tree->headnode = AllocNode();
 410         VectorCopy( tree->mins, tree->headnode->mins );
 411         VectorCopy( tree->maxs, tree->headnode->maxs );
 412         c_faceLeafs = 0;
 413
 414         BuildFaceTree_r( tree->headnode, list );
 415
 416         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
 417
 418         return tree;
 419 }
 420
 421
 422
 423 /*
 424    MakeStructuralBSPFaceList()
 425    get structural brush faces
 426  */
 427
 428 face_t *MakeStructuralBSPFaceList( brush_t *list ){
 429         brush_t     *b;
 430         int i;
 431         side_t      *s;
 432         winding_t   *w;
 433         face_t      *f, *flist;
 434
 435
 436         flist = NULL;
 437         for ( b = list; b != NULL; b = b->next )
 438         {
 439                 if ( !deepBSP && b->detail ) {
 440                         continue;
 441                 }
 442
 443                 for ( i = 0; i < b->numsides; i++ )
 444                 {
 445                         /* get side and winding */
 446                         s = &b->sides[ i ];
 447                         w = s->winding;
 448                         if ( w == NULL ) {
 449                                 continue;
 450                         }
 451
 452                         /* ydnar: skip certain faces */
 453                         if ( s->compileFlags & C_SKIP ) {
 454                                 continue;
 455                         }
 456
 457                         /* allocate a face */
 458                         f = AllocBspFace();
 459                         f->w = CopyWinding( w );
 460                         f->planenum = s->planenum & ~1;
 461                         f->compileFlags = s->compileFlags;  /* ydnar */
 462                         if ( b->detail ) {
 463                                 f->compileFlags |= C_DETAIL;
 464                         }
 465
 466                         /* ydnar: set priority */
 467                         f->priority = 0;
 468                         if ( f->compileFlags & C_HINT ) {
 469                                 f->priority += HINT_PRIORITY;
 470                         }
 471                         if ( f->compileFlags & C_ANTIPORTAL ) {
 472                                 f->priority += ANTIPORTAL_PRIORITY;
 473                         }
 474                         if ( f->compileFlags & C_AREAPORTAL ) {
 475                                 f->priority += AREAPORTAL_PRIORITY;
 476                         }
 477                         if ( f->compileFlags & C_DETAIL ) {
 478                                 f->priority += DETAIL_PRIORITY;
 479                         }
 480
 481                         /* get next face */
 482                         f->next = flist;
 483                         flist = f;
 484                 }
 485         }
 486
 487         return flist;
 488 }
 489
 490
 491
 492 /*
 493    MakeVisibleBSPFaceList()
 494    get visible brush faces
 495  */
 496
 497 face_t *MakeVisibleBSPFaceList( brush_t *list ){
 498         brush_t     *b;
 499         int i;
 500         side_t      *s;
 501         winding_t   *w;
 502         face_t      *f, *flist;
 503
 504
 505         flist = NULL;
 506         for ( b = list; b != NULL; b = b->next )
 507         {
 508                 if ( !deepBSP && b->detail ) {
 509                         continue;
 510                 }
 511
 512                 for ( i = 0; i < b->numsides; i++ )
 513                 {
 514                         /* get side and winding */
 515                         s = &b->sides[ i ];
 516                         w = s->visibleHull;
 517                         if ( w == NULL ) {
 518                                 continue;
 519                         }
 520
 521                         /* ydnar: skip certain faces */
 522                         if ( s->compileFlags & C_SKIP ) {
 523                                 continue;
 524                         }
 525
 526                         /* allocate a face */
 527                         f = AllocBspFace();
 528                         f->w = CopyWinding( w );
 529                         f->planenum = s->planenum & ~1;
 530                         f->compileFlags = s->compileFlags;  /* ydnar */
 531                         if ( b->detail ) {
 532                                 f->compileFlags |= C_DETAIL;
 533                         }
 534
 535                         /* ydnar: set priority */
 536                         f->priority = 0;
 537                         if ( f->compileFlags & C_HINT ) {
 538                                 f->priority += HINT_PRIORITY;
 539                         }
 540                         if ( f->compileFlags & C_ANTIPORTAL ) {
 541                                 f->priority += ANTIPORTAL_PRIORITY;
 542                         }
 543                         if ( f->compileFlags & C_AREAPORTAL ) {
 544                                 f->priority += AREAPORTAL_PRIORITY;
 545                         }
 546                         if ( f->compileFlags & C_DETAIL ) {
 547                                 f->priority += DETAIL_PRIORITY;
 548                         }
 549
 550                         /* get next face */
 551                         f->next = flist;
 552                         flist = f;
 553                 }
 554         }
 555
 556         return flist;
 557 }