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         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                         } else if ( side == SIDE_FRONT ) {
 148                                 front++;
 149                         } else if ( side == SIDE_BACK ) {
 150                                 back++;
 151                         }
 152                 }
 153
 154                 if(bspAlternateSplitWeights)
 155                 {
 156                         // from 27
 157
 158                         //Bigger is better
 159                         sizeBias=WindingArea(split->w);
 160
 161                         //Base score = 20000 perfectly balanced
 162                         value = 20000-(abs(front-back));
 163                         value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again
 164                         value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
 165                         value -= splits*5;        //more splits = bad
 166                         value +=  sizeBias*10; //We want a huge score bias based on plane size
 167                 }
 168                 else
 169                 {
 170                         value =  5*facing - 5*splits; // - abs(front-back);
 171                         if ( plane->type < 3 ) {
 172                                 value+=5;               // axial is better
 173                         }
 174                 }
 175
 176           value += split->priority;             // prioritize hints higher
 177
 178                 if ( value > bestValue ) {
 179                         bestValue = value;
 180                         bestSplit = split;
 181                         //frontC=front;
 182                         //backC=back;
 183                         //splitsC=splits;
 184                         //facingC=facing;
 185                 }
 186         }
 187
 188         /* nothing, we have a leaf */
 189         if( bestValue == -99999 )
 190                 return;
 191
 192         //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
 193
 194         /* set best split data */
 195         *splitPlaneNum = bestSplit->planenum;
 196         *compileFlags = bestSplit->compileFlags;
 197
 198    if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;
 199 }
 200
 201
 202
 203 /*
 204 CountFaceList()
 205 counts bsp faces in the linked list
 206 */
 207
 208 int     CountFaceList( face_t *list )
 209 {
 210         int             c;
 211
 212
 213         c = 0;
 214         for( ; list != NULL; list = list->next )
 215                 c++;
 216         return c;
 217 }
 218
 219
 220
 221 /*
 222 BuildFaceTree_r()
 223 recursively builds the bsp, splitting on face planes
 224 */
 225
 226 void BuildFaceTree_r( node_t *node, face_t *list )
 227 {
 228         face_t          *split;
 229         face_t          *next;
 230         int                     side;
 231         plane_t         *plane;
 232         face_t          *newFace;
 233         face_t          *childLists[2];
 234         winding_t       *frontWinding, *backWinding;
 235         int                     i;
 236         int                     splitPlaneNum, compileFlags;
 237
 238
 239         /* count faces left */
 240         i = CountFaceList( list );
 241
 242         /* select the best split plane */
 243         SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
 244
 245         /* if we don't have any more faces, this is a node */
 246         if ( splitPlaneNum == -1 )
 247         {
 248                 node->planenum = PLANENUM_LEAF;
 249                 c_faceLeafs++;
 250                 return;
 251         }
 252
 253         /* partition the list */
 254         node->planenum = splitPlaneNum;
 255         node->compileFlags = compileFlags;
 256         plane = &mapplanes[ splitPlaneNum ];
 257         childLists[0] = NULL;
 258         childLists[1] = NULL;
 259         for( split = list; split; split = next )
 260         {
 261                 /* set next */
 262                 next = split->next;
 263
 264                 /* don't split by identical plane */
 265                 if( split->planenum == node->planenum )
 266                 {
 267                         FreeBspFace( split );
 268                         continue;
 269                 }
 270
 271                 /* determine which side the face falls on */
 272                 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
 273
 274                 /* switch on side */
 275                 if( side == SIDE_CROSS )
 276                 {
 277                         ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
 278                                 &frontWinding, &backWinding );
 279                         if( frontWinding ) {
 280                                 newFace = AllocBspFace();
 281                                 newFace->w = frontWinding;
 282                                 newFace->next = childLists[0];
 283                                 newFace->planenum = split->planenum;
 284                                 newFace->priority = split->priority;
 285                                 newFace->compileFlags = split->compileFlags;
 286                                 childLists[0] = newFace;
 287                         }
 288                         if( backWinding ) {
 289                                 newFace = AllocBspFace();
 290                                 newFace->w = backWinding;
 291                                 newFace->next = childLists[1];
 292                                 newFace->planenum = split->planenum;
 293                                 newFace->priority = split->priority;
 294                                 newFace->compileFlags = split->compileFlags;
 295                                 childLists[1] = newFace;
 296                         }
 297                         FreeBspFace( split );
 298                 } else if ( side == SIDE_FRONT ) {
 299                         split->next = childLists[0];
 300                         childLists[0] = split;
 301                 } else if ( side == SIDE_BACK ) {
 302                         split->next = childLists[1];
 303                         childLists[1] = split;
 304                 }
 305         }
 306
 307
 308         // recursively process children
 309         for ( i = 0 ; i < 2 ; i++ ) {
 310                 node->children[i] = AllocNode();
 311                 node->children[i]->parent = node;
 312                 VectorCopy( node->mins, node->children[i]->mins );
 313                 VectorCopy( node->maxs, node->children[i]->maxs );
 314         }
 315
 316         for ( i = 0 ; i < 3 ; i++ ) {
 317                 if ( plane->normal[i] == 1 ) {
 318                         node->children[0]->mins[i] = plane->dist;
 319                         node->children[1]->maxs[i] = plane->dist;
 320                         break;
 321                 }
 322         }
 323
 324         for ( i = 0 ; i < 2 ; i++ ) {
 325                 BuildFaceTree_r ( node->children[i], childLists[i]);
 326         }
 327 }
 328
 329
 330 /*
 331 ================
 332 FaceBSP
 333
 334 List will be freed before returning
 335 ================
 336 */
 337 tree_t *FaceBSP( face_t *list ) {
 338         tree_t          *tree;
 339         face_t  *face;
 340         int                     i;
 341         int                     count;
 342
 343         Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
 344
 345         tree = AllocTree ();
 346
 347         count = 0;
 348         for( face = list; face != NULL; face = face->next )
 349         {
 350                 count++;
 351                 for( i = 0; i < face->w->numpoints; i++ )
 352                 {
 353                         AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
 354                 }
 355         }
 356         Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
 357
 358    for( i = 0; i < nummapplanes; i++)
 359    {
 360       mapplanes[ i ].counter=0;
 361    }
 362
 363         tree->headnode = AllocNode();
 364         VectorCopy( tree->mins, tree->headnode->mins );
 365         VectorCopy( tree->maxs, tree->headnode->maxs );
 366         c_faceLeafs = 0;
 367
 368         BuildFaceTree_r ( tree->headnode, list );
 369
 370         Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
 371
 372         return tree;
 373 }
 374
 375
 376
 377 /*
 378 MakeStructuralBSPFaceList()
 379 get structural brush faces
 380 */
 381
 382 face_t *MakeStructuralBSPFaceList( brush_t *list )
 383 {
 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( b->detail )
 395                         continue;
 396
 397                 for( i = 0; i < b->numsides; i++ )
 398                 {
 399                         /* get side and winding */
 400                         s = &b->sides[ i ];
 401                         w = s->winding;
 402                         if( w == NULL )
 403                                 continue;
 404
 405                         /* ydnar: skip certain faces */
 406                         if( s->compileFlags & C_SKIP )
 407                                 continue;
 408
 409                         /* allocate a face */
 410                         f = AllocBspFace();
 411                         f->w = CopyWinding( w );
 412                         f->planenum = s->planenum & ~1;
 413                         f->compileFlags = s->compileFlags;      /* ydnar */
 414
 415                         /* ydnar: set priority */
 416                         f->priority = 0;
 417                         if( f->compileFlags & C_HINT )
 418                                 f->priority += HINT_PRIORITY;
 419                         if( f->compileFlags & C_ANTIPORTAL )
 420                                 f->priority += ANTIPORTAL_PRIORITY;
 421                         if( f->compileFlags & C_AREAPORTAL )
 422                                 f->priority += AREAPORTAL_PRIORITY;
 423
 424                         /* get next face */
 425                         f->next = flist;
 426                         flist = f;
 427                 }
 428         }
 429
 430         return flist;
 431 }
 432
 433
 434
 435 /*
 436 MakeVisibleBSPFaceList()
 437 get visible brush faces
 438 */
 439
 440 face_t *MakeVisibleBSPFaceList( brush_t *list )
 441 {
 442         brush_t         *b;
 443         int                     i;
 444         side_t          *s;
 445         winding_t       *w;
 446         face_t          *f, *flist;
 447
 448
 449         flist = NULL;
 450         for( b = list; b != NULL; b = b->next )
 451         {
 452                 if( b->detail )
 453                         continue;
 454
 455                 for( i = 0; i < b->numsides; i++ )
 456                 {
 457                         /* get side and winding */
 458                         s = &b->sides[ i ];
 459                         w = s->visibleHull;
 460                         if( w == NULL )
 461                                 continue;
 462
 463                         /* ydnar: skip certain faces */
 464                         if( s->compileFlags & C_SKIP )
 465                                 continue;
 466
 467                         /* allocate a face */
 468                         f = AllocBspFace();
 469                         f->w = CopyWinding( w );
 470                         f->planenum = s->planenum & ~1;
 471                         f->compileFlags = s->compileFlags;      /* ydnar */
 472
 473                         /* ydnar: set priority */
 474                         f->priority = 0;
 475                         if( f->compileFlags & C_HINT )
 476                                 f->priority += HINT_PRIORITY;
 477                         if( f->compileFlags & C_ANTIPORTAL )
 478                                 f->priority += ANTIPORTAL_PRIORITY;
 479                         if( f->compileFlags & C_AREAPORTAL )
 480                                 f->priority += AREAPORTAL_PRIORITY;
 481
 482                         /* get next face */
 483                         f->next = flist;
 484                         flist = f;
 485                 }
 486         }
 487
 488         return flist;
 489 }
 490