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 )
81 for( ; brushes != NULL; brushes = brushes->next )
93 brush_t *AllocBrush( int numSides )
99 /* allocate and clear */
101 Error( "AllocBrush called with numsides = %d", numSides );
102 c = (size_t)&(((brush_t*) 0)->sides[ numSides ]);
103 bb = safe_malloc( c );
105 if( numthreads == 1 )
116 frees a single brush and all sides/windings
119 void FreeBrush( brush_t *b )
125 if( *((unsigned int*) b) == 0xFEFEFEFE )
127 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
131 /* free brush sides */
132 for( i = 0; i < b->numsides; i++ )
133 if( b->sides[i].winding != NULL )
134 FreeWinding( b->sides[ i ].winding );
136 /* ydnar: overwrite it */
137 memset( b, 0xFE, (size_t)&(((brush_t*) 0)->sides[ b->numsides ]) );
138 *((unsigned int*) b) = 0xFEFEFEFE;
142 if( numthreads == 1 )
150 frees a linked list of brushes
153 void FreeBrushList( brush_t *brushes )
158 /* walk brush list */
159 for( ; brushes != NULL; brushes = next )
161 next = brushes->next;
162 FreeBrush( brushes );
170 duplicates the brush, sides, and windings
173 brush_t *CopyBrush( brush_t *brush )
181 size = (size_t)&(((brush_t*) 0)->sides[ brush->numsides ]);
182 newBrush = AllocBrush( brush->numsides );
183 memcpy( newBrush, brush, size );
185 /* ydnar: nuke linked list */
186 newBrush->next = NULL;
189 for( i = 0; i < brush->numsides; i++ )
191 if( brush->sides[ i ].winding != NULL )
192 newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
204 sets the mins/maxs based on the windings
205 returns false if the brush doesn't enclose a valid volume
208 qboolean BoundBrush( brush_t *brush )
214 ClearBounds( brush->mins, brush->maxs );
215 for( i = 0; i < brush->numsides; i++ )
217 w = brush->sides[ i ].winding;
220 for( j = 0; j < w->numpoints; j++ )
221 AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
224 for( i = 0; i < 3; i++ )
226 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 )
251 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 */
264 else if( bi == b[ i ] )
268 else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )
274 outi = Q_rint( out[ i ] );
275 if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )
284 Welds two vectors into a third, taking into account nearest-to-integer
285 instead of averaging.
288 void SnapWeldVectorAccu(vec3_accu_t a, vec3_accu_t b, vec3_accu_t out)
290 // I'm just preserving what I think was the intended logic of the original
291 // SnapWeldVector(). I'm not actually sure where this function should even
292 // be used. I'd like to know which kinds of problems this function addresses.
294 // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
295 // So what is natural about snapping to the nearest integer? Maybe we should
296 // be snapping to the nearest 1/8 unit instead?
299 vec_accu_t ai, bi, ad, bd;
301 if (a == NULL || b == NULL || out == NULL)
302 Error("SnapWeldVectorAccu: NULL argument");
304 for (i = 0; i < 3; i++)
306 ai = Q_rintAccu(a[i]);
307 bi = Q_rintAccu(b[i]);
308 ad = fabs(ai - a[i]);
309 bd = fabs(bi - b[i]);
313 if (ad < SNAP_EPSILON) out[i] = ai;
318 if (bd < SNAP_EPSILON) out[i] = bi;
328 Welds two vectors into a third, taking into account nearest-to-integer
329 instead of averaging.
332 void SnapWeldVectorAccu(vec3_accu_t a, vec3_accu_t b, vec3_accu_t out)
334 // I'm just preserving what I think was the intended logic of the original
335 // SnapWeldVector(). I'm not actually sure where this function should even
336 // be used. I'd like to know which kinds of problems this function addresses.
338 // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
339 // So what is natural about snapping to the nearest integer? Maybe we should
340 // be snapping to the nearest 1/8 unit instead?
343 vec_accu_t ai, bi, ad, bd;
345 if (a == NULL || b == NULL || out == NULL)
346 Error("SnapWeldVectorAccu: NULL argument");
348 for (i = 0; i < 3; i++)
350 ai = Q_rintAccu(a[i]);
351 bi = Q_rintAccu(b[i]);
352 ad = fabs(ai - a[i]);
353 bd = fabs(bi - b[i]);
357 if (ad < SNAP_EPSILON) out[i] = ai;
362 if (bd < SNAP_EPSILON) out[i] = bi;
372 removes degenerate edges from a winding
373 returns qtrue if the winding is valid
376 #define DEGENERATE_EPSILON 0.1
378 qboolean FixWinding( winding_t *w )
380 qboolean valid = qtrue;
390 /* check all verts */
391 for( i = 0; i < w->numpoints; i++ )
393 /* don't remove points if winding is a triangle */
394 if( w->numpoints == 3 )
397 /* get second point index */
398 j = (i + 1) % w->numpoints;
400 /* degenerate edge? */
401 VectorSubtract( w->p[ i ], w->p[ j ], vec );
402 dist = VectorLength( vec );
403 if( dist < DEGENERATE_EPSILON )
406 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
408 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
409 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
410 VectorCopy( vec, w->p[ i ] );
411 //VectorAdd( w->p[ i ], w->p[ j ], vec );
412 //VectorScale( vec, 0.5, w->p[ i ] );
414 /* move the remaining verts */
415 for( k = i + 2; k < w->numpoints; k++ )
417 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
423 /* one last check and return */
424 if( w->numpoints < 3 )
433 Removes degenerate edges (edges that are too short) from a winding.
434 Returns qtrue if the winding has been altered by this function.
435 Returns qfalse if the winding is untouched by this function.
437 It's advised that you check the winding after this function exits to make
438 sure it still has at least 3 points. If that is not the case, the winding
439 cannot be considered valid. The winding may degenerate to one or two points
440 if the some of the winding's points are close together.
443 qboolean FixWindingAccu(winding_accu_t *w)
448 qboolean done, altered;
450 if (w == NULL) Error("FixWindingAccu: NULL argument");
456 if (w->numpoints < 2) break; // Don't remove the only remaining point.
458 for (i = 0; i < w->numpoints; i++)
460 j = (((i + 1) == w->numpoints) ? 0 : (i + 1));
462 VectorSubtractAccu(w->p[i], w->p[j], vec);
463 dist = VectorLengthAccu(vec);
464 if (dist < DEGENERATE_EPSILON)
466 // TODO: I think the "snap weld vector" was written before
467 // some of the math precision fixes, and its purpose was
468 // probably to address math accuracy issues. We can think
469 // about changing the logic here. Maybe once plane distance
470 // gets 64 bits, we can look at it then.
471 SnapWeldVectorAccu(w->p[i], w->p[j], vec);
472 VectorCopyAccu(vec, w->p[i]);
473 for (k = j + 1; k < w->numpoints; k++)
475 VectorCopyAccu(w->p[k], w->p[k - 1]);
479 // The only way to finish off fixing the winding consistently and
480 // accurately is by fixing the winding all over again. For example,
481 // the point at index i and the point at index i-1 could now be
482 // less than the epsilon distance apart. There are too many special
483 // case problems we'd need to handle if we didn't start from the
486 break; // This will cause us to return to the "while" loop.
497 CreateBrushWindings()
498 makes basewindigs for sides and mins/maxs for the brush
499 returns false if the brush doesn't enclose a valid volume
502 qboolean CreateBrushWindings( brush_t *brush )
505 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
514 /* walk the list of brush sides */
515 for( i = 0; i < brush->numsides; i++ )
517 /* get side and plane */
518 side = &brush->sides[ i ];
519 plane = &mapplanes[ side->planenum ];
521 /* make huge winding */
522 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
523 w = BaseWindingForPlaneAccu(plane->normal, plane->dist);
525 w = BaseWindingForPlane( plane->normal, plane->dist );
528 /* walk the list of brush sides */
529 for( j = 0; j < brush->numsides && w != NULL; j++ )
533 if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
534 continue; /* back side clipaway */
535 if( brush->sides[ j ].bevel )
537 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
538 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
539 ChopWindingInPlaceAccu(&w, plane->normal, plane->dist, 0);
541 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
544 /* ydnar: fix broken windings that would generate trifans */
545 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
546 // I think it's better to FixWindingAccu() once after we chop with all planes
547 // so that error isn't multiplied. There is nothing natural about welding
548 // the points unless they are the final endpoints. ChopWindingInPlaceAccu()
549 // is able to handle all kinds of degenerate windings.
555 /* set side winding */
556 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
560 if (w->numpoints < 3)
566 side->winding = (w ? CopyWindingAccuToRegular(w) : NULL);
567 if (w) FreeWindingAccu(w);
573 /* find brush bounds */
574 return BoundBrush( brush );
584 Creates a new axial brush
587 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
596 for (i=0 ; i<3 ; i++)
598 VectorClear (normal);
601 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
605 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
608 CreateBrushWindings (b);
619 vec_t BrushVolume (brush_t *brush)
624 vec_t d, area, volume;
630 // grab the first valid point as the corner
633 for (i=0 ; i<brush->numsides ; i++)
635 w = brush->sides[i].winding;
641 VectorCopy (w->p[0], corner);
643 // make tetrahedrons to all other faces
646 for ( ; i<brush->numsides ; i++)
648 w = brush->sides[i].winding;
651 plane = &mapplanes[brush->sides[i].planenum];
652 d = -(DotProduct (corner, plane->normal) - plane->dist);
653 area = WindingArea (w);
665 writes a map with the split bsp brushes
668 void WriteBSPBrushMap( char *name, brush_t *list )
677 Sys_Printf( "Writing %s\n", name );
679 /* open the map file */
680 f = fopen( name, "wb" );
682 Error( "Can't write %s\b", name );
684 fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
686 for ( ; list ; list=list->next )
689 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
691 // TODO: See if we can use a smaller winding to prevent resolution loss.
692 // Is WriteBSPBrushMap() used only to decompile maps?
693 w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
695 fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
696 fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
697 fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
699 fprintf (f, "notexture 0 0 0 1 1\n" );
713 FilterBrushIntoTree_r()
714 adds brush reference to any intersecting bsp leafnode
717 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
719 brush_t *front, *back;
727 /* add it to the leaf list */
728 if( node->planenum == PLANENUM_LEAF )
730 /* something somewhere is hammering brushlist */
731 b->next = node->brushlist;
734 /* classify the leaf by the structural brush */
739 node->opaque = qtrue;
740 node->areaportal = qfalse;
742 else if( b->compileFlags & C_AREAPORTAL )
745 node->areaportal = qtrue;
752 /* split it by the node plane */
754 SplitBrush( b, node->planenum, &front, &back );
758 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
759 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
767 FilterDetailBrushesIntoTree
768 fragment all the detail brushes into the structural leafs
771 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
775 int c_unique, c_clusters;
780 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
782 /* walk the list of brushes */
785 for( b = e->brushes; b; b = b->next )
790 newb = CopyBrush( b );
791 r = FilterBrushIntoTree_r( newb, tree->headnode );
794 /* mark all sides as visible so drawsurfs are created */
797 for( i = 0; i < b->numsides; i++ )
799 if( b->sides[ i ].winding )
800 b->sides[ i ].visible = qtrue;
805 /* emit some statistics */
806 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
807 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
811 =====================
812 FilterStructuralBrushesIntoTree
814 Mark the leafs as opaque and areaportals
815 =====================
817 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
820 int c_unique, c_clusters;
823 Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
827 for ( b = e->brushes ; b ; b = b->next ) {
832 newb = CopyBrush( b );
833 r = FilterBrushIntoTree_r( newb, tree->headnode );
836 // mark all sides as visible so drawsurfs are created
838 for ( i = 0 ; i < b->numsides ; i++ ) {
839 if ( b->sides[i].winding ) {
840 b->sides[i].visible = qtrue;
846 /* emit some statistics */
847 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
848 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
858 tree_t *AllocTree (void)
862 tree = safe_malloc(sizeof(*tree));
863 memset (tree, 0, sizeof(*tree));
864 ClearBounds (tree->mins, tree->maxs);
874 node_t *AllocNode (void)
878 node = safe_malloc(sizeof(*node));
879 memset (node, 0, sizeof(*node));
889 Returns true if the winding would be crunched out of
890 existance by the vertex snapping.
893 #define EDGE_LENGTH 0.2
894 qboolean WindingIsTiny (winding_t *w)
897 if (WindingArea (w) < 1)
907 for (i=0 ; i<w->numpoints ; i++)
909 j = i == w->numpoints - 1 ? 0 : i+1;
910 VectorSubtract (w->p[j], w->p[i], delta);
911 len = VectorLength (delta);
912 if (len > EDGE_LENGTH)
925 Returns true if the winding still has one of the points
926 from basewinding for plane
929 qboolean WindingIsHuge (winding_t *w)
933 for (i=0 ; i<w->numpoints ; i++)
935 for (j=0 ; j<3 ; j++)
936 if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
942 //============================================================
950 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
959 for (i=0 ; i<brush->numsides ; i++)
961 w = brush->sides[i].winding;
964 for (j=0 ; j<w->numpoints ; j++)
966 d = DotProduct (w->p[j], plane->normal) - plane->dist;
986 generates two new brushes, leaving the original unchanged
989 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
993 winding_t *w, *cw[2], *midwinding;
994 plane_t *plane, *plane2;
996 float d, d_front, d_back;
1001 plane = &mapplanes[planenum];
1004 d_front = d_back = 0;
1005 for (i=0 ; i<brush->numsides ; i++)
1007 w = brush->sides[i].winding;
1010 for (j=0 ; j<w->numpoints ; j++)
1012 d = DotProduct (w->p[j], plane->normal) - plane->dist;
1013 if (d > 0 && d > d_front)
1015 if (d < 0 && d < d_back)
1020 if (d_front < 0.1) // PLANESIDE_EPSILON)
1022 *back = CopyBrush( brush );
1026 if (d_back > -0.1) // PLANESIDE_EPSILON)
1028 *front = CopyBrush( brush );
1032 // create a new winding from the split plane
1033 w = BaseWindingForPlane (plane->normal, plane->dist);
1034 for (i=0 ; i<brush->numsides && w ; i++)
1036 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1037 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
1040 if (!w || WindingIsTiny (w) )
1041 { // the brush isn't really split
1044 side = BrushMostlyOnSide (brush, plane);
1045 if (side == PSIDE_FRONT)
1046 *front = CopyBrush (brush);
1047 if (side == PSIDE_BACK)
1048 *back = CopyBrush (brush);
1052 if( WindingIsHuge( w ) )
1053 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1057 // split it for real
1059 for (i=0 ; i<2 ; i++)
1061 b[i] = AllocBrush (brush->numsides+1);
1062 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1065 b[i]->original = brush->original;
1068 // split all the current windings
1070 for (i=0 ; i<brush->numsides ; i++)
1072 s = &brush->sides[i];
1076 ClipWindingEpsilon (w, plane->normal, plane->dist,
1077 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
1078 for (j=0 ; j<2 ; j++)
1082 cs = &b[j]->sides[b[j]->numsides];
1085 cs->winding = cw[j];
1090 // see if we have valid polygons on both sides
1091 for (i=0 ; i<2 ; i++)
1093 if (b[i]->numsides < 3 || !BoundBrush (b[i]))
1095 if (b[i]->numsides >= 3)
1096 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
1102 if ( !(b[0] && b[1]) )
1105 Sys_FPrintf (SYS_VRB,"split removed brush\n");
1107 Sys_FPrintf (SYS_VRB,"split not on both sides\n");
1111 *front = CopyBrush (brush);
1116 *back = CopyBrush (brush);
1121 // add the midwinding to both sides
1122 for (i=0 ; i<2 ; i++)
1124 cs = &b[i]->sides[b[i]->numsides];
1127 cs->planenum = planenum^i^1;
1128 cs->shaderInfo = NULL;
1130 cs->winding = CopyWinding (midwinding);
1132 cs->winding = midwinding;
1140 for (i=0 ; i<2 ; i++)
1142 v1 = BrushVolume (b[i]);
1147 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");