2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ----------------------------------------------------------------------------------
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26 ------------------------------------------------------------------------------- */
40 /* -------------------------------------------------------------------------------
44 ------------------------------------------------------------------------------- */
47 AllocSideRef() - ydnar
48 allocates and assigns a brush side reference
51 sideRef_t *AllocSideRef( side_t *side, sideRef_t *next )
60 /* allocate and return */
61 sideRef = safe_malloc( sizeof( *sideRef ) );
71 counts the number of brushes in a brush linked list
74 int CountBrushList( brush_t *brushes )
80 for( brushes; brushes != NULL; brushes = brushes->next )
92 brush_t *AllocBrush( int numSides )
98 /* allocate and clear */
100 Error( "AllocBrush called with numsides = %d", numSides );
101 c = (int) &(((brush_t*) 0)->sides[ numSides ]);
102 bb = safe_malloc( c );
104 if( numthreads == 1 )
115 frees a single brush and all sides/windings
118 void FreeBrush( brush_t *b )
124 if( *((int*) b) == 0xFEFEFEFE )
126 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
130 /* free brush sides */
131 for( i = 0; i < b->numsides; i++ )
132 if( b->sides[i].winding != NULL )
133 FreeWinding( b->sides[ i ].winding );
135 /* ydnar: overwrite it */
136 memset( b, 0xFE, (int) &(((brush_t*) 0)->sides[ b->numsides ]) );
137 *((int*) b) = 0xFEFEFEFE;
141 if( numthreads == 1 )
149 frees a linked list of brushes
152 void FreeBrushList( brush_t *brushes )
157 /* walk brush list */
158 for( brushes; 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 )
180 size = (int) &(((brush_t*) 0)->sides[ brush->numsides ]);
181 newBrush = AllocBrush( brush->numsides );
182 memcpy( newBrush, brush, size );
184 /* ydnar: nuke linked list */
185 newBrush->next = NULL;
188 for( i = 0; i < brush->numsides; i++ )
190 if( brush->sides[ i ].winding != NULL )
191 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 )
213 ClearBounds( brush->mins, brush->maxs );
214 for( i = 0; i < brush->numsides; i++ )
216 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 ] )
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 )
250 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( a[ i ] );
260 /* prefer exact integer */
263 else if( bi == b[ i ] )
267 else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )
273 outi = Q_rint( out[ i ] );
274 if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )
283 removes degenerate edges from a winding
284 returns qtrue if the winding is valid
287 #define DEGENERATE_EPSILON 0.1
289 qboolean FixWinding( winding_t *w )
291 qboolean valid = qtrue;
301 /* check all verts */
302 for( i = 0; i < w->numpoints; i++ )
304 /* don't remove points if winding is a triangle */
305 if( w->numpoints == 3 )
308 /* get second point index */
309 j = (i + 1) % w->numpoints;
311 /* degenerate edge? */
312 VectorSubtract( w->p[ i ], w->p[ j ], vec );
313 dist = VectorLength( vec );
314 if( dist < DEGENERATE_EPSILON )
317 //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
319 /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
320 SnapWeldVector( w->p[ i ], w->p[ j ], vec );
321 VectorCopy( vec, w->p[ i ] );
322 //VectorAdd( w->p[ i ], w->p[ j ], vec );
323 //VectorScale( vec, 0.5, w->p[ i ] );
325 /* move the remaining verts */
326 for( k = i + 2; k < w->numpoints; k++ )
328 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
334 /* one last check and return */
335 if( w->numpoints < 3 )
347 CreateBrushWindings()
348 makes basewindigs for sides and mins/maxs for the brush
349 returns false if the brush doesn't enclose a valid volume
352 qboolean CreateBrushWindings( brush_t *brush )
360 /* walk the list of brush sides */
361 for( i = 0; i < brush->numsides; i++ )
363 /* get side and plane */
364 side = &brush->sides[ i ];
365 plane = &mapplanes[ side->planenum ];
367 /* make huge winding */
368 w = BaseWindingForPlane( plane->normal, plane->dist );
370 /* walk the list of brush sides */
371 for( j = 0; j < brush->numsides && w != NULL; j++ )
375 if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
376 continue; /* back side clipaway */
377 if( brush->sides[ j ].bevel )
379 if( brush->sides[ j ].backSide )
381 plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
382 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
384 /* ydnar: fix broken windings that would generate trifans */
388 /* set side winding */
392 /* find brush bounds */
393 return BoundBrush( brush );
403 Creates a new axial brush
406 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
415 for (i=0 ; i<3 ; i++)
417 VectorClear (normal);
420 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
424 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
427 CreateBrushWindings (b);
438 vec_t BrushVolume (brush_t *brush)
443 vec_t d, area, volume;
449 // grab the first valid point as the corner
452 for (i=0 ; i<brush->numsides ; i++)
454 w = brush->sides[i].winding;
460 VectorCopy (w->p[0], corner);
462 // make tetrahedrons to all other faces
465 for ( ; i<brush->numsides ; i++)
467 w = brush->sides[i].winding;
470 plane = &mapplanes[brush->sides[i].planenum];
471 d = -(DotProduct (corner, plane->normal) - plane->dist);
472 area = WindingArea (w);
484 writes a map with the split bsp brushes
487 void WriteBSPBrushMap( char *name, brush_t *list )
496 Sys_Printf( "Writing %s\n", name );
498 /* open the map file */
499 f = fopen( name, "wb" );
501 Error( "Can't write %s\b", name );
503 fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
505 for ( ; list ; list=list->next )
508 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
510 w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
512 fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
513 fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
514 fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
516 fprintf (f, "notexture 0 0 0 1 1\n" );
530 FilterBrushIntoTree_r()
531 adds brush reference to any intersecting bsp leafnode
534 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
536 brush_t *front, *back;
544 /* add it to the leaf list */
545 if( node->planenum == PLANENUM_LEAF )
547 /* something somewhere is hammering brushlist */
548 b->next = node->brushlist;
551 /* classify the leaf by the structural brush */
556 node->opaque = qtrue;
557 node->areaportal = qfalse;
559 else if( b->compileFlags & C_AREAPORTAL )
562 node->areaportal = qtrue;
569 /* split it by the node plane */
571 SplitBrush( b, node->planenum, &front, &back );
575 c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
576 c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
584 FilterDetailBrushesIntoTree
585 fragment all the detail brushes into the structural leafs
588 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
592 int c_unique, c_clusters;
597 Sys_FPrintf( SYS_VRB, "--- FilterDetailBrushesIntoTree ---\n" );
599 /* walk the list of brushes */
602 for( b = e->brushes; b; b = b->next )
607 newb = CopyBrush( b );
608 r = FilterBrushIntoTree_r( newb, tree->headnode );
611 /* mark all sides as visible so drawsurfs are created */
614 for( i = 0; i < b->numsides; i++ )
616 if( b->sides[ i ].winding )
617 b->sides[ i ].visible = qtrue;
622 /* emit some statistics */
623 Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
624 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
628 =====================
629 FilterStructuralBrushesIntoTree
631 Mark the leafs as opaque and areaportals
632 =====================
634 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
637 int c_unique, c_clusters;
640 Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
644 for ( b = e->brushes ; b ; b = b->next ) {
649 newb = CopyBrush( b );
650 r = FilterBrushIntoTree_r( newb, tree->headnode );
653 // mark all sides as visible so drawsurfs are created
655 for ( i = 0 ; i < b->numsides ; i++ ) {
656 if ( b->sides[i].winding ) {
657 b->sides[i].visible = qtrue;
663 /* emit some statistics */
664 Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
665 Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
675 tree_t *AllocTree (void)
679 tree = safe_malloc(sizeof(*tree));
680 memset (tree, 0, sizeof(*tree));
681 ClearBounds (tree->mins, tree->maxs);
691 node_t *AllocNode (void)
695 node = safe_malloc(sizeof(*node));
696 memset (node, 0, sizeof(*node));
706 Returns true if the winding would be crunched out of
707 existance by the vertex snapping.
710 #define EDGE_LENGTH 0.2
711 qboolean WindingIsTiny (winding_t *w)
714 if (WindingArea (w) < 1)
724 for (i=0 ; i<w->numpoints ; i++)
726 j = i == w->numpoints - 1 ? 0 : i+1;
727 VectorSubtract (w->p[j], w->p[i], delta);
728 len = VectorLength (delta);
729 if (len > EDGE_LENGTH)
742 Returns true if the winding still has one of the points
743 from basewinding for plane
746 qboolean WindingIsHuge (winding_t *w)
750 for (i=0 ; i<w->numpoints ; i++)
752 for (j=0 ; j<3 ; j++)
753 if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
759 //============================================================
767 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
776 for (i=0 ; i<brush->numsides ; i++)
778 w = brush->sides[i].winding;
781 for (j=0 ; j<w->numpoints ; j++)
783 d = DotProduct (w->p[j], plane->normal) - plane->dist;
803 generates two new brushes, leaving the original unchanged
806 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
810 winding_t *w, *cw[2], *midwinding;
811 plane_t *plane, *plane2;
813 float d, d_front, d_back;
818 plane = &mapplanes[planenum];
821 d_front = d_back = 0;
822 for (i=0 ; i<brush->numsides ; i++)
824 w = brush->sides[i].winding;
827 for (j=0 ; j<w->numpoints ; j++)
829 d = DotProduct (w->p[j], plane->normal) - plane->dist;
830 if (d > 0 && d > d_front)
832 if (d < 0 && d < d_back)
837 if (d_front < 0.1) // PLANESIDE_EPSILON)
839 *back = CopyBrush( brush );
843 if (d_back > -0.1) // PLANESIDE_EPSILON)
845 *front = CopyBrush( brush );
849 // create a new winding from the split plane
850 w = BaseWindingForPlane (plane->normal, plane->dist);
851 for (i=0 ; i<brush->numsides && w ; i++)
853 if ( brush->sides[i].backSide ) {
854 continue; // fake back-sided polygons never split
856 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
857 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
860 if (!w || WindingIsTiny (w) )
861 { // the brush isn't really split
864 side = BrushMostlyOnSide (brush, plane);
865 if (side == PSIDE_FRONT)
866 *front = CopyBrush (brush);
867 if (side == PSIDE_BACK)
868 *back = CopyBrush (brush);
872 if( WindingIsHuge( w ) )
873 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
879 for (i=0 ; i<2 ; i++)
881 b[i] = AllocBrush (brush->numsides+1);
882 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
885 b[i]->original = brush->original;
888 // split all the current windings
890 for (i=0 ; i<brush->numsides ; i++)
892 s = &brush->sides[i];
896 ClipWindingEpsilon (w, plane->normal, plane->dist,
897 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
898 for (j=0 ; j<2 ; j++)
902 cs = &b[j]->sides[b[j]->numsides];
910 // see if we have valid polygons on both sides
911 for (i=0 ; i<2 ; i++)
914 for (j=0 ; j<3 ; j++)
916 if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD)
918 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
923 if (b[i]->numsides < 3 || j < 3)
930 if ( !(b[0] && b[1]) )
933 Sys_FPrintf (SYS_VRB,"split removed brush\n");
935 Sys_FPrintf (SYS_VRB,"split not on both sides\n");
939 *front = CopyBrush (brush);
944 *back = CopyBrush (brush);
949 // add the midwinding to both sides
950 for (i=0 ; i<2 ; i++)
952 cs = &b[i]->sides[b[i]->numsides];
955 cs->planenum = planenum^i^1;
956 cs->shaderInfo = NULL;
958 cs->winding = CopyWinding (midwinding);
960 cs->winding = midwinding;
968 for (i=0 ; i<2 ; i++)
970 v1 = BrushVolume (b[i]);
975 // Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");