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 {
  81         face_t          *split;
  82         face_t          *check;
  83         face_t          *bestSplit;
  84         int                     splits, facing, front, back;
  85         int                     side;
  86         plane_t         *plane;
  87         int                     value, bestValue;
  88         int                     i;
  89         vec3_t          normal;
  90         float           dist;
  91         int                     planenum;
  92         float       sizeBias;
  93
  94         //int frontC,backC,splitsC,facingC;
  95
  96
  97         /* ydnar: set some defaults */
  98         *splitPlaneNum = -1; /* leaf */
  99         *compileFlags = 0;
 100
 101         /* ydnar 2002-06-24: changed this to split on z-axis as well */
 102         /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
 103
 104         /* if it is crossing a block boundary, force a split */
 105         for( i = 0; i < 3; i++ )
 106         {
 107                 if( blockSize[ i ] <= 0 )
 108                         continue;
 109                 dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
 110                 if( node->maxs[ i ] > dist )
 111                 {
 112                         VectorClear( normal );
 113                         normal[ i ] = 1;
 114                         planenum = FindFloatPlane( normal, dist, 0, NULL );
 115                         *splitPlaneNum = planenum;
 116                         return;
 117                 }
 118         }
 119
 120         /* pick one of the face planes */
 121         bestValue = -99999;
 122         bestSplit = list;
 123
 124
 125         // div0: this check causes detail/structural mixes
 126         //for( split = list; split; split = split->next )
 127         //      split->checked = qfalse;
 128
 129         for( split = list; split; split = split->next )
 130         {
 131                 //if ( split->checked )
 132                 //      continue;
 133
 134                 plane = &mapplanes[ split->planenum ];
 135                 splits = 0;
 136                 facing = 0;
 137                 front = 0;
 138                 back = 0;
 139                 for ( check = list ; check ; check = check->next ) {
 140                         if ( check->planenum == split->planenum ) {
 141                                 facing++;
 142                                 //check->checked = qtrue;       // won't need to test this plane again
 143                                 continue;
 144                         }
 145                         side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
 146                         if ( side == SIDE_CROSS ) {
 147                                 splits++;
 148                         } else if ( side == SIDE_FRONT ) {
 149                                 front++;
 150                         } else if ( side == SIDE_BACK ) {
 151                                 back++;
 152                         }
 153                 }
 154
 155                 if(bspAlternateSplitWeights)
 156                 {
 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         //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
 194
 195         /* set best split data */
 196         *splitPlaneNum = bestSplit->planenum;
 197         *compileFlags = bestSplit->compileFlags;
 198
 199 #if 0
 200         if(bestSplit->compileFlags & C_DETAIL)
 201                 for( split = list; split; split = split->next )
 202                         if(!(split->compileFlags & C_DETAIL))
 203                                 Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (1)\n");
 204         if((node->compileFlags & C_DETAIL) && !(bestSplit->compileFlags & C_DETAIL))
 205                 Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (2)\n");
 206 #endif
 207
 208    if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;
 209 }
 210
 211
 212
 213 /*
 214 CountFaceList()
 215 counts bsp faces in the linked list
 216 */
 217
 218 int     CountFaceList( face_t *list )
 219 {
 220         int             c;
 221
 222
 223         c = 0;
 224         for( ; list != NULL; list = list->next )
 225                 c++;
 226         return c;
 227 }
 228
 229
 230
 231 /*
 232 BuildFaceTree_r()
 233 recursively builds the bsp, splitting on face planes
 234 */
 235
 236 void BuildFaceTree_r( node_t *node, face_t *list )
 237 {
 238         face_t          *split;
 239         face_t          *next;
 240         int                     side;
 241         plane_t         *plane;
 242         face_t          *newFace;
 243         face_t          *childLists[2];
 244         winding_t       *frontWinding, *backWinding;
 245         int                     i;
 246         int                     splitPlaneNum, compileFlags;
 247         qboolean isstruct = qfalse;
 248
 249
 250         /* count faces left */
 251         i = CountFaceList( list );
 252
 253         /* select the best split plane */
 254         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
 255
 256         /* if we don't have any more faces, this is a node */
 257         if ( splitPlaneNum == -1 )
 258         {
 259                 node->planenum = PLANENUM_LEAF;
 260                 node->has_structural_children = qfalse;
 261                 c_faceLeafs++;
 262                 return;
 263         }
 264
 265         /* partition the list */
 266         node->planenum = splitPlaneNum;
 267         node->compileFlags = compileFlags;
 268         node->has_structural_children = !(compileFlags & C_DETAIL) && !node->opaque;
 269         plane = &mapplanes[ splitPlaneNum ];
 270         childLists[0] = NULL;
 271         childLists[1] = NULL;
 272
 273         for( split = list; split; split = next )
 274         {
 275                 /* set next */
 276                 next = split->next;
 277
 278                 /* don't split by identical plane */
 279                 if( split->planenum == node->planenum )
 280                 {
 281                         FreeBspFace( split );
 282                         continue;
 283                 }
 284
 285                 if(!(split->compileFlags & C_DETAIL))
 286                         isstruct = 1;
 287
 288                 /* determine which side the face falls on */
 289                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
 290
 291                 /* switch on side */
 292                 if( side == SIDE_CROSS )
 293                 {
 294                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
 295                                 &frontWinding, &backWinding );
 296                         if( frontWinding ) {
 297                                 newFace = AllocBspFace();
 298                                 newFace->w = frontWinding;
 299                                 newFace->next = childLists[0];
 300                                 newFace->planenum = split->planenum;
 301                                 newFace->priority = split->priority;
 302                                 newFace->compileFlags = split->compileFlags;
 303                                 childLists[0] = newFace;
 304                         }
 305                         if( backWinding ) {
 306                                 newFace = AllocBspFace();
 307                                 newFace->w = backWinding;
 308                                 newFace->next = childLists[1];
 309                                 newFace->planenum = split->planenum;
 310                                 newFace->priority = split->priority;
 311                                 newFace->compileFlags = split->compileFlags;
 312                                 childLists[1] = newFace;
 313                         }
 314                         FreeBspFace( split );
 315                 } else if ( side == SIDE_FRONT ) {
 316                         split->next = childLists[0];
 317                         childLists[0] = split;
 318                 } else if ( side == SIDE_BACK ) {
 319                         split->next = childLists[1];
 320                         childLists[1] = split;
 321                 }
 322         }
 323
 324
 325         // recursively process children
 326         for ( i = 0 ; i < 2 ; i++ ) {
 327                 node->children[i] = AllocNode();
 328                 node->children[i]->parent = node;
 329                 VectorCopy( node->mins, node->children[i]->mins );
 330                 VectorCopy( node->maxs, node->children[i]->maxs );
 331         }
 332
 333         for ( i = 0 ; i < 3 ; i++ ) {
 334                 if ( plane->normal[i] == 1 ) {
 335                         node->children[0]->mins[i] = plane->dist;
 336                         node->children[1]->maxs[i] = plane->dist;
 337                         break;
 338                 }
 339         }
 340
 341 #if 0
 342         if((node->compileFlags & C_DETAIL) && isstruct)
 343                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children);
 344 #endif
 345
 346         for ( i = 0 ; i < 2 ; i++ ) {
 347                 BuildFaceTree_r ( node->children[i], childLists[i]);
 348                 node->has_structural_children |= node->children[i]->has_structural_children;
 349         }
 350
 351 #if 0
 352         if((node->compileFlags & C_DETAIL) && !(node->children[0]->compileFlags & C_DETAIL) && node->children[0]->planenum != PLANENUM_LEAF)
 353                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children);
 354         if((node->compileFlags & C_DETAIL) && isstruct)
 355                 Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children);
 356 #endif
 357 }
 358
 359
 360 /*
 361 ================
 362 FaceBSP
 363
 364 List will be freed before returning
 365 ================
 366 */
 367 tree_t *FaceBSP( face_t *list ) {
 368         tree_t          *tree;
 369         face_t  *face;
 370         int                     i;
 371         int                     count;
 372
 373         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
 374
 375         tree = AllocTree ();
 376
 377         count = 0;
 378         for( face = list; face != NULL; face = face->next )
 379         {
 380                 count++;
 381                 for( i = 0; i < face->w->numpoints; i++ )
 382                 {
 383                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
 384                 }
 385         }
 386         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
 387
 388    for( i = 0; i < nummapplanes; i++)
 389    {
 390       mapplanes[ i ].counter=0;
 391    }
 392
 393         tree->headnode = AllocNode();
 394         VectorCopy( tree->mins, tree->headnode->mins );
 395         VectorCopy( tree->maxs, tree->headnode->maxs );
 396         c_faceLeafs = 0;
 397
 398         BuildFaceTree_r ( tree->headnode, list );
 399
 400         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
 401
 402         return tree;
 403 }
 404
 405
 406
 407 /*
 408 MakeStructuralBSPFaceList()
 409 get structural brush faces
 410 */
 411
 412 face_t *MakeStructuralBSPFaceList( brush_t *list )
 413 {
 414         brush_t         *b;
 415         int                     i;
 416         side_t          *s;
 417         winding_t       *w;
 418         face_t          *f, *flist;
 419
 420
 421         flist = NULL;
 422         for( b = list; b != NULL; b = b->next )
 423         {
 424                 if( !deepBSP && b->detail )
 425                         continue;
 426
 427                 for( i = 0; i < b->numsides; i++ )
 428                 {
 429                         /* get side and winding */
 430                         s = &b->sides[ i ];
 431                         w = s->winding;
 432                         if( w == NULL )
 433                                 continue;
 434
 435                         /* ydnar: skip certain faces */
 436                         if( s->compileFlags & C_SKIP )
 437                                 continue;
 438
 439                         /* allocate a face */
 440                         f = AllocBspFace();
 441                         f->w = CopyWinding( w );
 442                         f->planenum = s->planenum & ~1;
 443                         f->compileFlags = s->compileFlags;      /* ydnar */
 444                         if(b->detail)
 445                                 f->compileFlags |= C_DETAIL;
 446
 447                         /* ydnar: set priority */
 448                         f->priority = 0;
 449                         if( f->compileFlags & C_HINT )
 450                                 f->priority += HINT_PRIORITY;
 451                         if( f->compileFlags & C_ANTIPORTAL )
 452                                 f->priority += ANTIPORTAL_PRIORITY;
 453                         if( f->compileFlags & C_AREAPORTAL )
 454                                 f->priority += AREAPORTAL_PRIORITY;
 455                         if( f->compileFlags & C_DETAIL )
 456                                 f->priority += DETAIL_PRIORITY;
 457
 458                         /* get next face */
 459                         f->next = flist;
 460                         flist = f;
 461                 }
 462         }
 463
 464         return flist;
 465 }
 466
 467
 468
 469 /*
 470 MakeVisibleBSPFaceList()
 471 get visible brush faces
 472 */
 473
 474 face_t *MakeVisibleBSPFaceList( brush_t *list )
 475 {
 476         brush_t         *b;
 477         int                     i;
 478         side_t          *s;
 479         winding_t       *w;
 480         face_t          *f, *flist;
 481
 482
 483         flist = NULL;
 484         for( b = list; b != NULL; b = b->next )
 485         {
 486                 if( !deepBSP && b->detail )
 487                         continue;
 488
 489                 for( i = 0; i < b->numsides; i++ )
 490                 {
 491                         /* get side and winding */
 492                         s = &b->sides[ i ];
 493                         w = s->visibleHull;
 494                         if( w == NULL )
 495                                 continue;
 496
 497                         /* ydnar: skip certain faces */
 498                         if( s->compileFlags & C_SKIP )
 499                                 continue;
 500
 501                         /* allocate a face */
 502                         f = AllocBspFace();
 503                         f->w = CopyWinding( w );
 504                         f->planenum = s->planenum & ~1;
 505                         f->compileFlags = s->compileFlags;      /* ydnar */
 506                         if(b->detail)
 507                                 f->compileFlags |= C_DETAIL;
 508
 509                         /* ydnar: set priority */
 510                         f->priority = 0;
 511                         if( f->compileFlags & C_HINT )
 512                                 f->priority += HINT_PRIORITY;
 513                         if( f->compileFlags & C_ANTIPORTAL )
 514                                 f->priority += ANTIPORTAL_PRIORITY;
 515                         if( f->compileFlags & C_AREAPORTAL )
 516                                 f->priority += AREAPORTAL_PRIORITY;
 517                         if( f->compileFlags & C_DETAIL )
 518                                 f->priority += DETAIL_PRIORITY;
 519
 520                         /* get next face */
 521                         f->next = flist;
 522                         flist = f;
 523                 }
 524         }
 525
 526         return flist;
 527 }
 528