1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
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.
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.
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
22 ----------------------------------------------------------------------------------
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."
27 ------------------------------------------------------------------------------- */
49 face_t *AllocBspFace( void ) {
52 f = safe_malloc( sizeof( *f ) );
53 memset( f, 0, sizeof( *f ) );
65 void FreeBspFace( face_t *f ) {
76 finds the best split plane for this node
79 static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ){
83 int splits, facing, front, back;
93 //int frontC,backC,splitsC,facingC;
96 /* ydnar: set some defaults */
97 *splitPlaneNum = -1; /* leaf */
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 */
103 /* if it is crossing a block boundary, force a split */
104 for ( i = 0; i < 3; i++ )
106 if ( blockSize[ i ] <= 0 ) {
109 dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 );
110 if ( node->maxs[ i ] > dist ) {
111 VectorClear( normal );
113 planenum = FindFloatPlane( normal, dist, 0, NULL );
114 *splitPlaneNum = planenum;
119 /* pick one of the face planes */
124 // div0: this check causes detail/structural mixes
125 //for( split = list; split; split = split->next )
126 // split->checked = qfalse;
128 for ( split = list; split; split = split->next )
130 //if ( split->checked )
133 plane = &mapplanes[ split->planenum ];
138 for ( check = list ; check ; check = check->next ) {
139 if ( check->planenum == split->planenum ) {
141 //check->checked = qtrue; // won't need to test this plane again
144 side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
145 if ( side == SIDE_CROSS ) {
148 else if ( side == SIDE_FRONT ) {
151 else if ( side == SIDE_BACK ) {
156 if ( bspAlternateSplitWeights ) {
160 sizeBias = WindingArea( split->w );
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
171 value = 5 * facing - 5 * splits; // - abs(front-back);
172 if ( plane->type < 3 ) {
173 value += 5; // axial is better
177 value += split->priority; // prioritize hints higher
179 if ( value > bestValue ) {
189 /* nothing, we have a leaf */
190 if ( bestValue == -99999 ) {
194 //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
196 /* set best split data */
197 *splitPlaneNum = bestSplit->planenum;
198 *compileFlags = bestSplit->compileFlags;
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" );
207 if ( ( node->compileFlags & C_DETAIL ) && !( bestSplit->compileFlags & C_DETAIL ) ) {
208 Sys_FPrintf( SYS_ERR, "DON'T DO SUCH SPLITS (2)\n" );
212 if ( *splitPlaneNum > -1 ) {
213 mapplanes[ *splitPlaneNum ].counter++;
221 counts bsp faces in the linked list
224 int CountFaceList( face_t *list ){
229 for ( ; list != NULL; list = list->next )
238 recursively builds the bsp, splitting on face planes
241 void BuildFaceTree_r( node_t *node, face_t *list ){
247 face_t *childLists[2];
248 winding_t *frontWinding, *backWinding;
250 int splitPlaneNum, compileFlags;
252 qboolean isstruct = qfalse;
256 /* count faces left */
257 i = CountFaceList( list );
259 /* select the best split plane */
260 SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
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;
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;
278 for ( split = list; split; split = next )
283 /* don't split by identical plane */
284 if ( split->planenum == node->planenum ) {
285 FreeBspFace( split );
290 if ( !( split->compileFlags & C_DETAIL ) ) {
295 /* determine which side the face falls on */
296 side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
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;
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;
320 FreeBspFace( split );
322 else if ( side == SIDE_FRONT ) {
323 split->next = childLists[0];
324 childLists[0] = split;
326 else if ( side == SIDE_BACK ) {
327 split->next = childLists[1];
328 childLists[1] = split;
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 );
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;
347 if ( plane->normal[i] == -1 ) {
348 node->children[0]->maxs[i] = -plane->dist;
349 node->children[1]->mins[i] = -plane->dist;
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 );
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;
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 );
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 );
380 List will be freed before returning
383 tree_t *FaceBSP( face_t *list ) {
389 Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" );
394 for ( face = list; face != NULL; face = face->next )
397 for ( i = 0; i < face->w->numpoints; i++ )
399 AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
402 Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
404 for ( i = 0; i < nummapplanes; i++ )
406 mapplanes[ i ].counter = 0;
409 tree->headnode = AllocNode();
410 VectorCopy( tree->mins, tree->headnode->mins );
411 VectorCopy( tree->maxs, tree->headnode->maxs );
414 BuildFaceTree_r( tree->headnode, list );
416 Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
424 MakeStructuralBSPFaceList()
425 get structural brush faces
428 face_t *MakeStructuralBSPFaceList( brush_t *list ){
437 for ( b = list; b != NULL; b = b->next )
439 if ( !deepBSP && b->detail ) {
443 for ( i = 0; i < b->numsides; i++ )
445 /* get side and winding */
452 /* ydnar: skip certain faces */
453 if ( s->compileFlags & C_SKIP ) {
457 /* allocate a face */
459 f->w = CopyWinding( w );
460 f->planenum = s->planenum & ~1;
461 f->compileFlags = s->compileFlags; /* ydnar */
463 f->compileFlags |= C_DETAIL;
466 /* ydnar: set priority */
468 if ( f->compileFlags & C_HINT ) {
469 f->priority += HINT_PRIORITY;
471 if ( f->compileFlags & C_ANTIPORTAL ) {
472 f->priority += ANTIPORTAL_PRIORITY;
474 if ( f->compileFlags & C_AREAPORTAL ) {
475 f->priority += AREAPORTAL_PRIORITY;
477 if ( f->compileFlags & C_DETAIL ) {
478 f->priority += DETAIL_PRIORITY;
493 MakeVisibleBSPFaceList()
494 get visible brush faces
497 face_t *MakeVisibleBSPFaceList( brush_t *list ){
506 for ( b = list; b != NULL; b = b->next )
508 if ( !deepBSP && b->detail ) {
512 for ( i = 0; i < b->numsides; i++ )
514 /* get side and winding */
521 /* ydnar: skip certain faces */
522 if ( s->compileFlags & C_SKIP ) {
526 /* allocate a face */
528 f->w = CopyWinding( w );
529 f->planenum = s->planenum & ~1;
530 f->compileFlags = s->compileFlags; /* ydnar */
532 f->compileFlags |= C_DETAIL;
535 /* ydnar: set priority */
537 if ( f->compileFlags & C_HINT ) {
538 f->priority += HINT_PRIORITY;
540 if ( f->compileFlags & C_ANTIPORTAL ) {
541 f->priority += ANTIPORTAL_PRIORITY;
543 if ( f->compileFlags & C_AREAPORTAL ) {
544 f->priority += AREAPORTAL_PRIORITY;
546 if ( f->compileFlags & C_DETAIL ) {
547 f->priority += DETAIL_PRIORITY;