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