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_malloc0( sizeof( *f ) );
  53
  54         return f;
  55 }
  56
  57
  58
  59 /*
  60    ================
  61    FreeBspFace
  62    ================
  63  */
  64 void    FreeBspFace( face_t *f ) {
  65         if ( f->w ) {
  66                 FreeWinding( f->w );
  67         }
  68         free( f );
  69 }
  70
  71
  72
  73 /*
  74    SelectSplitPlaneNum()
  75    finds the best split plane for this node
  76  */
  77
  78 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ){
  79         face_t *split;
  80         face_t *check;
  81         face_t *bestSplit;
  82         int splits, facing, front, back;
  83         int side;
  84         plane_t *plane;
  85         int value, bestValue;
  86         int i;
  87         vec3_t normal;
  88         float dist;
  89         int planenum;
  90         float sizeBias;
  91
  92         /* ydnar: set some defaults */
  93         *splitPlaneNum = -1; /* leaf */
  94         *compileFlags = 0;
  95
  96         /* ydnar 2002-06-24: changed this to split on z-axis as well */
  97         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
  98
  99         /* if it is crossing a block boundary, force a split */
 100         for ( i = 0; i < 3; i++ )
 101         {
 102                 if ( blockSize[ i ] <= 0 ) {
 103                         continue;
 104                 }
 105                 dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
 106                 if ( node->maxs[ i ] > dist ) {
 107                         VectorClear( normal );
 108                         normal[ i ] = 1;
 109                         planenum = FindFloatPlane( normal, dist, 0, NULL );
 110                         *splitPlaneNum = planenum;
 111                         return;
 112                 }
 113         }
 114
 115         /* pick one of the face planes */
 116         bestValue = -99999;
 117         bestSplit = list;
 118
 119
 120         // div0: this check causes detail/structural mixes
 121         //for( split = list; split; split = split->next )
 122         //      split->checked = qfalse;
 123
 124         for ( split = list; split; split = split->next )
 125         {
 126                 //if ( split->checked )
 127                 //      continue;
 128
 129                 plane = &mapplanes[ split->planenum ];
 130                 splits = 0;
 131                 facing = 0;
 132                 front = 0;
 133                 back = 0;
 134                 for ( check = list ; check ; check = check->next ) {
 135                         if ( check->planenum == split->planenum ) {
 136                                 facing++;
 137                                 //check->checked = qtrue;       // won't need to test this plane again
 138                                 continue;
 139                         }
 140                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
 141                         if ( side == SIDE_CROSS ) {
 142                                 splits++;
 143                         }
 144                         else if ( side == SIDE_FRONT ) {
 145                                 front++;
 146                         }
 147                         else if ( side == SIDE_BACK ) {
 148                                 back++;
 149                         }
 150                 }
 151
 152                 if ( bspAlternateSplitWeights ) {
 153                         // from 27
 154
 155                         //Bigger is better
 156                         sizeBias = WindingArea( split->w );
 157
 158                         //Base score = 20000 perfectly balanced
 159                         value = 20000 - ( abs( front - back ) );
 160                         value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again
 161                         value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
 162                         value -= splits * 5;        //more splits = bad
 163                         value +=  sizeBias * 10; //We want a huge score bias based on plane size
 164                 }
 165                 else
 166                 {
 167                         value =  5 * facing - 5 * splits; // - abs(front-back);
 168                         if ( plane->type < 3 ) {
 169                                 value += 5;       // axial is better
 170                         }
 171                 }
 172
 173                 value += split->priority;       // prioritize hints higher
 174
 175                 if ( value > bestValue ) {
 176                         bestValue = value;
 177                         bestSplit = split;
 178                 }
 179         }
 180
 181         /* nothing, we have a leaf */
 182         if ( bestValue == -99999 ) {
 183                 return;
 184         }
 185
 186         /* set best split data */
 187         *splitPlaneNum = bestSplit->planenum;
 188         *compileFlags = bestSplit->compileFlags;
 189
 190         if ( *splitPlaneNum > -1 ) {
 191                 mapplanes[ *splitPlaneNum ].counter++;
 192         }
 193 }
 194
 195
 196
 197 /*
 198    CountFaceList()
 199    counts bsp faces in the linked list
 200  */
 201
 202 int CountFaceList( face_t *list ){
 203         int c;
 204
 205
 206         c = 0;
 207         for ( ; list != NULL; list = list->next )
 208                 c++;
 209         return c;
 210 }
 211
 212
 213
 214 /*
 215    BuildFaceTree_r()
 216    recursively builds the bsp, splitting on face planes
 217  */
 218
 219 void BuildFaceTree_r( node_t *node, face_t *list ){
 220         face_t      *split;
 221         face_t      *next;
 222         int side;
 223         plane_t     *plane;
 224         face_t      *newFace;
 225         face_t      *childLists[2];
 226         winding_t   *frontWinding, *backWinding;
 227         int i;
 228         int splitPlaneNum, compileFlags;
 229
 230
 231         /* count faces left */
 232         i = CountFaceList( list );
 233
 234         /* select the best split plane */
 235         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
 236
 237         /* if we don't have any more faces, this is a node */
 238         if ( splitPlaneNum == -1 ) {
 239                 node->planenum = PLANENUM_LEAF;
 240                 node->has_structural_children = qfalse;
 241                 c_faceLeafs++;
 242                 return;
 243         }
 244
 245         /* partition the list */
 246         node->planenum = splitPlaneNum;
 247         node->compileFlags = compileFlags;
 248         node->has_structural_children = !( compileFlags & C_DETAIL ) && !node->opaque;
 249         plane = &mapplanes[ splitPlaneNum ];
 250         childLists[0] = NULL;
 251         childLists[1] = NULL;
 252
 253         for ( split = list; split; split = next )
 254         {
 255                 /* set next */
 256                 next = split->next;
 257
 258                 /* don't split by identical plane */
 259                 if ( split->planenum == node->planenum ) {
 260                         FreeBspFace( split );
 261                         continue;
 262                 }
 263
 264                 /* determine which side the face falls on */
 265                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
 266
 267                 /* switch on side */
 268                 if ( side == SIDE_CROSS ) {
 269                         /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */
 270                         ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
 271                                                                 &frontWinding, &backWinding );
 272                         if ( frontWinding ) {
 273                                 newFace = AllocBspFace();
 274                                 newFace->w = frontWinding;
 275                                 newFace->next = childLists[0];
 276                                 newFace->planenum = split->planenum;
 277                                 newFace->priority = split->priority;
 278                                 newFace->compileFlags = split->compileFlags;
 279                                 childLists[0] = newFace;
 280                         }
 281                         if ( backWinding ) {
 282                                 newFace = AllocBspFace();
 283                                 newFace->w = backWinding;
 284                                 newFace->next = childLists[1];
 285                                 newFace->planenum = split->planenum;
 286                                 newFace->priority = split->priority;
 287                                 newFace->compileFlags = split->compileFlags;
 288                                 childLists[1] = newFace;
 289                         }
 290                         FreeBspFace( split );
 291                 }
 292                 else if ( side == SIDE_FRONT ) {
 293                         split->next = childLists[0];
 294                         childLists[0] = split;
 295                 }
 296                 else if ( side == SIDE_BACK ) {
 297                         split->next = childLists[1];
 298                         childLists[1] = split;
 299                 }
 300         }
 301
 302
 303         // recursively process children
 304         for ( i = 0 ; i < 2 ; i++ ) {
 305                 node->children[i] = AllocNode();
 306                 node->children[i]->parent = node;
 307                 VectorCopy( node->mins, node->children[i]->mins );
 308                 VectorCopy( node->maxs, node->children[i]->maxs );
 309         }
 310
 311         for ( i = 0 ; i < 3 ; i++ ) {
 312                 if ( plane->normal[i] == 1 ) {
 313                         node->children[0]->mins[i] = plane->dist;
 314                         node->children[1]->maxs[i] = plane->dist;
 315                         break;
 316                 }
 317                 if ( plane->normal[i] == -1 ) {
 318                         node->children[0]->maxs[i] = -plane->dist;
 319                         node->children[1]->mins[i] = -plane->dist;
 320                         break;
 321                 }
 322         }
 323
 324         for ( i = 0 ; i < 2 ; i++ ) {
 325                 BuildFaceTree_r( node->children[i], childLists[i] );
 326                 node->has_structural_children |= node->children[i]->has_structural_children;
 327         }
 328 }
 329
 330
 331 /*
 332    ================
 333    FaceBSP
 334
 335    List will be freed before returning
 336    ================
 337  */
 338 tree_t *FaceBSP( face_t *list ) {
 339         tree_t      *tree;
 340         face_t  *face;
 341         int i;
 342         int count;
 343
 344         Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
 345
 346         tree = AllocTree();
 347
 348         count = 0;
 349         for ( face = list; face != NULL; face = face->next )
 350         {
 351                 count++;
 352                 for ( i = 0; i < face->w->numpoints; i++ )
 353                 {
 354                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
 355                 }
 356         }
 357         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
 358
 359         for ( i = 0; i < nummapplanes; i++ )
 360         {
 361                 mapplanes[ i ].counter = 0;
 362         }
 363
 364         tree->headnode = AllocNode();
 365         VectorCopy( tree->mins, tree->headnode->mins );
 366         VectorCopy( tree->maxs, tree->headnode->maxs );
 367         c_faceLeafs = 0;
 368
 369         BuildFaceTree_r( tree->headnode, list );
 370
 371         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
 372
 373         return tree;
 374 }
 375
 376
 377
 378 /*
 379    MakeStructuralBSPFaceList()
 380    get structural brush faces
 381  */
 382
 383 face_t *MakeStructuralBSPFaceList( brush_t *list ){
 384         brush_t     *b;
 385         int i;
 386         side_t      *s;
 387         winding_t   *w;
 388         face_t      *f, *flist;
 389
 390
 391         flist = NULL;
 392         for ( b = list; b != NULL; b = b->next )
 393         {
 394                 if ( !deepBSP && b->detail ) {
 395                         continue;
 396                 }
 397
 398                 for ( i = 0; i < b->numsides; i++ )
 399                 {
 400                         /* get side and winding */
 401                         s = &b->sides[ i ];
 402                         w = s->winding;
 403                         if ( w == NULL ) {
 404                                 continue;
 405                         }
 406
 407                         /* ydnar: skip certain faces */
 408                         if ( s->compileFlags & C_SKIP ) {
 409                                 continue;
 410                         }
 411
 412                         /* allocate a face */
 413                         f = AllocBspFace();
 414                         f->w = CopyWinding( w );
 415                         f->planenum = s->planenum & ~1;
 416                         f->compileFlags = s->compileFlags;  /* ydnar */
 417                         if ( b->detail ) {
 418                                 f->compileFlags |= C_DETAIL;
 419                         }
 420
 421                         /* ydnar: set priority */
 422                         f->priority = 0;
 423                         if ( f->compileFlags & C_HINT ) {
 424                                 f->priority += HINT_PRIORITY;
 425                         }
 426                         if ( f->compileFlags & C_ANTIPORTAL ) {
 427                                 f->priority += ANTIPORTAL_PRIORITY;
 428                         }
 429                         if ( f->compileFlags & C_AREAPORTAL ) {
 430                                 f->priority += AREAPORTAL_PRIORITY;
 431                         }
 432                         if ( f->compileFlags & C_DETAIL ) {
 433                                 f->priority += DETAIL_PRIORITY;
 434                         }
 435
 436                         /* get next face */
 437                         f->next = flist;
 438                         flist = f;
 439                 }
 440         }
 441
 442         return flist;
 443 }
 444
 445
 446
 447 /*
 448    MakeVisibleBSPFaceList()
 449    get visible brush faces
 450  */
 451
 452 face_t *MakeVisibleBSPFaceList( brush_t *list ){
 453         brush_t     *b;
 454         int i;
 455         side_t      *s;
 456         winding_t   *w;
 457         face_t      *f, *flist;
 458
 459
 460         flist = NULL;
 461         for ( b = list; b != NULL; b = b->next )
 462         {
 463                 if ( !deepBSP && b->detail ) {
 464                         continue;
 465                 }
 466
 467                 for ( i = 0; i < b->numsides; i++ )
 468                 {
 469                         /* get side and winding */
 470                         s = &b->sides[ i ];
 471                         w = s->visibleHull;
 472                         if ( w == NULL ) {
 473                                 continue;
 474                         }
 475
 476                         /* ydnar: skip certain faces */
 477                         if ( s->compileFlags & C_SKIP ) {
 478                                 continue;
 479                         }
 480
 481                         /* allocate a face */
 482                         f = AllocBspFace();
 483                         f->w = CopyWinding( w );
 484                         f->planenum = s->planenum & ~1;
 485                         f->compileFlags = s->compileFlags;  /* ydnar */
 486                         if ( b->detail ) {
 487                                 f->compileFlags |= C_DETAIL;
 488                         }
 489
 490                         /* ydnar: set priority */
 491                         f->priority = 0;
 492                         if ( f->compileFlags & C_HINT ) {
 493                                 f->priority += HINT_PRIORITY;
 494                         }
 495                         if ( f->compileFlags & C_ANTIPORTAL ) {
 496                                 f->priority += ANTIPORTAL_PRIORITY;
 497                         }
 498                         if ( f->compileFlags & C_AREAPORTAL ) {
 499                                 f->priority += AREAPORTAL_PRIORITY;
 500                         }
 501                         if ( f->compileFlags & C_DETAIL ) {
 502                                 f->priority += DETAIL_PRIORITY;
 503                         }
 504
 505                         /* get next face */
 506                         f->next = flist;
 507                         flist = f;
 508                 }
 509         }
 510
 511         return flist;
 512 }