2 Copyright (C) 1999-2006 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)
44 if (node->planenum == PLANENUM_LEAF)
46 for (b=node->brushlist ; b ; b=b->next)
47 if (b->original->brushnum == brushnum)
48 Sys_Printf ("here\n");
51 FindBrushInTree (node->children[0], brushnum);
52 FindBrushInTree (node->children[1], brushnum);
55 //==================================================
62 void DrawBrushList (bspbrush_t *brush, node_t *node)
68 for ( ; brush ; brush=brush->next)
70 for (i=0 ; i<brush->numsides ; i++)
75 if (s->texinfo == TEXINFO_NODE)
76 GLS_Winding (s->winding, 1);
78 GLS_Winding (s->winding, 2);
80 GLS_Winding (s->winding, 0);
91 void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
97 Sys_FPrintf( SYS_VRB, "writing %s\n", name);
98 f = SafeOpenWrite (name);
100 for ( ; brush ; brush=brush->next)
102 for (i=0 ; i<brush->numsides ; i++)
104 s = &brush->sides[i];
107 if (onlyvis && !s->visible)
109 OutputWinding (brush->sides[i].winding, f);
116 void PrintBrush (bspbrush_t *brush)
120 Sys_Printf ("brush: %p\n", brush);
121 for (i=0;i<brush->numsides ; i++)
123 pw(brush->sides[i].winding);
132 Sets the mins/maxs based on the windings
135 void BoundBrush (bspbrush_t *brush)
140 ClearBounds (brush->mins, brush->maxs);
141 for (i=0 ; i<brush->numsides ; i++)
143 w = brush->sides[i].winding;
146 for (j=0 ; j<w->numpoints ; j++)
147 AddPointToBounds (w->p[j], brush->mins, brush->maxs);
157 void CreateBrushWindings (bspbrush_t *brush)
164 for (i=0 ; i<brush->numsides ; i++)
166 side = &brush->sides[i];
167 plane = &mapplanes[side->planenum];
168 w = BaseWindingForPlane (plane->normal, plane->dist);
169 for (j=0 ; j<brush->numsides && w; j++)
173 if (brush->sides[j].bevel)
175 plane = &mapplanes[brush->sides[j].planenum^1];
176 ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
189 Creates a new axial brush
192 bspbrush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
201 for (i=0 ; i<3 ; i++)
203 VectorClear (normal);
206 b->sides[i].planenum = FindFloatPlane (normal, dist);
210 b->sides[3+i].planenum = FindFloatPlane (normal, dist);
213 CreateBrushWindings (b);
224 vec_t BrushVolume (bspbrush_t *brush)
229 vec_t d, area, volume;
235 // grab the first valid point as the corner
238 for (i=0 ; i<brush->numsides ; i++)
240 w = brush->sides[i].winding;
246 VectorCopy (w->p[0], corner);
248 // make tetrahedrons to all other faces
251 for ( ; i<brush->numsides ; i++)
253 w = brush->sides[i].winding;
256 plane = &mapplanes[brush->sides[i].planenum];
257 d = -(DotProduct (corner, plane->normal) - plane->dist);
258 area = WindingArea (w);
271 int CountBrushList (bspbrush_t *brushes)
276 for ( ; brushes ; brushes = brushes->next)
286 tree_t *AllocTree (void)
290 tree = malloc(sizeof(*tree));
291 memset (tree, 0, sizeof(*tree));
292 ClearBounds (tree->mins, tree->maxs);
302 node_t *AllocNode (void)
306 node = malloc(sizeof(*node));
307 memset (node, 0, sizeof(*node));
318 bspbrush_t *AllocBrush (int numsides)
323 c = (int)&(((bspbrush_t *)0)->sides[numsides]);
336 void FreeBrush (bspbrush_t *brushes)
340 for (i=0 ; i<brushes->numsides ; i++)
341 if (brushes->sides[i].winding)
342 FreeWinding(brushes->sides[i].winding);
354 void FreeBrushList (bspbrush_t *brushes)
358 for ( ; brushes ; brushes = next)
360 next = brushes->next;
370 Duplicates the brush, the sides, and the windings
373 bspbrush_t *CopyBrush (bspbrush_t *brush)
375 bspbrush_t *newbrush;
379 size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);
381 newbrush = AllocBrush (brush->numsides);
382 memcpy (newbrush, brush, size);
384 for (i=0 ; i<brush->numsides ; i++)
386 if (brush->sides[i].winding)
387 newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);
400 node_t *PointInLeaf (node_t *node, vec3_t point)
405 while (node->planenum != PLANENUM_LEAF)
407 plane = &mapplanes[node->planenum];
408 d = DotProduct (point, plane->normal) - plane->dist;
410 node = node->children[0];
412 node = node->children[1];
418 //========================================================
424 Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
427 int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
434 // axial planes are easy
438 if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
440 if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
445 // create the proper leading and trailing verts for the box
447 for (i=0 ; i<3 ; i++)
449 if (plane->normal[i] < 0)
451 corners[0][i] = mins[i];
452 corners[1][i] = maxs[i];
456 corners[1][i] = mins[i];
457 corners[0][i] = maxs[i];
461 dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
462 dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
464 if (dist1 >= PLANESIDE_EPSILON)
466 if (dist2 < PLANESIDE_EPSILON)
474 QuickTestBrushToPlanenum
478 int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
486 // if the brush actually uses the planenum,
487 // we can tell the side for sure
488 for (i=0 ; i<brush->numsides ; i++)
490 num = brush->sides[i].planenum;
492 Error ("bad planenum");
494 return PSIDE_BACK|PSIDE_FACING;
495 if (num == (planenum ^ 1) )
496 return PSIDE_FRONT|PSIDE_FACING;
500 plane = &mapplanes[planenum];
501 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
503 // if both sides, count the visible faces split
518 int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
519 int *numsplits, qboolean *hintsplit, int *epsilonbrush)
525 vec_t d, d_front, d_back;
531 // if the brush actually uses the planenum,
532 // we can tell the side for sure
533 for (i=0 ; i<brush->numsides ; i++)
535 num = brush->sides[i].planenum;
537 Error ("bad planenum");
539 return PSIDE_BACK|PSIDE_FACING;
540 if (num == (planenum ^ 1) )
541 return PSIDE_FRONT|PSIDE_FACING;
545 plane = &mapplanes[planenum];
546 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
551 // if both sides, count the visible faces split
552 d_front = d_back = 0;
554 for (i=0 ; i<brush->numsides ; i++)
556 if (brush->sides[i].texinfo == TEXINFO_NODE)
557 continue; // on node, don't worry about splits
558 if (!brush->sides[i].visible)
559 continue; // we don't care about non-visible
560 w = brush->sides[i].winding;
564 for (j=0 ; j<w->numpoints; j++)
566 d = DotProduct (w->p[j], plane->normal) - plane->dist;
572 if (d > 0.1) // PLANESIDE_EPSILON)
574 if (d < -0.1) // PLANESIDE_EPSILON)
579 if ( !(brush->sides[i].surf & SURF_SKIP) )
582 if (brush->sides[i].surf & SURF_HINT)
588 if ( (d_front > 0.0 && d_front < 1.0)
589 || (d_back < 0.0 && d_back > -1.0) )
594 { // didn't really need to be split
607 //========================================================
613 Returns true if the winding would be crunched out of
614 existance by the vertex snapping.
617 #define EDGE_LENGTH 0.2
618 qboolean WindingIsTiny (winding_t *w)
621 if (WindingArea (w) < 1)
631 for (i=0 ; i<w->numpoints ; i++)
633 j = i == w->numpoints - 1 ? 0 : i+1;
634 VectorSubtract (w->p[j], w->p[i], delta);
635 len = (float) VectorLength (delta);
636 if (len > EDGE_LENGTH)
650 Returns true if the winding still has one of the points
651 from basewinding for plane
654 qboolean WindingIsHuge (winding_t *w)
658 for (i=0 ; i<w->numpoints ; i++)
660 for (j=0 ; j<3 ; j++)
661 if (w->p[i][j] < -8000 || w->p[i][j] > 8000)
667 //============================================================
674 void LeafNode (node_t *node, bspbrush_t *brushes)
679 node->planenum = PLANENUM_LEAF;
682 for (b=brushes ; b ; b=b->next)
684 // if the brush is solid and all of its sides are on nodes,
685 // it eats everything
686 if (b->original->contents & CONTENTS_SOLID)
688 for (i=0 ; i<b->numsides ; i++)
689 if (b->sides[i].texinfo != TEXINFO_NODE)
691 if (i == b->numsides)
693 node->contents = CONTENTS_SOLID;
697 node->contents |= b->original->contents;
700 node->brushlist = brushes;
704 //============================================================
706 void CheckPlaneAgainstParents (int pnum, node_t *node)
710 for (p=node->parent ; p ; p=p->parent)
712 if (p->planenum == pnum)
713 Error ("Tried parent");
717 qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
719 bspbrush_t *front, *back;
722 SplitBrush (node->volume, pnum, &front, &back);
724 good = (front && back);
738 Using a hueristic, choses one of the sides out of the brushlist
739 to partition the brushes with.
740 Returns NULL if there are no valid planes to split with..
743 side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
745 int value, bestvalue;
746 bspbrush_t *brush, *test;
747 side_t *side, *bestside;
748 int i, j, pass, numpasses;
751 int front, back, both, facing, splits;
761 // the search order goes: visible-structural, visible-detail,
762 // nonvisible-structural, nonvisible-detail.
763 // If any valid plane is available in a pass, no further
764 // passes will be tried.
766 for (pass = 0 ; pass < numpasses ; pass++)
768 for (brush = brushes ; brush ; brush=brush->next)
770 if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
772 if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
774 for (i=0 ; i<brush->numsides ; i++)
776 side = brush->sides + i;
778 continue; // never use a bevel as a spliter
780 continue; // nothing visible, so it can't split
781 if (side->texinfo == TEXINFO_NODE)
782 continue; // allready a node splitter
784 continue; // we allready have metrics for this plane
785 if (side->surf & SURF_SKIP)
786 continue; // skip surfaces are never chosen
787 if ( side->visible ^ (pass<2) )
788 continue; // only check visible faces on first pass
790 pnum = side->planenum;
791 pnum &= ~1; // allways use positive facing plane
793 CheckPlaneAgainstParents (pnum, node);
795 if (!CheckPlaneAgainstVolume (pnum, node))
796 continue; // would produce a tiny volume
805 for (test = brushes ; test ; test=test->next)
807 s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);
810 if (bsplits && (s&PSIDE_FACING) )
811 Error ("PSIDE_FACING with splits");
814 // if the brush shares this face, don't bother
815 // testing that facenum as a splitter again
816 if (s & PSIDE_FACING)
819 for (j=0 ; j<test->numsides ; j++)
821 if ( (test->sides[j].planenum&~1) == pnum)
822 test->sides[j].tested = true;
833 // give a value estimate for using this plane
835 value = 5*facing - 5*splits - abs(front-back);
836 // value = -5*splits;
837 // value = 5*facing - 5*splits;
838 if (mapplanes[pnum].type < 3)
839 value+=5; // axial is better
840 value -= epsilonbrush*1000; // avoid!
842 // never split a hint side except with another hint
843 if (hintsplit && !(side->surf & SURF_HINT) )
846 // save off the side test so we don't need
847 // to recalculate it when we actually seperate
849 if (value > bestvalue)
854 for (test = brushes ; test ; test=test->next)
855 test->side = test->testside;
860 // if we found a good plane, don't bother trying any
870 node->detail_seperator = true; // not needed for vis
876 // clear all the tested flags we set
878 for (brush = brushes ; brush ; brush=brush->next)
880 for (i=0 ; i<brush->numsides ; i++)
881 brush->sides[i].tested = false;
894 int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
903 for (i=0 ; i<brush->numsides ; i++)
905 w = brush->sides[i].winding;
908 for (j=0 ; j<w->numpoints ; j++)
910 d = DotProduct (w->p[j], plane->normal) - plane->dist;
930 Generates two new brushes, leaving the original
934 void SplitBrush (bspbrush_t *brush, int planenum,
935 bspbrush_t **front, bspbrush_t **back)
939 winding_t *w, *cw[2], *midwinding;
940 plane_t *plane, *plane2;
942 float d, d_front, d_back;
944 *front = *back = NULL;
945 plane = &mapplanes[planenum];
948 d_front = d_back = 0;
949 for (i=0 ; i<brush->numsides ; i++)
951 w = brush->sides[i].winding;
954 for (j=0 ; j<w->numpoints ; j++)
956 d = DotProduct (w->p[j], plane->normal) - plane->dist;
957 if (d > 0 && d > d_front)
959 if (d < 0 && d < d_back)
963 if (d_front < 0.1) // PLANESIDE_EPSILON)
965 *back = CopyBrush (brush);
968 if (d_back > -0.1) // PLANESIDE_EPSILON)
970 *front = CopyBrush (brush);
974 // create a new winding from the split plane
976 w = BaseWindingForPlane (plane->normal, plane->dist);
977 for (i=0 ; i<brush->numsides && w ; i++)
979 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
980 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
983 if (!w || WindingIsTiny (w) )
984 { // the brush isn't really split
987 side = BrushMostlyOnSide (brush, plane);
988 if (side == PSIDE_FRONT)
989 *front = CopyBrush (brush);
990 if (side == PSIDE_BACK)
991 *back = CopyBrush (brush);
995 if (WindingIsHuge (w))
997 Sys_FPrintf( SYS_VRB, "WARNING: huge winding\n");
1002 // split it for real
1004 for (i=0 ; i<2 ; i++)
1006 b[i] = AllocBrush (brush->numsides+1);
1007 b[i]->original = brush->original;
1010 // split all the current windings
1012 for (i=0 ; i<brush->numsides ; i++)
1014 s = &brush->sides[i];
1018 ClipWindingEpsilon (w, plane->normal, plane->dist,
1019 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
1020 for (j=0 ; j<2 ; j++)
1025 if (WindingIsTiny (cw[j]))
1027 FreeWinding (cw[j]);
1031 cs = &b[j]->sides[b[j]->numsides];
1034 // cs->planenum = s->planenum;
1035 // cs->texinfo = s->texinfo;
1036 // cs->visible = s->visible;
1037 // cs->original = s->original;
1038 cs->winding = cw[j];
1044 // see if we have valid polygons on both sides
1046 for (i=0 ; i<2 ; i++)
1049 for (j=0 ; j<3 ; j++)
1051 if (b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096)
1053 Sys_FPrintf( SYS_VRB, "bogus brush after clip\n");
1058 if (b[i]->numsides < 3 || j < 3)
1065 if ( !(b[0] && b[1]) )
1068 Sys_FPrintf( SYS_VRB, "split removed brush\n");
1070 Sys_FPrintf( SYS_VRB, "split not on both sides\n");
1074 *front = CopyBrush (brush);
1079 *back = CopyBrush (brush);
1084 // add the midwinding to both sides
1085 for (i=0 ; i<2 ; i++)
1087 cs = &b[i]->sides[b[i]->numsides];
1090 cs->planenum = planenum^i^1;
1091 cs->texinfo = TEXINFO_NODE;
1092 cs->visible = false;
1095 cs->winding = CopyWinding (midwinding);
1097 cs->winding = midwinding;
1104 for (i=0 ; i<2 ; i++)
1106 v1 = BrushVolume (b[i]);
1111 Sys_FPrintf( SYS_VRB, "tiny volume after clip\n");
1125 void SplitBrushList (bspbrush_t *brushes,
1126 node_t *node, bspbrush_t **front, bspbrush_t **back)
1128 bspbrush_t *brush, *newbrush, *newbrush2;
1133 *front = *back = NULL;
1135 for (brush = brushes ; brush ; brush=brush->next)
1137 sides = brush->side;
1139 if (sides == PSIDE_BOTH)
1140 { // split into two brushes
1141 SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
1144 newbrush->next = *front;
1149 newbrush2->next = *back;
1155 newbrush = CopyBrush (brush);
1157 // if the planenum is actualy a part of the brush
1158 // find the plane and flag it as used so it won't be tried
1159 // as a splitter again
1160 if (sides & PSIDE_FACING)
1162 for (i=0 ; i<newbrush->numsides ; i++)
1164 side = newbrush->sides + i;
1165 if ( (side->planenum& ~1) == node->planenum)
1166 side->texinfo = TEXINFO_NODE;
1171 if (sides & PSIDE_FRONT)
1173 newbrush->next = *front;
1177 if (sides & PSIDE_BACK)
1179 newbrush->next = *back;
1192 node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
1197 bspbrush_t *children[2];
1199 if (numthreads == 1)
1203 DrawBrushList (brushes, node);
1205 // find the best plane to use as a splitter
1206 bestside = SelectSplitSide (brushes, node);
1211 node->planenum = -1;
1212 LeafNode (node, brushes);
1216 // this is a splitplane node
1217 node->side = bestside;
1218 node->planenum = bestside->planenum & ~1; // always use front facing
1220 SplitBrushList (brushes, node, &children[0], &children[1]);
1221 FreeBrushList (brushes);
1223 // allocate children before recursing
1224 for (i=0 ; i<2 ; i++)
1226 newnode = AllocNode ();
1227 newnode->parent = node;
1228 node->children[i] = newnode;
1231 SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
1232 &node->children[1]->volume);
1234 // recursively process children
1235 for (i=0 ; i<2 ; i++)
1237 node->children[i] = BuildTree_r (node->children[i], children[i]);
1243 //===========================================================
1249 The incoming list will be freed before exiting
1252 tree_t *BrushBSP (bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
1256 int c_faces, c_nonvisfaces;
1262 Sys_FPrintf( SYS_VRB, "--- BrushBSP ---\n");
1264 tree = AllocTree ();
1269 for (b=brushlist ; b ; b=b->next)
1273 volume = BrushVolume (b);
1274 if (volume < microvolume)
1276 Sys_Printf ("WARNING: entity %i, brush %i: microbrush\n",
1277 b->original->entitynum, b->original->brushnum);
1280 for (i=0 ; i<b->numsides ; i++)
1282 if (b->sides[i].bevel)
1284 if (!b->sides[i].winding)
1286 if (b->sides[i].texinfo == TEXINFO_NODE)
1288 if (b->sides[i].visible)
1294 AddPointToBounds (b->mins, tree->mins, tree->maxs);
1295 AddPointToBounds (b->maxs, tree->mins, tree->maxs);
1298 Sys_FPrintf( SYS_VRB, "%5i brushes\n", c_brushes);
1299 Sys_FPrintf( SYS_VRB, "%5i visible faces\n", c_faces);
1300 Sys_FPrintf( SYS_VRB, "%5i nonvisible faces\n", c_nonvisfaces);
1304 node = AllocNode ();
1306 node->volume = BrushFromBounds (mins, maxs);
1308 tree->headnode = node;
1310 node = BuildTree_r (node, brushlist);
1311 Sys_FPrintf( SYS_VRB, "%5i visible nodes\n", c_nodes/2 - c_nonvis);
1312 Sys_FPrintf( SYS_VRB, "%5i nonvis nodes\n", c_nonvis);
1313 Sys_FPrintf( SYS_VRB, "%5i leafs\n", (c_nodes+1)/2);
1316 static node_t *tnode;
1322 tnode = PointInLeaf (tree->headnode, p);
1323 Sys_Printf ("contents: %i\n", tnode->contents);