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 ------------------------------------------------------------------------------- */
41 /* -------------------------------------------------------------------------------
45 ------------------------------------------------------------------------------- */
48 AllocSideRef() - ydnar
49 allocates and assigns a brush side reference
52 sideRef_t *AllocSideRef( side_t *side, sideRef_t *next ){
61 /* allocate and return */
62 sideRef = safe_malloc( sizeof( *sideRef ) );
72 counts the number of brushes in a brush linked list
75 int CountBrushList( brush_t *brushes ){
80 for ( ; brushes != NULL; brushes = brushes->next )
92 brush_t *AllocBrush( int numSides ){
96 /* allocate and clear */
97 /*if ( numSides <= 0 ) {
98 Error( "AllocBrush called with numsides = %d", numSides );
100 c = (size_t)&( ( (brush_t*) 0 )->sides[ numSides ] );*/
101 c = sizeof(*bb) + (numSides > 6 ? sizeof(side_t)*(numSides - 6) : 0);
102 bb = safe_malloc0( c );
103 if ( numthreads == 1 ) {
115 frees a single brush and all sides/windings
118 void FreeBrush( brush_t *b ){
123 if ( *( (unsigned int*) b ) == 0xFEFEFEFE ) {
124 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
128 /* free brush sides */
129 for ( i = 0; i < b->numsides; i++ )
130 if ( b->sides[i].winding != NULL ) {
131 FreeWinding( b->sides[ i ].winding );
134 /* ydnar: overwrite it */
135 memset( b, 0xFE, (size_t)&( ( (brush_t*) 0 )->sides[ b->numsides ] ) );
136 *( (unsigned int*) b ) = 0xFEFEFEFE;
140 if ( numthreads == 1 ) {
149 frees a linked list of brushes
152 void FreeBrushList( brush_t *brushes ){
156 /* walk brush list */
157 for ( ; brushes != NULL; brushes = next )
159 next = brushes->next;
160 FreeBrush( brushes );
168 duplicates the brush, sides, and windings
171 brush_t *CopyBrush( brush_t *brush ){
178 size = (size_t)&( ( (brush_t*) 0 )->sides[ brush->numsides ] );
179 newBrush = AllocBrush( brush->numsides );
180 memcpy( newBrush, brush, size );
182 /* ydnar: nuke linked list */
183 newBrush->next = NULL;
186 for ( i = 0; i < brush->numsides; i++ )
188 if ( brush->sides[ i ].winding != NULL ) {
189 newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
202 sets the mins/maxs based on the windings
203 returns false if the brush doesn't enclose a valid volume
206 qboolean BoundBrush( brush_t *brush ){
211 ClearBounds( brush->mins, brush->maxs );
212 for ( i = 0; i < brush->numsides; i++ )
214 w = brush->sides[ i ].winding;
218 for ( j = 0; j < w->numpoints; j++ )
219 AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
222 for ( i = 0; i < 3; i++ )
224 if ( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] ) {
236 SnapWeldVector() - ydnar
237 welds two vec3_t's into a third, taking into account nearest-to-integer
241 #define SNAP_EPSILON 0.01
243 void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out ){
249 if ( a == NULL || b == NULL || out == NULL ) {
253 /* do each element */
254 for ( i = 0; i < 3; i++ )
256 /* round to integer */
257 ai = Q_rint( a[ i ] );
258 bi = Q_rint( b[ i ] );
260 /* prefer exact integer */
261 if ( ai == a[ i ] ) {
264 else if ( bi == b[ i ] ) {
269 else if ( fabs( ai - a[ i ] ) < fabs( bi - b[ i ] ) ) {
277 outi = Q_rint( out[ i ] );
278 if ( fabs( outi - out[ i ] ) <= SNAP_EPSILON ) {
290 Welds two vectors into a third, taking into account nearest-to-integer
291 instead of averaging.
294 void SnapWeldVectorAccu( vec3_accu_t a, vec3_accu_t b, vec3_accu_t out ){
295 // I'm just preserving what I think was the intended logic of the original
296 // SnapWeldVector(). I'm not actually sure where this function should even
297 // be used. I'd like to know which kinds of problems this function addresses.
299 // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
300 // So what is natural about snapping to the nearest integer? Maybe we should
301 // be snapping to the nearest 1/8 unit instead?
304 vec_accu_t ai, bi, ad, bd;
306 if ( a == NULL || b == NULL || out == NULL ) {
307 Error( "SnapWeldVectorAccu: NULL argument" );
310 for ( i = 0; i < 3; i++ )
312 ai = Q_rintAccu( a[i] );
313 bi = Q_rintAccu( b[i] );
314 ad = fabs( ai - a[i] );
315 bd = fabs( bi - b[i] );
318 if ( ad < SNAP_EPSILON ) {
321 else{out[i] = a[i]; }
325 if ( bd < SNAP_EPSILON ) {
328 else{out[i] = b[i]; }
337 removes degenerate edges from a winding
338 returns qtrue if the winding is valid
341 #define DEGENERATE_EPSILON 0.1
343 qboolean FixWinding( winding_t *w ){
344 qboolean valid = qtrue;
355 /* check all verts */
356 for ( i = 0; i < w->numpoints; i++ )
358 /* don't remove points if winding is a triangle */
359 if ( w->numpoints == 3 ) {
363 /* get second point index */
364 j = ( i + 1 ) % w->numpoints;
366 /* degenerate edge? */
367 VectorSubtract( w->p[ i ], w->p[ j ], vec );
368 dist = VectorLength( vec );
369 if ( dist < DEGENERATE_EPSILON ) {
371 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
373 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
374 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
375 VectorCopy( vec, w->p[ i ] );
376 //VectorAdd( w->p[ i ], w->p[ j ], vec );
377 //VectorScale( vec, 0.5, w->p[ i ] );
379 /* move the remaining verts */
380 for ( k = i + 2; k < w->numpoints; k++ )
382 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
388 /* one last check and return */
389 if ( w->numpoints < 3 ) {
399 Removes degenerate edges (edges that are too short) from a winding.
400 Returns qtrue if the winding has been altered by this function.
401 Returns qfalse if the winding is untouched by this function.
403 It's advised that you check the winding after this function exits to make
404 sure it still has at least 3 points. If that is not the case, the winding
405 cannot be considered valid. The winding may degenerate to one or two points
406 if the some of the winding's points are close together.
409 qboolean FixWindingAccu( winding_accu_t *w ){
413 qboolean done, altered;
416 Error( "FixWindingAccu: NULL argument" );
423 if ( w->numpoints < 2 ) {
424 break; // Don't remove the only remaining point.
427 for ( i = 0; i < w->numpoints; i++ )
429 j = ( ( ( i + 1 ) == w->numpoints ) ? 0 : ( i + 1 ) );
431 VectorSubtractAccu( w->p[i], w->p[j], vec );
432 dist = VectorLengthAccu( vec );
433 if ( dist < DEGENERATE_EPSILON ) {
434 // TODO: I think the "snap weld vector" was written before
435 // some of the math precision fixes, and its purpose was
436 // probably to address math accuracy issues. We can think
437 // about changing the logic here. Maybe once plane distance
438 // gets 64 bits, we can look at it then.
439 SnapWeldVectorAccu( w->p[i], w->p[j], vec );
440 VectorCopyAccu( vec, w->p[i] );
441 for ( k = j + 1; k < w->numpoints; k++ )
443 VectorCopyAccu( w->p[k], w->p[k - 1] );
447 // The only way to finish off fixing the winding consistently and
448 // accurately is by fixing the winding all over again. For example,
449 // the point at index i and the point at index i-1 could now be
450 // less than the epsilon distance apart. There are too many special
451 // case problems we'd need to handle if we didn't start from the
454 break; // This will cause us to return to the "while" loop.
467 CreateBrushWindings()
468 makes basewindigs for sides and mins/maxs for the brush
469 returns false if the brush doesn't enclose a valid volume
472 qboolean CreateBrushWindings( brush_t *brush ){
474 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
483 /* walk the list of brush sides */
484 for ( i = 0; i < brush->numsides; i++ )
486 /* get side and plane */
487 side = &brush->sides[ i ];
488 plane = &mapplanes[ side->planenum ];
490 /* make huge winding */
491 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
492 w = BaseWindingForPlaneAccu( plane->normal, plane->dist );
494 w = BaseWindingForPlane( plane->normal, plane->dist );
497 /* walk the list of brush sides */
498 for ( j = 0; j < brush->numsides && w != NULL; j++ )
503 if ( brush->sides[ j ].planenum == ( brush->sides[ i ].planenum ^ 1 ) ) {
504 continue; /* back side clipaway */
506 if ( brush->sides[ j ].bevel ) {
509 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
510 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
511 ChopWindingInPlaceAccu( &w, plane->normal, plane->dist, 0 );
513 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
516 /* ydnar: fix broken windings that would generate trifans */
517 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
518 // I think it's better to FixWindingAccu() once after we chop with all planes
519 // so that error isn't multiplied. There is nothing natural about welding
520 // the points unless they are the final endpoints. ChopWindingInPlaceAccu()
521 // is able to handle all kinds of degenerate windings.
527 /* set side winding */
528 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
531 if ( w->numpoints < 3 ) {
532 FreeWindingAccu( w );
536 side->winding = ( w ? CopyWindingAccuToRegular( w ) : NULL );
538 FreeWindingAccu( w );
545 /* find brush bounds */
546 return BoundBrush( brush );
556 Creates a new axial brush
559 brush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){
567 for ( i = 0 ; i < 3 ; i++ )
569 VectorClear( normal );
572 b->sides[i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &maxs );
576 b->sides[3 + i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &mins );
579 CreateBrushWindings( b );
590 vec_t BrushVolume( brush_t *brush ){
594 vec_t d, area, volume;
601 // grab the first valid point as the corner
604 for ( i = 0 ; i < brush->numsides ; i++ )
606 w = brush->sides[i].winding;
614 VectorCopy( w->p[0], corner );
616 // make tetrahedrons to all other faces
619 for ( ; i < brush->numsides ; i++ )
621 w = brush->sides[i].winding;
625 plane = &mapplanes[brush->sides[i].planenum];
626 d = -( DotProduct( corner, plane->normal ) - plane->dist );
627 area = WindingArea( w );
639 writes a map with the split bsp brushes
642 void WriteBSPBrushMap( char *name, brush_t *list ){
650 Sys_Printf( "Writing %s\n", name );
652 /* open the map file */
653 f = fopen( name, "wb" );
655 Error( "Can't write %s\b", name );
658 fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
660 for ( ; list ; list = list->next )
663 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
665 // TODO: See if we can use a smaller winding to prevent resolution loss.
666 // Is WriteBSPBrushMap() used only to decompile maps?
667 w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
669 fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
670 fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
671 fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
673 fprintf( f, "notexture 0 0 0 1 1\n" );
687 FilterBrushIntoTree_r()
688 adds brush reference to any intersecting bsp leafnode
691 int FilterBrushIntoTree_r( brush_t *b, node_t *node ){
692 brush_t *front, *back;
701 /* add it to the leaf list */
702 if ( node->planenum == PLANENUM_LEAF ) {
703 /* something somewhere is hammering brushlist */
704 b->next = node->brushlist;
707 /* classify the leaf by the structural brush */
710 node->opaque = qtrue;
711 node->areaportal = qfalse;
713 else if ( b->compileFlags & C_AREAPORTAL ) {
714 if ( !node->opaque ) {
715 node->areaportal = qtrue;
723 /* split it by the node plane */
725 SplitBrush( b, node->planenum, &front, &back );
729 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
730 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
738 FilterDetailBrushesIntoTree
739 fragment all the detail brushes into the structural leafs
742 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ){
745 int c_unique, c_clusters;
750 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
752 /* walk the list of brushes */
755 for ( b = e->brushes; b; b = b->next )
761 newb = CopyBrush( b );
762 r = FilterBrushIntoTree_r( newb, tree->headnode );
765 /* mark all sides as visible so drawsurfs are created */
767 for ( i = 0; i < b->numsides; i++ )
769 if ( b->sides[ i ].winding ) {
770 b->sides[ i ].visible = qtrue;
776 /* emit some statistics */
777 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
778 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
782 =====================
783 FilterStructuralBrushesIntoTree
785 Mark the leafs as opaque and areaportals
786 =====================
788 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
791 int c_unique, c_clusters;
794 Sys_FPrintf( SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n" );
798 for ( b = e->brushes ; b ; b = b->next ) {
803 newb = CopyBrush( b );
804 r = FilterBrushIntoTree_r( newb, tree->headnode );
807 // mark all sides as visible so drawsurfs are created
809 for ( i = 0 ; i < b->numsides ; i++ ) {
810 if ( b->sides[i].winding ) {
811 b->sides[i].visible = qtrue;
817 /* emit some statistics */
818 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
819 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
829 tree_t *AllocTree( void ){
832 tree = safe_malloc0( sizeof( *tree ) );
833 ClearBounds( tree->mins, tree->maxs );
843 node_t *AllocNode( void ){
846 node = safe_malloc0( sizeof( *node ) );
856 Returns true if the winding would be crunched out of
857 existance by the vertex snapping.
860 #define EDGE_LENGTH 0.2
861 qboolean WindingIsTiny( winding_t *w ){
863 if (WindingArea (w) < 1)
873 for ( i = 0 ; i < w->numpoints ; i++ )
875 j = i == w->numpoints - 1 ? 0 : i + 1;
876 VectorSubtract( w->p[j], w->p[i], delta );
877 len = VectorLength( delta );
878 if ( len > EDGE_LENGTH ) {
879 if ( ++edges == 3 ) {
891 Returns true if the winding still has one of the points
892 from basewinding for plane
895 qboolean WindingIsHuge( winding_t *w ){
898 for ( i = 0 ; i < w->numpoints ; i++ )
900 for ( j = 0 ; j < 3 ; j++ )
901 if ( w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD ) {
908 //============================================================
916 int BrushMostlyOnSide( brush_t *brush, plane_t *plane ){
924 for ( i = 0 ; i < brush->numsides ; i++ )
926 w = brush->sides[i].winding;
930 for ( j = 0 ; j < w->numpoints ; j++ )
932 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
950 generates two new brushes, leaving the original unchanged
953 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ){
956 winding_t *w, *cw[2], *midwinding;
957 plane_t *plane, *plane2;
959 float d, d_front, d_back;
964 plane = &mapplanes[planenum];
967 d_front = d_back = 0;
968 for ( i = 0 ; i < brush->numsides ; i++ )
970 w = brush->sides[i].winding;
974 for ( j = 0 ; j < w->numpoints ; j++ )
976 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
977 if ( d > 0 && d > d_front ) {
980 if ( d < 0 && d < d_back ) {
986 if ( d_front < 0.1 ) { // PLANESIDE_EPSILON)
988 *back = CopyBrush( brush );
992 if ( d_back > -0.1 ) { // PLANESIDE_EPSILON)
994 *front = CopyBrush( brush );
998 // create a new winding from the split plane
999 w = BaseWindingForPlane( plane->normal, plane->dist );
1000 for ( i = 0 ; i < brush->numsides && w ; i++ )
1002 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1003 ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON);
1006 if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split
1009 side = BrushMostlyOnSide( brush, plane );
1010 if ( side == PSIDE_FRONT ) {
1011 *front = CopyBrush( brush );
1013 if ( side == PSIDE_BACK ) {
1014 *back = CopyBrush( brush );
1019 if ( WindingIsHuge( w ) ) {
1020 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1025 // split it for real
1027 for ( i = 0 ; i < 2 ; i++ )
1029 b[i] = AllocBrush( brush->numsides + 1 );
1030 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1033 b[i]->original = brush->original;
1036 // split all the current windings
1038 for ( i = 0 ; i < brush->numsides ; i++ )
1040 s = &brush->sides[i];
1045 /* strict, in parallel case we get the face back because it also is the midwinding */
1046 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1047 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] );
1048 for ( j = 0 ; j < 2 ; j++ )
1053 cs = &b[j]->sides[b[j]->numsides];
1056 cs->winding = cw[j];
1061 // see if we have valid polygons on both sides
1062 for ( i = 0 ; i < 2 ; i++ )
1064 if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) {
1065 if ( b[i]->numsides >= 3 ) {
1066 Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" );
1073 if ( !( b[0] && b[1] ) ) {
1074 if ( !b[0] && !b[1] ) {
1075 Sys_FPrintf( SYS_VRB,"split removed brush\n" );
1078 Sys_FPrintf( SYS_VRB,"split not on both sides\n" );
1082 *front = CopyBrush( brush );
1086 *back = CopyBrush( brush );
1091 // add the midwinding to both sides
1092 for ( i = 0 ; i < 2 ; i++ )
1094 cs = &b[i]->sides[b[i]->numsides];
1097 cs->planenum = planenum ^ i ^ 1;
1098 cs->shaderInfo = NULL;
1100 cs->winding = CopyWinding( midwinding );
1103 cs->winding = midwinding;
1112 for ( i = 0 ; i < 2 ; i++ )
1114 v1 = BrushVolume( b[i] );
1118 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");