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 ){
97 /* allocate and clear */
98 if ( numSides <= 0 ) {
99 Error( "AllocBrush called with numsides = %d", numSides );
101 c = (size_t)&( ( (brush_t*) 0 )->sides[ numSides ] );
102 bb = safe_malloc( c );
104 if ( numthreads == 1 ) {
116 frees a single brush and all sides/windings
119 void FreeBrush( brush_t *b ){
124 if ( *( (unsigned int*) b ) == 0xFEFEFEFE ) {
125 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
129 /* free brush sides */
130 for ( i = 0; i < b->numsides; i++ )
131 if ( b->sides[i].winding != NULL ) {
132 FreeWinding( b->sides[ i ].winding );
135 /* ydnar: overwrite it */
136 memset( b, 0xFE, (size_t)&( ( (brush_t*) 0 )->sides[ b->numsides ] ) );
137 *( (unsigned int*) b ) = 0xFEFEFEFE;
141 if ( numthreads == 1 ) {
150 frees a linked list of brushes
153 void FreeBrushList( brush_t *brushes ){
157 /* walk brush list */
158 for ( ; brushes != NULL; brushes = next )
160 next = brushes->next;
161 FreeBrush( brushes );
169 duplicates the brush, sides, and windings
172 brush_t *CopyBrush( brush_t *brush ){
179 size = (size_t)&( ( (brush_t*) 0 )->sides[ brush->numsides ] );
180 newBrush = AllocBrush( brush->numsides );
181 memcpy( newBrush, brush, size );
183 /* ydnar: nuke linked list */
184 newBrush->next = NULL;
187 for ( i = 0; i < brush->numsides; i++ )
189 if ( brush->sides[ i ].winding != NULL ) {
190 newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
203 sets the mins/maxs based on the windings
204 returns false if the brush doesn't enclose a valid volume
207 qboolean BoundBrush( brush_t *brush ){
212 ClearBounds( brush->mins, brush->maxs );
213 for ( i = 0; i < brush->numsides; i++ )
215 w = brush->sides[ i ].winding;
219 for ( j = 0; j < w->numpoints; j++ )
220 AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
223 for ( i = 0; i < 3; i++ )
225 if ( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] ) {
237 SnapWeldVector() - ydnar
238 welds two vec3_t's into a third, taking into account nearest-to-integer
242 #define SNAP_EPSILON 0.01
244 void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out ){
250 if ( a == NULL || b == NULL || out == NULL ) {
254 /* do each element */
255 for ( i = 0; i < 3; i++ )
257 /* round to integer */
258 ai = Q_rint( a[ i ] );
259 bi = Q_rint( a[ i ] );
261 /* prefer exact integer */
262 if ( ai == a[ i ] ) {
265 else if ( bi == b[ i ] ) {
270 else if ( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) ) {
278 outi = Q_rint( out[ i ] );
279 if ( fabs( outi - out[ i ] ) <= SNAP_EPSILON ) {
289 Welds two vectors into a third, taking into account nearest-to-integer
290 instead of averaging.
293 void SnapWeldVectorAccu( vec3_accu_t a, vec3_accu_t b, vec3_accu_t out ){
294 // I'm just preserving what I think was the intended logic of the original
295 // SnapWeldVector(). I'm not actually sure where this function should even
296 // be used. I'd like to know which kinds of problems this function addresses.
298 // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
299 // So what is natural about snapping to the nearest integer? Maybe we should
300 // be snapping to the nearest 1/8 unit instead?
303 vec_accu_t ai, bi, ad, bd;
305 if ( a == NULL || b == NULL || out == NULL ) {
306 Error( "SnapWeldVectorAccu: NULL argument" );
309 for ( i = 0; i < 3; i++ )
311 ai = Q_rintAccu( a[i] );
312 bi = Q_rintAccu( b[i] );
313 ad = fabs( ai - a[i] );
314 bd = fabs( bi - b[i] );
317 if ( ad < SNAP_EPSILON ) {
320 else{out[i] = a[i]; }
324 if ( bd < SNAP_EPSILON ) {
327 else{out[i] = b[i]; }
334 removes degenerate edges from a winding
335 returns qtrue if the winding is valid
338 #define DEGENERATE_EPSILON 0.1
340 qboolean FixWinding( winding_t *w ){
341 qboolean valid = qtrue;
352 /* check all verts */
353 for ( i = 0; i < w->numpoints; i++ )
355 /* don't remove points if winding is a triangle */
356 if ( w->numpoints == 3 ) {
360 /* get second point index */
361 j = ( i + 1 ) % w->numpoints;
363 /* degenerate edge? */
364 VectorSubtract( w->p[ i ], w->p[ j ], vec );
365 dist = VectorLength( vec );
366 if ( dist < DEGENERATE_EPSILON ) {
368 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
370 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
371 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
372 VectorCopy( vec, w->p[ i ] );
373 //VectorAdd( w->p[ i ], w->p[ j ], vec );
374 //VectorScale( vec, 0.5, w->p[ i ] );
376 /* move the remaining verts */
377 for ( k = i + 2; k < w->numpoints; k++ )
379 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
385 /* one last check and return */
386 if ( w->numpoints < 3 ) {
396 Removes degenerate edges (edges that are too short) from a winding.
397 Returns qtrue if the winding has been altered by this function.
398 Returns qfalse if the winding is untouched by this function.
400 It's advised that you check the winding after this function exits to make
401 sure it still has at least 3 points. If that is not the case, the winding
402 cannot be considered valid. The winding may degenerate to one or two points
403 if the some of the winding's points are close together.
406 qboolean FixWindingAccu( winding_accu_t *w ){
410 qboolean done, altered;
413 Error( "FixWindingAccu: NULL argument" );
420 if ( w->numpoints < 2 ) {
421 break; // Don't remove the only remaining point.
424 for ( i = 0; i < w->numpoints; i++ )
426 j = ( ( ( i + 1 ) == w->numpoints ) ? 0 : ( i + 1 ) );
428 VectorSubtractAccu( w->p[i], w->p[j], vec );
429 dist = VectorLengthAccu( vec );
430 if ( dist < DEGENERATE_EPSILON ) {
431 // TODO: I think the "snap weld vector" was written before
432 // some of the math precision fixes, and its purpose was
433 // probably to address math accuracy issues. We can think
434 // about changing the logic here. Maybe once plane distance
435 // gets 64 bits, we can look at it then.
436 SnapWeldVectorAccu( w->p[i], w->p[j], vec );
437 VectorCopyAccu( vec, w->p[i] );
438 for ( k = j + 1; k < w->numpoints; k++ )
440 VectorCopyAccu( w->p[k], w->p[k - 1] );
444 // The only way to finish off fixing the winding consistently and
445 // accurately is by fixing the winding all over again. For example,
446 // the point at index i and the point at index i-1 could now be
447 // less than the epsilon distance apart. There are too many special
448 // case problems we'd need to handle if we didn't start from the
451 break; // This will cause us to return to the "while" loop.
464 CreateBrushWindings()
465 makes basewindigs for sides and mins/maxs for the brush
466 returns false if the brush doesn't enclose a valid volume
469 qboolean CreateBrushWindings( brush_t *brush ){
471 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
480 /* walk the list of brush sides */
481 for ( i = 0; i < brush->numsides; i++ )
483 /* get side and plane */
484 side = &brush->sides[ i ];
485 plane = &mapplanes[ side->planenum ];
487 /* make huge winding */
488 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
489 w = BaseWindingForPlaneAccu( plane->normal, plane->dist );
491 w = BaseWindingForPlane( plane->normal, plane->dist );
494 /* walk the list of brush sides */
495 for ( j = 0; j < brush->numsides && w != NULL; j++ )
500 if ( brush->sides[ j ].planenum == ( brush->sides[ i ].planenum ^ 1 ) ) {
501 continue; /* back side clipaway */
503 if ( brush->sides[ j ].bevel ) {
506 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
507 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
508 ChopWindingInPlaceAccu( &w, plane->normal, plane->dist, 0 );
510 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
513 /* ydnar: fix broken windings that would generate trifans */
514 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
515 // I think it's better to FixWindingAccu() once after we chop with all planes
516 // so that error isn't multiplied. There is nothing natural about welding
517 // the points unless they are the final endpoints. ChopWindingInPlaceAccu()
518 // is able to handle all kinds of degenerate windings.
524 /* set side winding */
525 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
528 if ( w->numpoints < 3 ) {
529 FreeWindingAccu( w );
533 side->winding = ( w ? CopyWindingAccuToRegular( w ) : NULL );
535 FreeWindingAccu( w );
542 /* find brush bounds */
543 return BoundBrush( brush );
553 Creates a new axial brush
556 brush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){
564 for ( i = 0 ; i < 3 ; i++ )
566 VectorClear( normal );
569 b->sides[i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &maxs );
573 b->sides[3 + i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &mins );
576 CreateBrushWindings( b );
587 vec_t BrushVolume( brush_t *brush ){
591 vec_t d, area, volume;
598 // grab the first valid point as the corner
601 for ( i = 0 ; i < brush->numsides ; i++ )
603 w = brush->sides[i].winding;
611 VectorCopy( w->p[0], corner );
613 // make tetrahedrons to all other faces
616 for ( ; i < brush->numsides ; i++ )
618 w = brush->sides[i].winding;
622 plane = &mapplanes[brush->sides[i].planenum];
623 d = -( DotProduct( corner, plane->normal ) - plane->dist );
624 area = WindingArea( w );
636 writes a map with the split bsp brushes
639 void WriteBSPBrushMap( char *name, brush_t *list ){
647 Sys_Printf( "Writing %s\n", name );
649 /* open the map file */
650 f = fopen( name, "wb" );
652 Error( "Can't write %s\b", name );
655 fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
657 for ( ; list ; list = list->next )
660 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
662 // TODO: See if we can use a smaller winding to prevent resolution loss.
663 // Is WriteBSPBrushMap() used only to decompile maps?
664 w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
666 fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
667 fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
668 fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
670 fprintf( f, "notexture 0 0 0 1 1\n" );
684 FilterBrushIntoTree_r()
685 adds brush reference to any intersecting bsp leafnode
688 int FilterBrushIntoTree_r( brush_t *b, node_t *node ){
689 brush_t *front, *back;
698 /* add it to the leaf list */
699 if ( node->planenum == PLANENUM_LEAF ) {
700 /* something somewhere is hammering brushlist */
701 b->next = node->brushlist;
704 /* classify the leaf by the structural brush */
707 node->opaque = qtrue;
708 node->areaportal = qfalse;
710 else if ( b->compileFlags & C_AREAPORTAL ) {
711 if ( !node->opaque ) {
712 node->areaportal = qtrue;
720 /* split it by the node plane */
722 SplitBrush( b, node->planenum, &front, &back );
726 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
727 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
735 FilterDetailBrushesIntoTree
736 fragment all the detail brushes into the structural leafs
739 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ){
742 int c_unique, c_clusters;
747 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
749 /* walk the list of brushes */
752 for ( b = e->brushes; b; b = b->next )
758 newb = CopyBrush( b );
759 r = FilterBrushIntoTree_r( newb, tree->headnode );
762 /* mark all sides as visible so drawsurfs are created */
764 for ( i = 0; i < b->numsides; i++ )
766 if ( b->sides[ i ].winding ) {
767 b->sides[ i ].visible = qtrue;
773 /* emit some statistics */
774 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
775 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
779 =====================
780 FilterStructuralBrushesIntoTree
782 Mark the leafs as opaque and areaportals
783 =====================
785 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
788 int c_unique, c_clusters;
791 Sys_FPrintf( SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n" );
795 for ( b = e->brushes ; b ; b = b->next ) {
800 newb = CopyBrush( b );
801 r = FilterBrushIntoTree_r( newb, tree->headnode );
804 // mark all sides as visible so drawsurfs are created
806 for ( i = 0 ; i < b->numsides ; i++ ) {
807 if ( b->sides[i].winding ) {
808 b->sides[i].visible = qtrue;
814 /* emit some statistics */
815 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
816 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
826 tree_t *AllocTree( void ){
829 tree = safe_malloc( sizeof( *tree ) );
830 memset( tree, 0, sizeof( *tree ) );
831 ClearBounds( tree->mins, tree->maxs );
841 node_t *AllocNode( void ){
844 node = safe_malloc( sizeof( *node ) );
845 memset( node, 0, sizeof( *node ) );
855 Returns true if the winding would be crunched out of
856 existance by the vertex snapping.
859 #define EDGE_LENGTH 0.2
860 qboolean WindingIsTiny( winding_t *w ){
862 if (WindingArea (w) < 1)
872 for ( i = 0 ; i < w->numpoints ; i++ )
874 j = i == w->numpoints - 1 ? 0 : i + 1;
875 VectorSubtract( w->p[j], w->p[i], delta );
876 len = VectorLength( delta );
877 if ( len > EDGE_LENGTH ) {
878 if ( ++edges == 3 ) {
890 Returns true if the winding still has one of the points
891 from basewinding for plane
894 qboolean WindingIsHuge( winding_t *w ){
897 for ( i = 0 ; i < w->numpoints ; i++ )
899 for ( j = 0 ; j < 3 ; j++ )
900 if ( w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD ) {
907 //============================================================
915 int BrushMostlyOnSide( brush_t *brush, plane_t *plane ){
923 for ( i = 0 ; i < brush->numsides ; i++ )
925 w = brush->sides[i].winding;
929 for ( j = 0 ; j < w->numpoints ; j++ )
931 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
949 generates two new brushes, leaving the original unchanged
952 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ){
955 winding_t *w, *cw[2], *midwinding;
956 plane_t *plane, *plane2;
958 float d, d_front, d_back;
963 plane = &mapplanes[planenum];
966 d_front = d_back = 0;
967 for ( i = 0 ; i < brush->numsides ; i++ )
969 w = brush->sides[i].winding;
973 for ( j = 0 ; j < w->numpoints ; j++ )
975 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
976 if ( d > 0 && d > d_front ) {
979 if ( d < 0 && d < d_back ) {
985 if ( d_front < 0.1 ) { // PLANESIDE_EPSILON)
987 *back = CopyBrush( brush );
991 if ( d_back > -0.1 ) { // PLANESIDE_EPSILON)
993 *front = CopyBrush( brush );
997 // create a new winding from the split plane
998 w = BaseWindingForPlane( plane->normal, plane->dist );
999 for ( i = 0 ; i < brush->numsides && w ; i++ )
1001 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1002 ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON);
1005 if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split
1008 side = BrushMostlyOnSide( brush, plane );
1009 if ( side == PSIDE_FRONT ) {
1010 *front = CopyBrush( brush );
1012 if ( side == PSIDE_BACK ) {
1013 *back = CopyBrush( brush );
1018 if ( WindingIsHuge( w ) ) {
1019 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1024 // split it for real
1026 for ( i = 0 ; i < 2 ; i++ )
1028 b[i] = AllocBrush( brush->numsides + 1 );
1029 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1032 b[i]->original = brush->original;
1035 // split all the current windings
1037 for ( i = 0 ; i < brush->numsides ; i++ )
1039 s = &brush->sides[i];
1044 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1045 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] ); /* strict, in parallel case we get the face back because it also is the midwinding */
1046 for ( j = 0 ; j < 2 ; j++ )
1051 cs = &b[j]->sides[b[j]->numsides];
1054 cs->winding = cw[j];
1059 // see if we have valid polygons on both sides
1060 for ( i = 0 ; i < 2 ; i++ )
1062 if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) {
1063 if ( b[i]->numsides >= 3 ) {
1064 Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" );
1071 if ( !( b[0] && b[1] ) ) {
1072 if ( !b[0] && !b[1] ) {
1073 Sys_FPrintf( SYS_VRB,"split removed brush\n" );
1076 Sys_FPrintf( SYS_VRB,"split not on both sides\n" );
1080 *front = CopyBrush( brush );
1084 *back = CopyBrush( brush );
1089 // add the midwinding to both sides
1090 for ( i = 0 ; i < 2 ; i++ )
1092 cs = &b[i]->sides[b[i]->numsides];
1095 cs->planenum = planenum ^ i ^ 1;
1096 cs->shaderInfo = NULL;
1098 cs->winding = CopyWinding( midwinding );
1101 cs->winding = midwinding;
1110 for ( i = 0 ; i < 2 ; i++ )
1112 v1 = BrushVolume( b[i] );
1116 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");