2 ===========================================================================
3 Copyright (C) 1997-2006 Id Software, Inc.
5 This file is part of Quake 2 Tools source code.
7 Quake 2 Tools source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
12 Quake 2 Tools source code is distributed in the hope that it will be
13 useful, 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 Quake 2 Tools source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
30 // if a brush just barely pokes onto the other side,
31 // let it slide by without chopping
32 #define PLANESIDE_EPSILON 0.001
37 #define PSIDE_BOTH (PSIDE_FRONT|PSIDE_BACK)
38 #define PSIDE_FACING 4
41 void FindBrushInTree (node_t *node, int brushnum)
45 if (node->planenum == PLANENUM_LEAF)
47 for (b=node->brushlist ; b ; b=b->next)
48 if (b->original->brushnum == brushnum)
52 FindBrushInTree (node->children[0], brushnum);
53 FindBrushInTree (node->children[1], brushnum);
56 //==================================================
63 void DrawBrushList (bspbrush_t *brush, node_t *node)
69 for ( ; brush ; brush=brush->next)
71 for (i=0 ; i<brush->numsides ; i++)
76 if (s->texinfo == TEXINFO_NODE)
77 GLS_Winding (s->winding, 1);
79 GLS_Winding (s->winding, 2);
81 GLS_Winding (s->winding, 0);
92 void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
98 qprintf ("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];
108 if (onlyvis && !s->visible)
110 OutputWinding (brush->sides[i].winding, f);
117 void PrintBrush (bspbrush_t *brush)
121 printf ("brush: %p\n", brush);
122 for (i=0;i<brush->numsides ; i++)
124 pw(brush->sides[i].winding);
133 Sets the mins/maxs based on the windings
136 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;
147 for (j=0 ; j<w->numpoints ; j++)
148 AddPointToBounds (w->p[j], brush->mins, brush->maxs);
158 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++)
174 if (brush->sides[j].bevel)
176 plane = &mapplanes[brush->sides[j].planenum^1];
177 ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
190 Creates a new axial brush
193 bspbrush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
202 for (i=0 ; i<3 ; i++)
204 VectorClear (normal);
207 b->sides[i].planenum = FindFloatPlane (normal, dist);
211 b->sides[3+i].planenum = FindFloatPlane (normal, dist);
214 CreateBrushWindings (b);
225 vec_t BrushVolume (bspbrush_t *brush)
230 vec_t d, area, volume;
236 // grab the first valid point as the corner
239 for (i=0 ; i<brush->numsides ; i++)
241 w = brush->sides[i].winding;
247 VectorCopy (w->p[0], corner);
249 // make tetrahedrons to all other faces
252 for ( ; i<brush->numsides ; i++)
254 w = brush->sides[i].winding;
257 plane = &mapplanes[brush->sides[i].planenum];
258 d = -(DotProduct (corner, plane->normal) - plane->dist);
259 area = WindingArea (w);
272 int CountBrushList (bspbrush_t *brushes)
277 for ( ; brushes ; brushes = brushes->next)
287 tree_t *AllocTree (void)
291 tree = malloc(sizeof(*tree));
292 memset (tree, 0, sizeof(*tree));
293 ClearBounds (tree->mins, tree->maxs);
303 node_t *AllocNode (void)
307 node = malloc(sizeof(*node));
308 memset (node, 0, sizeof(*node));
319 bspbrush_t *AllocBrush (int numsides)
324 c = (int)&(((bspbrush_t *)0)->sides[numsides]);
337 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);
355 void FreeBrushList (bspbrush_t *brushes)
359 for ( ; brushes ; brushes = next)
361 next = brushes->next;
371 Duplicates the brush, the sides, and the windings
374 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);
401 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];
413 node = node->children[1];
419 //========================================================
425 Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
428 int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
435 // axial planes are easy
439 if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
441 if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
446 // create the proper leading and trailing verts for the box
448 for (i=0 ; i<3 ; i++)
450 if (plane->normal[i] < 0)
452 corners[0][i] = mins[i];
453 corners[1][i] = maxs[i];
457 corners[1][i] = mins[i];
458 corners[0][i] = maxs[i];
462 dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
463 dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
465 if (dist1 >= PLANESIDE_EPSILON)
467 if (dist2 < PLANESIDE_EPSILON)
475 QuickTestBrushToPlanenum
479 int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
487 // if the brush actually uses the planenum,
488 // we can tell the side for sure
489 for (i=0 ; i<brush->numsides ; i++)
491 num = brush->sides[i].planenum;
493 Error ("bad planenum");
495 return PSIDE_BACK|PSIDE_FACING;
496 if (num == (planenum ^ 1) )
497 return PSIDE_FRONT|PSIDE_FACING;
501 plane = &mapplanes[planenum];
502 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
504 // if both sides, count the visible faces split
519 int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
520 int *numsplits, qboolean *hintsplit, int *epsilonbrush)
526 vec_t d, d_front, d_back;
532 // if the brush actually uses the planenum,
533 // we can tell the side for sure
534 for (i=0 ; i<brush->numsides ; i++)
536 num = brush->sides[i].planenum;
538 Error ("bad planenum");
540 return PSIDE_BACK|PSIDE_FACING;
541 if (num == (planenum ^ 1) )
542 return PSIDE_FRONT|PSIDE_FACING;
546 plane = &mapplanes[planenum];
547 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
552 // if both sides, count the visible faces split
553 d_front = d_back = 0;
555 for (i=0 ; i<brush->numsides ; i++)
557 if (brush->sides[i].texinfo == TEXINFO_NODE)
558 continue; // on node, don't worry about splits
559 if (!brush->sides[i].visible)
560 continue; // we don't care about non-visible
561 w = brush->sides[i].winding;
565 for (j=0 ; j<w->numpoints; j++)
567 d = DotProduct (w->p[j], plane->normal) - plane->dist;
573 if (d > 0.1) // PLANESIDE_EPSILON)
575 if (d < -0.1) // PLANESIDE_EPSILON)
580 if ( !(brush->sides[i].surf & SURF_SKIP) )
583 if (brush->sides[i].surf & SURF_HINT)
589 if ( (d_front > 0.0 && d_front < 1.0)
590 || (d_back < 0.0 && d_back > -1.0) )
595 { // didn't really need to be split
608 //========================================================
614 Returns true if the winding would be crunched out of
615 existance by the vertex snapping.
618 #define EDGE_LENGTH 0.2
619 qboolean WindingIsTiny (winding_t *w)
622 if (WindingArea (w) < 1)
632 for (i=0 ; i<w->numpoints ; i++)
634 j = i == w->numpoints - 1 ? 0 : i+1;
635 VectorSubtract (w->p[j], w->p[i], delta);
636 len = VectorLength (delta);
637 if (len > EDGE_LENGTH)
651 Returns true if the winding still has one of the points
652 from basewinding for plane
655 qboolean WindingIsHuge (winding_t *w)
659 for (i=0 ; i<w->numpoints ; i++)
661 for (j=0 ; j<3 ; j++)
662 if (w->p[i][j] < -8000 || w->p[i][j] > 8000)
668 //============================================================
675 void LeafNode (node_t *node, bspbrush_t *brushes)
680 node->planenum = PLANENUM_LEAF;
683 for (b=brushes ; b ; b=b->next)
685 // if the brush is solid and all of its sides are on nodes,
686 // it eats everything
687 if (b->original->contents & CONTENTS_SOLID)
689 for (i=0 ; i<b->numsides ; i++)
690 if (b->sides[i].texinfo != TEXINFO_NODE)
692 if (i == b->numsides)
694 node->contents = CONTENTS_SOLID;
698 node->contents |= b->original->contents;
701 node->brushlist = brushes;
705 //============================================================
707 void CheckPlaneAgainstParents (int pnum, node_t *node)
711 for (p=node->parent ; p ; p=p->parent)
713 if (p->planenum == pnum)
714 Error ("Tried parent");
718 qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
720 bspbrush_t *front, *back;
723 SplitBrush (node->volume, pnum, &front, &back);
725 good = (front && back);
739 Using a hueristic, choses one of the sides out of the brushlist
740 to partition the brushes with.
741 Returns NULL if there are no valid planes to split with..
744 side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
746 int value, bestvalue;
747 bspbrush_t *brush, *test;
748 side_t *side, *bestside;
749 int i, j, pass, numpasses;
752 int front, back, both, facing, splits;
762 // the search order goes: visible-structural, visible-detail,
763 // nonvisible-structural, nonvisible-detail.
764 // If any valid plane is available in a pass, no further
765 // passes will be tried.
767 for (pass = 0 ; pass < numpasses ; pass++)
769 for (brush = brushes ; brush ; brush=brush->next)
771 if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
773 if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
775 for (i=0 ; i<brush->numsides ; i++)
777 side = brush->sides + i;
779 continue; // never use a bevel as a spliter
781 continue; // nothing visible, so it can't split
782 if (side->texinfo == TEXINFO_NODE)
783 continue; // allready a node splitter
785 continue; // we allready have metrics for this plane
786 if (side->surf & SURF_SKIP)
787 continue; // skip surfaces are never chosen
788 if ( side->visible ^ (pass<2) )
789 continue; // only check visible faces on first pass
791 pnum = side->planenum;
792 pnum &= ~1; // allways use positive facing plane
794 CheckPlaneAgainstParents (pnum, node);
796 if (!CheckPlaneAgainstVolume (pnum, node))
797 continue; // would produce a tiny volume
806 for (test = brushes ; test ; test=test->next)
808 s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);
811 if (bsplits && (s&PSIDE_FACING) )
812 Error ("PSIDE_FACING with splits");
815 // if the brush shares this face, don't bother
816 // testing that facenum as a splitter again
817 if (s & PSIDE_FACING)
820 for (j=0 ; j<test->numsides ; j++)
822 if ( (test->sides[j].planenum&~1) == pnum)
823 test->sides[j].tested = true;
834 // give a value estimate for using this plane
836 value = 5*facing - 5*splits - abs(front-back);
837 // value = -5*splits;
838 // value = 5*facing - 5*splits;
839 if (mapplanes[pnum].type < 3)
840 value+=5; // axial is better
841 value -= epsilonbrush*1000; // avoid!
843 // never split a hint side except with another hint
844 if (hintsplit && !(side->surf & SURF_HINT) )
847 // save off the side test so we don't need
848 // to recalculate it when we actually seperate
850 if (value > bestvalue)
855 for (test = brushes ; test ; test=test->next)
856 test->side = test->testside;
861 // if we found a good plane, don't bother trying any
871 node->detail_seperator = true; // not needed for vis
877 // clear all the tested flags we set
879 for (brush = brushes ; brush ; brush=brush->next)
881 for (i=0 ; i<brush->numsides ; i++)
882 brush->sides[i].tested = false;
895 int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
904 for (i=0 ; i<brush->numsides ; i++)
906 w = brush->sides[i].winding;
909 for (j=0 ; j<w->numpoints ; j++)
911 d = DotProduct (w->p[j], plane->normal) - plane->dist;
931 Generates two new brushes, leaving the original
935 void SplitBrush (bspbrush_t *brush, int planenum,
936 bspbrush_t **front, bspbrush_t **back)
940 winding_t *w, *cw[2], *midwinding;
941 plane_t *plane, *plane2;
943 float d, d_front, d_back;
945 *front = *back = NULL;
946 plane = &mapplanes[planenum];
949 d_front = d_back = 0;
950 for (i=0 ; i<brush->numsides ; i++)
952 w = brush->sides[i].winding;
955 for (j=0 ; j<w->numpoints ; j++)
957 d = DotProduct (w->p[j], plane->normal) - plane->dist;
958 if (d > 0 && d > d_front)
960 if (d < 0 && d < d_back)
964 if (d_front < 0.1) // PLANESIDE_EPSILON)
966 *back = CopyBrush (brush);
969 if (d_back > -0.1) // PLANESIDE_EPSILON)
971 *front = CopyBrush (brush);
975 // create a new winding from the split plane
977 w = BaseWindingForPlane (plane->normal, plane->dist);
978 for (i=0 ; i<brush->numsides && w ; i++)
980 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
981 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
984 if (!w || WindingIsTiny (w) )
985 { // the brush isn't really split
988 side = BrushMostlyOnSide (brush, plane);
989 if (side == PSIDE_FRONT)
990 *front = CopyBrush (brush);
991 if (side == PSIDE_BACK)
992 *back = CopyBrush (brush);
996 if (WindingIsHuge (w))
998 qprintf ("WARNING: huge winding\n");
1003 // split it for real
1005 for (i=0 ; i<2 ; i++)
1007 b[i] = AllocBrush (brush->numsides+1);
1008 b[i]->original = brush->original;
1011 // split all the current windings
1013 for (i=0 ; i<brush->numsides ; i++)
1015 s = &brush->sides[i];
1019 ClipWindingEpsilon (w, plane->normal, plane->dist,
1020 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
1021 for (j=0 ; j<2 ; j++)
1026 if (WindingIsTiny (cw[j]))
1028 FreeWinding (cw[j]);
1032 cs = &b[j]->sides[b[j]->numsides];
1035 // cs->planenum = s->planenum;
1036 // cs->texinfo = s->texinfo;
1037 // cs->visible = s->visible;
1038 // cs->original = s->original;
1039 cs->winding = cw[j];
1045 // see if we have valid polygons on both sides
1047 for (i=0 ; i<2 ; i++)
1050 for (j=0 ; j<3 ; j++)
1052 if (b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096)
1054 qprintf ("bogus brush after clip\n");
1059 if (b[i]->numsides < 3 || j < 3)
1066 if ( !(b[0] && b[1]) )
1069 qprintf ("split removed brush\n");
1071 qprintf ("split not on both sides\n");
1075 *front = CopyBrush (brush);
1080 *back = CopyBrush (brush);
1085 // add the midwinding to both sides
1086 for (i=0 ; i<2 ; i++)
1088 cs = &b[i]->sides[b[i]->numsides];
1091 cs->planenum = planenum^i^1;
1092 cs->texinfo = TEXINFO_NODE;
1093 cs->visible = false;
1096 cs->winding = CopyWinding (midwinding);
1098 cs->winding = midwinding;
1105 for (i=0 ; i<2 ; i++)
1107 v1 = BrushVolume (b[i]);
1112 // qprintf ("tiny volume after clip\n");
1126 void SplitBrushList (bspbrush_t *brushes,
1127 node_t *node, bspbrush_t **front, bspbrush_t **back)
1129 bspbrush_t *brush, *newbrush, *newbrush2;
1134 *front = *back = NULL;
1136 for (brush = brushes ; brush ; brush=brush->next)
1138 sides = brush->side;
1140 if (sides == PSIDE_BOTH)
1141 { // split into two brushes
1142 SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
1145 newbrush->next = *front;
1150 newbrush2->next = *back;
1156 newbrush = CopyBrush (brush);
1158 // if the planenum is actualy a part of the brush
1159 // find the plane and flag it as used so it won't be tried
1160 // as a splitter again
1161 if (sides & PSIDE_FACING)
1163 for (i=0 ; i<newbrush->numsides ; i++)
1165 side = newbrush->sides + i;
1166 if ( (side->planenum& ~1) == node->planenum)
1167 side->texinfo = TEXINFO_NODE;
1172 if (sides & PSIDE_FRONT)
1174 newbrush->next = *front;
1178 if (sides & PSIDE_BACK)
1180 newbrush->next = *back;
1193 node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
1198 bspbrush_t *children[2];
1200 if (numthreads == 1)
1204 DrawBrushList (brushes, node);
1206 // find the best plane to use as a splitter
1207 bestside = SelectSplitSide (brushes, node);
1212 node->planenum = -1;
1213 LeafNode (node, brushes);
1217 // this is a splitplane node
1218 node->side = bestside;
1219 node->planenum = bestside->planenum & ~1; // always use front facing
1221 SplitBrushList (brushes, node, &children[0], &children[1]);
1222 FreeBrushList (brushes);
1224 // allocate children before recursing
1225 for (i=0 ; i<2 ; i++)
1227 newnode = AllocNode ();
1228 newnode->parent = node;
1229 node->children[i] = newnode;
1232 SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
1233 &node->children[1]->volume);
1235 // recursively process children
1236 for (i=0 ; i<2 ; i++)
1238 node->children[i] = BuildTree_r (node->children[i], children[i]);
1244 //===========================================================
1250 The incoming list will be freed before exiting
1253 tree_t *BrushBSP (bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
1257 int c_faces, c_nonvisfaces;
1263 qprintf ("--- BrushBSP ---\n");
1265 tree = AllocTree ();
1270 for (b=brushlist ; b ; b=b->next)
1274 volume = BrushVolume (b);
1275 if (volume < microvolume)
1277 printf ("WARNING: entity %i, brush %i: microbrush\n",
1278 b->original->entitynum, b->original->brushnum);
1281 for (i=0 ; i<b->numsides ; i++)
1283 if (b->sides[i].bevel)
1285 if (!b->sides[i].winding)
1287 if (b->sides[i].texinfo == TEXINFO_NODE)
1289 if (b->sides[i].visible)
1295 AddPointToBounds (b->mins, tree->mins, tree->maxs);
1296 AddPointToBounds (b->maxs, tree->mins, tree->maxs);
1299 qprintf ("%5i brushes\n", c_brushes);
1300 qprintf ("%5i visible faces\n", c_faces);
1301 qprintf ("%5i nonvisible faces\n", c_nonvisfaces);
1305 node = AllocNode ();
1307 node->volume = BrushFromBounds (mins, maxs);
1309 tree->headnode = node;
1311 node = BuildTree_r (node, brushlist);
1312 qprintf ("%5i visible nodes\n", c_nodes/2 - c_nonvis);
1313 qprintf ("%5i nonvis nodes\n", c_nonvis);
1314 qprintf ("%5i leafs\n", (c_nodes+1)/2);
1317 static node_t *tnode;
1323 tnode = PointInLeaf (tree->headnode, p);
1324 printf ("contents: %i\n", tnode->contents);