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 removes degenerate edges from a winding
285 returns qtrue if the winding is valid
288 #define DEGENERATE_EPSILON 0.1
290 qboolean FixWinding( winding_t *w )
292 qboolean valid = qtrue;
302 /* check all verts */
303 for( i = 0; i < w->numpoints; i++ )
305 /* don't remove points if winding is a triangle */
306 if( w->numpoints == 3 )
309 /* get second point index */
310 j = (i + 1) % w->numpoints;
312 /* degenerate edge? */
313 VectorSubtract( w->p[ i ], w->p[ j ], vec );
314 dist = VectorLength( vec );
315 if( dist < DEGENERATE_EPSILON )
318 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
320 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
321 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
322 VectorCopy( vec, w->p[ i ] );
323 //VectorAdd( w->p[ i ], w->p[ j ], vec );
324 //VectorScale( vec, 0.5, w->p[ i ] );
326 /* move the remaining verts */
327 for( k = i + 2; k < w->numpoints; k++ )
329 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
335 /* one last check and return */
336 if( w->numpoints < 3 )
348 CreateBrushWindings()
349 makes basewindigs for sides and mins/maxs for the brush
350 returns false if the brush doesn't enclose a valid volume
353 qboolean CreateBrushWindings( brush_t *brush )
361 /* walk the list of brush sides */
362 for( i = 0; i < brush->numsides; i++ )
364 /* get side and plane */
365 side = &brush->sides[ i ];
366 plane = &mapplanes[ side->planenum ];
368 /* make huge winding */
369 w = BaseWindingForPlane( plane->normal, plane->dist );
371 /* walk the list of brush sides */
372 for( j = 0; j < brush->numsides && w != NULL; j++ )
376 if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
377 continue; /* back side clipaway */
378 if( brush->sides[ j ].bevel )
380 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
381 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
383 /* ydnar: fix broken windings that would generate trifans */
387 /* set side winding */
391 /* find brush bounds */
392 return BoundBrush( brush );
402 Creates a new axial brush
405 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
414 for (i=0 ; i<3 ; i++)
416 VectorClear (normal);
419 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
423 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
426 CreateBrushWindings (b);
437 vec_t BrushVolume (brush_t *brush)
442 vec_t d, area, volume;
448 // grab the first valid point as the corner
451 for (i=0 ; i<brush->numsides ; i++)
453 w = brush->sides[i].winding;
459 VectorCopy (w->p[0], corner);
461 // make tetrahedrons to all other faces
464 for ( ; i<brush->numsides ; i++)
466 w = brush->sides[i].winding;
469 plane = &mapplanes[brush->sides[i].planenum];
470 d = -(DotProduct (corner, plane->normal) - plane->dist);
471 area = WindingArea (w);
483 writes a map with the split bsp brushes
486 void WriteBSPBrushMap( char *name, brush_t *list )
495 Sys_Printf( "Writing %s\n", name );
497 /* open the map file */
498 f = fopen( name, "wb" );
500 Error( "Can't write %s\b", name );
502 fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
504 for ( ; list ; list=list->next )
507 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
509 w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
511 fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
512 fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
513 fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
515 fprintf (f, "notexture 0 0 0 1 1\n" );
529 FilterBrushIntoTree_r()
530 adds brush reference to any intersecting bsp leafnode
533 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
535 brush_t *front, *back;
543 /* add it to the leaf list */
544 if( node->planenum == PLANENUM_LEAF )
546 /* something somewhere is hammering brushlist */
547 b->next = node->brushlist;
550 /* classify the leaf by the structural brush */
555 node->opaque = qtrue;
556 node->areaportal = qfalse;
558 else if( b->compileFlags & C_AREAPORTAL )
561 node->areaportal = qtrue;
568 /* split it by the node plane */
570 SplitBrush( b, node->planenum, &front, &back );
574 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
575 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
583 FilterDetailBrushesIntoTree
584 fragment all the detail brushes into the structural leafs
587 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
591 int c_unique, c_clusters;
596 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
598 /* walk the list of brushes */
601 for( b = e->brushes; b; b = b->next )
606 newb = CopyBrush( b );
607 r = FilterBrushIntoTree_r( newb, tree->headnode );
610 /* mark all sides as visible so drawsurfs are created */
613 for( i = 0; i < b->numsides; i++ )
615 if( b->sides[ i ].winding )
616 b->sides[ i ].visible = qtrue;
621 /* emit some statistics */
622 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
623 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
627 =====================
628 FilterStructuralBrushesIntoTree
630 Mark the leafs as opaque and areaportals
631 =====================
633 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
636 int c_unique, c_clusters;
639 Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
643 for ( b = e->brushes ; b ; b = b->next ) {
648 newb = CopyBrush( b );
649 r = FilterBrushIntoTree_r( newb, tree->headnode );
652 // mark all sides as visible so drawsurfs are created
654 for ( i = 0 ; i < b->numsides ; i++ ) {
655 if ( b->sides[i].winding ) {
656 b->sides[i].visible = qtrue;
662 /* emit some statistics */
663 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
664 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
674 tree_t *AllocTree (void)
678 tree = safe_malloc(sizeof(*tree));
679 memset (tree, 0, sizeof(*tree));
680 ClearBounds (tree->mins, tree->maxs);
690 node_t *AllocNode (void)
694 node = safe_malloc(sizeof(*node));
695 memset (node, 0, sizeof(*node));
705 Returns true if the winding would be crunched out of
706 existance by the vertex snapping.
709 #define EDGE_LENGTH 0.2
710 qboolean WindingIsTiny (winding_t *w)
713 if (WindingArea (w) < 1)
723 for (i=0 ; i<w->numpoints ; i++)
725 j = i == w->numpoints - 1 ? 0 : i+1;
726 VectorSubtract (w->p[j], w->p[i], delta);
727 len = VectorLength (delta);
728 if (len > EDGE_LENGTH)
741 Returns true if the winding still has one of the points
742 from basewinding for plane
745 qboolean WindingIsHuge (winding_t *w)
749 for (i=0 ; i<w->numpoints ; i++)
751 for (j=0 ; j<3 ; j++)
752 if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
758 //============================================================
766 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
775 for (i=0 ; i<brush->numsides ; i++)
777 w = brush->sides[i].winding;
780 for (j=0 ; j<w->numpoints ; j++)
782 d = DotProduct (w->p[j], plane->normal) - plane->dist;
802 generates two new brushes, leaving the original unchanged
805 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
809 winding_t *w, *cw[2], *midwinding;
810 plane_t *plane, *plane2;
812 float d, d_front, d_back;
817 plane = &mapplanes[planenum];
820 d_front = d_back = 0;
821 for (i=0 ; i<brush->numsides ; i++)
823 w = brush->sides[i].winding;
826 for (j=0 ; j<w->numpoints ; j++)
828 d = DotProduct (w->p[j], plane->normal) - plane->dist;
829 if (d > 0 && d > d_front)
831 if (d < 0 && d < d_back)
836 if (d_front < 0.1) // PLANESIDE_EPSILON)
838 *back = CopyBrush( brush );
842 if (d_back > -0.1) // PLANESIDE_EPSILON)
844 *front = CopyBrush( brush );
848 // create a new winding from the split plane
849 w = BaseWindingForPlane (plane->normal, plane->dist);
850 for (i=0 ; i<brush->numsides && w ; i++)
852 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
853 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
856 if (!w || WindingIsTiny (w) )
857 { // the brush isn't really split
860 side = BrushMostlyOnSide (brush, plane);
861 if (side == PSIDE_FRONT)
862 *front = CopyBrush (brush);
863 if (side == PSIDE_BACK)
864 *back = CopyBrush (brush);
868 if( WindingIsHuge( w ) )
869 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
875 for (i=0 ; i<2 ; i++)
877 b[i] = AllocBrush (brush->numsides+1);
878 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
881 b[i]->original = brush->original;
884 // split all the current windings
886 for (i=0 ; i<brush->numsides ; i++)
888 s = &brush->sides[i];
892 ClipWindingEpsilon (w, plane->normal, plane->dist,
893 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
894 for (j=0 ; j<2 ; j++)
898 cs = &b[j]->sides[b[j]->numsides];
906 // see if we have valid polygons on both sides
907 for (i=0 ; i<2 ; i++)
909 if (b[i]->numsides < 3 || !BoundBrush (b[i]))
911 if (b[i]->numsides >= 3)
912 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
918 if ( !(b[0] && b[1]) )
921 Sys_FPrintf (SYS_VRB,"split removed brush\n");
923 Sys_FPrintf (SYS_VRB,"split not on both sides\n");
927 *front = CopyBrush (brush);
932 *back = CopyBrush (brush);
937 // add the midwinding to both sides
938 for (i=0 ; i<2 ; i++)
940 cs = &b[i]->sides[b[i]->numsides];
943 cs->planenum = planenum^i^1;
944 cs->shaderInfo = NULL;
946 cs->winding = CopyWinding (midwinding);
948 cs->winding = midwinding;
956 for (i=0 ; i<2 ; i++)
958 v1 = BrushVolume (b[i]);
963 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");