X-Git-Url: http://de.git.xonotic.org/?p=xonotic%2Fnetradiant.git;a=blobdiff_plain;f=tools%2Fquake3%2Fq3map2%2Ffacebsp.c;h=e5390ede45a1fcc32da6a2893b4df1d17674e161;hp=65532a17acea0976a5a7e6ab91d6942b01ae5e05;hb=043d08127ab87117ddfd16e8b439f47c6b66a87f;hpb=889347e958d7c7c99d50021661d7af39bcb19849 diff --git a/tools/quake3/q3map2/facebsp.c b/tools/quake3/q3map2/facebsp.c index 65532a17..e5390ede 100644 --- a/tools/quake3/q3map2/facebsp.c +++ b/tools/quake3/q3map2/facebsp.c @@ -1,30 +1,30 @@ /* ------------------------------------------------------------------------------- -Copyright (C) 1999-2007 id Software, Inc. and contributors. -For a list of contributors, see the accompanying CONTRIBUTORS file. + Copyright (C) 1999-2007 id Software, Inc. and contributors. + For a list of contributors, see the accompanying CONTRIBUTORS file. -This file is part of GtkRadiant. + This file is part of GtkRadiant. -GtkRadiant is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + GtkRadiant is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -GtkRadiant is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + GtkRadiant is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with GtkRadiant; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + You should have received a copy of the GNU General Public License + along with GtkRadiant; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA ----------------------------------------------------------------------------------- + ---------------------------------------------------------------------------------- -This code has been altered significantly from its original form, to support -several games based on the Quake III Arena engine, in the form of "Q3Map2." + This code has been altered significantly from its original form, to support + several games based on the Quake III Arena engine, in the form of "Q3Map2." -------------------------------------------------------------------------------- */ + ------------------------------------------------------------------------------- */ @@ -38,19 +38,19 @@ several games based on the Quake III Arena engine, in the form of "Q3Map2." -int c_faceLeafs; +int c_faceLeafs; /* -================ -AllocBspFace -================ -*/ -face_t *AllocBspFace( void ) { - face_t *f; + ================ + AllocBspFace + ================ + */ +face_t *AllocBspFace( void ) { + face_t *f; - f = safe_malloc(sizeof(*f)); - memset( f, 0, sizeof(*f) ); + f = safe_malloc( sizeof( *f ) ); + memset( f, 0, sizeof( *f ) ); return f; } @@ -58,11 +58,11 @@ face_t *AllocBspFace( void ) { /* -================ -FreeBspFace -================ -*/ -void FreeBspFace( face_t *f ) { + ================ + FreeBspFace + ================ + */ +void FreeBspFace( face_t *f ) { if ( f->w ) { FreeWinding( f->w ); } @@ -72,43 +72,39 @@ void FreeBspFace( face_t *f ) { /* -SelectSplitPlaneNum() -finds the best split plane for this node -*/ - -static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ) -{ - face_t *split; - face_t *check; - face_t *bestSplit; - int splits, facing, front, back; - int side; - plane_t *plane; - int value, bestValue; - int i; - vec3_t normal; - float dist; - int planenum; - float sizeBias; - - //int frontC,backC,splitsC,facingC; - - + SelectSplitPlaneNum() + finds the best split plane for this node + */ + +static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags ){ + face_t *split; + face_t *check; + face_t *bestSplit; + int splits, facing, front, back; + int side; + plane_t *plane; + int value, bestValue; + int i; + vec3_t normal; + float dist; + int planenum; + float sizeBias; + /* ydnar: set some defaults */ *splitPlaneNum = -1; /* leaf */ *compileFlags = 0; - + /* ydnar 2002-06-24: changed this to split on z-axis as well */ /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */ - + /* if it is crossing a block boundary, force a split */ - for( i = 0; i < 3; i++ ) + for ( i = 0; i < 3; i++ ) { - if( blockSize[ i ] <= 0 ) + if ( blockSize[ i ] <= 0 ) { continue; - dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1); - if( node->maxs[ i ] > dist ) - { + } + dist = blockSize[ i ] * ( floor( node->mins[ i ] / blockSize[ i ] ) + 1 ); + if ( node->maxs[ i ] > dist ) { VectorClear( normal ); normal[ i ] = 1; planenum = FindFloatPlane( normal, dist, 0, NULL ); @@ -116,20 +112,21 @@ static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, return; } } - + /* pick one of the face planes */ bestValue = -99999; bestSplit = list; - - for( split = list; split; split = split->next ) - split->checked = qfalse; - - for( split = list; split; split = split->next ) + + // div0: this check causes detail/structural mixes + //for( split = list; split; split = split->next ) + // split->checked = qfalse; + + for ( split = list; split; split = split->next ) { - if ( split->checked ) - continue; - + //if ( split->checked ) + // continue; + plane = &mapplanes[ split->planenum ]; splits = 0; facing = 0; @@ -138,80 +135,77 @@ static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, for ( check = list ; check ; check = check->next ) { if ( check->planenum == split->planenum ) { facing++; - check->checked = qtrue; // won't need to test this plane again + //check->checked = qtrue; // won't need to test this plane again continue; } side = WindingOnPlaneSide( check->w, plane->normal, plane->dist ); if ( side == SIDE_CROSS ) { splits++; - } else if ( side == SIDE_FRONT ) { + } + else if ( side == SIDE_FRONT ) { front++; - } else if ( side == SIDE_BACK ) { + } + else if ( side == SIDE_BACK ) { back++; } } - if(bspAlternateSplitWeights) - { + if ( bspAlternateSplitWeights ) { // from 27 //Bigger is better - sizeBias=WindingArea(split->w); + sizeBias = WindingArea( split->w ); - //Base score = 20000 perfectly balanced - value = 20000-(abs(front-back)); - value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again + //Base score = 20000 perfectly balanced + value = 20000 - ( abs( front - back ) ); + value -= plane->counter; // If we've already used this plane sometime in the past try not to use it again value -= facing ; // if we're going to have alot of other surfs use this plane, we want to get it in quickly. - value -= splits*5; //more splits = bad - value += sizeBias*10; //We want a huge score bias based on plane size + value -= splits * 5; //more splits = bad + value += sizeBias * 10; //We want a huge score bias based on plane size } else { - value = 5*facing - 5*splits; // - abs(front-back); + value = 5 * facing - 5 * splits; // - abs(front-back); if ( plane->type < 3 ) { - value+=5; // axial is better + value += 5; // axial is better } } - value += split->priority; // prioritize hints higher + value += split->priority; // prioritize hints higher if ( value > bestValue ) { bestValue = value; bestSplit = split; - //frontC=front; - //backC=back; - //splitsC=splits; - //facingC=facing; } } - + /* nothing, we have a leaf */ - if( bestValue == -99999 ) + if ( bestValue == -99999 ) { return; - - //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC ); + } /* set best split data */ *splitPlaneNum = bestSplit->planenum; *compileFlags = bestSplit->compileFlags; - if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++; + if ( *splitPlaneNum > -1 ) { + mapplanes[ *splitPlaneNum ].counter++; + } } /* -CountFaceList() -counts bsp faces in the linked list -*/ + CountFaceList() + counts bsp faces in the linked list + */ + +int CountFaceList( face_t *list ){ + int c; -int CountFaceList( face_t *list ) -{ - int c; - c = 0; - for( ; list != NULL; list = list->next ) + for ( ; list != NULL; list = list->next ) c++; return c; } @@ -219,64 +213,64 @@ int CountFaceList( face_t *list ) /* -BuildFaceTree_r() -recursively builds the bsp, splitting on face planes -*/ - -void BuildFaceTree_r( node_t *node, face_t *list ) -{ - face_t *split; - face_t *next; - int side; - plane_t *plane; - face_t *newFace; - face_t *childLists[2]; - winding_t *frontWinding, *backWinding; - int i; - int splitPlaneNum, compileFlags; - - + BuildFaceTree_r() + recursively builds the bsp, splitting on face planes + */ + +void BuildFaceTree_r( node_t *node, face_t *list ){ + face_t *split; + face_t *next; + int side; + plane_t *plane; + face_t *newFace; + face_t *childLists[2]; + winding_t *frontWinding, *backWinding; + int i; + int splitPlaneNum, compileFlags; + + /* count faces left */ i = CountFaceList( list ); - + /* select the best split plane */ SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags ); - + /* if we don't have any more faces, this is a node */ - if ( splitPlaneNum == -1 ) - { + if ( splitPlaneNum == -1 ) { node->planenum = PLANENUM_LEAF; + node->has_structural_children = qfalse; c_faceLeafs++; return; } - + /* partition the list */ node->planenum = splitPlaneNum; node->compileFlags = compileFlags; + node->has_structural_children = !( compileFlags & C_DETAIL ) && !node->opaque; plane = &mapplanes[ splitPlaneNum ]; childLists[0] = NULL; childLists[1] = NULL; - for( split = list; split; split = next ) + + for ( split = list; split; split = next ) { /* set next */ next = split->next; - + /* don't split by identical plane */ - if( split->planenum == node->planenum ) - { + if ( split->planenum == node->planenum ) { FreeBspFace( split ); continue; } - + /* determine which side the face falls on */ side = WindingOnPlaneSide( split->w, plane->normal, plane->dist ); - + /* switch on side */ - if( side == SIDE_CROSS ) - { - ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2, - &frontWinding, &backWinding ); - if( frontWinding ) { + if ( side == SIDE_CROSS ) { + /* strict; if no winding is left, we have a "virtually identical" plane and don't want to split by it */ + ClipWindingEpsilonStrict( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2, + &frontWinding, &backWinding ); + if ( frontWinding ) { newFace = AllocBspFace(); newFace->w = frontWinding; newFace->next = childLists[0]; @@ -285,7 +279,7 @@ void BuildFaceTree_r( node_t *node, face_t *list ) newFace->compileFlags = split->compileFlags; childLists[0] = newFace; } - if( backWinding ) { + if ( backWinding ) { newFace = AllocBspFace(); newFace->w = backWinding; newFace->next = childLists[1]; @@ -295,10 +289,12 @@ void BuildFaceTree_r( node_t *node, face_t *list ) childLists[1] = newFace; } FreeBspFace( split ); - } else if ( side == SIDE_FRONT ) { + } + else if ( side == SIDE_FRONT ) { split->next = childLists[0]; childLists[0] = split; - } else if ( side == SIDE_BACK ) { + } + else if ( side == SIDE_BACK ) { split->next = childLists[1]; childLists[1] = split; } @@ -319,53 +315,59 @@ void BuildFaceTree_r( node_t *node, face_t *list ) node->children[1]->maxs[i] = plane->dist; break; } + if ( plane->normal[i] == -1 ) { + node->children[0]->maxs[i] = -plane->dist; + node->children[1]->mins[i] = -plane->dist; + break; + } } for ( i = 0 ; i < 2 ; i++ ) { - BuildFaceTree_r ( node->children[i], childLists[i]); + BuildFaceTree_r( node->children[i], childLists[i] ); + node->has_structural_children |= node->children[i]->has_structural_children; } } /* -================ -FaceBSP + ================ + FaceBSP -List will be freed before returning -================ -*/ + List will be freed before returning + ================ + */ tree_t *FaceBSP( face_t *list ) { - tree_t *tree; - face_t *face; - int i; - int count; + tree_t *tree; + face_t *face; + int i; + int count; - Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" ); + Sys_FPrintf( SYS_VRB, "--- FaceBSP ---\n" ); - tree = AllocTree (); + tree = AllocTree(); count = 0; - for( face = list; face != NULL; face = face->next ) + for ( face = list; face != NULL; face = face->next ) { count++; - for( i = 0; i < face->w->numpoints; i++ ) + for ( i = 0; i < face->w->numpoints; i++ ) { AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs ); } } Sys_FPrintf( SYS_VRB, "%9d faces\n", count ); - for( i = 0; i < nummapplanes; i++) - { - mapplanes[ i ].counter=0; - } + for ( i = 0; i < nummapplanes; i++ ) + { + mapplanes[ i ].counter = 0; + } tree->headnode = AllocNode(); VectorCopy( tree->mins, tree->headnode->mins ); VectorCopy( tree->maxs, tree->headnode->maxs ); c_faceLeafs = 0; - BuildFaceTree_r ( tree->headnode, list ); + BuildFaceTree_r( tree->headnode, list ); Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs ); @@ -375,116 +377,137 @@ tree_t *FaceBSP( face_t *list ) { /* -MakeStructuralBSPFaceList() -get structural brush faces -*/ - -face_t *MakeStructuralBSPFaceList( brush_t *list ) -{ - brush_t *b; - int i; - side_t *s; - winding_t *w; - face_t *f, *flist; - - + MakeStructuralBSPFaceList() + get structural brush faces + */ + +face_t *MakeStructuralBSPFaceList( brush_t *list ){ + brush_t *b; + int i; + side_t *s; + winding_t *w; + face_t *f, *flist; + + flist = NULL; - for( b = list; b != NULL; b = b->next ) + for ( b = list; b != NULL; b = b->next ) { - if( b->detail ) + if ( !deepBSP && b->detail ) { continue; - - for( i = 0; i < b->numsides; i++ ) + } + + for ( i = 0; i < b->numsides; i++ ) { /* get side and winding */ s = &b->sides[ i ]; w = s->winding; - if( w == NULL ) + if ( w == NULL ) { continue; - + } + /* ydnar: skip certain faces */ - if( s->compileFlags & C_SKIP ) + if ( s->compileFlags & C_SKIP ) { continue; - + } + /* allocate a face */ f = AllocBspFace(); f->w = CopyWinding( w ); f->planenum = s->planenum & ~1; - f->compileFlags = s->compileFlags; /* ydnar */ - + f->compileFlags = s->compileFlags; /* ydnar */ + if ( b->detail ) { + f->compileFlags |= C_DETAIL; + } + /* ydnar: set priority */ f->priority = 0; - if( f->compileFlags & C_HINT ) + if ( f->compileFlags & C_HINT ) { f->priority += HINT_PRIORITY; - if( f->compileFlags & C_ANTIPORTAL ) + } + if ( f->compileFlags & C_ANTIPORTAL ) { f->priority += ANTIPORTAL_PRIORITY; - if( f->compileFlags & C_AREAPORTAL ) + } + if ( f->compileFlags & C_AREAPORTAL ) { f->priority += AREAPORTAL_PRIORITY; - + } + if ( f->compileFlags & C_DETAIL ) { + f->priority += DETAIL_PRIORITY; + } + /* get next face */ f->next = flist; flist = f; } } - + return flist; } /* -MakeVisibleBSPFaceList() -get visible brush faces -*/ - -face_t *MakeVisibleBSPFaceList( brush_t *list ) -{ - brush_t *b; - int i; - side_t *s; - winding_t *w; - face_t *f, *flist; - - + MakeVisibleBSPFaceList() + get visible brush faces + */ + +face_t *MakeVisibleBSPFaceList( brush_t *list ){ + brush_t *b; + int i; + side_t *s; + winding_t *w; + face_t *f, *flist; + + flist = NULL; - for( b = list; b != NULL; b = b->next ) + for ( b = list; b != NULL; b = b->next ) { - if( b->detail ) + if ( !deepBSP && b->detail ) { continue; - - for( i = 0; i < b->numsides; i++ ) + } + + for ( i = 0; i < b->numsides; i++ ) { /* get side and winding */ s = &b->sides[ i ]; w = s->visibleHull; - if( w == NULL ) + if ( w == NULL ) { continue; - + } + /* ydnar: skip certain faces */ - if( s->compileFlags & C_SKIP ) + if ( s->compileFlags & C_SKIP ) { continue; - + } + /* allocate a face */ f = AllocBspFace(); f->w = CopyWinding( w ); f->planenum = s->planenum & ~1; - f->compileFlags = s->compileFlags; /* ydnar */ - + f->compileFlags = s->compileFlags; /* ydnar */ + if ( b->detail ) { + f->compileFlags |= C_DETAIL; + } + /* ydnar: set priority */ f->priority = 0; - if( f->compileFlags & C_HINT ) + if ( f->compileFlags & C_HINT ) { f->priority += HINT_PRIORITY; - if( f->compileFlags & C_ANTIPORTAL ) + } + if ( f->compileFlags & C_ANTIPORTAL ) { f->priority += ANTIPORTAL_PRIORITY; - if( f->compileFlags & C_AREAPORTAL ) + } + if ( f->compileFlags & C_AREAPORTAL ) { f->priority += AREAPORTAL_PRIORITY; - + } + if ( f->compileFlags & C_DETAIL ) { + f->priority += DETAIL_PRIORITY; + } + /* get next face */ f->next = flist; flist = f; } } - + return flist; } -