1417 lines
48 KiB
C++
Executable File
1417 lines
48 KiB
C++
Executable File
//-----------------------------------------------------------------------------
|
|
// Torque Game Engine
|
|
// Copyright (C) GarageGames.com, Inc.
|
|
//-----------------------------------------------------------------------------
|
|
|
|
#include "core/bitVector.h"
|
|
#include "map2difPlus/bspNode.h"
|
|
#include "map2difPlus/csgBrush.h"
|
|
#include "math/mRandom.h"
|
|
|
|
namespace {
|
|
|
|
void flushedOutput(const char* string)
|
|
{
|
|
dPrintf(string);
|
|
dFflushStdout();
|
|
}
|
|
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
//-------------------------------------- EditBSPNode functions
|
|
//------------------------------------------------------------------------------
|
|
EditBSPNode::~EditBSPNode()
|
|
{
|
|
for (U32 i = 0; i < portals.size(); i++) {
|
|
delete portals[i];
|
|
portals[i] = NULL;
|
|
}
|
|
|
|
if (solidBrush)
|
|
gBrushArena.freeBrush(solidBrush);
|
|
|
|
// We do NOT release our links. they're doubled up, and we
|
|
// don't know if the bspnode on the other side is valid. let
|
|
// the arena remove them...
|
|
// We do need to delete mInteriorRes->mBrushes tho
|
|
for (U32 i = 0; i < brushList.size(); i++)
|
|
gBrushArena.freeBrush(brushList[i]);
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::createBSP(PlaneType _planeType)
|
|
{
|
|
if (brushList.size() != 0 && planeEQIndex != -1) {
|
|
AssertFatal(_planeType != planeType,
|
|
"Error, must be a different phase of insertion for us to be here...");
|
|
|
|
splitBrushList();
|
|
pFront->splitBrushList();
|
|
pBack->splitBrushList();
|
|
}
|
|
|
|
if (brushList.size() == 0) {
|
|
if (planeEQIndex != -1) {
|
|
pFront->createBSP(_planeType);
|
|
pBack->createBSP(_planeType);
|
|
} else {
|
|
planeType = _planeType;
|
|
}
|
|
return;
|
|
}
|
|
AssertFatal(planeEQIndex == -1, "Must be a leaf if we are here...");
|
|
|
|
U32 splitPlane = selectBestPlane();
|
|
if (splitPlane == U32(-1)) {
|
|
// We're done. no more planes to insert...
|
|
//
|
|
if (brushList.size() > 1) {
|
|
for (U32 i = 1; i < brushList.size(); i++) {
|
|
AssertFatal(brushList[0]->isEquivalent(*brushList[i]), "Error, non-equivalent mInteriorRes->mBrushes in leaf!");
|
|
}
|
|
|
|
U32 maxIndex = 0;
|
|
U32 maxVal = brushList[0]->brushId;
|
|
for (U32 i = 1; i < brushList.size(); i++) {
|
|
if (brushList[i]->brushId > maxVal) {
|
|
maxVal = brushList[i]->brushId;
|
|
maxIndex = i;
|
|
}
|
|
}
|
|
CSGBrush* pKeepBrush = brushList[maxIndex];
|
|
brushList[maxIndex] = NULL;
|
|
|
|
for (U32 i = 0; i < brushList.size(); i++) {
|
|
gBrushArena.freeBrush(brushList[i]);
|
|
}
|
|
|
|
brushList.setSize(1);
|
|
brushList[0] = pKeepBrush;
|
|
}
|
|
|
|
return;
|
|
}
|
|
AssertFatal(planeInParents(splitPlane) == false, "error, inserting a plane that's in a parent list...");
|
|
|
|
planeEQIndex = splitPlane;
|
|
planeType = _planeType;
|
|
|
|
pFront = gWorkingGeometry->mNodeArena.allocateNode(this);
|
|
pBack = gWorkingGeometry->mNodeArena.allocateNode(this);
|
|
pFront->isSolid = isSolid;
|
|
pBack->isSolid = isSolid;
|
|
pFront->zoneId = zoneId;
|
|
pBack->zoneId = zoneId;
|
|
|
|
splitBrushList();
|
|
pFront->createBSP(_planeType);
|
|
pBack->createBSP(_planeType);
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::zoneFlood()
|
|
{
|
|
// All we have to do is find an unflooded (empty) leaf, flood it, then continue until
|
|
// we're out...
|
|
if (planeEQIndex == -1) {
|
|
if (isSolid == true)
|
|
return;
|
|
|
|
// Do the flood fill here...
|
|
if (zoneId == -1) {
|
|
// Need to create the zone in the working geometry
|
|
//
|
|
gWorkingGeometry->mZones.push_back(new EditGeometry::Zone);
|
|
S32 markZoneId = (gWorkingGeometry->mZones.size() - 1);
|
|
gWorkingGeometry->mZones.last()->zoneId = markZoneId;
|
|
floodZone(markZoneId);
|
|
}
|
|
return;
|
|
}
|
|
|
|
pFront->zoneFlood();
|
|
pBack->zoneFlood();
|
|
}
|
|
|
|
S32 EditBSPNode::findZone(const Point3D& rPoint)
|
|
{
|
|
if (planeEQIndex == -1 || zoneId != -1) {
|
|
return zoneId;
|
|
}
|
|
|
|
PlaneSide side = gWorkingGeometry->getPlaneEQ(planeEQIndex).whichSideLow(rPoint);
|
|
|
|
if (side == PlaneFront) {
|
|
return pFront->findZone(rPoint);
|
|
} else if (side == PlaneBack) {
|
|
return pBack->findZone(rPoint);
|
|
} else {
|
|
if (pFront->isSolid == false) {
|
|
return pFront->findZone(rPoint);
|
|
} else if (pBack->isSolid == false) {
|
|
return pBack->findZone(rPoint);
|
|
} else {
|
|
return -1;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::gatherPortals()
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
if (isSolid) {
|
|
AssertFatal(portals.size() == 0, "error, no portals should be in a solid leaf!");
|
|
return;
|
|
}
|
|
|
|
if (portals.size() == 0)
|
|
return;
|
|
|
|
// leaf
|
|
for (U32 i = 0; i < portals.size(); i++) {
|
|
const PortalEntry* pEntry = portals[i];
|
|
|
|
// First, check if there is a vislink associated with this portal...
|
|
const VisLink* associatedLink = NULL;
|
|
for (U32 i = 0; i < visLinks.size(); i++) {
|
|
if (U32(visLinks[i]->portalId) == U32(pEntry->portalId)) {
|
|
associatedLink = visLinks[i];
|
|
break;
|
|
}
|
|
}
|
|
|
|
// Next, insert the appropriate information into the portal entry in the
|
|
// working geometry
|
|
EditGeometry::Portal* pGeomPortal = gWorkingGeometry->mPortals[pEntry->portalId];
|
|
if (pGeomPortal->planeEQIndex == -1) {
|
|
pGeomPortal->planeEQIndex = pEntry->planeEQIndex;
|
|
} else {
|
|
AssertFatal(U32(pGeomPortal->planeEQIndex) == U32(pEntry->planeEQIndex), "Error, mismatched portal planes!");
|
|
}
|
|
|
|
if (associatedLink != NULL) {
|
|
// Put the front/back info in place...
|
|
EditBSPNode* actualFront;
|
|
EditBSPNode* actualBack;
|
|
if (pEntry->planeEQIndex == associatedLink->planeEQIndex) {
|
|
actualFront = associatedLink->pFront;
|
|
actualBack = associatedLink->pBack;
|
|
} else {
|
|
AssertFatal(pEntry->planeEQIndex == gWorkingGeometry->getPlaneInverse(associatedLink->planeEQIndex), "Error, wtf!");
|
|
|
|
actualFront = associatedLink->pBack;
|
|
actualBack = associatedLink->pFront;
|
|
}
|
|
|
|
if (pGeomPortal->frontZone == -1) {
|
|
pGeomPortal->frontZone = actualFront->zoneId;
|
|
pGeomPortal->backZone = actualBack->zoneId;
|
|
} else if (pGeomPortal->frontZone != actualFront->zoneId ||
|
|
pGeomPortal->backZone != actualBack->zoneId) {
|
|
|
|
gWorkingGeometry->mPortals.push_back(new EditGeometry::Portal);
|
|
pGeomPortal = gWorkingGeometry->mPortals.last();
|
|
pGeomPortal->portalId = gWorkingGeometry->mPortals.size() - 1;
|
|
pGeomPortal->planeEQIndex = pEntry->planeEQIndex;
|
|
pGeomPortal->frontZone = actualFront->zoneId;
|
|
pGeomPortal->backZone = actualBack->zoneId;
|
|
|
|
const_cast<PortalEntry*>(pEntry)->portalId = pGeomPortal->portalId;
|
|
}
|
|
}
|
|
|
|
// Regardless of whether or not we've set the zones, we need to insert the winding
|
|
// but only if it's unique. Remember that we'll encounter each portal twice...
|
|
AssertFatal(pEntry->windings.size() == 1, "error, should only be one winding on the portal at this point...");
|
|
bool insert = true;
|
|
for (U32 i = 0; i < pGeomPortal->windings.size(); i++) {
|
|
if (windingsEquivalent(*pEntry->windings[0], pGeomPortal->windings[i]) == true) {
|
|
insert = false;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (insert == true)
|
|
pGeomPortal->windings.push_back(*pEntry->windings[0]);
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
// Non-leaf, continue...
|
|
|
|
AssertFatal(portals.size() == 0, "Error, shouldn't have portals here...");
|
|
|
|
pFront->gatherPortals();
|
|
pBack->gatherPortals();
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::floodZone(S32 markZoneId)
|
|
{
|
|
AssertFatal(planeEQIndex == -1, "Must be leaf, wtf!");
|
|
AssertFatal(zoneId == -1, "error, overwriting zone id, wtf!");
|
|
|
|
zoneId = markZoneId;
|
|
|
|
for (U32 i = 0; i < visLinks.size(); i++) {
|
|
VisLink* pLink = visLinks[i];
|
|
|
|
// Don't traverse through any portal links here...
|
|
if (pLink->portalId != -1)
|
|
continue;
|
|
|
|
EditBSPNode* pOtherNode = NULL;
|
|
if (pLink->pFront == this)
|
|
pOtherNode = pLink->pBack;
|
|
else if (pLink->pBack == this)
|
|
pOtherNode = pLink->pFront;
|
|
//else
|
|
// AssertFatal(false, "Error, Armageddon will shortly occur. Rip in the fabric of space-time. Talk to DMoore");
|
|
|
|
if (pOtherNode)
|
|
{
|
|
if (pOtherNode->zoneId == -1)
|
|
pOtherNode->floodZone(markZoneId);
|
|
else
|
|
AssertFatal(pOtherNode->zoneId == markZoneId, "Hmm. That's bad. shouldn't have adjacent leaves with non -1 differing zoneIds");
|
|
}
|
|
}
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::createVisLinks()
|
|
{
|
|
// First if we are a leaf, we can delete any links that bound on solid nodes,
|
|
// and return...
|
|
if (planeEQIndex == -1) {
|
|
|
|
if( true == gWorkingGeometry->mGenerateGraph ){
|
|
gWorkingGeometry->gatherLinksForGraph(this);
|
|
}
|
|
|
|
if (isSolid == true){
|
|
eraseReferencingLinks();
|
|
}
|
|
|
|
// Ok, now we need to determine for all links, if any correspond to a
|
|
// portal.
|
|
for (U32 i = 0; i < portals.size(); i++) {
|
|
const PortalEntry* pEntry = portals[i];
|
|
AssertISV(pEntry->windings.size() == 1, avar("Error, bad assumption (pEntry->windings.size() == %d, not 1) Go smack DMoore", pEntry->windings.size()));
|
|
|
|
for (U32 j = 0; j < visLinks.size(); j++) {
|
|
if (windingsEquivalent(visLinks[j]->winding, *pEntry->windings[0])) {
|
|
AssertFatal(visLinks[j]->portalId == -1 || U32(visLinks[j]->portalId) == pEntry->portalId,
|
|
"Error, different portals corresponding to the same link?");
|
|
visLinks[j]->portalId = pEntry->portalId;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
// If not, we need to create a planeWinding for our plane. This will be
|
|
// clipped to all the bounding faces of the gWorkingGeometry, and all
|
|
// the planes of the node's parents.
|
|
//
|
|
VisLink* pVisLink = gWorkingGeometry->mVisLinkArena.allocateLink();
|
|
pVisLink->planeEQIndex = planeEQIndex;
|
|
pVisLink->pFront = pFront;
|
|
pVisLink->pBack = pBack;
|
|
|
|
createBoundedWinding(gWorkingGeometry->getMinBound(),
|
|
gWorkingGeometry->getMaxBound(),
|
|
planeEQIndex,
|
|
&pVisLink->winding);
|
|
|
|
// Now, clip to parents...
|
|
EditBSPNode* pParProbePrev = this;
|
|
EditBSPNode* pParProbe = pParent;
|
|
while (pParProbe != NULL) {
|
|
if (pParProbe->pFront == pParProbePrev)
|
|
clipWindingToPlaneFront(&pVisLink->winding, pParProbe->planeEQIndex);
|
|
else
|
|
clipWindingToPlaneFront(&pVisLink->winding, gWorkingGeometry->getPlaneInverse(pParProbe->planeEQIndex));
|
|
|
|
AssertFatal(pVisLink->winding.numIndices != 0, "This should never happen: 0 verts in a vis link?");
|
|
|
|
pParProbePrev = pParProbe;
|
|
pParProbe = pParProbe->pParent;
|
|
}
|
|
|
|
// Ok, we now have a shiny new vis link that represents us
|
|
// Now, we split our _current_ list, and push our links down to our children.
|
|
//
|
|
splitVisLinks();
|
|
|
|
// Now we push the "us" link into front and back, and descend...
|
|
// Note that we want to shove this back ourselves...
|
|
pFront->visLinks.push_back(pVisLink);
|
|
pBack->visLinks.push_back(pVisLink);
|
|
|
|
splitPortalEntries();
|
|
|
|
pBack->createVisLinks();
|
|
pFront->createVisLinks();
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::createPortalWindings(const PortalEntry& rBaseWindings,
|
|
PortalEntry* pFinalEntry)
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
// Leaf. Keep or toss winding based on solid flag.
|
|
//
|
|
if (isSolid == true)
|
|
return;
|
|
|
|
for (U32 i = 0; i < rBaseWindings.windings.size(); i++) {
|
|
pFinalEntry->windings.push_back(new Winding);
|
|
*(pFinalEntry->windings.last()) = *(rBaseWindings.windings[i]);
|
|
}
|
|
return;
|
|
}
|
|
|
|
if (gWorkingGeometry->isCoplanar(planeEQIndex, rBaseWindings.planeEQIndex)) {
|
|
// Coplanar. Have to handle this specially.
|
|
//
|
|
PortalEntry frontClipped;
|
|
frontClipped.planeEQIndex = rBaseWindings.planeEQIndex;
|
|
|
|
pFront->createPortalWindings(rBaseWindings,
|
|
&frontClipped);
|
|
|
|
// frontClipped now becomes the base windings that are submitted to
|
|
// the back side.
|
|
//
|
|
pBack->createPortalWindings(frontClipped, pFinalEntry);
|
|
} else {
|
|
// Split the windings, and pass them to children...
|
|
//
|
|
PortalEntry fCopy, bCopy;
|
|
fCopy.planeEQIndex = bCopy.planeEQIndex = rBaseWindings.planeEQIndex;
|
|
|
|
for (U32 i = 0; i < rBaseWindings.windings.size(); i++) {
|
|
Winding* fWinding = new Winding;
|
|
Winding* bWinding = new Winding;
|
|
*fWinding = *(rBaseWindings.windings[i]);
|
|
*bWinding = *(rBaseWindings.windings[i]);
|
|
|
|
clipWindingToPlaneFront(fWinding, planeEQIndex);
|
|
clipWindingToPlaneFront(bWinding, gWorkingGeometry->getPlaneInverse(planeEQIndex));
|
|
AssertFatal(fWinding->numIndices != 0 || bWinding->numIndices != 0,
|
|
"Bad clipping. Should never happen unless coplanar.");
|
|
|
|
if (fWinding->numIndices != 0)
|
|
fCopy.windings.push_back(fWinding);
|
|
if (bWinding->numIndices != 0)
|
|
bCopy.windings.push_back(bWinding);
|
|
|
|
AssertFatal(fWinding->numIndices != 0 || bWinding->numIndices != 0,
|
|
"EditBSPNode::createPortalWindings: can only happen if coplanar, and then we shouldn't be here!");
|
|
if (fWinding->numIndices == 0)
|
|
delete fWinding;
|
|
if (bWinding->numIndices == 0)
|
|
delete bWinding;
|
|
}
|
|
|
|
if (fCopy.windings.size() != 0)
|
|
pFront->createPortalWindings(fCopy, pFinalEntry);
|
|
if (bCopy.windings.size() != 0)
|
|
pBack->createPortalWindings(bCopy, pFinalEntry);
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
bool EditBSPNode::planeInParents(U32 testPlane)
|
|
{
|
|
const EditBSPNode* pProbe = pParent;
|
|
while (pProbe != NULL) {
|
|
AssertFatal(pProbe->planeEQIndex != -1, "Huh");
|
|
|
|
if (U32(pProbe->planeEQIndex) == testPlane ||
|
|
U32(pProbe->planeEQIndex) == gWorkingGeometry->getPlaneInverse(testPlane))
|
|
return true;
|
|
|
|
pProbe = pProbe->pParent;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
S32 EditBSPNode::calcPlaneRating(U32 testPlane)
|
|
{
|
|
// Things that we don't like:
|
|
// - Splitting of many planes
|
|
// - Creation of tiny windings
|
|
// - Imbalance of planes on one side or the other
|
|
// Things that we do like:
|
|
// - Planes that are coplanar with many other planes under consideration
|
|
// - axial planes
|
|
|
|
AssertFatal((testPlane & 0x1) == 0, "Only test even plane nums!");
|
|
|
|
bool isAxial = false;
|
|
S32 numCoplanar = 0;
|
|
S32 numTinyWindings = 0;
|
|
S32 numSplits = 0;
|
|
S32 numFront = 0;
|
|
S32 numBack = 0;
|
|
|
|
const PlaneEQ& rPlane = gWorkingGeometry->getPlaneEQ(testPlane);
|
|
|
|
// Axial test
|
|
U32 zeroCount = 0;
|
|
zeroCount += (rPlane.normal.x == 0) ? 1 : 0;
|
|
zeroCount += (rPlane.normal.y == 0) ? 1 : 0;
|
|
zeroCount += (rPlane.normal.z == 0) ? 1 : 0;
|
|
AssertFatal(zeroCount != 3, "Huh? This is a really bad plane");
|
|
if (zeroCount == 2)
|
|
isAxial = true;
|
|
|
|
// Count splits, sides, etc.
|
|
for (U32 i = 0; i < brushList.size(); i++) {
|
|
assessPlane(testPlane,
|
|
*brushList[i],
|
|
&numCoplanar,
|
|
&numTinyWindings,
|
|
&numSplits,
|
|
&numFront,
|
|
&numBack);
|
|
}
|
|
|
|
// Ok. Now, I'm blatantly copying this from the qbsp3 source. Their hueristic:
|
|
// score = 5 * coplanar +
|
|
// -5 * splits +
|
|
// - abs(numFront - numBack) +
|
|
// -1000 * numTinyWindings +
|
|
// 5 * isAxial
|
|
// Plus some crap we don't care about. For now, we'll just duplicate this.
|
|
//
|
|
S32 finalScore = 5 * numCoplanar - 5 * numSplits - mAbs(numFront - numBack);
|
|
finalScore -= 1000 * numTinyWindings;
|
|
finalScore += isAxial ? 5 : 0;
|
|
|
|
return finalScore;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::splitBrushList()
|
|
{
|
|
if (planeEQIndex == -1)
|
|
return;
|
|
|
|
if (planeEQIndex == 630)
|
|
U32 test = 0;
|
|
|
|
// Ok, Ok, we have to do actual work here.
|
|
for (S32 i = S32(brushList.size()) - 1; i >= 0 ; i--) {
|
|
CSGBrush* pBrush = brushList[i];
|
|
brushList.erase(i);
|
|
|
|
CSGBrush* pFrontBrush = NULL;
|
|
CSGBrush* pBackBrush = NULL;
|
|
splitBrush(pBrush, planeEQIndex, pFrontBrush, pBackBrush);
|
|
|
|
if (pFrontBrush != NULL) {
|
|
for (U32 j = 0; j < pFrontBrush->mPlanes.size(); j++) {
|
|
if (gWorkingGeometry->isCoplanar(pFrontBrush->mPlanes[j].planeEQIndex, planeEQIndex)) {
|
|
AssertFatal(pFrontBrush->mPlanes[j].isInserted() == false, "Error, bad assumption somewhere in splitBrushList");
|
|
pFrontBrush->mPlanes[j].markInserted();
|
|
|
|
if (pFrontBrush->noMoreInsertables() == true) {
|
|
pFront->isSolid = true;
|
|
|
|
if (pFront->solidBrush == NULL) {
|
|
AssertFatal(pFront->solidBrush == NULL, "hmm");
|
|
pFront->solidBrush = pFrontBrush;
|
|
pFrontBrush = NULL;
|
|
break;
|
|
} else {
|
|
gBrushArena.freeBrush(pFrontBrush);
|
|
pFrontBrush = NULL;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (pFrontBrush) {
|
|
if (pFront->isSolid == false) {
|
|
pFront->brushList.push_back(pFrontBrush);
|
|
}
|
|
else {
|
|
// This next condition is a little wierd, so I'm separating it out.
|
|
// If the solid Brush is null, the brush has passed the test on
|
|
// a brush that knows better (i.e, our parent), and we can insert
|
|
// it.
|
|
if (pFront->solidBrush == NULL ||
|
|
pFront->solidBrush->mBrushType >= pFrontBrush->mBrushType) {
|
|
pFront->brushList.push_back(pFrontBrush);
|
|
} else {
|
|
gBrushArena.freeBrush(pFrontBrush);
|
|
pFrontBrush = NULL;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if (pBackBrush != NULL) {
|
|
for (U32 j = 0; j < pBackBrush->mPlanes.size(); j++) {
|
|
if (gWorkingGeometry->isCoplanar(pBackBrush->mPlanes[j].planeEQIndex, planeEQIndex)) {
|
|
AssertFatal(pBackBrush->mPlanes[j].isInserted() == false, "Error, bad assumption somewhere in splitBrushList");
|
|
pBackBrush->mPlanes[j].markInserted();
|
|
|
|
if (pBackBrush->noMoreInsertables() == true) {
|
|
pBack->isSolid = true;
|
|
|
|
if (pBack->solidBrush == NULL) {
|
|
AssertFatal(pBack->solidBrush == NULL, "hmm");
|
|
pBack->solidBrush = pBackBrush;
|
|
pBackBrush = NULL;
|
|
break;
|
|
} else {
|
|
gBrushArena.freeBrush(pBackBrush);
|
|
pBackBrush = NULL;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if (pBackBrush) {
|
|
if (pBack->isSolid == false) {
|
|
pBack->brushList.push_back(pBackBrush);
|
|
}
|
|
else {
|
|
// This next condition is a little wierd, so I'm separating it out.
|
|
// If the solid Brush is null, the brush has passed the test on
|
|
// a brush that knows better (i.e, our parent), and we can insert
|
|
// it.
|
|
if (pBack->solidBrush == NULL ||
|
|
pBack->solidBrush->mBrushType >= pBackBrush->mBrushType) {
|
|
pBack->brushList.push_back(pBackBrush);
|
|
} else {
|
|
gBrushArena.freeBrush(pBackBrush);
|
|
pBackBrush = NULL;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
gBrushArena.freeBrush(pBrush);
|
|
}
|
|
brushList.compact();
|
|
|
|
pFront->splitBrushList();
|
|
pBack->splitBrushList();
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::splitVisLinks()
|
|
{
|
|
AssertFatal(pFront->visLinks.size() == 0 && pBack->visLinks.size() == 0, "Error, children may not have visLinks at this point!");
|
|
for (S32 i = S32(visLinks.size()) - 1; i >= 0; i--) {
|
|
VisLink* pSplit = visLinks[i];
|
|
visLinks[i] = NULL;
|
|
visLinks.erase(i);
|
|
|
|
if (pSplit->intersect(planeEQIndex) == true) {
|
|
// Need to split this link.
|
|
VisLink* pOther = gWorkingGeometry->mVisLinkArena.allocateLink();
|
|
pOther->planeEQIndex = pSplit->planeEQIndex;
|
|
pOther->pFront = pSplit->pFront;
|
|
pOther->pBack = pSplit->pBack;
|
|
pOther->winding = pSplit->winding;
|
|
|
|
clipWindingToPlaneFront(&pSplit->winding, planeEQIndex);
|
|
clipWindingToPlaneFront(&pOther->winding, gWorkingGeometry->getPlaneInverse(planeEQIndex));
|
|
AssertFatal(pSplit->winding.numIndices != 0 && pOther->winding.numIndices != 0,
|
|
"Intersections must result in two non-zero windings!");
|
|
|
|
if (pSplit->pFront == this) {
|
|
AssertFatal(pOther->pFront == this, "Error in vissplit. Back does not point to proper node");
|
|
|
|
pSplit->pFront = pFront;
|
|
if (pFront)
|
|
pFront->enterLink(pSplit);
|
|
|
|
if (pOther->pBack)
|
|
pOther->pBack->visLinks.push_back(pOther);
|
|
|
|
if (pOther)
|
|
pOther->pFront = pBack;
|
|
|
|
if (pBack)
|
|
pBack->enterLink(pOther);
|
|
}
|
|
else if (pSplit->pBack == this) {
|
|
AssertFatal(pOther->pBack == this, "Error in vissplit. Back does not point to proper node");
|
|
|
|
pSplit->pBack = pFront;
|
|
if (pFront)
|
|
pFront->enterLink(pSplit);
|
|
|
|
if (pOther->pFront)
|
|
pOther->pFront->visLinks.push_back(pOther);
|
|
|
|
if (pOther)
|
|
pOther->pBack = pBack;
|
|
|
|
if (pBack)
|
|
pBack->enterLink(pOther);
|
|
}
|
|
else {
|
|
AssertFatal(false, "Error in vissplit. Does not point to proper nodes");
|
|
}
|
|
} else {
|
|
// Just find out what side to put it in...
|
|
PlaneSide side = pSplit->whichSide(planeEQIndex);
|
|
|
|
EditBSPNode* insertNode;
|
|
if (side == PlaneFront) {
|
|
insertNode = pFront;
|
|
}
|
|
else if (side == PlaneBack) {
|
|
insertNode = pBack;
|
|
}
|
|
else {
|
|
//AssertISV(false, "Vislink cannot be coplanar with a node!");
|
|
insertNode = NULL;
|
|
}
|
|
|
|
if (pSplit->pFront == this)
|
|
pSplit->pFront = insertNode;
|
|
else if (pSplit->pBack == this)
|
|
pSplit->pBack = insertNode;
|
|
else
|
|
AssertISV(false, "Error in vissplit. Does not point to proper nodes");
|
|
|
|
if (insertNode)
|
|
insertNode->enterLink(pSplit);
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::splitPortalEntries()
|
|
{
|
|
AssertFatal(planeEQIndex != -1 && pFront && pBack,
|
|
"Shouldn't be here unless we're a node");
|
|
|
|
|
|
for (S32 i = S32(portals.size()) - 1; i >= 0; i--) {
|
|
// Now, these windings should be all on one side or the other.
|
|
// it is an error to split portal entries at this point...
|
|
//
|
|
PortalEntry* pEntry = portals[i];
|
|
portals.erase(i);
|
|
|
|
|
|
if (gWorkingGeometry->isCoplanar(pEntry->planeEQIndex, planeEQIndex) == false) {
|
|
PortalEntry* pFrontCopy = new PortalEntry;
|
|
PortalEntry* pBackCopy = new PortalEntry;
|
|
pFrontCopy->copyEntry(*pEntry);
|
|
pBackCopy->copyEntry(*pEntry);
|
|
|
|
PortalEntry* pInsertFront = NULL;
|
|
PortalEntry* pInsertBack = NULL;
|
|
|
|
for (S32 i = S32(pEntry->windings.size()) - 1; i >= 0; i--) {
|
|
U32 side = windingWhichSide(*pEntry->windings[i], pEntry->planeEQIndex, planeEQIndex);
|
|
AssertFatal(side != PlaneSpecialOn, "Error, should only happen on coplanar portal");
|
|
|
|
if (side & PlaneSpecialFront) {
|
|
// Gotta put it into the front node
|
|
pInsertFront = pFrontCopy;
|
|
|
|
// Gotta clip this winding?
|
|
if (side & PlaneSpecialBack)
|
|
clipWindingToPlaneFront(pFrontCopy->windings[i], planeEQIndex);
|
|
}
|
|
else {
|
|
// Delete this winding from the front
|
|
delete pFrontCopy->windings[i];
|
|
pFrontCopy->windings.erase(i);
|
|
}
|
|
|
|
if (side & PlaneSpecialBack) {
|
|
pInsertBack = pBackCopy;
|
|
|
|
if (side & PlaneSpecialFront)
|
|
clipWindingToPlaneFront(pBackCopy->windings[i], planeEQIndex);
|
|
}
|
|
else {
|
|
delete pBackCopy->windings[i];
|
|
pBackCopy->windings.erase(i);
|
|
}
|
|
}
|
|
|
|
// Ok, we only insert the copies if at least one winding wound up in the
|
|
// appropriate child
|
|
//
|
|
if (pInsertFront != NULL)
|
|
pFront->portals.push_back(pInsertFront);
|
|
else
|
|
delete pFrontCopy;
|
|
|
|
if (pInsertBack != NULL)
|
|
pBack->portals.push_back(pInsertBack);
|
|
else
|
|
delete pBackCopy;
|
|
}
|
|
else {
|
|
// Portal is coplanar to node plane, push into both children...
|
|
PortalEntry* pFrontCopy = new PortalEntry;
|
|
PortalEntry* pBackCopy = new PortalEntry;
|
|
pFrontCopy->copyEntry(*pEntry);
|
|
pBackCopy->copyEntry(*pEntry);
|
|
pFront->portals.push_back(pFrontCopy);
|
|
pBack->portals.push_back(pBackCopy);
|
|
}
|
|
|
|
delete pEntry;
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
U32 EditBSPNode::selectBestPlane()
|
|
{
|
|
// Shuffle the brush indices...
|
|
static MRandomLCG sRand;
|
|
static Vector<U32> shuffledIndices;
|
|
shuffledIndices.setSize(brushList.size());
|
|
for (U32 i = 0; i < shuffledIndices.size(); i++)
|
|
shuffledIndices[i] = i;
|
|
|
|
for (S32 i = shuffledIndices.size() - 1; i > 0; i--) {
|
|
U32 k = mFloor(sRand.randF() * F32(i)) + 1;
|
|
U32 temp = shuffledIndices[i];
|
|
shuffledIndices[i] = shuffledIndices[k];
|
|
shuffledIndices[k] = temp;
|
|
}
|
|
|
|
BitVector uniqueSet(gWorkingGeometry->mPlaneEQs.size() / 2);
|
|
uniqueSet.clear();
|
|
|
|
extern U32 gMaxPlanesConsidered;
|
|
U32 planeCount = 0;
|
|
for (U32 i = 0; i < brushList.size() && planeCount < gMaxPlanesConsidered; i++) {
|
|
CSGBrush* pBrush = brushList[shuffledIndices[i]];
|
|
for (U32 j = 0; j < pBrush->mPlanes.size() && planeCount < gMaxPlanesConsidered; j++) {
|
|
if (pBrush->mPlanes[j].isInserted())
|
|
continue;
|
|
|
|
if (uniqueSet.test(pBrush->mPlanes[j].planeEQIndex >> 1) == false)
|
|
planeCount++;
|
|
uniqueSet.set(pBrush->mPlanes[j].planeEQIndex >> 1);
|
|
}
|
|
}
|
|
|
|
Vector<U32> uniquePlanes;
|
|
uniquePlanes.reserve(planeCount);
|
|
for (U32 i = 0; i < gWorkingGeometry->mPlaneEQs.size() / 2; i++) {
|
|
if (uniqueSet.test(i))
|
|
uniquePlanes.push_back(i << 1);
|
|
}
|
|
|
|
if (uniquePlanes.size() == 0)
|
|
return U32(-1);
|
|
|
|
S32 maxRating = -(1 << 30);
|
|
S32 maxIndex = -1;
|
|
for (U32 i = 0; i < uniquePlanes.size(); i++) {
|
|
S32 currRating = calcPlaneRating(uniquePlanes[i]);
|
|
if (currRating > maxRating) {
|
|
maxRating = currRating;
|
|
maxIndex = i;
|
|
}
|
|
}
|
|
AssertFatal(maxIndex != -1, "Error, no index selected?");
|
|
|
|
// Note that while we have rated only the front sides, we insert the planes
|
|
// as they are found...
|
|
//
|
|
return uniquePlanes[maxIndex];
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
EditBSPNode::PortalEntry* EditBSPNode::mungePortalBrush(CSGBrush* pBrush)
|
|
{
|
|
// We first need to determine which plane we are going to use. This is
|
|
// determined by finding the plane with the winding that has the most
|
|
// surface area, before clipping.
|
|
//
|
|
F64 maxArea = -1;
|
|
S32 maxIndex = -1;
|
|
|
|
for (U32 i = 0; i < pBrush->mPlanes.size(); i++) {
|
|
CSGPlane& rPlane = pBrush->mPlanes[i];
|
|
|
|
F64 area = getWindingSurfaceArea(rPlane.winding, rPlane.planeEQIndex);
|
|
AssertFatal(area >= 0.0, "Error, negative area returned for winding...");
|
|
if (area > maxArea) {
|
|
maxArea = area;
|
|
maxIndex = i;
|
|
}
|
|
}
|
|
AssertFatal(maxIndex != -1, "error, no portal plane found to insert?");
|
|
|
|
// Ok, we have our plane. Toss out all planes on the brush but the selected
|
|
// one, and insert it in the BSP.
|
|
//
|
|
CSGPlane& rPlane = pBrush->mPlanes[maxIndex];
|
|
Point3D ortho1;
|
|
Point3D ortho2;
|
|
bool found1 = false;
|
|
for (U32 i = 0; i < pBrush->mPlanes.size(); i++) {
|
|
if (i == maxIndex)
|
|
continue;
|
|
|
|
CSGPlane& rPoss = pBrush->mPlanes[i];
|
|
if (mFabs(mDot(gWorkingGeometry->getPlaneEQ(rPoss.planeEQIndex).normal,
|
|
gWorkingGeometry->getPlaneEQ(rPlane.planeEQIndex).normal)) < 0.0000001) {
|
|
ortho1 = gWorkingGeometry->getPlaneEQ(rPoss.planeEQIndex).normal;
|
|
found1 = true;
|
|
break;
|
|
}
|
|
}
|
|
AssertFatal(found1, "Error, portal brush is likely not a cube!");
|
|
mCross(ortho1, gWorkingGeometry->getPlaneEQ(rPlane.planeEQIndex).normal, &ortho2);
|
|
ortho2.normalize();
|
|
AssertFatal(mDot(ortho1, gWorkingGeometry->getPlaneEQ(rPlane.planeEQIndex).normal) < 0.0000001, "Bad normal vectors0 for portal");
|
|
AssertFatal(mDot(ortho2, gWorkingGeometry->getPlaneEQ(rPlane.planeEQIndex).normal) < 0.0000001, "Bad normal vectors1 for portal");
|
|
AssertFatal(mDot(ortho1, ortho2) < 0.0000001, "Bad normal vectors2 for portal");
|
|
|
|
if (maxIndex != 0)
|
|
pBrush->mPlanes[0] = pBrush->mPlanes[maxIndex];
|
|
pBrush->mPlanes.setSize(1);
|
|
|
|
// First, create the portal windings...
|
|
//
|
|
PortalEntry baseWindings;
|
|
baseWindings.windings.push_back(new Winding);
|
|
*(baseWindings.windings[0]) = pBrush->mPlanes[0].winding;
|
|
baseWindings.planeEQIndex = pBrush->mPlanes[0].planeEQIndex;
|
|
|
|
PortalEntry* pFinalWindings = new PortalEntry;
|
|
pFinalWindings->planeEQIndex = pBrush->mPlanes[0].planeEQIndex;
|
|
createPortalWindings(baseWindings, pFinalWindings);
|
|
|
|
pFinalWindings->ortho1 = ortho1;
|
|
pFinalWindings->ortho2 = ortho2;
|
|
|
|
if (pFinalWindings->windings.size() != 0) {
|
|
return pFinalWindings;
|
|
} else {
|
|
delete pFinalWindings;
|
|
return NULL;
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::insertPortalEntry(PortalEntry* pPortal)
|
|
{
|
|
// This is just a straight plane insert, with one difference. If we escape out
|
|
// on a co-planar planeEQ, we need to mark the node as a portal containing node,
|
|
// and place the portal windings in it.
|
|
//
|
|
if (planeEQIndex == -1) {
|
|
// We can't be in a solid node because of the way that we clipped the portal
|
|
// windings.
|
|
AssertFatal(pFront == NULL && pBack == NULL,
|
|
"EditBSPNode::insertPortalBrush: front/back must be NULL if planeEQ == -1");
|
|
AssertFatal(isSolid == false, "Must insert into an empty node");
|
|
// AssertISV(planeType == EditBSPNode::Structural,
|
|
// "Error, portal breaking a portal leaf. Bad. "
|
|
// "Probably a floating portal brush somewhere. Talk to DMoore for more info");
|
|
|
|
// A portal plane insertion into a leaf node creates two empty nodes on either
|
|
// side.
|
|
planeEQIndex = pPortal->planeEQIndex;
|
|
planeType = EditBSPNode::Portal;
|
|
|
|
pFront = gWorkingGeometry->mNodeArena.allocateNode(this);
|
|
pBack = gWorkingGeometry->mNodeArena.allocateNode(this);
|
|
pFront->planeType = EditBSPNode::Portal;
|
|
pBack->planeType = EditBSPNode::Portal;
|
|
pFront->isSolid = pBack->isSolid = false;
|
|
|
|
// We need to note that we're a portal, and enter the PortalEntry into our
|
|
// list...
|
|
AssertISV(pPortal->windings.size() == 1, avar("Error, bad assumption (pEntry->windings.size() == %d, not 1) Go smack DMoore", pPortal->windings.size()));
|
|
portals.push_back(pPortal);
|
|
|
|
return;
|
|
}
|
|
|
|
if (gWorkingGeometry->isCoplanar(planeEQIndex, pPortal->planeEQIndex)) {
|
|
// Coplanar to this node. Mark the node as a portal node, and insert the
|
|
// portal windings into the nodes list. Make sure we can merge any superfluous
|
|
// windings...
|
|
//
|
|
if (pPortal->windings.size() > 1) {
|
|
for (U32 i = 0; i < pPortal->windings.size(); i++)
|
|
pPortal->windings[i]->numNodes = 0;
|
|
|
|
bool collapsed = true;
|
|
while (collapsed == true) {
|
|
collapsed = false;
|
|
for (U32 i = 0; i < pPortal->windings.size() && !collapsed; i++) {
|
|
for (U32 j = i + 1; j < pPortal->windings.size() && !collapsed; j++) {
|
|
if (collapseWindings(*pPortal->windings[i], *pPortal->windings[j]) == true) {
|
|
collapsed = true;
|
|
delete pPortal->windings[j];
|
|
pPortal->windings.erase(j);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
AssertISV(pPortal->windings.size() == 1, avar("Error, bad assumption (pEntry->windings.size() == %d, not 1) Go smack DMoore (portal %d)", pPortal->windings.size(), pPortal->portalId));
|
|
|
|
portals.push_back(pPortal);
|
|
} else {
|
|
// Gotta split. Make a copy, and split against the front and the back
|
|
// of our plane.
|
|
//
|
|
PortalEntry* backPortals = new PortalEntry;
|
|
backPortals->planeEQIndex = pPortal->planeEQIndex;
|
|
backPortals->portalId = pPortal->portalId;
|
|
|
|
for (U32 i = 0; i < pPortal->windings.size(); i++) {
|
|
backPortals->windings.push_back(new Winding);
|
|
*(backPortals->windings[i]) = *(pPortal->windings[i]);
|
|
}
|
|
|
|
for (U32 i = 0; i < pPortal->windings.size(); i++) {
|
|
clipWindingToPlaneFront(pPortal->windings[i], planeEQIndex);
|
|
clipWindingToPlaneFront(backPortals->windings[i], gWorkingGeometry->getPlaneInverse(planeEQIndex));
|
|
AssertFatal(pPortal->windings[i]->numIndices + backPortals->windings[i]->numIndices != 0,
|
|
"Error, bad clip. should only happen if coplanar");
|
|
}
|
|
|
|
for (S32 i = S32(pPortal->windings.size() - 1); i >= 0; i--) {
|
|
if (pPortal->windings[i]->numIndices == 0) {
|
|
delete pPortal->windings[i];
|
|
pPortal->windings.erase(i);
|
|
}
|
|
if (backPortals->windings[i]->numIndices == 0) {
|
|
delete backPortals->windings[i];
|
|
backPortals->windings.erase(i);
|
|
}
|
|
}
|
|
|
|
if (pPortal->windings.size() != 0)
|
|
pFront->insertPortalEntry(pPortal);
|
|
else
|
|
delete pPortal;
|
|
|
|
if (backPortals->windings.size() != 0)
|
|
pBack->insertPortalEntry(backPortals);
|
|
else
|
|
delete backPortals;
|
|
}
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::eraseReferencingLinks()
|
|
{
|
|
for (S32 i = S32(visLinks.size()) - 1; i >= 0; i--) {
|
|
VisLink* pRemove = visLinks[i];
|
|
visLinks[i] = NULL;
|
|
visLinks.erase(i);
|
|
|
|
AssertFatal(pRemove->portalId == -1, "Error, removing a link associated with a portal!");
|
|
|
|
EditBSPNode* pOtherNode;
|
|
if (pRemove->pFront == this)
|
|
pOtherNode = pRemove->pBack;
|
|
else if (pRemove->pBack == this)
|
|
pOtherNode = pRemove->pFront;
|
|
else {
|
|
//AssertFatal(false, "Vislink points to wrong nodes!");
|
|
pOtherNode = NULL;
|
|
}
|
|
|
|
if (pOtherNode)
|
|
{
|
|
bool found = false;
|
|
for (U32 i = 0; i < pOtherNode->visLinks.size(); i++) {
|
|
if (pOtherNode->visLinks[i] == pRemove) {
|
|
found = true;
|
|
pOtherNode->visLinks.erase(i);
|
|
break;
|
|
}
|
|
}
|
|
AssertFatal(found == true, "Error, visLink not on other node?");
|
|
}
|
|
|
|
gWorkingGeometry->mVisLinkArena.releaseLink(pRemove);
|
|
}
|
|
}
|
|
|
|
|
|
////------------------------------------------------------------------------------
|
|
CSGBrush* EditBSPNode::findSolidBrush()
|
|
{
|
|
if (solidBrush != NULL)
|
|
return solidBrush;
|
|
|
|
if (pParent != NULL)
|
|
return pParent->findSolidBrush();
|
|
else
|
|
return NULL;
|
|
}
|
|
|
|
void EditBSPNode::breakWindingS(const Vector<Winding>& windings,
|
|
U32 windingPlaneIndex,
|
|
const CSGBrush* sourceBrush,
|
|
Vector<Winding>& outputWindings)
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
if (isSolid) {
|
|
CSGBrush* definingSolid = findSolidBrush();
|
|
AssertFatal(definingSolid != NULL, "Error, solid leaves must have a solid brush!");
|
|
|
|
// Toss if we're in someone else's zone...
|
|
if (sourceBrush->brushId != definingSolid->brushId)
|
|
return;
|
|
}
|
|
|
|
// Otherwise, we keep these windings...
|
|
for (U32 i = 0; i < windings.size(); i++) {
|
|
outputWindings.push_back(windings[i]);
|
|
|
|
if (isSolid == false) {
|
|
outputWindings.last().insertZone(zoneId);
|
|
} else {
|
|
bool found = false;
|
|
for (U32 i = 0; i < outputWindings.last().numNodes; i++) {
|
|
if (outputWindings.last().solidNodes[i] == nodeId) {
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
if (found == false) {
|
|
AssertFatal(outputWindings.last().numNodes < MaxWindingNodes, "Error, too many solid nodes affecting poly. Plase ask DMoore to increase the allowed number!");
|
|
outputWindings.last().solidNodes[outputWindings.last().numNodes++] = nodeId;
|
|
}
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
if (planeType == Detail && sourceBrush->mBrushType == StructuralBrush) {
|
|
// Break no further, keep these windings.
|
|
// DMM: What to do about nodeIds?
|
|
// AssertFatal(isSolid == false, "error, shouldn't be in solid here");
|
|
|
|
for (U32 i = 0; i < windings.size(); i++) {
|
|
outputWindings.push_back(windings[i]);
|
|
outputWindings.last().insertZone(zoneId);
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
if (gWorkingGeometry->isCoplanar(planeEQIndex, windingPlaneIndex)) {
|
|
AssertISV(planeType != Portal, "Geometry coplanar with a portal plane. This is bad. Talk to DMoore");
|
|
Vector<Winding> toFront(128);
|
|
pFront->breakWindingS(windings, windingPlaneIndex, sourceBrush, toFront);
|
|
pBack->breakWindingS(toFront, windingPlaneIndex, sourceBrush, outputWindings);
|
|
}
|
|
else {
|
|
Vector<Winding> frontCopy = windings;
|
|
Vector<Winding> backCopy = windings;
|
|
|
|
for (S32 i = S32(windings.size()) - 1; i >= 0; i--) {
|
|
clipWindingToPlaneFront(&frontCopy[i], planeEQIndex);
|
|
clipWindingToPlaneFront(&backCopy[i], gWorkingGeometry->getPlaneInverse(planeEQIndex));
|
|
|
|
if (frontCopy[i].numIndices == 0)
|
|
frontCopy.erase(i);
|
|
if (backCopy[i].numIndices == 0)
|
|
backCopy.erase(i);
|
|
}
|
|
|
|
Vector<Winding> childWindings(128);
|
|
if (frontCopy.size() != 0)
|
|
pFront->breakWindingS(frontCopy, windingPlaneIndex, sourceBrush, childWindings);
|
|
|
|
if (backCopy.size() != 0)
|
|
pBack->breakWindingS(backCopy, windingPlaneIndex, sourceBrush, childWindings);
|
|
|
|
for (U32 i = 0; i < childWindings.size(); i++) {
|
|
outputWindings.push_back(childWindings[i]);
|
|
}
|
|
}
|
|
|
|
// Here, we try to stitch these back together, and fix any colinearities...
|
|
//
|
|
bool collapsed = true;
|
|
while (collapsed == true) {
|
|
collapsed = false;
|
|
for (U32 i = 0; i < outputWindings.size() && !collapsed; i++) {
|
|
for (U32 j = i + 1; j < outputWindings.size() && !collapsed; j++) {
|
|
if (collapseWindings(outputWindings[i], outputWindings[j]) == true) {
|
|
collapsed = true;
|
|
outputWindings.erase(j);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void EditBSPNode::breakWinding(const Vector<Winding>& windings,
|
|
U32 windingPlaneIndex,
|
|
const CSGBrush* sourceBrush,
|
|
Vector<Winding>& outputWindings)
|
|
{
|
|
breakWindingS(windings, windingPlaneIndex, sourceBrush, outputWindings);
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::gatherBSPStats(U32* pNumLeaves,
|
|
U32* pTotalLeafDepth,
|
|
U32* pMaxLeafDepth,
|
|
U32 depth)
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
(*pNumLeaves)++;
|
|
(*pTotalLeafDepth) += depth;
|
|
if (depth > *pMaxLeafDepth)
|
|
*pMaxLeafDepth = depth;
|
|
|
|
return;
|
|
}
|
|
|
|
pFront->gatherBSPStats(pNumLeaves, pTotalLeafDepth, pMaxLeafDepth, depth + 1);
|
|
pBack->gatherBSPStats(pNumLeaves, pTotalLeafDepth, pMaxLeafDepth, depth + 1);
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void EditBSPNode::gatherVISStats(U32* pEmptyLeaves,
|
|
U32* pTotalLinks,
|
|
U32* pMaxLinks)
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
if (isSolid) {
|
|
AssertFatal(portals.size() == 0 && visLinks.size() == 0,
|
|
"EditBSPNode::gatherVISStats: error, must not have any portals or vislinks in a solid leaf!");
|
|
return;
|
|
}
|
|
|
|
(*pEmptyLeaves)++;
|
|
(*pTotalLinks) += visLinks.size();
|
|
|
|
if (visLinks.size() > *pMaxLinks)
|
|
*pMaxLinks = visLinks.size();
|
|
|
|
return;
|
|
}
|
|
|
|
pFront->gatherVISStats(pEmptyLeaves, pTotalLinks, pMaxLinks);
|
|
pBack->gatherVISStats(pEmptyLeaves, pTotalLinks, pMaxLinks);
|
|
}
|
|
|
|
void EditBSPNode::removeVISInfo()
|
|
{
|
|
if (planeEQIndex == -1) {
|
|
if (isSolid) {
|
|
AssertFatal(portals.size() == 0 && visLinks.size() == 0,
|
|
"EditBSPNode::gatherVISStats: error, must not have any portals or vislinks in a solid leaf!");
|
|
return;
|
|
}
|
|
|
|
visLinks.clear();
|
|
visLinks.compact();
|
|
return;
|
|
}
|
|
|
|
pFront->removeVISInfo();
|
|
pBack->removeVISInfo();
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
//-------------------------------------- VisLink stuff
|
|
//
|
|
bool EditBSPNode::VisLink::intersect(U32 in_planeEQIndex)
|
|
{
|
|
bool anyFront = false;
|
|
bool anyBack = false;
|
|
|
|
const PlaneEQ& rPlane = gWorkingGeometry->getPlaneEQ(in_planeEQIndex);
|
|
|
|
for (U32 i = 0; i < winding.numIndices; i++) {
|
|
switch (rPlane.whichSideLow(gWorkingGeometry->getPoint(winding.indices[i]))) {
|
|
case PlaneFront:
|
|
anyFront = true;
|
|
break;
|
|
case PlaneBack:
|
|
anyBack = true;
|
|
break;
|
|
|
|
case PlaneOn:
|
|
break;
|
|
|
|
default:
|
|
AssertFatal(false, "Error, misunderstood plane code");
|
|
break;
|
|
}
|
|
}
|
|
|
|
return (anyFront == true && anyBack == true);
|
|
}
|
|
|
|
PlaneSide EditBSPNode::VisLink::whichSide(U32 in_planeEQIndex)
|
|
{
|
|
bool anyFront = false;
|
|
bool anyBack = false;
|
|
|
|
const PlaneEQ& rPlane = gWorkingGeometry->getPlaneEQ(in_planeEQIndex);
|
|
|
|
for (U32 i = 0; i < winding.numIndices; i++) {
|
|
switch (rPlane.whichSideLow(gWorkingGeometry->getPoint(winding.indices[i]))) {
|
|
case PlaneFront:
|
|
anyFront = true;
|
|
break;
|
|
case PlaneBack:
|
|
anyBack = true;
|
|
break;
|
|
|
|
case PlaneOn:
|
|
break;
|
|
|
|
default:
|
|
AssertFatal(false, "Error, misunderstood plane code");
|
|
break;
|
|
}
|
|
}
|
|
|
|
AssertFatal(anyFront == false || anyBack == false, "error, should only be called for non-intersecting visLinks...");
|
|
if (anyFront == true)
|
|
return PlaneFront;
|
|
else if (anyBack == true)
|
|
return PlaneBack;
|
|
else
|
|
return PlaneOn;
|
|
}
|
|
|
|
|
|
EditBSPNode::PortalEntry::~PortalEntry()
|
|
{
|
|
for (U32 i = 0; i < windings.size(); i++) {
|
|
delete windings[i];
|
|
windings[i] = NULL;
|
|
}
|
|
}
|
|
|
|
void EditBSPNode::PortalEntry::copyEntry(const PortalEntry& rPortal)
|
|
{
|
|
AssertFatal(windings.size() == 0, "Error, must have zero windings here");
|
|
|
|
for (U32 i = 0; i < rPortal.windings.size(); i++) {
|
|
windings.push_back(new Winding);
|
|
*(windings.last()) = *(rPortal.windings[i]);
|
|
}
|
|
|
|
planeEQIndex = rPortal.planeEQIndex;
|
|
portalId = rPortal.portalId;
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
//-------------------------------------- ARENA FUNCTIONS
|
|
NodeArena::NodeArena(U32 _arenaSize)
|
|
{
|
|
AssertFatal(_arenaSize > 0, "Error, impossible size");
|
|
arenaSize = _arenaSize;
|
|
|
|
currBuffer = new EditBSPNode[arenaSize];
|
|
currPosition = 0;
|
|
mBuffers.push_back(currBuffer);
|
|
}
|
|
|
|
NodeArena::~NodeArena()
|
|
{
|
|
arenaSize = 0;
|
|
currBuffer = NULL;
|
|
currPosition = 0;
|
|
|
|
for (U32 i = 0; i < mBuffers.size(); i++) {
|
|
delete [] mBuffers[i];
|
|
mBuffers[i] = NULL;
|
|
}
|
|
}
|
|
|
|
VisLinkArena::VisLinkArena(U32 _arenaSize)
|
|
{
|
|
arenaSize = _arenaSize;
|
|
pCurrent = new EditBSPNode::VisLink[arenaSize];
|
|
for (U32 i = 0; i < arenaSize - 1; i++)
|
|
pCurrent[i].pNext = &pCurrent[i+1];
|
|
pCurrent[arenaSize - 1].pNext = NULL;
|
|
|
|
mBuffers.push_back(pCurrent);
|
|
}
|
|
|
|
VisLinkArena::~VisLinkArena()
|
|
{
|
|
clearAll();
|
|
}
|
|
|
|
void VisLinkArena::clearAll()
|
|
{
|
|
for (U32 i = 0; i < mBuffers.size(); i++) {
|
|
delete [] mBuffers[i];
|
|
mBuffers[i] = NULL;
|
|
}
|
|
|
|
pCurrent = NULL;
|
|
}
|
|
|
|
EditBSPNode::VisLink* VisLinkArena::allocateLink()
|
|
{
|
|
if (pCurrent == NULL) {
|
|
pCurrent = new EditBSPNode::VisLink[arenaSize];
|
|
for (U32 i = 0; i < arenaSize - 1; i++)
|
|
pCurrent[i].pNext = &pCurrent[i+1];
|
|
pCurrent[arenaSize - 1].pNext = NULL;
|
|
mBuffers.push_back(pCurrent);
|
|
}
|
|
|
|
EditBSPNode::VisLink* pRet = pCurrent;
|
|
pCurrent = pCurrent->pNext;
|
|
|
|
pRet->pNext = NULL;
|
|
pRet->portalId = -1;
|
|
return pRet;
|
|
}
|
|
|
|
void VisLinkArena::releaseLink(EditBSPNode::VisLink* pRelease)
|
|
{
|
|
AssertFatal(pRelease->pNext == NULL, "Huh? Should never happen. Talk to DMoore");
|
|
|
|
pRelease->pNext = pCurrent;
|
|
pCurrent = pRelease;
|
|
}
|