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
29 // if a brush just barely pokes onto the other side,
30 // let it slide by without chopping
31 #define PLANESIDE_EPSILON 0.001
36 #define PSIDE_BOTH ( PSIDE_FRONT | PSIDE_BACK )
37 #define PSIDE_FACING 4
40 void FindBrushInTree( node_t *node, int brushnum ){
43 if ( node->planenum == PLANENUM_LEAF ) {
44 for ( b = node->brushlist ; b ; b = b->next )
45 if ( b->original->brushnum == brushnum ) {
46 Sys_Printf( "here\n" );
50 FindBrushInTree( node->children[0], brushnum );
51 FindBrushInTree( node->children[1], brushnum );
54 //==================================================
61 void DrawBrushList( bspbrush_t *brush, node_t *node ){
66 for ( ; brush ; brush = brush->next )
68 for ( i = 0 ; i < brush->numsides ; i++ )
74 if ( s->texinfo == TEXINFO_NODE ) {
75 GLS_Winding( s->winding, 1 );
77 else if ( !s->visible ) {
78 GLS_Winding( s->winding, 2 );
81 GLS_Winding( s->winding, 0 );
93 void WriteBrushList( char *name, bspbrush_t *brush, qboolean onlyvis ){
98 Sys_FPrintf( SYS_VRB, "writing %s\n", name );
99 f = SafeOpenWrite( name );
101 for ( ; brush ; brush = brush->next )
103 for ( i = 0 ; i < brush->numsides ; i++ )
105 s = &brush->sides[i];
109 if ( onlyvis && !s->visible ) {
112 OutputWinding( brush->sides[i].winding, f );
119 void PrintBrush( bspbrush_t *brush ){
122 Sys_Printf( "brush: %p\n", brush );
123 for ( i = 0; i < brush->numsides ; i++ )
125 pw( brush->sides[i].winding );
134 Sets the mins/maxs based on the windings
137 void BoundBrush( bspbrush_t *brush ){
141 ClearBounds( brush->mins, brush->maxs );
142 for ( i = 0 ; i < brush->numsides ; i++ )
144 w = brush->sides[i].winding;
148 for ( j = 0 ; j < w->numpoints ; j++ )
149 AddPointToBounds( w->p[j], brush->mins, brush->maxs );
159 void CreateBrushWindings( bspbrush_t *brush ){
165 for ( i = 0 ; i < brush->numsides ; i++ )
167 side = &brush->sides[i];
168 plane = &mapplanes[side->planenum];
169 w = BaseWindingForPlane( plane->normal, plane->dist );
170 for ( j = 0 ; j < brush->numsides && w; j++ )
175 if ( brush->sides[j].bevel ) {
178 plane = &mapplanes[brush->sides[j].planenum ^ 1];
179 ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); //CLIP_EPSILON);
192 Creates a new axial brush
195 bspbrush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){
203 for ( i = 0 ; i < 3 ; i++ )
205 VectorClear( normal );
208 b->sides[i].planenum = FindFloatPlane( normal, dist );
212 b->sides[3 + i].planenum = FindFloatPlane( normal, dist );
215 CreateBrushWindings( b );
226 vec_t BrushVolume( bspbrush_t *brush ){
230 vec_t d, area, volume;
237 // grab the first valid point as the corner
240 for ( i = 0 ; i < brush->numsides ; i++ )
242 w = brush->sides[i].winding;
250 VectorCopy( w->p[0], corner );
252 // make tetrahedrons to all other faces
255 for ( ; i < brush->numsides ; i++ )
257 w = brush->sides[i].winding;
261 plane = &mapplanes[brush->sides[i].planenum];
262 d = -( DotProduct( corner, plane->normal ) - plane->dist );
263 area = WindingArea( w );
276 int CountBrushList( bspbrush_t *brushes ){
280 for ( ; brushes ; brushes = brushes->next )
290 tree_t *AllocTree( void ){
293 tree = malloc( sizeof( *tree ) );
294 memset( tree, 0, sizeof( *tree ) );
295 ClearBounds( tree->mins, tree->maxs );
305 node_t *AllocNode( void ){
308 node = malloc( sizeof( *node ) );
309 memset( node, 0, sizeof( *node ) );
320 bspbrush_t *AllocBrush( int numsides ){
324 c = (int)&( ( (bspbrush_t *)0 )->sides[numsides] );
327 if ( numthreads == 1 ) {
338 void FreeBrush( bspbrush_t *brushes ){
341 for ( i = 0 ; i < brushes->numsides ; i++ )
342 if ( brushes->sides[i].winding ) {
343 FreeWinding( brushes->sides[i].winding );
346 if ( numthreads == 1 ) {
357 void FreeBrushList( bspbrush_t *brushes ){
360 for ( ; brushes ; brushes = next )
362 next = brushes->next;
364 FreeBrush( brushes );
372 Duplicates the brush, the sides, and the windings
375 bspbrush_t *CopyBrush( bspbrush_t *brush ){
376 bspbrush_t *newbrush;
380 size = (int)&( ( (bspbrush_t *)0 )->sides[brush->numsides] );
382 newbrush = AllocBrush( brush->numsides );
383 memcpy( newbrush, brush, size );
385 for ( i = 0 ; i < brush->numsides ; i++ )
387 if ( brush->sides[i].winding ) {
388 newbrush->sides[i].winding = CopyWinding( brush->sides[i].winding );
402 node_t *PointInLeaf( node_t *node, vec3_t point ){
406 while ( node->planenum != PLANENUM_LEAF )
408 plane = &mapplanes[node->planenum];
409 d = DotProduct( point, plane->normal ) - plane->dist;
411 node = node->children[0];
414 node = node->children[1];
421 //========================================================
427 Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
430 int BoxOnPlaneSide( vec3_t mins, vec3_t maxs, plane_t *plane ){
436 // axial planes are easy
437 if ( plane->type < 3 ) {
439 if ( maxs[plane->type] > plane->dist + PLANESIDE_EPSILON ) {
442 if ( mins[plane->type] < plane->dist - PLANESIDE_EPSILON ) {
448 // create the proper leading and trailing verts for the box
450 for ( i = 0 ; i < 3 ; i++ )
452 if ( plane->normal[i] < 0 ) {
453 corners[0][i] = mins[i];
454 corners[1][i] = maxs[i];
458 corners[1][i] = mins[i];
459 corners[0][i] = maxs[i];
463 dist1 = DotProduct( plane->normal, corners[0] ) - plane->dist;
464 dist2 = DotProduct( plane->normal, corners[1] ) - plane->dist;
466 if ( dist1 >= PLANESIDE_EPSILON ) {
469 if ( dist2 < PLANESIDE_EPSILON ) {
478 QuickTestBrushToPlanenum
482 int QuickTestBrushToPlanenum( bspbrush_t *brush, int planenum, int *numsplits ){
489 // if the brush actually uses the planenum,
490 // we can tell the side for sure
491 for ( i = 0 ; i < brush->numsides ; i++ )
493 num = brush->sides[i].planenum;
494 if ( num >= 0x10000 ) {
495 Error( "bad planenum" );
497 if ( num == planenum ) {
498 return PSIDE_BACK | PSIDE_FACING;
500 if ( num == ( planenum ^ 1 ) ) {
501 return PSIDE_FRONT | PSIDE_FACING;
506 plane = &mapplanes[planenum];
507 s = BoxOnPlaneSide( brush->mins, brush->maxs, plane );
509 // if both sides, count the visible faces split
510 if ( s == PSIDE_BOTH ) {
523 int TestBrushToPlanenum( bspbrush_t *brush, int planenum,
524 int *numsplits, qboolean *hintsplit, int *epsilonbrush ){
529 vec_t d, d_front, d_back;
535 // if the brush actually uses the planenum,
536 // we can tell the side for sure
537 for ( i = 0 ; i < brush->numsides ; i++ )
539 num = brush->sides[i].planenum;
540 if ( num >= 0x10000 ) {
541 Error( "bad planenum" );
543 if ( num == planenum ) {
544 return PSIDE_BACK | PSIDE_FACING;
546 if ( num == ( planenum ^ 1 ) ) {
547 return PSIDE_FRONT | PSIDE_FACING;
552 plane = &mapplanes[planenum];
553 s = BoxOnPlaneSide( brush->mins, brush->maxs, plane );
555 if ( s != PSIDE_BOTH ) {
559 // if both sides, count the visible faces split
560 d_front = d_back = 0;
562 for ( i = 0 ; i < brush->numsides ; i++ )
564 if ( brush->sides[i].texinfo == TEXINFO_NODE ) {
565 continue; // on node, don't worry about splits
567 if ( !brush->sides[i].visible ) {
568 continue; // we don't care about non-visible
570 w = brush->sides[i].winding;
575 for ( j = 0 ; j < w->numpoints; j++ )
577 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
585 if ( d > 0.1 ) { // PLANESIDE_EPSILON)
588 if ( d < -0.1 ) { // PLANESIDE_EPSILON)
592 if ( front && back ) {
593 if ( !( brush->sides[i].surf & SURF_SKIP ) ) {
595 if ( brush->sides[i].surf & SURF_HINT ) {
602 if ( ( d_front > 0.0 && d_front < 1.0 )
603 || ( d_back < 0.0 && d_back > -1.0 ) ) {
608 if ( *numsplits == 0 ) { // didn't really need to be split
624 //========================================================
630 Returns true if the winding would be crunched out of
631 existance by the vertex snapping.
634 #define EDGE_LENGTH 0.2
635 qboolean WindingIsTiny( winding_t *w ){
637 if ( WindingArea( w ) < 1 ) {
648 for ( i = 0 ; i < w->numpoints ; i++ )
650 j = i == w->numpoints - 1 ? 0 : i + 1;
651 VectorSubtract( w->p[j], w->p[i], delta );
652 len = (float) VectorLength( delta );
653 if ( len > EDGE_LENGTH ) {
654 if ( ++edges == 3 ) {
667 Returns true if the winding still has one of the points
668 from basewinding for plane
671 qboolean WindingIsHuge( winding_t *w ){
674 for ( i = 0 ; i < w->numpoints ; i++ )
676 for ( j = 0 ; j < 3 ; j++ )
677 if ( w->p[i][j] < -8000 || w->p[i][j] > 8000 ) {
684 //============================================================
691 void LeafNode( node_t *node, bspbrush_t *brushes ){
695 node->planenum = PLANENUM_LEAF;
698 for ( b = brushes ; b ; b = b->next )
700 // if the brush is solid and all of its sides are on nodes,
701 // it eats everything
702 if ( b->original->contents & CONTENTS_SOLID ) {
703 for ( i = 0 ; i < b->numsides ; i++ )
704 if ( b->sides[i].texinfo != TEXINFO_NODE ) {
707 if ( i == b->numsides ) {
708 node->contents = CONTENTS_SOLID;
712 node->contents |= b->original->contents;
715 node->brushlist = brushes;
719 //============================================================
721 void CheckPlaneAgainstParents( int pnum, node_t *node ){
724 for ( p = node->parent ; p ; p = p->parent )
726 if ( p->planenum == pnum ) {
727 Error( "Tried parent" );
732 qboolean CheckPlaneAgainstVolume( int pnum, node_t *node ){
733 bspbrush_t *front, *back;
736 SplitBrush( node->volume, pnum, &front, &back );
738 good = ( front && back );
754 Using a hueristic, choses one of the sides out of the brushlist
755 to partition the brushes with.
756 Returns NULL if there are no valid planes to split with..
759 side_t *SelectSplitSide( bspbrush_t *brushes, node_t *node ){
760 int value, bestvalue;
761 bspbrush_t *brush, *test;
762 side_t *side, *bestside;
763 int i, j, pass, numpasses;
766 int front, back, both, facing, splits;
776 // the search order goes: visible-structural, visible-detail,
777 // nonvisible-structural, nonvisible-detail.
778 // If any valid plane is available in a pass, no further
779 // passes will be tried.
781 for ( pass = 0 ; pass < numpasses ; pass++ )
783 for ( brush = brushes ; brush ; brush = brush->next )
785 if ( ( pass & 1 ) && !( brush->original->contents & CONTENTS_DETAIL ) ) {
788 if ( !( pass & 1 ) && ( brush->original->contents & CONTENTS_DETAIL ) ) {
791 for ( i = 0 ; i < brush->numsides ; i++ )
793 side = brush->sides + i;
795 continue; // never use a bevel as a spliter
797 if ( !side->winding ) {
798 continue; // nothing visible, so it can't split
800 if ( side->texinfo == TEXINFO_NODE ) {
801 continue; // allready a node splitter
803 if ( side->tested ) {
804 continue; // we allready have metrics for this plane
806 if ( side->surf & SURF_SKIP ) {
807 continue; // skip surfaces are never chosen
809 if ( side->visible ^ ( pass < 2 ) ) {
810 continue; // only check visible faces on first pass
813 pnum = side->planenum;
814 pnum &= ~1; // allways use positive facing plane
816 CheckPlaneAgainstParents( pnum, node );
818 if ( !CheckPlaneAgainstVolume( pnum, node ) ) {
819 continue; // would produce a tiny volume
829 for ( test = brushes ; test ; test = test->next )
831 s = TestBrushToPlanenum( test, pnum, &bsplits, &hintsplit, &epsilonbrush );
834 if ( bsplits && ( s & PSIDE_FACING ) ) {
835 Error( "PSIDE_FACING with splits" );
839 // if the brush shares this face, don't bother
840 // testing that facenum as a splitter again
841 if ( s & PSIDE_FACING ) {
843 for ( j = 0 ; j < test->numsides ; j++ )
845 if ( ( test->sides[j].planenum & ~1 ) == pnum ) {
846 test->sides[j].tested = true;
850 if ( s & PSIDE_FRONT ) {
853 if ( s & PSIDE_BACK ) {
856 if ( s == PSIDE_BOTH ) {
861 // give a value estimate for using this plane
863 value = 5 * facing - 5 * splits - abs( front - back );
864 // value = -5*splits;
865 // value = 5*facing - 5*splits;
866 if ( mapplanes[pnum].type < 3 ) {
867 value += 5; // axial is better
869 value -= epsilonbrush * 1000; // avoid!
871 // never split a hint side except with another hint
872 if ( hintsplit && !( side->surf & SURF_HINT ) ) {
876 // save off the side test so we don't need
877 // to recalculate it when we actually seperate
879 if ( value > bestvalue ) {
883 for ( test = brushes ; test ; test = test->next )
884 test->side = test->testside;
889 // if we found a good plane, don't bother trying any
893 if ( numthreads == 1 ) {
898 node->detail_seperator = true; // not needed for vis
905 // clear all the tested flags we set
907 for ( brush = brushes ; brush ; brush = brush->next )
909 for ( i = 0 ; i < brush->numsides ; i++ )
910 brush->sides[i].tested = false;
923 int BrushMostlyOnSide( bspbrush_t *brush, plane_t *plane ){
931 for ( i = 0 ; i < brush->numsides ; i++ )
933 w = brush->sides[i].winding;
937 for ( j = 0 ; j < w->numpoints ; j++ )
939 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
957 Generates two new brushes, leaving the original
961 void SplitBrush( bspbrush_t *brush, int planenum,
962 bspbrush_t **front, bspbrush_t **back ){
965 winding_t *w, *cw[2], *midwinding;
966 plane_t *plane, *plane2;
968 float d, d_front, d_back;
970 *front = *back = NULL;
971 plane = &mapplanes[planenum];
974 d_front = d_back = 0;
975 for ( i = 0 ; i < brush->numsides ; i++ )
977 w = brush->sides[i].winding;
981 for ( j = 0 ; j < w->numpoints ; j++ )
983 d = DotProduct( w->p[j], plane->normal ) - plane->dist;
984 if ( d > 0 && d > d_front ) {
987 if ( d < 0 && d < d_back ) {
992 if ( d_front < 0.1 ) { // PLANESIDE_EPSILON)
994 *back = CopyBrush( brush );
997 if ( d_back > -0.1 ) { // PLANESIDE_EPSILON)
999 *front = CopyBrush( brush );
1003 // create a new winding from the split plane
1005 w = BaseWindingForPlane( plane->normal, plane->dist );
1006 for ( i = 0 ; i < brush->numsides && w ; i++ )
1008 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1009 ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON);
1012 if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split
1015 side = BrushMostlyOnSide( brush, plane );
1016 if ( side == PSIDE_FRONT ) {
1017 *front = CopyBrush( brush );
1019 if ( side == PSIDE_BACK ) {
1020 *back = CopyBrush( brush );
1025 if ( WindingIsHuge( w ) ) {
1026 Sys_FPrintf( SYS_VRB, "WARNING: huge winding\n" );
1031 // split it for real
1033 for ( i = 0 ; i < 2 ; i++ )
1035 b[i] = AllocBrush( brush->numsides + 1 );
1036 b[i]->original = brush->original;
1039 // split all the current windings
1041 for ( i = 0 ; i < brush->numsides ; i++ )
1043 s = &brush->sides[i];
1048 ClipWindingEpsilon( w, plane->normal, plane->dist,
1049 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] );
1050 for ( j = 0 ; j < 2 ; j++ )
1056 if ( WindingIsTiny( cw[j] ) ) {
1057 FreeWinding( cw[j] );
1061 cs = &b[j]->sides[b[j]->numsides];
1064 // cs->planenum = s->planenum;
1065 // cs->texinfo = s->texinfo;
1066 // cs->visible = s->visible;
1067 // cs->original = s->original;
1068 cs->winding = cw[j];
1074 // see if we have valid polygons on both sides
1076 for ( i = 0 ; i < 2 ; i++ )
1079 for ( j = 0 ; j < 3 ; j++ )
1081 if ( b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096 ) {
1082 Sys_FPrintf( SYS_VRB, "bogus brush after clip\n" );
1087 if ( b[i]->numsides < 3 || j < 3 ) {
1093 if ( !( b[0] && b[1] ) ) {
1094 if ( !b[0] && !b[1] ) {
1095 Sys_FPrintf( SYS_VRB, "split removed brush\n" );
1098 Sys_FPrintf( SYS_VRB, "split not on both sides\n" );
1102 *front = CopyBrush( brush );
1106 *back = CopyBrush( brush );
1111 // add the midwinding to both sides
1112 for ( i = 0 ; i < 2 ; i++ )
1114 cs = &b[i]->sides[b[i]->numsides];
1117 cs->planenum = planenum ^ i ^ 1;
1118 cs->texinfo = TEXINFO_NODE;
1119 cs->visible = false;
1122 cs->winding = CopyWinding( midwinding );
1125 cs->winding = midwinding;
1133 for ( i = 0 ; i < 2 ; i++ )
1135 v1 = BrushVolume( b[i] );
1139 Sys_FPrintf( SYS_VRB, "tiny volume after clip\n" );
1153 void SplitBrushList( bspbrush_t *brushes,
1154 node_t *node, bspbrush_t **front, bspbrush_t **back ){
1155 bspbrush_t *brush, *newbrush, *newbrush2;
1160 *front = *back = NULL;
1162 for ( brush = brushes ; brush ; brush = brush->next )
1164 sides = brush->side;
1166 if ( sides == PSIDE_BOTH ) { // split into two brushes
1167 SplitBrush( brush, node->planenum, &newbrush, &newbrush2 );
1169 newbrush->next = *front;
1173 newbrush2->next = *back;
1179 newbrush = CopyBrush( brush );
1181 // if the planenum is actualy a part of the brush
1182 // find the plane and flag it as used so it won't be tried
1183 // as a splitter again
1184 if ( sides & PSIDE_FACING ) {
1185 for ( i = 0 ; i < newbrush->numsides ; i++ )
1187 side = newbrush->sides + i;
1188 if ( ( side->planenum & ~1 ) == node->planenum ) {
1189 side->texinfo = TEXINFO_NODE;
1195 if ( sides & PSIDE_FRONT ) {
1196 newbrush->next = *front;
1200 if ( sides & PSIDE_BACK ) {
1201 newbrush->next = *back;
1214 node_t *BuildTree_r( node_t *node, bspbrush_t *brushes ){
1218 bspbrush_t *children[2];
1220 if ( numthreads == 1 ) {
1225 DrawBrushList( brushes, node );
1228 // find the best plane to use as a splitter
1229 bestside = SelectSplitSide( brushes, node );
1233 node->planenum = -1;
1234 LeafNode( node, brushes );
1238 // this is a splitplane node
1239 node->side = bestside;
1240 node->planenum = bestside->planenum & ~1; // always use front facing
1242 SplitBrushList( brushes, node, &children[0], &children[1] );
1243 FreeBrushList( brushes );
1245 // allocate children before recursing
1246 for ( i = 0 ; i < 2 ; i++ )
1248 newnode = AllocNode();
1249 newnode->parent = node;
1250 node->children[i] = newnode;
1253 SplitBrush( node->volume, node->planenum, &node->children[0]->volume,
1254 &node->children[1]->volume );
1256 // recursively process children
1257 for ( i = 0 ; i < 2 ; i++ )
1259 node->children[i] = BuildTree_r( node->children[i], children[i] );
1265 //===========================================================
1271 The incoming list will be freed before exiting
1274 tree_t *BrushBSP( bspbrush_t *brushlist, vec3_t mins, vec3_t maxs ){
1277 int c_faces, c_nonvisfaces;
1283 Sys_FPrintf( SYS_VRB, "--- BrushBSP ---\n" );
1290 for ( b = brushlist ; b ; b = b->next )
1294 volume = BrushVolume( b );
1295 if ( volume < microvolume ) {
1296 Sys_FPrintf( SYS_WRN, "WARNING: entity %i, brush %i: microbrush\n",
1297 b->original->entitynum, b->original->brushnum );
1300 for ( i = 0 ; i < b->numsides ; i++ )
1302 if ( b->sides[i].bevel ) {
1305 if ( !b->sides[i].winding ) {
1308 if ( b->sides[i].texinfo == TEXINFO_NODE ) {
1311 if ( b->sides[i].visible ) {
1319 AddPointToBounds( b->mins, tree->mins, tree->maxs );
1320 AddPointToBounds( b->maxs, tree->mins, tree->maxs );
1323 Sys_FPrintf( SYS_VRB, "%5i brushes\n", c_brushes );
1324 Sys_FPrintf( SYS_VRB, "%5i visible faces\n", c_faces );
1325 Sys_FPrintf( SYS_VRB, "%5i nonvisible faces\n", c_nonvisfaces );
1331 node->volume = BrushFromBounds( mins, maxs );
1333 tree->headnode = node;
1335 node = BuildTree_r( node, brushlist );
1336 Sys_FPrintf( SYS_VRB, "%5i visible nodes\n", c_nodes / 2 - c_nonvis );
1337 Sys_FPrintf( SYS_VRB, "%5i nonvis nodes\n", c_nonvis );
1338 Sys_FPrintf( SYS_VRB, "%5i leafs\n", ( c_nodes + 1 ) / 2 );
1341 static node_t *tnode;
1347 tnode = PointInLeaf( tree->headnode, p );
1348 Sys_Printf( "contents: %i\n", tnode->contents );