From f56bb35301836e56582a575a75864392a0177875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20P=2E=20Tjern=C3=B8?= Date: Mon, 2 Dec 2013 19:31:46 -0800 Subject: Fix line endings. WHAMMY. --- mp/src/utils/vbsp/brushbsp.cpp | 2938 ++++++++++++++++++++-------------------- 1 file changed, 1469 insertions(+), 1469 deletions(-) (limited to 'mp/src/utils/vbsp/brushbsp.cpp') diff --git a/mp/src/utils/vbsp/brushbsp.cpp b/mp/src/utils/vbsp/brushbsp.cpp index 17323c58..d455f30b 100644 --- a/mp/src/utils/vbsp/brushbsp.cpp +++ b/mp/src/utils/vbsp/brushbsp.cpp @@ -1,1469 +1,1469 @@ -//========= 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 ; inumsides ; 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 ; inumsides ; 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;inumsides ; 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 ; inumsides ; i++) - { - w = brush->sides[i].winding; - if (!w) - continue; - for (j=0 ; jnumpoints ; 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 ; inumsides ; i++) - { - side = &brush->sides[i]; - plane = &g_MainMap->mapplanes[side->planenum]; - w = BaseWindingForPlane (plane->normal, plane->dist + DotProduct(plane->normal, offset)); - for (j=0 ; jnumsides && 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 ; inumsides ; 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 ( ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; jnumpoints; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumsides ; 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 ; inumsides ; 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 ; jnumsides ; 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 ; inumsides ; 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 ; inumsides ; i++) - { - w = brush->sides[i].winding; - if (!w) - continue; - for (j=0 ; jnumpoints ; 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 ; inumsides ; i++) - { - w = brush->sides[i].winding; - if (!w) - continue; - for (j=0 ; jnumpoints ; 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 ; inumsides && 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 ; inumsides ; 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 ; inumsides ; 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; -} - +//========= 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 ; inumsides ; 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 ; inumsides ; 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;inumsides ; 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 ; inumsides ; i++) + { + w = brush->sides[i].winding; + if (!w) + continue; + for (j=0 ; jnumpoints ; 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 ; inumsides ; i++) + { + side = &brush->sides[i]; + plane = &g_MainMap->mapplanes[side->planenum]; + w = BaseWindingForPlane (plane->normal, plane->dist + DotProduct(plane->normal, offset)); + for (j=0 ; jnumsides && 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 ; inumsides ; 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 ( ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; inumsides ; 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 ; jnumpoints; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumpoints ; 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 ; inumsides ; 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 ; inumsides ; 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 ; jnumsides ; 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 ; inumsides ; 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 ; inumsides ; i++) + { + w = brush->sides[i].winding; + if (!w) + continue; + for (j=0 ; jnumpoints ; 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 ; inumsides ; i++) + { + w = brush->sides[i].winding; + if (!w) + continue; + for (j=0 ; jnumpoints ; 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 ; inumsides && 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 ; inumsides ; 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 ; inumsides ; 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; +} + -- cgit v1.2.3