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;
326 removes degenerate edges from a winding
327 returns qtrue if the winding is valid
330 #define DEGENERATE_EPSILON 0.1
332 qboolean FixWinding( winding_t *w )
334 qboolean valid = qtrue;
344 /* check all verts */
345 for( i = 0; i < w->numpoints; i++ )
347 /* don't remove points if winding is a triangle */
348 if( w->numpoints == 3 )
351 /* get second point index */
352 j = (i + 1) % w->numpoints;
354 /* degenerate edge? */
355 VectorSubtract( w->p[ i ], w->p[ j ], vec );
356 dist = VectorLength( vec );
357 if( dist < DEGENERATE_EPSILON )
360 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
362 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
363 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
364 VectorCopy( vec, w->p[ i ] );
365 //VectorAdd( w->p[ i ], w->p[ j ], vec );
366 //VectorScale( vec, 0.5, w->p[ i ] );
368 /* move the remaining verts */
369 for( k = i + 2; k < w->numpoints; k++ )
371 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
377 /* one last check and return */
378 if( w->numpoints < 3 )
387 Removes degenerate edges (edges that are too short) from a winding.
388 Returns qtrue if the winding has been altered by this function.
389 Returns qfalse if the winding is untouched by this function.
391 It's advised that you check the winding after this function exits to make
392 sure it still has at least 3 points. If that is not the case, the winding
393 cannot be considered valid. The winding may degenerate to one or two points
394 if the some of the winding's points are close together.
397 qboolean FixWindingAccu(winding_accu_t *w)
402 qboolean done, altered;
404 if (w == NULL) Error("FixWindingAccu: NULL argument");
410 if (w->numpoints < 2) break; // Don't remove the only remaining point.
412 for (i = 0; i < w->numpoints; i++)
414 j = (((i + 1) == w->numpoints) ? 0 : (i + 1));
416 VectorSubtractAccu(w->p[i], w->p[j], vec);
417 dist = VectorLengthAccu(vec);
418 if (dist < DEGENERATE_EPSILON)
420 // TODO: I think the "snap weld vector" was written before
421 // some of the math precision fixes, and its purpose was
422 // probably to address math accuracy issues. We can think
423 // about changing the logic here. Maybe once plane distance
424 // gets 64 bits, we can look at it then.
425 SnapWeldVectorAccu(w->p[i], w->p[j], vec);
426 VectorCopyAccu(vec, w->p[i]);
427 for (k = j + 1; k < w->numpoints; k++)
429 VectorCopyAccu(w->p[k], w->p[k - 1]);
433 // The only way to finish off fixing the winding consistently and
434 // accurately is by fixing the winding all over again. For example,
435 // the point at index i and the point at index i-1 could now be
436 // less than the epsilon distance apart. There are too many special
437 // case problems we'd need to handle if we didn't start from the
440 break; // This will cause us to return to the "while" loop.
451 CreateBrushWindings()
452 makes basewindigs for sides and mins/maxs for the brush
453 returns false if the brush doesn't enclose a valid volume
456 qboolean CreateBrushWindings( brush_t *brush )
459 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
468 /* walk the list of brush sides */
469 for( i = 0; i < brush->numsides; i++ )
471 /* get side and plane */
472 side = &brush->sides[ i ];
473 plane = &mapplanes[ side->planenum ];
475 /* make huge winding */
476 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
477 w = BaseWindingForPlaneAccu(plane->normal, plane->dist);
479 w = BaseWindingForPlane( plane->normal, plane->dist );
482 /* walk the list of brush sides */
483 for( j = 0; j < brush->numsides && w != NULL; j++ )
487 if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
488 continue; /* back side clipaway */
489 if( brush->sides[ j ].bevel )
491 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
492 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
493 ChopWindingInPlaceAccu(&w, plane->normal, plane->dist, 0);
495 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
498 /* ydnar: fix broken windings that would generate trifans */
499 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
500 // I think it's better to FixWindingAccu() once after we chop with all planes
501 // so that error isn't multiplied. There is nothing natural about welding
502 // the points unless they are the final endpoints. ChopWindingInPlaceAccu()
503 // is able to handle all kinds of degenerate windings.
509 /* set side winding */
510 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
514 if (w->numpoints < 3)
520 side->winding = (w ? CopyWindingAccuToRegular(w) : NULL);
521 if (w) FreeWindingAccu(w);
527 /* find brush bounds */
528 return BoundBrush( brush );
538 Creates a new axial brush
541 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
550 for (i=0 ; i<3 ; i++)
552 VectorClear (normal);
555 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
559 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
562 CreateBrushWindings (b);
573 vec_t BrushVolume (brush_t *brush)
578 vec_t d, area, volume;
584 // grab the first valid point as the corner
587 for (i=0 ; i<brush->numsides ; i++)
589 w = brush->sides[i].winding;
595 VectorCopy (w->p[0], corner);
597 // make tetrahedrons to all other faces
600 for ( ; i<brush->numsides ; i++)
602 w = brush->sides[i].winding;
605 plane = &mapplanes[brush->sides[i].planenum];
606 d = -(DotProduct (corner, plane->normal) - plane->dist);
607 area = WindingArea (w);
619 writes a map with the split bsp brushes
622 void WriteBSPBrushMap( char *name, brush_t *list )
631 Sys_Printf( "Writing %s\n", name );
633 /* open the map file */
634 f = fopen( name, "wb" );
636 Error( "Can't write %s\b", name );
638 fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
640 for ( ; list ; list=list->next )
643 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
645 // TODO: See if we can use a smaller winding to prevent resolution loss.
646 // Is WriteBSPBrushMap() used only to decompile maps?
647 w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
649 fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
650 fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
651 fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
653 fprintf (f, "notexture 0 0 0 1 1\n" );
667 FilterBrushIntoTree_r()
668 adds brush reference to any intersecting bsp leafnode
671 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
673 brush_t *front, *back;
681 /* add it to the leaf list */
682 if( node->planenum == PLANENUM_LEAF )
684 /* something somewhere is hammering brushlist */
685 b->next = node->brushlist;
688 /* classify the leaf by the structural brush */
693 node->opaque = qtrue;
694 node->areaportal = qfalse;
696 else if( b->compileFlags & C_AREAPORTAL )
699 node->areaportal = qtrue;
706 /* split it by the node plane */
708 SplitBrush( b, node->planenum, &front, &back );
712 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
713 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
721 FilterDetailBrushesIntoTree
722 fragment all the detail brushes into the structural leafs
725 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
729 int c_unique, c_clusters;
734 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
736 /* walk the list of brushes */
739 for( b = e->brushes; b; b = b->next )
744 newb = CopyBrush( b );
745 r = FilterBrushIntoTree_r( newb, tree->headnode );
748 /* mark all sides as visible so drawsurfs are created */
751 for( i = 0; i < b->numsides; i++ )
753 if( b->sides[ i ].winding )
754 b->sides[ i ].visible = qtrue;
759 /* emit some statistics */
760 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
761 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
765 =====================
766 FilterStructuralBrushesIntoTree
768 Mark the leafs as opaque and areaportals
769 =====================
771 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
774 int c_unique, c_clusters;
777 Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
781 for ( b = e->brushes ; b ; b = b->next ) {
786 newb = CopyBrush( b );
787 r = FilterBrushIntoTree_r( newb, tree->headnode );
790 // mark all sides as visible so drawsurfs are created
792 for ( i = 0 ; i < b->numsides ; i++ ) {
793 if ( b->sides[i].winding ) {
794 b->sides[i].visible = qtrue;
800 /* emit some statistics */
801 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
802 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
812 tree_t *AllocTree (void)
816 tree = safe_malloc(sizeof(*tree));
817 memset (tree, 0, sizeof(*tree));
818 ClearBounds (tree->mins, tree->maxs);
828 node_t *AllocNode (void)
832 node = safe_malloc(sizeof(*node));
833 memset (node, 0, sizeof(*node));
843 Returns true if the winding would be crunched out of
844 existance by the vertex snapping.
847 #define EDGE_LENGTH 0.2
848 qboolean WindingIsTiny (winding_t *w)
851 if (WindingArea (w) < 1)
861 for (i=0 ; i<w->numpoints ; i++)
863 j = i == w->numpoints - 1 ? 0 : i+1;
864 VectorSubtract (w->p[j], w->p[i], delta);
865 len = VectorLength (delta);
866 if (len > EDGE_LENGTH)
879 Returns true if the winding still has one of the points
880 from basewinding for plane
883 qboolean WindingIsHuge (winding_t *w)
887 for (i=0 ; i<w->numpoints ; i++)
889 for (j=0 ; j<3 ; j++)
890 if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
896 //============================================================
904 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
913 for (i=0 ; i<brush->numsides ; i++)
915 w = brush->sides[i].winding;
918 for (j=0 ; j<w->numpoints ; j++)
920 d = DotProduct (w->p[j], plane->normal) - plane->dist;
940 generates two new brushes, leaving the original unchanged
943 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
947 winding_t *w, *cw[2], *midwinding;
948 plane_t *plane, *plane2;
950 float d, d_front, d_back;
955 plane = &mapplanes[planenum];
958 d_front = d_back = 0;
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;
967 if (d > 0 && d > d_front)
969 if (d < 0 && d < d_back)
974 if (d_front < 0.1) // PLANESIDE_EPSILON)
976 *back = CopyBrush( brush );
980 if (d_back > -0.1) // PLANESIDE_EPSILON)
982 *front = CopyBrush( brush );
986 // create a new winding from the split plane
987 w = BaseWindingForPlane (plane->normal, plane->dist);
988 for (i=0 ; i<brush->numsides && w ; i++)
990 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
991 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
994 if (!w || WindingIsTiny (w) )
995 { // the brush isn't really split
998 side = BrushMostlyOnSide (brush, plane);
999 if (side == PSIDE_FRONT)
1000 *front = CopyBrush (brush);
1001 if (side == PSIDE_BACK)
1002 *back = CopyBrush (brush);
1006 if( WindingIsHuge( w ) )
1007 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1011 // split it for real
1013 for (i=0 ; i<2 ; i++)
1015 b[i] = AllocBrush (brush->numsides+1);
1016 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1019 b[i]->original = brush->original;
1022 // split all the current windings
1024 for (i=0 ; i<brush->numsides ; i++)
1026 s = &brush->sides[i];
1030 ClipWindingEpsilonStrict (w, plane->normal, plane->dist,
1031 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]); /* strict, in parallel case we get the face back because it also is the midwinding */
1032 for (j=0 ; j<2 ; j++)
1036 cs = &b[j]->sides[b[j]->numsides];
1039 cs->winding = cw[j];
1044 // see if we have valid polygons on both sides
1045 for (i=0 ; i<2 ; i++)
1047 if (b[i]->numsides < 3 || !BoundBrush (b[i]))
1049 if (b[i]->numsides >= 3)
1050 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
1056 if ( !(b[0] && b[1]) )
1059 Sys_FPrintf (SYS_VRB,"split removed brush\n");
1061 Sys_FPrintf (SYS_VRB,"split not on both sides\n");
1065 *front = CopyBrush (brush);
1070 *back = CopyBrush (brush);
1075 // add the midwinding to both sides
1076 for (i=0 ; i<2 ; i++)
1078 cs = &b[i]->sides[b[i]->numsides];
1081 cs->planenum = planenum^i^1;
1082 cs->shaderInfo = NULL;
1084 cs->winding = CopyWinding (midwinding);
1086 cs->winding = midwinding;
1094 for (i=0 ; i<2 ; i++)
1096 v1 = BrushVolume (b[i]);
1101 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");