diff options
Diffstat (limited to 'code/bspc/brushbsp.c')
| -rwxr-xr-x | code/bspc/brushbsp.c | 1871 |
1 files changed, 1871 insertions, 0 deletions
diff --git a/code/bspc/brushbsp.c b/code/bspc/brushbsp.c new file mode 100755 index 0000000..22cb0dd --- /dev/null +++ b/code/bspc/brushbsp.c @@ -0,0 +1,1871 @@ +/*
+===========================================================================
+Copyright (C) 1999-2005 Id Software, Inc.
+
+This file is part of Quake III Arena source code.
+
+Quake III Arena source code is free software; you can redistribute it
+and/or modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 2 of the License,
+or (at your option) any later version.
+
+Quake III Arena source code is distributed in the hope that it will be
+useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with Foobar; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+===========================================================================
+*/
+
+#include "qbsp.h"
+#include "l_mem.h"
+#include "../botlib/aasfile.h"
+#include "aas_store.h"
+#include "aas_cfg.h"
+
+#include <assert.h>
+
+/*
+each side has a count of the other sides it splits
+
+the best split will be the one that minimizes the total split counts
+of all remaining sides
+
+precalc side on plane table
+
+evaluate split side
+{
+cost = 0
+for all sides
+ for all sides
+ get
+ if side splits side and splitside is on same child
+ cost++;
+}
+*/
+
+int c_nodes;
+int c_nonvis;
+int c_active_brushes;
+int c_solidleafnodes;
+int c_totalsides;
+int c_brushmemory;
+int c_peak_brushmemory;
+int c_nodememory;
+int c_peak_totalbspmemory;
+
+// if a brush just barely pokes onto the other side,
+// let it slide by without chopping
+#define PLANESIDE_EPSILON 0.001
+//0.1
+
+//#ifdef DEBUG
+typedef struct cname_s
+{
+ int value;
+ char *name;
+} cname_t;
+
+cname_t contentnames[] =
+{
+ {CONTENTS_SOLID,"CONTENTS_SOLID"},
+ {CONTENTS_WINDOW,"CONTENTS_WINDOW"},
+ {CONTENTS_AUX,"CONTENTS_AUX"},
+ {CONTENTS_LAVA,"CONTENTS_LAVA"},
+ {CONTENTS_SLIME,"CONTENTS_SLIME"},
+ {CONTENTS_WATER,"CONTENTS_WATER"},
+ {CONTENTS_MIST,"CONTENTS_MIST"},
+ {LAST_VISIBLE_CONTENTS,"LAST_VISIBLE_CONTENTS"},
+
+ {CONTENTS_AREAPORTAL,"CONTENTS_AREAPORTAL"},
+ {CONTENTS_PLAYERCLIP,"CONTENTS_PLAYERCLIP"},
+ {CONTENTS_MONSTERCLIP,"CONTENTS_MONSTERCLIP"},
+ {CONTENTS_CURRENT_0,"CONTENTS_CURRENT_0"},
+ {CONTENTS_CURRENT_90,"CONTENTS_CURRENT_90"},
+ {CONTENTS_CURRENT_180,"CONTENTS_CURRENT_180"},
+ {CONTENTS_CURRENT_270,"CONTENTS_CURRENT_270"},
+ {CONTENTS_CURRENT_UP,"CONTENTS_CURRENT_UP"},
+ {CONTENTS_CURRENT_DOWN,"CONTENTS_CURRENT_DOWN"},
+ {CONTENTS_ORIGIN,"CONTENTS_ORIGIN"},
+ {CONTENTS_MONSTER,"CONTENTS_MONSTER"},
+ {CONTENTS_DEADMONSTER,"CONTENTS_DEADMONSTER"},
+ {CONTENTS_DETAIL,"CONTENTS_DETAIL"},
+ {CONTENTS_Q2TRANSLUCENT,"CONTENTS_TRANSLUCENT"},
+ {CONTENTS_LADDER,"CONTENTS_LADDER"},
+ {0, 0}
+};
+
+void PrintContents(int contents)
+{
+ int i;
+
+ for (i = 0; contentnames[i].value; i++)
+ {
+ if (contents & contentnames[i].value)
+ {
+ Log_Write("%s,", contentnames[i].name);
+ } //end if
+ } //end for
+} //end of the function PrintContents
+
+//#endif DEBUG
+
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void ResetBrushBSP(void)
+{
+ c_nodes = 0;
+ c_nonvis = 0;
+ c_active_brushes = 0;
+ c_solidleafnodes = 0;
+ c_totalsides = 0;
+ c_brushmemory = 0;
+ c_peak_brushmemory = 0;
+ c_nodememory = 0;
+ c_peak_totalbspmemory = 0;
+} //end of the function ResetBrushBSP
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void FindBrushInTree (node_t *node, int brushnum)
+{
+ bspbrush_t *b;
+
+ if (node->planenum == PLANENUM_LEAF)
+ {
+ for (b=node->brushlist ; b ; b=b->next)
+ if (b->original->brushnum == brushnum)
+ Log_Print ("here\n");
+ return;
+ }
+ FindBrushInTree(node->children[0], brushnum);
+ FindBrushInTree(node->children[1], brushnum);
+} //end of the function FindBrushInTree
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void DrawBrushList (bspbrush_t *brush, node_t *node)
+{
+ int i;
+ side_t *s;
+
+ GLS_BeginScene ();
+ for ( ; brush ; brush=brush->next)
+ {
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ s = &brush->sides[i];
+ if (!s->winding)
+ continue;
+ if (s->texinfo == TEXINFO_NODE)
+ GLS_Winding (s->winding, 1);
+ else if (!(s->flags & SFL_VISIBLE))
+ GLS_Winding (s->winding, 2);
+ else
+ GLS_Winding (s->winding, 0);
+ }
+ }
+ GLS_EndScene ();
+} //end of the function DrawBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
+{
+ int i;
+ side_t *s;
+ FILE *f;
+
+ qprintf ("writing %s\n", name);
+ f = SafeOpenWrite (name);
+
+ for ( ; brush ; brush=brush->next)
+ {
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ s = &brush->sides[i];
+ if (!s->winding)
+ continue;
+ if (onlyvis && !(s->flags & SFL_VISIBLE))
+ continue;
+ OutputWinding (brush->sides[i].winding, f);
+ }
+ }
+
+ fclose (f);
+} //end of the function WriteBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void PrintBrush (bspbrush_t *brush)
+{
+ int i;
+
+ printf ("brush: %p\n", brush);
+ for (i=0;i<brush->numsides ; i++)
+ {
+ pw(brush->sides[i].winding);
+ printf ("\n");
+ } //end for
+} //end of the function PrintBrush
+//===========================================================================
+// Sets the mins/maxs based on the windings
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void BoundBrush (bspbrush_t *brush)
+{
+ int i, j;
+ winding_t *w;
+
+ ClearBounds (brush->mins, brush->maxs);
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ w = brush->sides[i].winding;
+ if (!w)
+ continue;
+ for (j=0 ; j<w->numpoints ; j++)
+ AddPointToBounds (w->p[j], brush->mins, brush->maxs);
+ }
+} //end of the function BoundBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void CreateBrushWindings (bspbrush_t *brush)
+{
+ int i, j;
+ winding_t *w;
+ side_t *side;
+ plane_t *plane;
+
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ side = &brush->sides[i];
+ plane = &mapplanes[side->planenum];
+ w = BaseWindingForPlane (plane->normal, plane->dist);
+ for (j=0 ; j<brush->numsides && w; j++)
+ {
+ if (i == j)
+ continue;
+ if (brush->sides[j].flags & SFL_BEVEL)
+ continue;
+ plane = &mapplanes[brush->sides[j].planenum^1];
+ ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
+ }
+
+ side->winding = w;
+ }
+
+ BoundBrush (brush);
+} //end of the function CreateBrushWindings
+//===========================================================================
+// Creates a new axial brush
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
+{
+ bspbrush_t *b;
+ int i;
+ vec3_t normal;
+ vec_t dist;
+
+ b = AllocBrush (6);
+ b->numsides = 6;
+ for (i=0 ; i<3 ; i++)
+ {
+ VectorClear (normal);
+ normal[i] = 1;
+ dist = maxs[i];
+ b->sides[i].planenum = FindFloatPlane (normal, dist);
+
+ normal[i] = -1;
+ dist = -mins[i];
+ b->sides[3+i].planenum = FindFloatPlane (normal, dist);
+ }
+
+ CreateBrushWindings (b);
+
+ return b;
+} //end of the function BrushFromBounds
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int BrushOutOfBounds(bspbrush_t *brush, vec3_t mins, vec3_t maxs, float epsilon)
+{
+ int i, j, n;
+ winding_t *w;
+ side_t *side;
+
+ for (i = 0; i < brush->numsides; i++)
+ {
+ side = &brush->sides[i];
+ w = side->winding;
+ for (j = 0; j < w->numpoints; j++)
+ {
+ for (n = 0; n < 3; n++)
+ {
+ if (w->p[j][n] < (mins[n] + epsilon) || w->p[j][n] > (maxs[n] - epsilon)) return true;
+ } //end for
+ } //end for
+ } //end for
+ return false;
+} //end of the function BrushOutOfBounds
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+vec_t BrushVolume (bspbrush_t *brush)
+{
+ int i;
+ winding_t *w;
+ vec3_t corner;
+ vec_t d, area, volume;
+ plane_t *plane;
+
+ if (!brush) return 0;
+
+ // grab the first valid point as the corner
+ w = NULL;
+ for (i = 0; i < brush->numsides; i++)
+ {
+ w = brush->sides[i].winding;
+ if (w) break;
+ } //end for
+ if (!w) return 0;
+ VectorCopy (w->p[0], corner);
+
+ // make tetrahedrons to all other faces
+ volume = 0;
+ for ( ; i < brush->numsides; i++)
+ {
+ w = brush->sides[i].winding;
+ if (!w) continue;
+ plane = &mapplanes[brush->sides[i].planenum];
+ d = -(DotProduct (corner, plane->normal) - plane->dist);
+ area = WindingArea(w);
+ volume += d * area;
+ } //end for
+
+ volume /= 3;
+ return volume;
+} //end of the function BrushVolume
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int CountBrushList (bspbrush_t *brushes)
+{
+ int c;
+
+ c = 0;
+ for ( ; brushes; brushes = brushes->next) c++;
+ return c;
+} //end of the function CountBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+node_t *AllocNode (void)
+{
+ node_t *node;
+
+ node = GetMemory(sizeof(*node));
+ memset (node, 0, sizeof(*node));
+ if (numthreads == 1)
+ {
+ c_nodememory += MemorySize(node);
+ } //end if
+ return node;
+} //end of the function AllocNode
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *AllocBrush (int numsides)
+{
+ bspbrush_t *bb;
+ int c;
+
+ c = (int)&(((bspbrush_t *)0)->sides[numsides]);
+ bb = GetMemory(c);
+ memset (bb, 0, c);
+ if (numthreads == 1)
+ {
+ c_active_brushes++;
+ c_brushmemory += MemorySize(bb);
+ if (c_brushmemory > c_peak_brushmemory)
+ c_peak_brushmemory = c_brushmemory;
+ } //end if
+ return bb;
+} //end of the function AllocBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void FreeBrush (bspbrush_t *brushes)
+{
+ int i;
+
+ for (i=0 ; i<brushes->numsides ; i++)
+ if (brushes->sides[i].winding)
+ FreeWinding(brushes->sides[i].winding);
+ if (numthreads == 1)
+ {
+ c_active_brushes--;
+ c_brushmemory -= MemorySize(brushes);
+ if (c_brushmemory < 0) c_brushmemory = 0;
+ } //end if
+ FreeMemory(brushes);
+} //end of the function FreeBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void FreeBrushList (bspbrush_t *brushes)
+{
+ bspbrush_t *next;
+
+ for ( ; brushes; brushes = next)
+ {
+ next = brushes->next;
+
+ FreeBrush(brushes);
+ } //end for
+} //end of the function FreeBrushList
+//===========================================================================
+// Duplicates the brush, the sides, and the windings
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+bspbrush_t *CopyBrush (bspbrush_t *brush)
+{
+ bspbrush_t *newbrush;
+ int size;
+ int i;
+
+ size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);
+
+ newbrush = AllocBrush (brush->numsides);
+ memcpy (newbrush, brush, size);
+
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ if (brush->sides[i].winding)
+ newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);
+ }
+
+ return newbrush;
+} //end of the function CopyBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+node_t *PointInLeaf (node_t *node, vec3_t point)
+{
+ vec_t d;
+ plane_t *plane;
+
+ while (node->planenum != PLANENUM_LEAF)
+ {
+ plane = &mapplanes[node->planenum];
+ d = DotProduct (point, plane->normal) - plane->dist;
+ if (d > 0)
+ node = node->children[0];
+ else
+ node = node->children[1];
+ }
+
+ return node;
+} //end of the function PointInLeaf
+//===========================================================================
+// Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+#if 0
+int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
+{
+ int side;
+ int i;
+ vec3_t corners[2];
+ vec_t dist1, dist2;
+
+ // axial planes are easy
+ if (plane->type < 3)
+ {
+ side = 0;
+ if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
+ side |= PSIDE_FRONT;
+ if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
+ side |= PSIDE_BACK;
+ return side;
+ }
+
+ // create the proper leading and trailing verts for the box
+
+ for (i=0 ; i<3 ; i++)
+ {
+ if (plane->normal[i] < 0)
+ {
+ corners[0][i] = mins[i];
+ corners[1][i] = maxs[i];
+ }
+ else
+ {
+ corners[1][i] = mins[i];
+ corners[0][i] = maxs[i];
+ }
+ }
+
+ dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
+ dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
+ side = 0;
+ if (dist1 >= PLANESIDE_EPSILON)
+ side = PSIDE_FRONT;
+ if (dist2 < PLANESIDE_EPSILON)
+ side |= PSIDE_BACK;
+
+ return side;
+}
+#else
+int BoxOnPlaneSide (vec3_t emins, vec3_t emaxs, plane_t *p)
+{
+ float dist1, dist2;
+ int sides;
+
+ // axial planes are easy
+ if (p->type < 3)
+ {
+ sides = 0;
+ if (emaxs[p->type] > p->dist+PLANESIDE_EPSILON) sides |= PSIDE_FRONT;
+ if (emins[p->type] < p->dist-PLANESIDE_EPSILON) sides |= PSIDE_BACK;
+ return sides;
+ } //end if
+
+// general case
+ switch (p->signbits)
+ {
+ case 0:
+ dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
+ dist2 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
+ break;
+ case 1:
+ dist1 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
+ dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
+ break;
+ case 2:
+ dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
+ dist2 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
+ break;
+ case 3:
+ dist1 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
+ dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
+ break;
+ case 4:
+ dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
+ dist2 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
+ break;
+ case 5:
+ dist1 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emins[2];
+ dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emaxs[2];
+ break;
+ case 6:
+ dist1 = p->normal[0]*emaxs[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
+ dist2 = p->normal[0]*emins[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
+ break;
+ case 7:
+ dist1 = p->normal[0]*emins[0] + p->normal[1]*emins[1] + p->normal[2]*emins[2];
+ dist2 = p->normal[0]*emaxs[0] + p->normal[1]*emaxs[1] + p->normal[2]*emaxs[2];
+ break;
+ default:
+ dist1 = dist2 = 0; // shut up compiler
+// assert( 0 );
+ break;
+ }
+
+ sides = 0;
+ if (dist1 - p->dist >= PLANESIDE_EPSILON) sides = PSIDE_FRONT;
+ if (dist2 - p->dist < PLANESIDE_EPSILON) sides |= PSIDE_BACK;
+
+// assert(sides != 0);
+
+ return sides;
+}
+#endif
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
+{
+ int i, num;
+ plane_t *plane;
+ int s;
+
+ *numsplits = 0;
+
+ plane = &mapplanes[planenum];
+
+#ifdef ME
+ //fast axial cases
+ if (plane->type < 3)
+ {
+ if (plane->dist + PLANESIDE_EPSILON < brush->mins[plane->type])
+ return PSIDE_FRONT;
+ if (plane->dist - PLANESIDE_EPSILON > brush->maxs[plane->type])
+ return PSIDE_BACK;
+ } //end if
+#endif //ME*/
+
+ // if the brush actually uses the planenum,
+ // we can tell the side for sure
+ for (i = 0; i < brush->numsides; i++)
+ {
+ num = brush->sides[i].planenum;
+ if (num >= MAX_MAPFILE_PLANES)
+ Error ("bad planenum");
+ if (num == planenum)
+ return PSIDE_BACK|PSIDE_FACING;
+ if (num == (planenum ^ 1) )
+ return PSIDE_FRONT|PSIDE_FACING;
+
+ }
+
+ // box on plane side
+ s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
+
+ // if both sides, count the visible faces split
+ if (s == PSIDE_BOTH)
+ {
+ *numsplits += 3;
+ }
+
+ return s;
+} //end of the function QuickTestBrushToPlanenum
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
+ int *numsplits, qboolean *hintsplit, int *epsilonbrush)
+{
+ int i, j, num;
+ plane_t *plane;
+ int s = 0;
+ winding_t *w;
+ vec_t d, d_front, d_back;
+ int front, back;
+ int type;
+ float dist;
+
+ *numsplits = 0;
+ *hintsplit = false;
+
+ plane = &mapplanes[planenum];
+
+#ifdef ME
+ //fast axial cases
+ type = plane->type;
+ if (type < 3)
+ {
+ dist = plane->dist;
+ if (dist + PLANESIDE_EPSILON < brush->mins[type]) return PSIDE_FRONT;
+ if (dist - PLANESIDE_EPSILON > brush->maxs[type]) return PSIDE_BACK;
+ if (brush->mins[type] < dist - PLANESIDE_EPSILON &&
+ brush->maxs[type] > dist + PLANESIDE_EPSILON) s = PSIDE_BOTH;
+ } //end if
+
+ if (s != PSIDE_BOTH)
+#endif //ME
+ {
+ // if the brush actually uses the planenum,
+ // we can tell the side for sure
+ for (i = 0; i < brush->numsides; i++)
+ {
+ num = brush->sides[i].planenum;
+ if (num >= MAX_MAPFILE_PLANES) Error ("bad planenum");
+ if (num == planenum)
+ {
+ //we don't need to test this side plane again
+ brush->sides[i].flags |= SFL_TESTED;
+ return PSIDE_BACK|PSIDE_FACING;
+ } //end if
+ if (num == (planenum ^ 1) )
+ {
+ //we don't need to test this side plane again
+ brush->sides[i].flags |= SFL_TESTED;
+ return PSIDE_FRONT|PSIDE_FACING;
+ } //end if
+ } //end for
+
+ // box on plane side
+ s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
+
+ if (s != PSIDE_BOTH) return s;
+ } //end if
+
+ // if both sides, count the visible faces split
+ d_front = d_back = 0;
+
+ for (i = 0; i < brush->numsides; i++)
+ {
+ if (brush->sides[i].texinfo == TEXINFO_NODE)
+ continue; // on node, don't worry about splits
+ if (!(brush->sides[i].flags & SFL_VISIBLE))
+ continue; // we don't care about non-visible
+ w = brush->sides[i].winding;
+ if (!w) continue;
+ front = back = 0;
+ for (j = 0; j < w->numpoints; j++)
+ {
+ d = DotProduct(w->p[j], plane->normal) - plane->dist;
+ if (d > d_front) d_front = d;
+ if (d < d_back) d_back = d;
+ if (d > 0.1) // PLANESIDE_EPSILON)
+ front = 1;
+ if (d < -0.1) // PLANESIDE_EPSILON)
+ back = 1;
+ } //end for
+ if (front && back)
+ {
+ if ( !(brush->sides[i].surf & SURF_SKIP) )
+ {
+ (*numsplits)++;
+ if (brush->sides[i].surf & SURF_HINT)
+ {
+ *hintsplit = true;
+ } //end if
+ } //end if
+ } //end if
+ } //end for
+
+ if ( (d_front > 0.0 && d_front < 1.0)
+ || (d_back < 0.0 && d_back > -1.0) )
+ (*epsilonbrush)++;
+
+#if 0
+ if (*numsplits == 0)
+ { // didn't really need to be split
+ if (front) s = PSIDE_FRONT;
+ else if (back) s = PSIDE_BACK;
+ else s = 0;
+ }
+#endif
+
+ return s;
+} //end of the function TestBrushToPlanenum
+//===========================================================================
+// Returns true if the winding would be crunched out of
+// existance by the vertex snapping.
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+#define EDGE_LENGTH 0.2
+qboolean WindingIsTiny (winding_t *w)
+{
+#if 0
+ if (WindingArea (w) < 1)
+ return true;
+ return false;
+#else
+ int i, j;
+ vec_t len;
+ vec3_t delta;
+ int edges;
+
+ edges = 0;
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ j = i == w->numpoints - 1 ? 0 : i+1;
+ VectorSubtract (w->p[j], w->p[i], delta);
+ len = VectorLength (delta);
+ if (len > EDGE_LENGTH)
+ {
+ if (++edges == 3)
+ return false;
+ }
+ }
+ return true;
+#endif
+} //end of the function WindingIsTiny
+//===========================================================================
+// Returns true if the winding still has one of the points
+// from basewinding for plane
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+qboolean WindingIsHuge (winding_t *w)
+{
+ int i, j;
+
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ for (j=0 ; j<3 ; j++)
+ if (w->p[i][j] < -BOGUS_RANGE+1 || w->p[i][j] > BOGUS_RANGE-1)
+ return true;
+ }
+ return false;
+} //end of the function WindingIsHuge
+//===========================================================================
+// creates a leaf out of the given nodes with the given brushes
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void LeafNode(node_t *node, bspbrush_t *brushes)
+{
+ bspbrush_t *b;
+ int i;
+
+ node->side = NULL;
+ node->planenum = PLANENUM_LEAF;
+ node->contents = 0;
+
+ for (b = brushes; b; b = b->next)
+ {
+ // if the brush is solid and all of its sides are on nodes,
+ // it eats everything
+ if (b->original->contents & CONTENTS_SOLID)
+ {
+ for (i=0 ; i<b->numsides ; i++)
+ if (b->sides[i].texinfo != TEXINFO_NODE)
+ break;
+ if (i == b->numsides)
+ {
+ node->contents = CONTENTS_SOLID;
+ break;
+ } //end if
+ } //end if
+ node->contents |= b->original->contents;
+ } //end for
+
+ if (create_aas)
+ {
+ node->expansionbboxes = 0;
+ node->contents = 0;
+ for (b = brushes; b; b = b->next)
+ {
+ node->expansionbboxes |= b->original->expansionbbox;
+ node->contents |= b->original->contents;
+ if (b->original->modelnum)
+ node->modelnum = b->original->modelnum;
+ } //end for
+ if (node->contents & CONTENTS_SOLID)
+ {
+ if (node->expansionbboxes != cfg.allpresencetypes)
+ {
+ node->contents &= ~CONTENTS_SOLID;
+ } //end if
+ } //end if
+ } //end if
+
+ node->brushlist = brushes;
+} //end of the function LeafNode
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void CheckPlaneAgainstParents (int pnum, node_t *node)
+{
+ node_t *p;
+
+ for (p = node->parent; p; p = p->parent)
+ {
+ if (p->planenum == pnum) Error("Tried parent");
+ } //end for
+} //end of the function CheckPlaneAgainstParants
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
+{
+ bspbrush_t *front, *back;
+ qboolean good;
+
+ SplitBrush (node->volume, pnum, &front, &back);
+
+ good = (front && back);
+
+ if (front) FreeBrush (front);
+ if (back) FreeBrush (back);
+
+ return good;
+} //end of the function CheckPlaneAgaintsVolume
+//===========================================================================
+// Using a hueristic, choses one of the sides out of the brushlist
+// to partition the brushes with.
+// Returns NULL if there are no valid planes to split with..
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
+{
+ int value, bestvalue;
+ bspbrush_t *brush, *test;
+ side_t *side, *bestside;
+ int i, pass, numpasses;
+ int pnum;
+ int s;
+ int front, back, both, facing, splits;
+ int bsplits;
+ int bestsplits;
+ int epsilonbrush;
+ qboolean hintsplit = false;
+
+ bestside = NULL;
+ bestvalue = -99999;
+ bestsplits = 0;
+
+ // the search order goes: visible-structural, visible-detail,
+ // nonvisible-structural, nonvisible-detail.
+ // If any valid plane is available in a pass, no further
+ // passes will be tried.
+ numpasses = 2;
+ for (pass = 0; pass < numpasses; pass++)
+ {
+ for (brush = brushes; brush; brush = brush->next)
+ {
+ // only check detail the second pass
+// if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
+// continue;
+// if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
+// continue;
+ for (i = 0; i < brush->numsides; i++)
+ {
+ side = brush->sides + i;
+// if (side->flags & SFL_BEVEL)
+// continue; // never use a bevel as a spliter
+ if (!side->winding)
+ continue; // nothing visible, so it can't split
+ if (side->texinfo == TEXINFO_NODE)
+ continue; // allready a node splitter
+ if (side->flags & SFL_TESTED)
+ continue; // we allready have metrics for this plane
+// if (side->surf & SURF_SKIP)
+// continue; // skip surfaces are never chosen
+
+// if (!(side->flags & SFL_VISIBLE) && (pass < 2))
+// continue; // only check visible faces on first pass
+
+ if ((side->flags & SFL_CURVE) && (pass < 1))
+ continue; // only check curves the second pass
+
+ pnum = side->planenum;
+ pnum &= ~1; // allways use positive facing plane
+
+ CheckPlaneAgainstParents (pnum, node);
+
+ if (!CheckPlaneAgainstVolume (pnum, node))
+ continue; // would produce a tiny volume
+
+ front = 0;
+ back = 0;
+ both = 0;
+ facing = 0;
+ splits = 0;
+ epsilonbrush = 0;
+
+ //inner loop: optimize
+ for (test = brushes; test; test = test->next)
+ {
+ s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);
+
+ splits += bsplits;
+// if (bsplits && (s&PSIDE_FACING) )
+// Error ("PSIDE_FACING with splits");
+
+ test->testside = s;
+ //
+ if (s & PSIDE_FACING) facing++;
+ if (s & PSIDE_FRONT) front++;
+ if (s & PSIDE_BACK) back++;
+ if (s == PSIDE_BOTH) both++;
+ } //end for
+
+ // give a value estimate for using this plane
+ value = 5*facing - 5*splits - abs(front-back);
+// value = -5*splits;
+// value = 5*facing - 5*splits;
+ if (mapplanes[pnum].type < 3)
+ value+=5; // axial is better
+
+ value -= epsilonbrush * 1000; // avoid!
+
+ // never split a hint side except with another hint
+ if (hintsplit && !(side->surf & SURF_HINT) )
+ value = -9999999;
+
+ // save off the side test so we don't need
+ // to recalculate it when we actually seperate
+ // the brushes
+ if (value > bestvalue)
+ {
+ bestvalue = value;
+ bestside = side;
+ bestsplits = splits;
+ for (test = brushes; test ; test = test->next)
+ test->side = test->testside;
+ } //end if
+ } //end for
+ } //end for (brush = brushes;
+
+ // if we found a good plane, don't bother trying any
+ // other passes
+ if (bestside)
+ {
+ if (pass > 1)
+ {
+ if (numthreads == 1) c_nonvis++;
+ }
+ if (pass > 0) node->detail_seperator = true; // not needed for vis
+ break;
+ } //end if
+ } //end for (pass = 0;
+
+ //
+ // clear all the tested flags we set
+ //
+ for (brush = brushes ; brush ; brush=brush->next)
+ {
+ for (i = 0; i < brush->numsides; i++)
+ {
+ brush->sides[i].flags &= ~SFL_TESTED;
+ } //end for
+ } //end for
+
+ return bestside;
+} //end of the function SelectSplitSide
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
+{
+ int i, j;
+ winding_t *w;
+ vec_t d, max;
+ int side;
+
+ max = 0;
+ side = PSIDE_FRONT;
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ w = brush->sides[i].winding;
+ if (!w)
+ continue;
+ for (j=0 ; j<w->numpoints ; j++)
+ {
+ d = DotProduct (w->p[j], plane->normal) - plane->dist;
+ if (d > max)
+ {
+ max = d;
+ side = PSIDE_FRONT;
+ }
+ if (-d > max)
+ {
+ max = -d;
+ side = PSIDE_BACK;
+ }
+ }
+ }
+ return side;
+} //end of the function BrushMostlyOnSide
+//===========================================================================
+// Generates two new brushes, leaving the original
+// unchanged
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void SplitBrush (bspbrush_t *brush, int planenum,
+ bspbrush_t **front, bspbrush_t **back)
+{
+ bspbrush_t *b[2];
+ int i, j;
+ winding_t *w, *cw[2], *midwinding;
+ plane_t *plane, *plane2;
+ side_t *s, *cs;
+ float d, d_front, d_back;
+
+ *front = *back = NULL;
+ plane = &mapplanes[planenum];
+
+ // check all points
+ d_front = d_back = 0;
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ w = brush->sides[i].winding;
+ if (!w)
+ continue;
+ for (j=0 ; j<w->numpoints ; j++)
+ {
+ d = DotProduct (w->p[j], plane->normal) - plane->dist;
+ if (d > 0 && d > d_front)
+ d_front = d;
+ if (d < 0 && d < d_back)
+ d_back = d;
+ }
+ }
+
+ if (d_front < 0.2) // PLANESIDE_EPSILON)
+ { // only on back
+ *back = CopyBrush (brush);
+ return;
+ }
+ if (d_back > -0.2) // PLANESIDE_EPSILON)
+ { // only on front
+ *front = CopyBrush (brush);
+ return;
+ }
+
+ // create a new winding from the split plane
+
+ w = BaseWindingForPlane (plane->normal, plane->dist);
+ for (i=0 ; i<brush->numsides && w ; i++)
+ {
+ plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
+ ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
+ }
+
+ if (!w || WindingIsTiny(w))
+ { // the brush isn't really split
+ int side;
+
+ side = BrushMostlyOnSide (brush, plane);
+ if (side == PSIDE_FRONT)
+ *front = CopyBrush (brush);
+ if (side == PSIDE_BACK)
+ *back = CopyBrush (brush);
+ //free a possible winding
+ if (w) FreeWinding(w);
+ return;
+ }
+
+ if (WindingIsHuge (w))
+ {
+ Log_Write("WARNING: huge winding\n");
+ }
+
+ midwinding = w;
+
+ // split it for real
+
+ for (i=0 ; i<2 ; i++)
+ {
+ b[i] = AllocBrush (brush->numsides+1);
+ b[i]->original = brush->original;
+ }
+
+ // split all the current windings
+
+ for (i=0 ; i<brush->numsides ; i++)
+ {
+ s = &brush->sides[i];
+ w = s->winding;
+ if (!w)
+ continue;
+ ClipWindingEpsilon (w, plane->normal, plane->dist,
+ 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
+ for (j=0 ; j<2 ; j++)
+ {
+ if (!cw[j])
+ continue;
+#if 0
+ if (WindingIsTiny (cw[j]))
+ {
+ FreeWinding (cw[j]);
+ continue;
+ }
+#endif
+ cs = &b[j]->sides[b[j]->numsides];
+ b[j]->numsides++;
+ *cs = *s;
+// cs->planenum = s->planenum;
+// cs->texinfo = s->texinfo;
+// cs->original = s->original;
+ cs->winding = cw[j];
+ cs->flags &= ~SFL_TESTED;
+ }
+ }
+
+
+ // see if we have valid polygons on both sides
+
+ for (i=0 ; i<2 ; i++)
+ {
+ BoundBrush (b[i]);
+ for (j=0 ; j<3 ; j++)
+ {
+ if (b[i]->mins[j] < -MAX_MAP_BOUNDS || b[i]->maxs[j] > MAX_MAP_BOUNDS)
+ {
+ Log_Write("bogus brush after clip");
+ break;
+ }
+ }
+
+ if (b[i]->numsides < 3 || j < 3)
+ {
+ FreeBrush (b[i]);
+ b[i] = NULL;
+ }
+ }
+
+ if ( !(b[0] && b[1]) )
+ {
+ if (!b[0] && !b[1])
+ Log_Write("split removed brush\r\n");
+ else
+ Log_Write("split not on both sides\r\n");
+ if (b[0])
+ {
+ FreeBrush (b[0]);
+ *front = CopyBrush (brush);
+ }
+ if (b[1])
+ {
+ FreeBrush (b[1]);
+ *back = CopyBrush (brush);
+ }
+ return;
+ }
+
+ // add the midwinding to both sides
+ for (i=0 ; i<2 ; i++)
+ {
+ cs = &b[i]->sides[b[i]->numsides];
+ b[i]->numsides++;
+
+ cs->planenum = planenum^i^1;
+ cs->texinfo = TEXINFO_NODE; //never use these sides as splitters
+ cs->flags &= ~SFL_VISIBLE;
+ cs->flags &= ~SFL_TESTED;
+ if (i==0)
+ cs->winding = CopyWinding (midwinding);
+ else
+ cs->winding = midwinding;
+ }
+
+{
+ vec_t v1;
+ int i;
+
+ for (i = 0; i < 2; i++)
+ {
+ v1 = BrushVolume (b[i]);
+ if (v1 < 1.0)
+ {
+ FreeBrush(b[i]);
+ b[i] = NULL;
+ //Log_Write("tiny volume after clip");
+ }
+ }
+ if (!b[0] && !b[1])
+ {
+ Log_Write("two tiny brushes\r\n");
+ } //end if
+}
+
+ *front = b[0];
+ *back = b[1];
+} //end of the function SplitBrush
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void SplitBrushList (bspbrush_t *brushes,
+ node_t *node, bspbrush_t **front, bspbrush_t **back)
+{
+ bspbrush_t *brush, *newbrush, *newbrush2;
+ side_t *side;
+ int sides;
+ int i;
+
+ *front = *back = NULL;
+
+ for (brush = brushes; brush; brush = brush->next)
+ {
+ sides = brush->side;
+
+ if (sides == PSIDE_BOTH)
+ { // split into two brushes
+ SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
+ if (newbrush)
+ {
+ newbrush->next = *front;
+ *front = newbrush;
+ } //end if
+ if (newbrush2)
+ {
+ newbrush2->next = *back;
+ *back = newbrush2;
+ } //end if
+ continue;
+ } //end if
+
+ newbrush = CopyBrush (brush);
+
+ // if the planenum is actualy a part of the brush
+ // find the plane and flag it as used so it won't be tried
+ // as a splitter again
+ if (sides & PSIDE_FACING)
+ {
+ for (i=0 ; i<newbrush->numsides ; i++)
+ {
+ side = newbrush->sides + i;
+ if ( (side->planenum& ~1) == node->planenum)
+ side->texinfo = TEXINFO_NODE;
+ } //end for
+ } //end if
+ if (sides & PSIDE_FRONT)
+ {
+ newbrush->next = *front;
+ *front = newbrush;
+ continue;
+ } //end if
+ if (sides & PSIDE_BACK)
+ {
+ newbrush->next = *back;
+ *back = newbrush;
+ continue;
+ } //end if
+ } //end for
+} //end of the function SplitBrushList
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void CheckBrushLists(bspbrush_t *brushlist1, bspbrush_t *brushlist2)
+{
+ bspbrush_t *brush1, *brush2;
+
+ for (brush1 = brushlist1; brush1; brush1 = brush1->next)
+ {
+ for (brush2 = brushlist2; brush2; brush2 = brush2->next)
+ {
+ assert(brush1 != brush2);
+ } //end for
+ } //end for
+} //end of the function CheckBrushLists
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+int numrecurse = 0;
+
+node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
+{
+ node_t *newnode;
+ side_t *bestside;
+ int i, totalmem;
+ bspbrush_t *children[2];
+
+ qprintf("\r%6d", numrecurse);
+ numrecurse++;
+
+ if (numthreads == 1)
+ {
+ totalmem = WindingMemory() + c_nodememory + c_brushmemory;
+ if (totalmem > c_peak_totalbspmemory)
+ c_peak_totalbspmemory = totalmem;
+ c_nodes++;
+ } //endif
+
+ if (drawflag)
+ DrawBrushList(brushes, node);
+
+ // find the best plane to use as a splitter
+ bestside = SelectSplitSide (brushes, node);
+ if (!bestside)
+ {
+ // leaf node
+ node->side = NULL;
+ node->planenum = -1;
+ LeafNode(node, brushes);
+ if (node->contents & CONTENTS_SOLID) c_solidleafnodes++;
+ if (create_aas)
+ {
+ //free up memory!!!
+ FreeBrushList(node->brushlist);
+ node->brushlist = NULL;
+ //free the node volume brush
+ if (node->volume)
+ {
+ FreeBrush(node->volume);
+ node->volume = NULL;
+ } //end if
+ } //end if
+ return node;
+ } //end if
+
+ // this is a splitplane node
+ node->side = bestside;
+ node->planenum = bestside->planenum & ~1; // always use front facing
+
+ //split the brush list in two for both children
+ SplitBrushList (brushes, node, &children[0], &children[1]);
+ //free the old brush list
+ FreeBrushList (brushes);
+
+ // allocate children before recursing
+ for (i = 0; i < 2; i++)
+ {
+ newnode = AllocNode ();
+ newnode->parent = node;
+ node->children[i] = newnode;
+ } //end for
+
+ //split the volume brush of the node for the children
+ SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
+ &node->children[1]->volume);
+
+ if (create_aas)
+ {
+ //free the volume brush
+ if (node->volume)
+ {
+ FreeBrush(node->volume);
+ node->volume = NULL;
+ } //end if
+ } //end if
+ // recursively process children
+ for (i = 0; i < 2; i++)
+ {
+ node->children[i] = BuildTree_r(node->children[i], children[i]);
+ } //end for
+
+ return node;
+} //end of the function BuildTree_r
+//===========================================================================
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+node_t *firstnode; //first node in the list
+node_t *lastnode; //last node in the list
+int nodelistsize; //number of nodes in the list
+int use_nodequeue = 0; //use nodequeue, otherwise a node stack is used
+int numwaiting = 0;
+
+void (*AddNodeToList)(node_t *node);
+
+//add the node to the front of the node list
+//(effectively using a node stack)
+void AddNodeToStack(node_t *node)
+{
+ ThreadLock();
+
+ node->next = firstnode;
+ firstnode = node;
+ if (!lastnode) lastnode = node;
+ nodelistsize++;
+
+ ThreadUnlock();
+ //
+ ThreadSemaphoreIncrease(1);
+} //end of the function AddNodeToStack
+//add the node to the end of the node list
+//(effectively using a node queue)
+void AddNodeToQueue(node_t *node)
+{
+ ThreadLock();
+
+ node->next = NULL;
+ if (lastnode) lastnode->next = node;
+ else firstnode = node;
+ lastnode = node;
+ nodelistsize++;
+
+ ThreadUnlock();
+ //
+ ThreadSemaphoreIncrease(1);
+} //end of the function AddNodeToQueue
+//get the first node from the front of the node list
+node_t *NextNodeFromList(void)
+{
+ node_t *node;
+
+ ThreadLock();
+ numwaiting++;
+ if (!firstnode)
+ {
+ if (numwaiting >= GetNumThreads()) ThreadSemaphoreIncrease(GetNumThreads());
+ } //end if
+ ThreadUnlock();
+
+ ThreadSemaphoreWait();
+
+ ThreadLock();
+
+ numwaiting--;
+
+ node = firstnode;
+ if (firstnode)
+ {
+ firstnode = firstnode->next;
+ nodelistsize--;
+ } //end if
+ if (!firstnode) lastnode = NULL;
+
+ ThreadUnlock();
+
+ return node;
+} //end of the function NextNodeFromList
+//returns the size of the node list
+int NodeListSize(void)
+{
+ int size;
+
+ ThreadLock();
+ size = nodelistsize;
+ ThreadUnlock();
+
+ return size;
+} //end of the function NodeListSize
+//
+void IncreaseNodeCounter(void)
+{
+ ThreadLock();
+ //if (verbose) printf("\r%6d", numrecurse++);
+ qprintf("\r%6d", numrecurse++);
+ //qprintf("\r%6d %d, %5d ", numrecurse++, GetNumThreads(), nodelistsize);
+ ThreadUnlock();
+} //end of the function IncreaseNodeCounter
+//thread function, gets nodes from the nodelist and processes them
+void BuildTreeThread(int threadid)
+{
+ node_t *newnode, *node;
+ side_t *bestside;
+ int i, totalmem;
+ bspbrush_t *brushes;
+
+ for (node = NextNodeFromList(); node; )
+ {
+ //if the nodelist isn't empty try to add another thread
+ //if (NodeListSize() > 10) AddThread(BuildTreeThread);
+ //display the number of nodes processed so far
+ if (numthreads == 1)
+ IncreaseNodeCounter();
+
+ brushes = node->brushlist;
+
+ if (numthreads == 1)
+ {
+ totalmem = WindingMemory() + c_nodememory + c_brushmemory;
+ if (totalmem > c_peak_totalbspmemory)
+ {
+ c_peak_totalbspmemory = totalmem;
+ } //end if
+ c_nodes++;
+ } //endif
+
+ if (drawflag)
+ {
+ DrawBrushList(brushes, node);
+ } //end if
+
+ if (cancelconversion)
+ {
+ bestside = NULL;
+ } //end if
+ else
+ {
+ // find the best plane to use as a splitter
+ bestside = SelectSplitSide(brushes, node);
+ } //end else
+ //if there's no split side left
+ if (!bestside)
+ {
+ //create a leaf out of the node
+ LeafNode(node, brushes);
+ if (node->contents & CONTENTS_SOLID) c_solidleafnodes++;
+ if (create_aas)
+ {
+ //free up memory!!!
+ FreeBrushList(node->brushlist);
+ node->brushlist = NULL;
+ } //end if
+ //free the node volume brush (it is not used anymore)
+ if (node->volume)
+ {
+ FreeBrush(node->volume);
+ node->volume = NULL;
+ } //end if
+ node = NextNodeFromList();
+ continue;
+ } //end if
+
+ // this is a splitplane node
+ node->side = bestside;
+ node->planenum = bestside->planenum & ~1; //always use front facing
+
+ //allocate children
+ for (i = 0; i < 2; i++)
+ {
+ newnode = AllocNode();
+ newnode->parent = node;
+ node->children[i] = newnode;
+ } //end for
+
+ //split the brush list in two for both children
+ SplitBrushList(brushes, node, &node->children[0]->brushlist, &node->children[1]->brushlist);
+
+ CheckBrushLists(node->children[0]->brushlist, node->children[1]->brushlist);
+ //free the old brush list
+ FreeBrushList(brushes);
+ node->brushlist = NULL;
+
+ //split the volume brush of the node for the children
+ SplitBrush(node->volume, node->planenum, &node->children[0]->volume,
+ &node->children[1]->volume);
+
+ if (!node->children[0]->volume || !node->children[1]->volume)
+ {
+ Error("child without volume brush");
+ } //end if
+
+ //free the volume brush
+ if (node->volume)
+ {
+ FreeBrush(node->volume);
+ node->volume = NULL;
+ } //end if
+ //add both children to the node list
+ //AddNodeToList(node->children[0]);
+ AddNodeToList(node->children[1]);
+ node = node->children[0];
+ } //end while
+ RemoveThread(threadid);
+} //end of the function BuildTreeThread
+//===========================================================================
+// build the bsp tree using a node list
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+void BuildTree(tree_t *tree)
+{
+ int i;
+
+ firstnode = NULL;
+ lastnode = NULL;
+ //use a node queue or node stack
+ if (use_nodequeue) AddNodeToList = AddNodeToQueue;
+ else AddNodeToList = AddNodeToStack;
+ //setup thread locking
+ ThreadSetupLock();
+ ThreadSetupSemaphore();
+ numwaiting = 0;
+ //
+ Log_Print("%6d threads max\n", numthreads);
+ if (use_nodequeue) Log_Print("breadth first bsp building\n");
+ else Log_Print("depth first bsp building\n");
+ qprintf("%6d splits", 0);
+ //add the first node to the list
+ AddNodeToList(tree->headnode);
+ //start the threads
+ for (i = 0; i < numthreads; i++)
+ AddThread(BuildTreeThread);
+ //wait for all added threads to be finished
+ WaitForAllThreadsFinished();
+ //shutdown the thread locking
+ ThreadShutdownLock();
+ ThreadShutdownSemaphore();
+} //end of the function BuildTree
+//===========================================================================
+// The incoming brush list will be freed before exiting
+//
+// Parameter: -
+// Returns: -
+// Changes Globals: -
+//===========================================================================
+tree_t *BrushBSP(bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
+{
+ int i, c_faces, c_nonvisfaces, c_brushes;
+ bspbrush_t *b;
+ node_t *node;
+ tree_t *tree;
+ vec_t volume;
+// vec3_t point;
+
+ Log_Print("-------- Brush BSP ---------\n");
+
+ tree = Tree_Alloc();
+
+ c_faces = 0;
+ c_nonvisfaces = 0;
+ c_brushes = 0;
+ c_totalsides = 0;
+ for (b = brushlist; b; b = b->next)
+ {
+ c_brushes++;
+
+ volume = BrushVolume(b);
+ if (volume < microvolume)
+ {
+ Log_Print("WARNING: entity %i, brush %i: microbrush\n",
+ b->original->entitynum, b->original->brushnum);
+ } //end if
+
+ for (i=0 ; i<b->numsides ; i++)
+ {
+ if (b->sides[i].flags & SFL_BEVEL)
+ continue;
+ if (!b->sides[i].winding)
+ continue;
+ if (b->sides[i].texinfo == TEXINFO_NODE)
+ continue;
+ if (b->sides[i].flags & SFL_VISIBLE)
+ {
+ c_faces++;
+ } //end if
+ else
+ {
+ c_nonvisfaces++;
+ //if (create_aas) b->sides[i].texinfo = TEXINFO_NODE;
+ } //end if
+ } //end for
+ c_totalsides += b->numsides;
+
+ AddPointToBounds (b->mins, tree->mins, tree->maxs);
+ AddPointToBounds (b->maxs, tree->mins, tree->maxs);
+ } //end for
+
+ Log_Print("%6i brushes\n", c_brushes);
+ Log_Print("%6i visible faces\n", c_faces);
+ Log_Print("%6i nonvisible faces\n", c_nonvisfaces);
+ Log_Print("%6i total sides\n", c_totalsides);
+
+ c_active_brushes = c_brushes;
+ c_nodememory = 0;
+ c_brushmemory = 0;
+ c_peak_brushmemory = 0;
+
+ c_nodes = 0;
+ c_nonvis = 0;
+ node = AllocNode ();
+
+ //volume of first node (head node)
+ node->volume = BrushFromBounds (mins, maxs);
+ //
+ tree->headnode = node;
+ //just get some statistics and the mins/maxs of the node
+ numrecurse = 0;
+// qprintf("%6d splits", numrecurse);
+
+ tree->headnode->brushlist = brushlist;
+ BuildTree(tree);
+
+ //build the bsp tree with the start node from the brushlist
+// node = BuildTree_r(node, brushlist);
+
+ //if the conversion is cancelled
+ if (cancelconversion) return tree;
+
+ qprintf("\n");
+ Log_Write("%6d splits\r\n", numrecurse);
+// Log_Print("%6i visible nodes\n", c_nodes/2 - c_nonvis);
+// Log_Print("%6i nonvis nodes\n", c_nonvis);
+// Log_Print("%6i leaves\n", (c_nodes+1)/2);
+// Log_Print("%6i solid leaf nodes\n", c_solidleafnodes);
+// Log_Print("%6i active brushes\n", c_active_brushes);
+ if (numthreads == 1)
+ {
+// Log_Print("%6i KB of node memory\n", c_nodememory >> 10);
+// Log_Print("%6i KB of brush memory\n", c_brushmemory >> 10);
+// Log_Print("%6i KB of peak brush memory\n", c_peak_brushmemory >> 10);
+// Log_Print("%6i KB of winding memory\n", WindingMemory() >> 10);
+// Log_Print("%6i KB of peak winding memory\n", WindingPeakMemory() >> 10);
+ Log_Print("%6i KB of peak total bsp memory\n", c_peak_totalbspmemory >> 10);
+ } //end if
+
+ /*
+ point[0] = 1485;
+ point[1] = 956.125;
+ point[2] = 352.125;
+ node = PointInLeaf(tree->headnode, point);
+ if (node->planenum != PLANENUM_LEAF)
+ {
+ Log_Print("node not a leaf\n");
+ } //end if
+ Log_Print("at %f %f %f:\n", point[0], point[1], point[2]);
+ PrintContents(node->contents);
+ Log_Print("node->expansionbboxes = %d\n", node->expansionbboxes);
+ //*/
+ return tree;
+} //end of the function BrushBSP
+
|