Modified source engine (2017) developed by valve and leaked in 2020. Not for commercial purporses
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1470 lines
27 KiB

5 years ago
//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// $NoKeywords: $
//
//=============================================================================//
#include "vbsp.h"
int c_nodes;
int c_nonvis;
int c_active_brushes;
// if a brush just barely pokes onto the other side,
// let it slide by without chopping
#define PLANESIDE_EPSILON 0.001
//0.1
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)
Msg("here\n");
return;
}
FindBrushInTree (node->children[0], brushnum);
FindBrushInTree (node->children[1], brushnum);
}
//==================================================
/*
================
DrawBrushList
================
*/
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->visible)
GLS_Winding (s->winding, 2);
else
GLS_Winding (s->winding, 0);
}
}
GLS_EndScene ();
}
/*
================
WriteBrushList
================
*/
void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
{
int i;
side_t *s;
qprintf ("writing %s\n", name);
FileHandle_t f = g_pFileSystem->Open(name, "w");
for ( ; brush ; brush=brush->next)
{
for (i=0 ; i<brush->numsides ; i++)
{
s = &brush->sides[i];
if (!s->winding)
continue;
if (onlyvis && !s->visible)
continue;
OutputWinding (brush->sides[i].winding, f);
}
}
g_pFileSystem->Close (f);
}
void PrintBrush (bspbrush_t *brush)
{
int i;
Msg("brush: %p\n", brush);
for (i=0;i<brush->numsides ; i++)
{
pw(brush->sides[i].winding);
Msg("\n");
}
}
/*
==================
BoundBrush
Sets the mins/maxs based on the windings
==================
*/
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);
}
}
Vector PointInsideBrush( bspbrush_t *brush )
{
Vector insidePoint = vec3_origin;
bool bInside = false;
for ( int k = 0; k < 4 && !bInside; k++ )
{
bInside = true;
for (int i = 0; i < brush->numsides; i++)
{
side_t *side = &brush->sides[i];
plane_t *plane = &g_MainMap->mapplanes[side->planenum];
float d = DotProduct( plane->normal, insidePoint ) - plane->dist;
if ( d < 0 )
{
bInside = false;
insidePoint -= d * plane->normal;
}
}
}
return insidePoint;
}
/*
==================
CreateBrushWindings
==================
*/
void CreateBrushWindings (bspbrush_t *brush)
{
int i, j;
winding_t *w;
side_t *side;
plane_t *plane;
// translate the CSG problem to improve precision
Vector insidePoint = PointInsideBrush( brush );
Vector offset = -insidePoint;
for (i=0 ; i<brush->numsides ; i++)
{
side = &brush->sides[i];
plane = &g_MainMap->mapplanes[side->planenum];
w = BaseWindingForPlane (plane->normal, plane->dist + DotProduct(plane->normal, offset));
for (j=0 ; j<brush->numsides && w; j++)
{
if (i == j)
continue;
if (brush->sides[j].bevel)
continue;
plane = &g_MainMap->mapplanes[brush->sides[j].planenum^1];
ChopWindingInPlace (&w, plane->normal, plane->dist + DotProduct(plane->normal, offset), 0); //CLIP_EPSILON);
}
TranslateWinding( w, -offset );
side->winding = w;
}
BoundBrush (brush);
}
/*
==================
BrushFromBounds
Creates a new axial brush
==================
*/
bspbrush_t *BrushFromBounds (Vector& mins, Vector& maxs)
{
bspbrush_t *b;
int i;
Vector 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 = g_MainMap->FindFloatPlane (normal, dist);
normal[i] = -1;
dist = -mins[i];
b->sides[3+i].planenum = g_MainMap->FindFloatPlane (normal, dist);
}
CreateBrushWindings (b);
return b;
}
/*
==================
BrushVolume
==================
*/
vec_t BrushVolume (bspbrush_t *brush)
{
int i;
winding_t *w;
Vector 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;
}
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 = &g_MainMap->mapplanes[brush->sides[i].planenum];
d = -(DotProduct (corner, plane->normal) - plane->dist);
area = WindingArea (w);
volume += d*area;
}
volume /= 3;
return volume;
}
/*
================
CountBrushList
================
*/
int CountBrushList (bspbrush_t *brushes)
{
int c;
c = 0;
for ( ; brushes ; brushes = brushes->next)
c++;
return c;
}
/*
================
AllocTree
================
*/
tree_t *AllocTree (void)
{
tree_t *tree;
tree = (tree_t*)malloc(sizeof(*tree));
memset (tree, 0, sizeof(*tree));
ClearBounds (tree->mins, tree->maxs);
return tree;
}
/*
================
AllocNode
================
*/
node_t *AllocNode (void)
{
static int s_NodeCount = 0;
node_t *node;
node = (node_t*)malloc(sizeof(*node));
memset (node, 0, sizeof(*node));
node->id = s_NodeCount;
node->diskId = -1;
s_NodeCount++;
return node;
}
/*
================
AllocBrush
================
*/
bspbrush_t *AllocBrush (int numsides)
{
static int s_BrushId = 0;
bspbrush_t *bb;
int c;
c = (int)&(((bspbrush_t *)0)->sides[numsides]);
bb = (bspbrush_t*)malloc(c);
memset (bb, 0, c);
bb->id = s_BrushId++;
if (numthreads == 1)
c_active_brushes++;
return bb;
}
/*
================
FreeBrush
================
*/
void FreeBrush (bspbrush_t *brushes)
{
int i;
for (i=0 ; i<brushes->numsides ; i++)
if (brushes->sides[i].winding)
FreeWinding(brushes->sides[i].winding);
free (brushes);
if (numthreads == 1)
c_active_brushes--;
}
/*
================
FreeBrushList
================
*/
void FreeBrushList (bspbrush_t *brushes)
{
bspbrush_t *next;
for ( ; brushes ; brushes = next)
{
next = brushes->next;
FreeBrush (brushes);
}
}
/*
==================
CopyBrush
Duplicates the brush, the sides, and the windings
==================
*/
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;
}
/*
==================
PointInLeaf
==================
*/
node_t *PointInLeaf (node_t *node, Vector& point)
{
vec_t d;
plane_t *plane;
while (node->planenum != PLANENUM_LEAF)
{
plane = &g_MainMap->mapplanes[node->planenum];
if (plane->type < 3)
{
d = point[plane->type] - plane->dist;
}
else
{
d = DotProduct (point, plane->normal) - plane->dist;
}
if (d >= 0)
node = node->children[0];
else
node = node->children[1];
}
return node;
}
//========================================================
/*
==============
BoxOnPlaneSide
Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
==============
*/
int BrushBspBoxOnPlaneSide (const Vector& mins, const Vector& maxs, dplane_t *plane)
{
int side;
int i;
Vector 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;
}
/*
============
QuickTestBrushToPlanenum
============
*/
int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
{
int i, num;
plane_t *plane;
int s;
*numsplits = 0;
// 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 >= 0x10000)
Error ("bad planenum");
if (num == planenum)
return PSIDE_BACK|PSIDE_FACING;
if (num == (planenum ^ 1) )
return PSIDE_FRONT|PSIDE_FACING;
}
// box on plane side
plane = &g_MainMap->mapplanes[planenum];
s = BrushBspBoxOnPlaneSide (brush->mins, brush->maxs, plane);
// if both sides, count the visible faces split
if (s == PSIDE_BOTH)
{
*numsplits += 3;
}
return s;
}
/*
============
TestBrushToPlanenum
============
*/
int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
int *numsplits, qboolean *hintsplit, int *epsilonbrush)
{
int i, j, num;
plane_t *plane;
int s;
winding_t *w;
vec_t d, d_front, d_back;
int front, back;
*numsplits = 0;
*hintsplit = false;
// 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 >= 0x10000)
Error ("bad planenum");
if (num == planenum)
return PSIDE_BACK|PSIDE_FACING;
if (num == (planenum ^ 1) )
return PSIDE_FRONT|PSIDE_FACING;
}
// box on plane side
plane = &g_MainMap->mapplanes[planenum];
s = BrushBspBoxOnPlaneSide (brush->mins, brush->maxs, plane);
if (s != PSIDE_BOTH)
return s;
// 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].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;
}
if (front && back)
{
if ( !(brush->sides[i].surf & SURF_SKIP) )
{
(*numsplits)++;
if (brush->sides[i].surf & SURF_HINT)
*hintsplit = true;
}
}
}
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;
}
//========================================================
/*
================
WindingIsTiny
Returns true if the winding would be crunched out of
existance by the vertex snapping.
================
*/
#define EDGE_LENGTH 0.2
qboolean WindingIsTiny (winding_t *w)
{
int i, j;
vec_t len;
Vector 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;
}
// UNDONE: JAY: This should be a slightly better heuristic - it builds an OBB
// around the winding and tests planar dimensions. NOTE: This can fail when a
// winding normal cannot be constructed (or is degenerate), but that is probably
// desired in this case.
// UNDONE: Test & use this instead.
#if 0
qboolean WindingIsTiny2 (winding_t *w)
{
int i, j;
vec_t len;
Vector delta;
int edges;
vec_t maxLen = 0;
Vector maxEdge = vec3_origin;
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 > maxLen)
{
maxEdge = delta;
maxLen = len;
}
}
Vector normal;
vec_t dist;
WindingPlane (w, normal, &dist); // normal can come back vec3_origin in some cases
VectorNormalize(maxEdge);
Vector cross = CrossProduct(normal, maxEdge);
VectorNormalize(cross);
Vector mins, maxs;
ClearBounds( mins, maxs );
for (i=0 ; i<w->numpoints ; i++)
{
Vector point;
point.x = DotProduct( w->p[i], maxEdge );
point.y = DotProduct( w->p[i], cross );
point.z = DotProduct( w->p[i], normal );
AddPointToBounds( point, mins, maxs );
}
// check to see if the size in the plane is too small in either dimension
Vector size = maxs - mins;
for ( i = 0; i < 2; i++ )
{
if ( size[i] < EDGE_LENGTH )
return true;
}
return false;
}
#endif
/*
================
WindingIsHuge
Returns true if the winding still has one of the points
from basewinding for plane
================
*/
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] < MIN_COORD_INTEGER || w->p[i][j] > MAX_COORD_INTEGER)
return true;
}
return false;
}
//============================================================
/*
================
Leafnode
================
*/
void LeafNode (node_t *node, bspbrush_t *brushes)
{
bspbrush_t *b;
int i;
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;
}
}
node->contents |= b->original->contents;
}
node->brushlist = brushes;
}
void RemoveAreaPortalBrushes_R( node_t *node )
{
if( node->planenum == PLANENUM_LEAF )
{
// Remove any CONTENTS_AREAPORTAL brushes we added. We don't want them in the engine
// at runtime but we do want their flags in the leaves.
bspbrush_t **pPrev = &node->brushlist;
for( bspbrush_t *b=node->brushlist; b; b=b->next )
{
if( b->original->contents == CONTENTS_AREAPORTAL )
{
*pPrev = b->next;
}
else
{
pPrev = &b->next;
}
}
}
else
{
RemoveAreaPortalBrushes_R( node->children[0] );
RemoveAreaPortalBrushes_R( node->children[1] );
}
}
//============================================================
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");
}
}
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;
}
/*
================
SelectSplitSide
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..
================
*/
side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
{
int value, bestvalue;
bspbrush_t *brush, *test;
side_t *side, *bestside;
int i, j, 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, nonvisible-structural
// 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)
{
for (i=0 ; i<brush->numsides ; i++)
{
side = brush->sides + i;
if (side->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->tested)
continue; // we allready have metrics for this plane
if (side->surf & SURF_SKIP)
continue; // skip surfaces are never chosen
if ( side->visible ^ (pass<1) )
continue; // only check visible faces on first 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;
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 the brush shares this face, don't bother
// testing that facenum as a splitter again
if (s & PSIDE_FACING)
{
facing++;
for (j=0 ; j<test->numsides ; j++)
{
if ( (test->sides[j].planenum&~1) == pnum)
test->sides[j].tested = true;
}
}
if (s & PSIDE_FRONT)
front++;
if (s & PSIDE_BACK)
back++;
if (s == PSIDE_BOTH)
both++;
}
// 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 (g_MainMap->mapplanes[pnum].type < 3)
value+=5; // axial is better
value -= epsilonbrush*1000; // avoid!
// trans should split last
if ( side->surf & SURF_TRANS )
{
value -= 500;
}
// never split a hint side except with another hint
if (hintsplit && !(side->surf & SURF_HINT) )
value = -9999999;
// water should split first
if (side->contents & (CONTENTS_WATER | CONTENTS_SLIME))
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;
}
}
}
// if we found a good plane, don't bother trying any
// other passes
if (bestside)
{
if (pass > 0)
{
if (numthreads == 1)
c_nonvis++;
}
break;
}
}
//
// clear all the tested flags we set
//
for (brush = brushes ; brush ; brush=brush->next)
{
for (i=0 ; i<brush->numsides ; i++)
brush->sides[i].tested = false;
}
return bestside;
}
/*
==================
BrushMostlyOnSide
==================
*/
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;
}
/*
================
SplitBrush
Generates two new brushes, leaving the original
unchanged
================
*/
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 = &g_MainMap->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.1) // PLANESIDE_EPSILON)
{ // only on back
*back = CopyBrush (brush);
return;
}
if (d_back > -0.1) // PLANESIDE_EPSILON)
{ // only on front
*front = CopyBrush (brush);
return;
}
// Move the CSG problem so that offset is at the origin
// This gives us much better floating point precision in the clipping operations
Vector offset = -0.5f * (brush->mins + brush->maxs);
// create a new winding from the split plane
w = BaseWindingForPlane (plane->normal, plane->dist + DotProduct(plane->normal,offset));
for (i=0 ; i<brush->numsides && w ; i++)
{
plane2 = &g_MainMap->mapplanes[brush->sides[i].planenum ^ 1];
ChopWindingInPlace (&w, plane2->normal, plane2->dist+DotProduct(plane2->normal,offset), 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);
return;
}
if (WindingIsHuge (w))
{
qprintf ("WARNING: huge winding\n");
}
TranslateWinding( w, -offset );
midwinding = w;
//
//
// split it for real
//
//
//
// allocate two new brushes referencing the original
//
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++ )
{
// get the current side
s = &brush->sides[i];
// get the sides winding
w = s->winding;
if( !w )
continue;
// clip the winding
ClipWindingEpsilon_Offset( w, plane->normal, plane->dist, 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1], offset );
for( j = 0; j < 2; j++ )
{
// does winding exist?
if( !cw[j] )
continue;
#if 0
if (WindingIsTiny (cw[j]))
{
FreeWinding (cw[j]);
continue;
}
#endif
//
// create a clipped "side" with the new winding
//
cs = &b[j]->sides[b[j]->numsides];
b[j]->numsides++;
*cs = *s;
cs->winding = cw[j];
cs->tested = false;
// save the original side information
//cs->original = s->original;
}
}
// 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] < MIN_COORD_INTEGER || b[i]->maxs[j] > MAX_COORD_INTEGER)
{
qprintf ("bogus brush after clip\n");
break;
}
}
if (b[i]->numsides < 3 || j < 3)
{
FreeBrush (b[i]);
b[i] = NULL;
}
}
if ( !(b[0] && b[1]) )
{
if (!b[0] && !b[1])
qprintf ("split removed brush\n");
else
qprintf ("split not on both sides\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;
// initialize the displacement map index
cs->pMapDisp = NULL;
cs->visible = false;
cs->tested = false;
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;
// qprintf ("tiny volume after clip\n");
}
}
}
*front = b[0];
*back = b[1];
}
/*
================
SplitBrushList
================
*/
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;
}
if (newbrush2)
{
newbrush2->next = *back;
*back = newbrush2;
}
continue;
}
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;
}
}
if (sides & PSIDE_FRONT)
{
newbrush->next = *front;
*front = newbrush;
continue;
}
if (sides & PSIDE_BACK)
{
newbrush->next = *back;
*back = newbrush;
continue;
}
}
}
/*
================
BuildTree_r
================
*/
node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
{
node_t *newnode;
side_t *bestside;
int i;
bspbrush_t *children[2];
if (numthreads == 1)
c_nodes++;
// 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);
return node;
}
// this is a splitplane node
node->side = bestside;
node->planenum = bestside->planenum & ~1; // always use front facing
SplitBrushList (brushes, node, &children[0], &children[1]);
FreeBrushList (brushes);
// allocate children before recursing
for (i=0 ; i<2 ; i++)
{
newnode = AllocNode ();
newnode->parent = node;
node->children[i] = newnode;
}
SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
&node->children[1]->volume);
// recursively process children
for (i=0 ; i<2 ; i++)
{
node->children[i] = BuildTree_r (node->children[i], children[i]);
}
return node;
}
//===========================================================
/*
=================
BrushBSP
The incoming list will be freed before exiting
=================
*/
tree_t *BrushBSP (bspbrush_t *brushlist, Vector& mins, Vector& maxs)
{
node_t *node;
bspbrush_t *b;
int c_faces, c_nonvisfaces;
int c_brushes;
tree_t *tree;
int i;
vec_t volume;
qprintf ("--- BrushBSP ---\n");
tree = AllocTree ();
c_faces = 0;
c_nonvisfaces = 0;
c_brushes = 0;
for (b=brushlist ; b ; b=b->next)
{
c_brushes++;
volume = BrushVolume (b);
if (volume < microvolume)
{
Warning("Brush %i: WARNING, microbrush\n", b->original->id);
}
for (i=0 ; i<b->numsides ; i++)
{
if (b->sides[i].bevel)
continue;
if (!b->sides[i].winding)
continue;
if (b->sides[i].texinfo == TEXINFO_NODE)
continue;
if (b->sides[i].visible)
c_faces++;
else
c_nonvisfaces++;
}
AddPointToBounds (b->mins, tree->mins, tree->maxs);
AddPointToBounds (b->maxs, tree->mins, tree->maxs);
}
qprintf ("%5i brushes\n", c_brushes);
qprintf ("%5i visible faces\n", c_faces);
qprintf ("%5i nonvisible faces\n", c_nonvisfaces);
c_nodes = 0;
c_nonvis = 0;
node = AllocNode ();
node->volume = BrushFromBounds (mins, maxs);
tree->headnode = node;
node = BuildTree_r (node, brushlist);
qprintf ("%5i visible nodes\n", c_nodes/2 - c_nonvis);
qprintf ("%5i nonvis nodes\n", c_nonvis);
qprintf ("%5i leafs\n", (c_nodes+1)/2);
#if 0
{ // debug code
static node_t *tnode;
Vector p;
p[0] = -1469;
p[1] = -118;
p[2] = 119;
tnode = PointInLeaf (tree->headnode, p);
Msg("contents: %i\n", tnode->contents);
p[0] = 0;
}
#endif
return tree;
}