X-Git-Url: http://de.git.xonotic.org/?p=xonotic%2Fnetradiant.git;a=blobdiff_plain;f=tools%2Fquake3%2Fq3map2%2Fbrush.c;h=4e3a37a05226ef44b38cd86967aaebe5ee9616d4;hp=44e99db7fce83ec6751eae93289ef3032224ce71;hb=fed7a21e608f1842ccd6381885c5a473a32165f2;hpb=12b372f89ce109a4db9d510884fbe7d05af79870 diff --git a/tools/quake3/q3map2/brush.c b/tools/quake3/q3map2/brush.c index 44e99db7..4e3a37a0 100644 --- a/tools/quake3/q3map2/brush.c +++ b/tools/quake3/q3map2/brush.c @@ -1,30 +1,30 @@ /* ------------------------------------------------------------------------------- -Copyright (C) 1999-2006 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." -------------------------------------------------------------------------------- */ + ------------------------------------------------------------------------------- */ @@ -40,24 +40,24 @@ several games based on the Quake III Arena engine, in the form of "Q3Map2." /* ------------------------------------------------------------------------------- -functions + functions -------------------------------------------------------------------------------- */ + ------------------------------------------------------------------------------- */ /* -AllocSideRef() - ydnar -allocates and assigns a brush side reference -*/ + AllocSideRef() - ydnar + allocates and assigns a brush side reference + */ -sideRef_t *AllocSideRef( side_t *side, sideRef_t *next ) -{ +sideRef_t *AllocSideRef( side_t *side, sideRef_t *next ){ sideRef_t *sideRef; - - + + /* dummy check */ - if( side == NULL ) + if ( side == NULL ) { return next; - + } + /* allocate and return */ sideRef = safe_malloc( sizeof( *sideRef ) ); sideRef->side = side; @@ -68,17 +68,16 @@ sideRef_t *AllocSideRef( side_t *side, sideRef_t *next ) /* -CountBrushList() -counts the number of brushes in a brush linked list -*/ - -int CountBrushList( brush_t *brushes ) -{ - int c = 0; - - + CountBrushList() + counts the number of brushes in a brush linked list + */ + +int CountBrushList( brush_t *brushes ){ + int c = 0; + + /* count brushes */ - for( brushes; brushes != NULL; brushes = brushes->next ) + for ( ; brushes != NULL; brushes = brushes->next ) c++; return c; } @@ -86,25 +85,26 @@ int CountBrushList( brush_t *brushes ) /* -AllocBrush() -allocates a new brush -*/ - -brush_t *AllocBrush( int numSides ) -{ - brush_t *bb; - int c; - - + AllocBrush() + allocates a new brush + */ + +brush_t *AllocBrush( int numSides ){ + brush_t *bb; + size_t c; + + /* allocate and clear */ - if( numSides <= 0 ) + if ( numSides <= 0 ) { Error( "AllocBrush called with numsides = %d", numSides ); - c = (int) &(((brush_t*) 0)->sides[ numSides ]); + } + c = (size_t)&( ( (brush_t*) 0 )->sides[ numSides ] ); bb = safe_malloc( c ); memset( bb, 0, c ); - if( numthreads == 1 ) + if ( numthreads == 1 ) { numActiveBrushes++; - + } + /* return it */ return bb; } @@ -112,86 +112,85 @@ brush_t *AllocBrush( int numSides ) /* -FreeBrush() -frees a single brush and all sides/windings -*/ - -void FreeBrush( brush_t *b ) -{ - int i; - - + FreeBrush() + frees a single brush and all sides/windings + */ + +void FreeBrush( brush_t *b ){ + int i; + + /* error check */ - if( *((int*) b) == 0xFEFEFEFE ) - { + if ( *( (unsigned int*) b ) == 0xFEFEFEFE ) { Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" ); return; } - + /* free brush sides */ - for( i = 0; i < b->numsides; i++ ) - if( b->sides[i].winding != NULL ) + for ( i = 0; i < b->numsides; i++ ) + if ( b->sides[i].winding != NULL ) { FreeWinding( b->sides[ i ].winding ); - + } + /* ydnar: overwrite it */ - memset( b, 0xFE, (int) &(((brush_t*) 0)->sides[ b->numsides ]) ); - *((int*) b) = 0xFEFEFEFE; - + memset( b, 0xFE, (size_t)&( ( (brush_t*) 0 )->sides[ b->numsides ] ) ); + *( (unsigned int*) b ) = 0xFEFEFEFE; + /* free it */ free( b ); - if( numthreads == 1 ) + if ( numthreads == 1 ) { numActiveBrushes--; + } } /* -FreeBrushList() -frees a linked list of brushes -*/ - -void FreeBrushList( brush_t *brushes ) -{ - brush_t *next; - - + FreeBrushList() + frees a linked list of brushes + */ + +void FreeBrushList( brush_t *brushes ){ + brush_t *next; + + /* walk brush list */ - for( brushes; brushes != NULL; brushes = next ) + for ( ; brushes != NULL; brushes = next ) { next = brushes->next; FreeBrush( brushes ); - } + } } /* -CopyBrush() -duplicates the brush, sides, and windings -*/ - -brush_t *CopyBrush( brush_t *brush ) -{ - brush_t *newBrush; - int size; - int i; - - + CopyBrush() + duplicates the brush, sides, and windings + */ + +brush_t *CopyBrush( brush_t *brush ){ + brush_t *newBrush; + size_t size; + int i; + + /* copy brush */ - size = (int) &(((brush_t*) 0)->sides[ brush->numsides ]); + size = (size_t)&( ( (brush_t*) 0 )->sides[ brush->numsides ] ); newBrush = AllocBrush( brush->numsides ); memcpy( newBrush, brush, size ); - + /* ydnar: nuke linked list */ newBrush->next = NULL; - + /* copy sides */ - for( i = 0; i < brush->numsides; i++ ) + for ( i = 0; i < brush->numsides; i++ ) { - if( brush->sides[ i ].winding != NULL ) + if ( brush->sides[ i ].winding != NULL ) { newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding ); + } } - + /* return it */ return newBrush; } @@ -200,33 +199,34 @@ brush_t *CopyBrush( brush_t *brush ) /* -BoundBrush() -sets the mins/maxs based on the windings -returns false if the brush doesn't enclose a valid volume -*/ - -qboolean BoundBrush( brush_t *brush ) -{ - int i, j; - winding_t *w; - - + BoundBrush() + sets the mins/maxs based on the windings + returns false if the brush doesn't enclose a valid volume + */ + +qboolean BoundBrush( brush_t *brush ){ + int i, j; + winding_t *w; + + ClearBounds( brush->mins, brush->maxs ); - for( i = 0; i < brush->numsides; i++ ) + for ( i = 0; i < brush->numsides; i++ ) { w = brush->sides[ i ].winding; - if( w == NULL ) + if ( w == NULL ) { continue; - for( j = 0; j < w->numpoints; j++ ) + } + for ( j = 0; j < w->numpoints; j++ ) AddPointToBounds( w->p[ j ], brush->mins, brush->maxs ); } - - for( i = 0; i < 3; i++ ) + + for ( i = 0; i < 3; i++ ) { - if( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] ) + if ( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] ) { return qfalse; + } } - + return qtrue; } @@ -234,160 +234,311 @@ qboolean BoundBrush( brush_t *brush ) /* -SnapWeldVector() - ydnar -welds two vec3_t's into a third, taking into account nearest-to-integer -instead of averaging -*/ - -#define SNAP_EPSILON 0.01 - -void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out ) -{ - int i; - vec_t ai, bi, outi; - - + SnapWeldVector() - ydnar + welds two vec3_t's into a third, taking into account nearest-to-integer + instead of averaging + */ + +#define SNAP_EPSILON 0.01 + +void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out ){ + int i; + vec_t ai, bi, outi; + + /* dummy check */ - if( a == NULL || b == NULL || out == NULL ) + if ( a == NULL || b == NULL || out == NULL ) { return; - + } + /* do each element */ - for( i = 0; i < 3; i++ ) + for ( i = 0; i < 3; i++ ) { /* round to integer */ ai = Q_rint( a[ i ] ); - bi = Q_rint( a[ i ] ); - + bi = Q_rint( b[ i ] ); + /* prefer exact integer */ - if( ai == a[ i ] ) + if ( ai == a[ i ] ) { out[ i ] = a[ i ]; - else if( bi == b[ i ] ) + } + else if ( bi == b[ i ] ) { out[ i ] = b[ i ]; + } /* use nearest */ - else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) ) + else if ( fabs( ai - a[ i ] ) < fabs( bi - b[ i ] ) ) { out[ i ] = a[ i ]; - else + } + else{ out[ i ] = b[ i ]; - + } + /* snap */ outi = Q_rint( out[ i ] ); - if( fabs( outi - out[ i ] ) <= SNAP_EPSILON ) + if ( fabs( outi - out[ i ] ) <= SNAP_EPSILON ) { out[ i ] = outi; + } } } +/* + ================== + SnapWeldVectorAccu + + Welds two vectors into a third, taking into account nearest-to-integer + instead of averaging. + ================== + */ +void SnapWeldVectorAccu( vec3_accu_t a, vec3_accu_t b, vec3_accu_t out ){ + // I'm just preserving what I think was the intended logic of the original + // SnapWeldVector(). I'm not actually sure where this function should even + // be used. I'd like to know which kinds of problems this function addresses. + + // TODO: I thought we're snapping all coordinates to nearest 1/8 unit? + // So what is natural about snapping to the nearest integer? Maybe we should + // be snapping to the nearest 1/8 unit instead? + + int i; + vec_accu_t ai, bi, ad, bd; + + if ( a == NULL || b == NULL || out == NULL ) { + Error( "SnapWeldVectorAccu: NULL argument" ); + } + for ( i = 0; i < 3; i++ ) + { + ai = Q_rintAccu( a[i] ); + bi = Q_rintAccu( b[i] ); + ad = fabs( ai - a[i] ); + bd = fabs( bi - b[i] ); + + if ( ad < bd ) { + if ( ad < SNAP_EPSILON ) { + out[i] = ai; + } + else{out[i] = a[i]; } + } + else + { + if ( bd < SNAP_EPSILON ) { + out[i] = bi; + } + else{out[i] = b[i]; } + } + } +} /* -FixWinding() - ydnar -removes degenerate edges from a winding -returns qtrue if the winding is valid -*/ - -#define DEGENERATE_EPSILON 0.1 - -qboolean FixWinding( winding_t *w ) -{ - qboolean valid = qtrue; - int i, j, k; - vec3_t vec; - float dist; - - + FixWinding() - ydnar + removes degenerate edges from a winding + returns qtrue if the winding is valid + */ + +#define DEGENERATE_EPSILON 0.1 + +qboolean FixWinding( winding_t *w ){ + qboolean valid = qtrue; + int i, j, k; + vec3_t vec; + float dist; + + /* dummy check */ - if( !w ) + if ( !w ) { return qfalse; - + } + /* check all verts */ - for( i = 0; i < w->numpoints; i++ ) + for ( i = 0; i < w->numpoints; i++ ) { /* don't remove points if winding is a triangle */ - if( w->numpoints == 3 ) + if ( w->numpoints == 3 ) { return valid; - + } + /* get second point index */ - j = (i + 1) % w->numpoints; - + j = ( i + 1 ) % w->numpoints; + /* degenerate edge? */ VectorSubtract( w->p[ i ], w->p[ j ], vec ); dist = VectorLength( vec ); - if( dist < DEGENERATE_EPSILON ) - { + if ( dist < DEGENERATE_EPSILON ) { valid = qfalse; //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" ); - + /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */ SnapWeldVector( w->p[ i ], w->p[ j ], vec ); VectorCopy( vec, w->p[ i ] ); //VectorAdd( w->p[ i ], w->p[ j ], vec ); //VectorScale( vec, 0.5, w->p[ i ] ); - + /* move the remaining verts */ - for( k = i + 2; k < w->numpoints; k++ ) + for ( k = i + 2; k < w->numpoints; k++ ) { VectorCopy( w->p[ k ], w->p[ k - 1 ] ); } w->numpoints--; } } - + /* one last check and return */ - if( w->numpoints < 3 ) + if ( w->numpoints < 3 ) { valid = qfalse; + } return valid; } +/* + ================== + FixWindingAccu + + Removes degenerate edges (edges that are too short) from a winding. + Returns qtrue if the winding has been altered by this function. + Returns qfalse if the winding is untouched by this function. + + It's advised that you check the winding after this function exits to make + sure it still has at least 3 points. If that is not the case, the winding + cannot be considered valid. The winding may degenerate to one or two points + if the some of the winding's points are close together. + ================== + */ +qboolean FixWindingAccu( winding_accu_t *w ){ + int i, j, k; + vec3_accu_t vec; + vec_accu_t dist; + qboolean done, altered; + + if ( w == NULL ) { + Error( "FixWindingAccu: NULL argument" ); + } + altered = qfalse; + while ( qtrue ) + { + if ( w->numpoints < 2 ) { + break; // Don't remove the only remaining point. + } + done = qtrue; + for ( i = 0; i < w->numpoints; i++ ) + { + j = ( ( ( i + 1 ) == w->numpoints ) ? 0 : ( i + 1 ) ); + + VectorSubtractAccu( w->p[i], w->p[j], vec ); + dist = VectorLengthAccu( vec ); + if ( dist < DEGENERATE_EPSILON ) { + // TODO: I think the "snap weld vector" was written before + // some of the math precision fixes, and its purpose was + // probably to address math accuracy issues. We can think + // about changing the logic here. Maybe once plane distance + // gets 64 bits, we can look at it then. + SnapWeldVectorAccu( w->p[i], w->p[j], vec ); + VectorCopyAccu( vec, w->p[i] ); + for ( k = j + 1; k < w->numpoints; k++ ) + { + VectorCopyAccu( w->p[k], w->p[k - 1] ); + } + w->numpoints--; + altered = qtrue; + // The only way to finish off fixing the winding consistently and + // accurately is by fixing the winding all over again. For example, + // the point at index i and the point at index i-1 could now be + // less than the epsilon distance apart. There are too many special + // case problems we'd need to handle if we didn't start from the + // beginning. + done = qfalse; + break; // This will cause us to return to the "while" loop. + } + } + if ( done ) { + break; + } + } - + return altered; +} /* -CreateBrushWindings() -makes basewindigs for sides and mins/maxs for the brush -returns false if the brush doesn't enclose a valid volume -*/ - -qboolean CreateBrushWindings( brush_t *brush ) -{ - int i, j; - winding_t *w; - side_t *side; - plane_t *plane; - - + CreateBrushWindings() + makes basewindigs for sides and mins/maxs for the brush + returns false if the brush doesn't enclose a valid volume + */ + +qboolean CreateBrushWindings( brush_t *brush ){ + int i, j; +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + winding_accu_t *w; +#else + winding_t *w; +#endif + side_t *side; + plane_t *plane; + + /* walk the list of brush sides */ - for( i = 0; i < brush->numsides; i++ ) + for ( i = 0; i < brush->numsides; i++ ) { /* get side and plane */ side = &brush->sides[ i ]; plane = &mapplanes[ side->planenum ]; - + /* make huge winding */ +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + w = BaseWindingForPlaneAccu( plane->normal, plane->dist ); +#else w = BaseWindingForPlane( plane->normal, plane->dist ); - +#endif + /* walk the list of brush sides */ - for( j = 0; j < brush->numsides && w != NULL; j++ ) + for ( j = 0; j < brush->numsides && w != NULL; j++ ) { - if( i == j ) + if ( i == j ) { continue; - if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) ) - continue; /* back side clipaway */ - if( brush->sides[ j ].bevel ) + } + if ( brush->sides[ j ].planenum == ( brush->sides[ i ].planenum ^ 1 ) ) { + continue; /* back side clipaway */ + } + if ( brush->sides[ j ].bevel ) { continue; + } plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ]; +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + ChopWindingInPlaceAccu( &w, plane->normal, plane->dist, 0 ); +#else ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON ); - +#endif + /* ydnar: fix broken windings that would generate trifans */ +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + // I think it's better to FixWindingAccu() once after we chop with all planes + // so that error isn't multiplied. There is nothing natural about welding + // the points unless they are the final endpoints. ChopWindingInPlaceAccu() + // is able to handle all kinds of degenerate windings. +#else FixWinding( w ); +#endif } - + /* set side winding */ +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + if ( w != NULL ) { + FixWindingAccu( w ); + if ( w->numpoints < 3 ) { + FreeWindingAccu( w ); + w = NULL; + } + } + side->winding = ( w ? CopyWindingAccuToRegular( w ) : NULL ); + if ( w ) { + FreeWindingAccu( w ); + } +#else side->winding = w; +#endif } - + /* find brush bounds */ return BoundBrush( brush ); } @@ -396,80 +547,82 @@ qboolean CreateBrushWindings( brush_t *brush ) /* -================== -BrushFromBounds - -Creates a new axial brush -================== -*/ -brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs) -{ - brush_t *b; - int i; - vec3_t normal; - vec_t dist; - - b = AllocBrush (6); + ================== + BrushFromBounds + + Creates a new axial brush + ================== + */ +brush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){ + brush_t *b; + int i; + vec3_t normal; + vec_t dist; + + b = AllocBrush( 6 ); b->numsides = 6; - for (i=0 ; i<3 ; i++) + for ( i = 0 ; i < 3 ; i++ ) { - VectorClear (normal); + VectorClear( normal ); normal[i] = 1; dist = maxs[i]; - b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs ); + b->sides[i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &maxs ); normal[i] = -1; dist = -mins[i]; - b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins ); + b->sides[3 + i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &mins ); } - CreateBrushWindings (b); + CreateBrushWindings( b ); return b; } /* -================== -BrushVolume - -================== -*/ -vec_t BrushVolume (brush_t *brush) -{ - int i; - winding_t *w; - vec3_t corner; - vec_t d, area, volume; - plane_t *plane; - - if (!brush) + ================== + BrushVolume + + ================== + */ +vec_t BrushVolume( brush_t *brush ){ + int i; + winding_t *w; + vec3_t corner; + vec_t d, area, volume; + plane_t *plane; + + if ( !brush ) { return 0; + } // grab the first valid point as the corner w = NULL; - for (i=0 ; inumsides ; i++) + for ( i = 0 ; i < brush->numsides ; i++ ) { w = brush->sides[i].winding; - if (w) + if ( w ) { break; + } } - if (!w) + if ( !w ) { return 0; - VectorCopy (w->p[0], corner); + } + VectorCopy( w->p[0], corner ); // make tetrahedrons to all other faces volume = 0; - for ( ; inumsides ; i++) + for ( ; i < brush->numsides ; i++ ) { w = brush->sides[i].winding; - if (!w) + if ( !w ) { continue; + } plane = &mapplanes[brush->sides[i].planenum]; - d = -(DotProduct (corner, plane->normal) - plane->dist); - area = WindingArea (w); - volume += d*area; + d = -( DotProduct( corner, plane->normal ) - plane->dist ); + area = WindingArea( w ); + volume += d * area; } volume /= 3; @@ -479,164 +632,163 @@ vec_t BrushVolume (brush_t *brush) /* -WriteBSPBrushMap() -writes a map with the split bsp brushes -*/ - -void WriteBSPBrushMap( char *name, brush_t *list ) -{ - FILE *f; - side_t *s; - int i; - winding_t *w; - - + WriteBSPBrushMap() + writes a map with the split bsp brushes + */ + +void WriteBSPBrushMap( char *name, brush_t *list ){ + FILE *f; + side_t *s; + int i; + winding_t *w; + + /* note it */ Sys_Printf( "Writing %s\n", name ); - + /* open the map file */ f = fopen( name, "wb" ); - if( f == NULL ) + if ( f == NULL ) { Error( "Can't write %s\b", name ); + } - fprintf (f, "{\n\"classname\" \"worldspawn\"\n"); + fprintf( f, "{\n\"classname\" \"worldspawn\"\n" ); - for ( ; list ; list=list->next ) + for ( ; list ; list = list->next ) { - fprintf (f, "{\n"); - for (i=0,s=list->sides ; inumsides ; i++,s++) + fprintf( f, "{\n" ); + for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ ) { - w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist); + // TODO: See if we can use a smaller winding to prevent resolution loss. + // Is WriteBSPBrushMap() used only to decompile maps? + w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist ); - fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]); - fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]); - fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]); + fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] ); + fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] ); + fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] ); - fprintf (f, "notexture 0 0 0 1 1\n" ); - FreeWinding (w); + fprintf( f, "notexture 0 0 0 1 1\n" ); + FreeWinding( w ); } - fprintf (f, "}\n"); + fprintf( f, "}\n" ); } - fprintf (f, "}\n"); + fprintf( f, "}\n" ); - fclose (f); + fclose( f ); } /* -FilterBrushIntoTree_r() -adds brush reference to any intersecting bsp leafnode -*/ - -int FilterBrushIntoTree_r( brush_t *b, node_t *node ) -{ - brush_t *front, *back; - int c; - - + FilterBrushIntoTree_r() + adds brush reference to any intersecting bsp leafnode + */ + +int FilterBrushIntoTree_r( brush_t *b, node_t *node ){ + brush_t *front, *back; + int c; + + /* dummy check */ - if( b == NULL ) + if ( b == NULL ) { return 0; - + } + /* add it to the leaf list */ - if( node->planenum == PLANENUM_LEAF ) - { + if ( node->planenum == PLANENUM_LEAF ) { /* something somewhere is hammering brushlist */ b->next = node->brushlist; node->brushlist = b; - + /* classify the leaf by the structural brush */ - if( !b->detail ) - { - if( b->opaque ) - { + if ( !b->detail ) { + if ( b->opaque ) { node->opaque = qtrue; node->areaportal = qfalse; } - else if( b->compileFlags & C_AREAPORTAL ) - { - if( !node->opaque ) + else if ( b->compileFlags & C_AREAPORTAL ) { + if ( !node->opaque ) { node->areaportal = qtrue; + } } } - + return 1; } - + /* split it by the node plane */ c = b->numsides; SplitBrush( b, node->planenum, &front, &back ); FreeBrush( b ); - + c = 0; c += FilterBrushIntoTree_r( front, node->children[ 0 ] ); c += FilterBrushIntoTree_r( back, node->children[ 1 ] ); - + return c; } /* -FilterDetailBrushesIntoTree -fragment all the detail brushes into the structural leafs -*/ - -void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ) -{ - brush_t *b, *newb; - int r; - int c_unique, c_clusters; - int i; - - + FilterDetailBrushesIntoTree + fragment all the detail brushes into the structural leafs + */ + +void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ){ + brush_t *b, *newb; + int r; + int c_unique, c_clusters; + int i; + + /* note it */ Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" ); - + /* walk the list of brushes */ c_unique = 0; c_clusters = 0; - for( b = e->brushes; b; b = b->next ) + for ( b = e->brushes; b; b = b->next ) { - if( !b->detail ) + if ( !b->detail ) { continue; + } c_unique++; newb = CopyBrush( b ); r = FilterBrushIntoTree_r( newb, tree->headnode ); c_clusters += r; - + /* mark all sides as visible so drawsurfs are created */ - if( r ) - { - for( i = 0; i < b->numsides; i++ ) + if ( r ) { + for ( i = 0; i < b->numsides; i++ ) { - if( b->sides[ i ].winding ) + if ( b->sides[ i ].winding ) { b->sides[ i ].visible = qtrue; + } } } } - + /* emit some statistics */ Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique ); Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters ); } /* -===================== -FilterStructuralBrushesIntoTree + ===================== + FilterStructuralBrushesIntoTree -Mark the leafs as opaque and areaportals -===================== -*/ + Mark the leafs as opaque and areaportals + ===================== + */ void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) { - brush_t *b, *newb; - int r; - int c_unique, c_clusters; - int i; + brush_t *b, *newb; + int r; + int c_unique, c_clusters; + int i; - Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n"); + Sys_FPrintf( SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n" ); c_unique = 0; c_clusters = 0; @@ -658,7 +810,7 @@ void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) { } } } - + /* emit some statistics */ Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique ); Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters ); @@ -667,90 +819,87 @@ void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) { /* -================ -AllocTree -================ -*/ -tree_t *AllocTree (void) -{ - tree_t *tree; - - tree = safe_malloc(sizeof(*tree)); - memset (tree, 0, sizeof(*tree)); - ClearBounds (tree->mins, tree->maxs); + ================ + AllocTree + ================ + */ +tree_t *AllocTree( void ){ + tree_t *tree; + + tree = safe_malloc( sizeof( *tree ) ); + memset( tree, 0, sizeof( *tree ) ); + ClearBounds( tree->mins, tree->maxs ); return tree; } /* -================ -AllocNode -================ -*/ -node_t *AllocNode (void) -{ - node_t *node; + ================ + AllocNode + ================ + */ +node_t *AllocNode( void ){ + node_t *node; - node = safe_malloc(sizeof(*node)); - memset (node, 0, sizeof(*node)); + node = safe_malloc( sizeof( *node ) ); + memset( node, 0, sizeof( *node ) ); return node; } /* -================ -WindingIsTiny - -Returns true if the winding would be crunched out of -existance by the vertex snapping. -================ -*/ -#define EDGE_LENGTH 0.2 -qboolean WindingIsTiny (winding_t *w) -{ + ================ + WindingIsTiny + + Returns true if the winding would be crunched out of + existance by the vertex snapping. + ================ + */ +#define EDGE_LENGTH 0.2 +qboolean WindingIsTiny( winding_t *w ){ /* - if (WindingArea (w) < 1) - return qtrue; - return qfalse; -*/ - int i, j; - vec_t len; - vec3_t delta; - int edges; + if (WindingArea (w) < 1) + return qtrue; + return qfalse; + */ + int i, j; + vec_t len; + vec3_t delta; + int edges; edges = 0; - for (i=0 ; inumpoints ; i++) + for ( i = 0 ; i < w->numpoints ; i++ ) { - j = i == w->numpoints - 1 ? 0 : i+1; - VectorSubtract (w->p[j], w->p[i], delta); - len = VectorLength (delta); - if (len > EDGE_LENGTH) - { - if (++edges == 3) + j = i == w->numpoints - 1 ? 0 : i + 1; + VectorSubtract( w->p[j], w->p[i], delta ); + len = VectorLength( delta ); + if ( len > EDGE_LENGTH ) { + if ( ++edges == 3 ) { return qfalse; + } } } return qtrue; } /* -================ -WindingIsHuge - -Returns true if the winding still has one of the points -from basewinding for plane -================ -*/ -qboolean WindingIsHuge (winding_t *w) -{ - int i, j; - - for (i=0 ; inumpoints ; i++) + ================ + WindingIsHuge + + Returns true if the winding still has one of the points + from basewinding for plane + ================ + */ +qboolean WindingIsHuge( winding_t *w ){ + int i, j; + + for ( i = 0 ; i < w->numpoints ; i++ ) { - for (j=0 ; j<3 ; j++) - if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD) + for ( j = 0 ; j < 3 ; j++ ) + if ( w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD ) { return qtrue; + } } return qfalse; } @@ -758,35 +907,33 @@ qboolean WindingIsHuge (winding_t *w) //============================================================ /* -================== -BrushMostlyOnSide - -================== -*/ -int BrushMostlyOnSide (brush_t *brush, plane_t *plane) -{ - int i, j; - winding_t *w; - vec_t d, max; - int side; + ================== + BrushMostlyOnSide + + ================== + */ +int BrushMostlyOnSide( brush_t *brush, plane_t *plane ){ + int i, j; + winding_t *w; + vec_t d, max; + int side; max = 0; side = PSIDE_FRONT; - for (i=0 ; inumsides ; i++) + for ( i = 0 ; i < brush->numsides ; i++ ) { w = brush->sides[i].winding; - if (!w) + if ( !w ) { continue; - for (j=0 ; jnumpoints ; j++) + } + for ( j = 0 ; j < w->numpoints ; j++ ) { - d = DotProduct (w->p[j], plane->normal) - plane->dist; - if (d > max) - { + d = DotProduct( w->p[j], plane->normal ) - plane->dist; + if ( d > max ) { max = d; side = PSIDE_FRONT; } - if (-d > max) - { + if ( -d > max ) { max = -d; side = PSIDE_BACK; } @@ -798,83 +945,87 @@ int BrushMostlyOnSide (brush_t *brush, plane_t *plane) /* -SplitBrush() -generates two new brushes, leaving the original unchanged -*/ - -void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ) -{ - brush_t *b[2]; - int i, j; - winding_t *w, *cw[2], *midwinding; - plane_t *plane, *plane2; - side_t *s, *cs; - float d, d_front, d_back; - - + SplitBrush() + generates two new brushes, leaving the original unchanged + */ + +void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ){ + brush_t *b[2]; + int i, j; + winding_t *w, *cw[2], *midwinding; + plane_t *plane, *plane2; + side_t *s, *cs; + float d, d_front, d_back; + + *front = NULL; *back = NULL; plane = &mapplanes[planenum]; - + // check all points d_front = d_back = 0; - for (i=0 ; inumsides ; i++) + for ( i = 0 ; i < brush->numsides ; i++ ) { w = brush->sides[i].winding; - if (!w) + if ( !w ) { continue; - for (j=0 ; jnumpoints ; j++) + } + for ( j = 0 ; j < w->numpoints ; j++ ) { - d = DotProduct (w->p[j], plane->normal) - plane->dist; - if (d > 0 && d > d_front) + d = DotProduct( w->p[j], plane->normal ) - plane->dist; + if ( d > 0 && d > d_front ) { d_front = d; - if (d < 0 && d < d_back) + } + if ( d < 0 && d < d_back ) { d_back = d; + } } } - - if (d_front < 0.1) // PLANESIDE_EPSILON) - { // only on back + + if ( d_front < 0.1 ) { // PLANESIDE_EPSILON) + // only on back *back = CopyBrush( brush ); return; } - - if (d_back > -0.1) // PLANESIDE_EPSILON) - { // only on front + + if ( d_back > -0.1 ) { // PLANESIDE_EPSILON) + // only on front *front = CopyBrush( brush ); return; } - + // create a new winding from the split plane - w = BaseWindingForPlane (plane->normal, plane->dist); - for (i=0 ; inumsides && w ; i++) + w = BaseWindingForPlane( plane->normal, plane->dist ); + for ( i = 0 ; i < brush->numsides && w ; i++ ) { plane2 = &mapplanes[brush->sides[i].planenum ^ 1]; - ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON); + ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON); } - if (!w || WindingIsTiny (w) ) - { // the brush isn't really split - int side; + if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split + int side; - side = BrushMostlyOnSide (brush, plane); - if (side == PSIDE_FRONT) - *front = CopyBrush (brush); - if (side == PSIDE_BACK) - *back = CopyBrush (brush); + side = BrushMostlyOnSide( brush, plane ); + if ( side == PSIDE_FRONT ) { + *front = CopyBrush( brush ); + } + if ( side == PSIDE_BACK ) { + *back = CopyBrush( brush ); + } return; } - - if( WindingIsHuge( w ) ) + + if ( WindingIsHuge( w ) ) { Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" ); + } midwinding = w; // split it for real - for (i=0 ; i<2 ; i++) + for ( i = 0 ; i < 2 ; i++ ) { - b[i] = AllocBrush (brush->numsides+1); + b[i] = AllocBrush( brush->numsides + 1 ); memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) ); b[i]->numsides = 0; b[i]->next = NULL; @@ -883,18 +1034,20 @@ void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ) // split all the current windings - for (i=0 ; inumsides ; i++) + for ( i = 0 ; i < brush->numsides ; i++ ) { s = &brush->sides[i]; w = s->winding; - if (!w) + if ( !w ) { continue; - ClipWindingEpsilon (w, plane->normal, plane->dist, - 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]); - for (j=0 ; j<2 ; j++) + } + ClipWindingEpsilonStrict( w, plane->normal, plane->dist, + 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] ); /* strict, in parallel case we get the face back because it also is the midwinding */ + for ( j = 0 ; j < 2 ; j++ ) { - if (!cw[j]) + if ( !cw[j] ) { continue; + } cs = &b[j]->sides[b[j]->numsides]; b[j]->numsides++; *cs = *s; @@ -904,75 +1057,67 @@ void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ) // see if we have valid polygons on both sides - for (i=0 ; i<2 ; i++) + for ( i = 0 ; i < 2 ; i++ ) { - BoundBrush (b[i]); - for (j=0 ; j<3 ; j++) - { - if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD) - { - Sys_FPrintf (SYS_VRB,"bogus brush after clip\n"); - break; + if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) { + if ( b[i]->numsides >= 3 ) { + Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" ); } - } - - if (b[i]->numsides < 3 || j < 3) - { - FreeBrush (b[i]); + FreeBrush( b[i] ); b[i] = NULL; } } - - if ( !(b[0] && b[1]) ) - { - if (!b[0] && !b[1]) - Sys_FPrintf (SYS_VRB,"split removed brush\n"); - else - Sys_FPrintf (SYS_VRB,"split not on both sides\n"); - if (b[0]) - { - FreeBrush (b[0]); - *front = CopyBrush (brush); + + if ( !( b[0] && b[1] ) ) { + if ( !b[0] && !b[1] ) { + Sys_FPrintf( SYS_VRB,"split removed brush\n" ); } - if (b[1]) - { - FreeBrush (b[1]); - *back = CopyBrush (brush); + else{ + Sys_FPrintf( SYS_VRB,"split not on both sides\n" ); + } + if ( b[0] ) { + FreeBrush( b[0] ); + *front = CopyBrush( brush ); + } + if ( b[1] ) { + FreeBrush( b[1] ); + *back = CopyBrush( brush ); } return; } - + // add the midwinding to both sides - for (i=0 ; i<2 ; i++) + for ( i = 0 ; i < 2 ; i++ ) { cs = &b[i]->sides[b[i]->numsides]; b[i]->numsides++; - cs->planenum = planenum^i^1; + cs->planenum = planenum ^ i ^ 1; cs->shaderInfo = NULL; - if (i==0) - cs->winding = CopyWinding (midwinding); - else + if ( i == 0 ) { + cs->winding = CopyWinding( midwinding ); + } + else{ cs->winding = midwinding; + } } - + { - vec_t v1; - int i; - - - for (i=0 ; i<2 ; i++) + vec_t v1; + int i; + + + for ( i = 0 ; i < 2 ; i++ ) { - v1 = BrushVolume (b[i]); - if (v1 < 1.0) - { - FreeBrush (b[i]); + v1 = BrushVolume( b[i] ); + if ( v1 < 1.0 ) { + FreeBrush( b[i] ); b[i] = NULL; - // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n"); + // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n"); } } } - + *front = b[0]; *back = b[1]; }