[subheading]Keep them doggies movin'[/subheading]

Here's the goodies
Please forgive the organic nature of the code and do check periodically for an update!
The Leaf class currently consists only of a class def.. this is a work in progress. I may in fact decide to eliminate it after all.

I'm not very proficient at writing code in C++ so please feel free to educate me, I will certainly not be offended !!


#pragma once
#include "stdafx.h"
#include
#include
#include
#include
#include "dxBSPTree.h"

// This method calculates the Surface Normal and Plane-Distance of the given Triangle.
// Inputs:
// TriangleIndex iTriangle = index of unique triangle in the mesh's IndexBuffer
// (which contains a TriangleList of vertex indices).
// Outputs:
// D3DXVECTOR4 vPlane = triangle's plane (as surfacenormal and planeD)
D3DXVECTOR4 dxBSPTree::Calculate_Plane(Triangle* pTriangle)
{
D3DXVECTOR4 out;
D3DXVECTOR3* pout = (D3DXVECTOR3*) &out // trick compiler into using the Vec4 as a Vec3 (ugh)

// Look up the Vertices corresponding to those indices,
// and calculate two Edge vectors originating at Point A
D3DXVECTOR3 vA = (m_pMesh->m_Vertices.at(pTriangle->ivA).Position);
D3DXVECTOR3 vAB = (m_pMesh->m_Vertices.at(pTriangle->ivB).Position) - vA;
D3DXVECTOR3 vAC = (m_pMesh->m_Vertices.at(pTriangle->ivC).Position) - vA;

// Calculate the Cross Product of the two vectors
D3DXVec3Cross(pout, &vAB, &vAC);

// Ensure the resulting Vector is of unit length
D3DXVec3Normalize(pout,pout);

// Calculate PlaneD : Ax + By + Cz + D = 0
out.w = - (D3DXVec3Dot(&vA, pout));



// Return the Plane
return out;
}

// This method generates the BSP Tree from the input list of triangle indices
void dxBSPTree::Generate_Tree()
{
dxPortal* pPortal;

if(m_pRootNode) delete m_pRootNode;

MessageBoxA(0,"Phase One: Generating BSP Tree","OK",MB_OK);

// Prepare the data we'll need during tree construction
std::vector *triangles = new std::vector();
int numtriangles = m_pMesh->GetIndexCount()/3;
for(int i=0; i {
// Grab the three indices for the current input triangle
int ivA = m_pMesh->m_SortedIndices.at(i*3);
int ivB = m_pMesh->m_SortedIndices.at(i*3+1);
int ivC = m_pMesh->m_SortedIndices.at(i*3+2);

// Create a container and fill its indices
Triangle* t = new Triangle(i,ivA,ivB,ivC); // #OriginalTriangle, #PointA, #PointB, #PointC

// Calculate the triangle's plane (as normal + planeD)
t->Plane = Calculate_Plane(t);

// Collect the new triangle object
triangles->push_back(t);

}

// Create Root Node, passing in the list of triangle indices
m_pRootNode = new dxBSPNode(this,NULL,triangles);

// Recurse Root Node - when we return, the entire tree has been created.
m_pRootNode->Generate_Tree();
MessageBoxA(0,"Phase One Complete: BSPTree generated and Portal List populated","Success",MB_OK);
MessageBoxA(0,"Phase Two: Shattering Portals","Here we go again",MB_OK);

vector* OutputList = new vector();

// We now have a list of Portals.
// For each Portal, we need to Split the Portal against every Splitting Plane (other than its own construction plane).
for(vector::iterator i=m_Portals.begin(); i!=m_Portals.end(); i++)
{
pPortal = (*i);
MessageBoxA(0,"NEXT PORTAL BEING SHATTERED",0,0);
// Rather than recurse the tree to access the splitting planes..
// Every Other Splitting Plane is available as 'the planes of all the other portals'
for(vector::iterator j=m_Portals.begin(); j!=m_Portals.end(); j++)
{
if(i==j) continue;


MessageBoxA(0,"NEXT PLANE BEING CONSIDERED",0,0);
// Let pPortal = the current Portal being Shattered
D3DXVECTOR4* pPlane = (*j)->GetPlane();

// We have to split every Polygon in this Portal
// Output polygons from splitting operations will be appended to the same list they were sourced from !!!
// We will make sure we process only the original number of polygons.
while(!pPortal->m_Polygons.empty())
{

dxPolygon* polygon = pPortal->m_Polygons.back();
pPortal->m_Polygons.pop_back();
PointPlaneResult res = pPortal->Split( polygon, pPlane, OutputList );
if(res!=-1)
{
// Polygon was not split - it was either totally in front, behind, or coplanar.
//OutputList->push_back(polygon);
MessageBoxA(0,"failed to split polygon",0,0);

}
else
{
// Polygon was Split... two childs were appended to the list.
MessageBoxA(0,"polygon was split",0,0);
}

}

//LOG("**************** RESULTS OF PORTAL POLYSPLIT **********************")
// Copy output polygons back into portal
while(!OutputList->empty())
{
//LOG("Polygon #"<m_Polygons.size());
dxPolygon* poly = OutputList->back();
//for(int i=0; i<(int)poly->m_Points.size();i++)
//{
// LOG("Point #" << i << " = " << poly->m_Points.x << "," << poly->m_Points.y << "," << poly->m_Points.z);
//}
pPortal->m_Polygons.push_back(poly);
OutputList->pop_back();
}


}
}
delete OutputList;




MessageBoxA(0,"Phase Two Complete: All Portals have been Shattered and resulting fragments are ready to be sent down the tree","ok",MB_OK);
}

// Check if the given plane has already been used as a splitting plane before
bool dxBSPTree::IsPlaneUsed(D3DXVECTOR4* pPlane)
{
for(vector::iterator i = m_Planes.begin(); i!=m_Planes.end(); i++)
{
if((*i)==*pPlane) return true;
}
return false;
}

// Determine which Leaf node contains a given Point
// Returns leafnode, or NULL (point is not in any legal subspace).
// If the point is 'not legal', its inside a solid volume in our world,
// or outside the world itself, ie, somewhere a player should never be.
// This method is an example of 'walking a tree' without recursion.
dxBSPLeafNode* dxBSPTree::Find_Containing_Leaf(D3DXVECTOR3* pvPoint)
{
dxBSPNode* node = m_pRootNode;
while(node && !node->Is_Leaf())
{
switch(dxBSPNode::ClassifyPointPlane(pvPoint,node->Get_Plane()))
{
case COPLANAR:
case FRONT:
node = node->Get_Front_Child();
break;
case BACK:
node = node->Get_Back_Child();
break;
}
}
// We replaced all terminal dxBSPNodes with a dxBSPLeafNode
return (dxBSPLeafNode*) node;
}

void dxBSPTree::FrogMarch_Portal_Polygons(dxBSPNode* pStartNode, dxPortal* portal)
{
while(!portal->m_Polygons.empty())
{
dxPolygon* poly = portal->m_Polygons.back();
portal->m_Polygons.pop_back();
m_pRootNode->Quick_March(poly);
}
}






// Credit to Alan Baylis apon whose code some of this was based

#include "stdafx.h"
#include "dxBSPNode.h"
#include "dxBSPLeafNode.h"
#include "dxPortal.h"


// Classify a Point and a Plane, returning an enumerated result value
PointPlaneResult dxBSPNode::ClassifyPointPlane(D3DXVECTOR3* pPt, D3DXVECTOR4* pPlane)
{
//LOG("ClassifyPoint ("<x<<", "<y<<", "<z<<")" );
float result = D3DXVec3Dot(pPt, (D3DXVECTOR3*) pPlane) + pPlane->w;
if(result< -PLANAR_HALF_EPSILON) {return BACK;}
else if(result > PLANAR_HALF_EPSILON) {return FRONT;}
return COPLANAR;
}

// RECURSIVE BEHAVIOR:
// This method attempts to split an input set of triangles (m_pvTriangles) into two subsets via a 'splitting plane'
// which is itself selected from the planes of the input triangles.
// Then it shoves the two output lists into two child nodes, and recurses them.
// TERMINAL CASE:
// If we fail to split an input set of triangles, the input set is considered to be Convex,
// and the node is considered to be a Leaf node - we will return from Recursion in this case.
void dxBSPNode::Generate_Tree()
{
LOG("============= GENERATING NODE =================== "<

for(int i=0;isize();i++)
{
Triangle* tri = m_pvTriangles->at(i);
D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
LOG("INPUT #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
LOG("INPUT #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
LOG("INPUT #"<x<<","<y<<","<z);
}


// Determine the bounds of the input set of triangles
Calculate_Bounds();

// Find the best partitioning plane for the input set of Triangles
// Set this plane as the current node's partitioning plane
int bestfront=-1, bestback=-1;
int bestplane = Choose_Partitioning_Plane(&bestfront,&bestback);

// If we failed to find a partitioning plane, the input triangles are considered to be a convex set,
// and therefore the current node is considered to be a terminal (ie leaf) node.
// In this case we will replace 'this' node with a more specialized Leaf node, and return from recursion.
if(bestplane == -1)
{
// Replace THIS node with a special 'leaf' node
// MessageBoxA(0,"FOUND CONVEX SET","LEAF",0);
dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,m_pvTriangles);
temp->m_Plane = m_Plane;
if(m_pParent->m_pFrontChild == this)
{
m_pParent->Attach_Front_Child(temp);
} else {
m_pParent->Attach_Back_Child(temp);
}
m_pvTriangles = 0; // preserve
delete this; // trash myself
return; // get outta here
}

// Set this node's partitioning plane
m_Plane = m_pvTriangles->at(bestplane)->Plane;
LOG("SELECTED PLANE: ("<
// Attempt to Partition input triangles into two child sets:
// Even though we found a 'best' splitting plane,
// this method can still return all the triangles in just one of the output lists !!
// This is because the heuristic we used only considers the triangle vertices as a point cloud,
// whereas the actual splitting method detects and handles special cases like splits and coplanars.
// We DO need to check what we have been returned and take it like a man.
vector* pFrontTris = new vector();
vector* pBackTris = new vector();
Split_Triangles(pFrontTris, pBackTris);

// If all the triangles landed in only one child list,
// replace this node with a Leaf containing the triangle list
if( pFrontTris->empty() && !pBackTris->empty() )
{
// All the triangles landed in the Back output list.
// Convert into convex subspace, retaining the 'used plane' data
delete pFrontTris;
if(m_pParent)
{
// Replace THIS node with a special 'leaf' node
dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,pBackTris);
temp->m_Plane = m_Plane;
if(m_pParent->m_pFrontChild == this)
{
m_pParent->Attach_Front_Child(temp);
} else {
m_pParent->Attach_Back_Child(temp);
}
delete this; // trash myself
//MessageBoxA(0,"RETURN FROM BACK OUTPUT","LEAF",0);
}
else
{
// Failed to split the root node??
MessageBoxA(0,"Error: Root Node triangles could not be Split A",0,0);
exit(1);
}

} else if ( !pFrontTris->empty() && pBackTris->empty() )
{
// All the triangles landed in the Front output list
// The back of the plane is solid space.
// We'll make a convex subspace out of this situation,
// and retain the 'used portal' data.
delete pBackTris;
if(m_pParent)
{
//MessageBoxA(0,"DISCOVERED FRONT LEAF","LEAF",0);
// Pop the last element back off the used planes list

// Replace THIS node with a special 'leaf' node,
// since the selected plane wasn't actually used.
dxBSPLeafNode* temp = new dxBSPLeafNode(m_pTree,m_pParent->m_pParent,pFrontTris);
temp->m_Plane = m_Plane;

if(m_pParent->m_pFrontChild == this)
{
//MessageBoxA(0,"attached to front","LEAF",0);
m_pParent->Attach_Front_Child(temp);
} else {
//MessageBoxA(0,"attached to back","LEAF",0);
m_pParent->Attach_Back_Child(temp);
}
delete this; // trash myself
//MessageBoxA(0,"RETURN FROM FRONT OUTPUT","LEAF",0);
}
else
{
// Failed to split the root node??
MessageBoxA(0,"Error: Root Node triangles could not be Split B",0,0);
exit(1);
}

} else if( !pFrontTris->empty() && !pBackTris->empty() )
{

LOG("*************** NODE WAS SPLIT ******************");
LOG("PLANE was "< LOG("front received "<size()<<", back received "<size());
for(int i=0;isize();i++)
{
Triangle* tri = pFrontTris->at(i);
D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
LOG("Front #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
LOG("Front #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
LOG("Front #"<x<<","<y<<","<z);
}
for(int i=0;isize();i++)
{
Triangle* tri = pBackTris->at(i);
D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
LOG("Back #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
LOG("Back #"<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
LOG("Back #"<x<<","<y<<","<z);
}

//MessageBoxA(0,"TYPICAL OUTPUT","NON LEAF",0);

// Both output lists contain triangles - this is the usual case.
// Attach and Recurse the list of triangles found to be in front of the plane
Attach_Front_Child(new dxBSPNode(m_pTree,this,pFrontTris));
Attach_Back_Child(new dxBSPNode(m_pTree,this,pBackTris));

delete m_pvTriangles; // trash input list
m_pvTriangles = 0;
m_pFrontChild->Generate_Tree();
m_pBackChild->Generate_Tree();

// Create a new Portal at this node
CreatePortal();

//MessageBoxA(0,"CREATED PORTAL : RETURN FROM NON LEAF NODE","NON LEAF",0);

} else
{
// We should never get here - it means both output lists were returned empty(!)
MessageBoxA(0,"Error: bsp node partitioning returned no triangles !!",0,0);
exit(1);
}
}

// Partition the node's triangles into two output lists
void dxBSPNode::Split_Triangles(vector* pFrontOutput, vector* pBackOutput)
{
int results[3];
dxMeshResource::Vertex Intersections[2];
Triangle* tri;

// We're going to consume this node's input triangles, at the end there should be none remaining
while(!m_pvTriangles->empty())
{
// Number of triangle vertices found behind, before, and on the plane
int front = 0;
int back = 0;
int coplanar = 0;

// Get a pointer to the current Triangle and remove it from the input list
tri = m_pvTriangles->back();
m_pvTriangles->pop_back();


D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
LOG("SPLITTING TRIANGLE: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
LOG("SPLITTING TRIANGLE: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
LOG("SPLITTING TRIANGLE: "<<"C = "<x<<","<y<<","<z);

// classify the triangle against the plane
int result = ClassifyTrianglePlane( tri, &m_Plane);

// tally the results: there are three PointPlaneResult values compressed into 6 bits
for(int i=0; i<3; i++)
{
int r = result & 3;
results=r;

if(r == FRONT)
{
front++;
}

else if(r == BACK)
{
back++;
}

else // COPLANAR
{
coplanar++;
}

// check the next point/plane result
result = result >> 2;
}


// Analyze the results: determine whether this triangle is intersected by the splitting plane.

// If the triangle is fully coplanar with the splitting plane,
// we will decide which half-space it is facing into, and send it to that child list.
if(coplanar==3)
{
// We want the Normals of the splitting plane and the triangle
D3DXVECTOR3* pNorm1 = (D3DXVECTOR3*) &m_Plane; // trick compiler into using the Vec4 as a Vec3 (ugh)
D3DXVECTOR3* pNorm2 = (D3DXVECTOR3*) &tri->Plane;
// Get the dot product of the two Normals (ie those of the triangle and the splitting plane)
float result = D3DXVec3Dot(pNorm1, pNorm2);
// Push the triangle reference down whichever child it faces into ;)
if(result > (1.0f - PLANAR_HALF_EPSILON*2 ))
{
LOG("(Coplanar->FRONT)");
pFrontOutput->push_back( tri );
}
else
{
LOG("(Coplanar->BACK)");
pBackOutput->push_back( tri );
}
}

// Else if the triangle is on the front side (abutting is included)
else if(back == 0 || front!=0 && front+coplanar==3)
{
LOG("(FRONT)");
pFrontOutput->push_back( tri );
}
// Else if the triangle is behind the plane (abutting is included)
else if(front == 0 || back!=0 && back+coplanar==3)
{
LOG("(BACK)");
pBackOutput->push_back( tri );
}

////////////////////////////////////////////////////////////////////////////////////
// Otherwise we must have a 'split' result - the plane cuts through this triangle
// We have a hack of a lot of work to do here
else
{
Triangle* baby;

LOG("SPLITTING: "< if(front==1 && back==2)
{


// One of the three points is on the front side of the plane.
// Our split results will depend on which one that is.
/*
A B C

=I1===I2== ========= =========
\
\
B C C A A B

*/
if(results[0]==FRONT)
{
float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);
if(fLerpFactorAB>0.0f && fLerpFactorAB<1.0f)
{
float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);
if(fLerpFactorCA>0.0f && fLerpFactorCA<1.0f)
{
LOG("Style = OneFrontTwoBack (1)");
Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;
Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;
Intersections[1].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
Intersections[1].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;
Intersections[1].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

// front = A I1 I2
// back1 = I1 B C
// back2 = I1 C I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivA,iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pFrontOutput->push_back(baby);

D3DXVECTOR3* pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, tri->ivC);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

delete tri;

}
else
{
MessageBoxA(0,"Expected CA intersection not found",0,0);
exit(1);
}

}
else
{
MessageBoxA(0,"Expected AB intersection not found",0,0);
exit(1);
}
}

else if(results[1]==FRONT)
{
float fLerpFactorBC = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorBC>0.0f && fLerpFactorBC<1.0f)
{
float fLerpFactorAB = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);
if(fLerpFactorAB>0.0f && fLerpFactorAB<1.0f)
{
LOG("Style = OneFrontTwoBack (2)");
Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;
Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;
Intersections[1].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
Intersections[1].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;
Intersections[1].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

// front = B I1 I2
// back1 = I1 C A
// back2 = I1 A I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, tri->ivA);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

delete tri;

}
else
{
MessageBoxA(0,"Expected AB intersection not found",0,0);
LOG("fLerpFactorAB ="< exit(1);
}

}
else
{
LOG("fLerpFactorBC =" << fLerpFactorBC);
MessageBoxA(0,"Expected BC intersection not found",0,0);
exit(1);
}
}
else
{
float fLerpFactorCA = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);
if(fLerpFactorCA>0.0f && fLerpFactorCA<1.0f)
{
float fLerpFactorBC = IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorBC>0.0f && fLerpFactorBC<1.0f)
{
LOG("Style = OneFrontTwoBack (3)");
Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;
Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;
Intersections[1].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
Intersections[1].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;
Intersections[1].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

// front = C I1 I2
// back1 = I1 A B
// back2 = I1 B I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, tri->ivB);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

delete tri;
}
else
{
MessageBoxA(0,"Expected BC intersection not found",0,0);
LOG("fLerpFactorBC ="< exit(1);
}

}
else
{
LOG("fLerpFactorCA =" << fLerpFactorCA);
MessageBoxA(0,"Expected CA intersection not found",0,0);
exit(1);
}

}
}

else if(front==2 && back==1)
{
// One of the three points is at the Back.
// Our split results will depend on which one.
/*
C B A C B A

=I2====I1== ========= =========

A B C
*/
if(results[0]==BACK)
{
float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);
if(fLerpFactorAB>0.0f && fLerpFactorAB<1.0f)
{
float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);
if(fLerpFactorCA>0.0f && fLerpFactorCA<1.0f)
{
LOG("Style = TwoFrontOneBack (1)");
Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;
Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;
Intersections[1].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
Intersections[1].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;
Intersections[1].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

// back = A I1 I2
// front1 = I1 B C
// front2 = I1 C I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivA, iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, tri->ivC);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, iIntersection2) ;
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

delete tri;
}
else
{
MessageBoxA(0,"Expected CA intersection not found",0,0);
exit(1);
}
}
else
{
MessageBoxA(0,"Expected AB intersection not found",0,0);
exit(1);
}
}

else if(results[1]==BACK)
{
float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorBC>0.0f && fLerpFactorBC<1.0f)
{
float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_Plane);
if(fLerpFactorAB>0.0f && fLerpFactorAB<1.0f)
{
LOG("Style = TwoFrontOneBack (2)");
Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;
Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;
Intersections[1].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
Intersections[1].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;
Intersections[1].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

// back = B I1 I2
// front1 = I1 C A
// front2 = I1 A I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivC, tri->ivA);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, iIntersection2);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

delete tri;
}
else
{
MessageBoxA(0,"Expected AB intersection not found",0,0);
exit(1);
}
}
else
{
MessageBoxA(0,"Expected BC intersection not found",0,0);
exit(1);
}


}
else
{
float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position,&m_Plane);
if(fLerpFactorCA>0.0f && fLerpFactorCA<1.0f)
{
float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorBC>0.0f && fLerpFactorBC<1.0f)
{

LOG("Style = TwoFrontOneBack (3)");
Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;
Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;
Intersections[1].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
Intersections[1].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;
Intersections[1].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;


// back = C I1 I2
// front1 = I1 A B
// front2 = I1 B I2
int iIntersection1 = m_pTree->m_pMesh->m_Vertices.size();
int iIntersection2 = iIntersection1+1;
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[1]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, iIntersection2);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("BACK FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("BACK FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("BACK FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivA, tri->ivB);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);

baby = new Triangle(tri->iOriginalIndex, iIntersection1, tri->ivB, iIntersection2) ;
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby);

pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivA).Position;
LOG("FRONT FRAGMENT: "<<"A = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivB).Position;
LOG("FRONT FRAGMENT: "<<"B = "<x<<","<y<<","<z);
pV = &m_pTree->m_pMesh->m_Vertices.at(baby->ivC).Position;
LOG("FRONT FRAGMENT: "<<"C = "<x<<","<y<<","<z);


delete tri;
}
else
{
MessageBoxA(0,"Expected BC intersection not found",0,0);
exit(1);
}
}
else
{
MessageBoxA(0,"Expected CA intersection not found",0,0);
exit(1);
}

}
}


else if(front==1 && back==1)
{

MessageBoxA(0,"SplitTheGuts",0,0);
// We have points that are coplanar, front and back.
// Our split result will depend on the configuration.
/*
A B C
| | |
| | |
| | |
B I C C I A A I B
*/
if(results[0]==COPLANAR)
{
// Calculate the Parametric Solution for the intersection point "u" (thanks Paul Bourke)
float fLerpFactorBC = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
// If "u" is between 0 and 1 then the intersection is legal (occurs between the endpoints of the line segment, our edge BC)
if(fLerpFactorBC>0.0f && fLerpFactorBC<1.0f)
{
MessageBoxA(0,"SplitTheGuts 1",0,0);
// Calculate the point where the plane intersects with edge BC (just interpolate using "u")
Intersections[0].Position = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
// I'm going to go ahead and interpolate for all components of my vertex format
Intersections[0].Normal = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal;
Intersections[0].UV = fLerpFactorBC * (m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV;

// Note the index of the new vertex at intersection point
int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();
// Add the new vertex
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

// Construct two output triangles according to the following template:
// FRONT = ABI
// BACK = AIC
baby = new Triangle(tri->iOriginalIndex, tri->ivA, tri->ivB, iIntersection1);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivA, iIntersection1, tri->ivC);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

}
else
{
MessageBoxA(0,"Expected BC intersection not found",0,0);
exit(1);
}

}
else if(results[1]==COPLANAR)
{
float fLerpFactorCA = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorCA>0.0f && fLerpFactorCA<1.0f)
{
MessageBoxA(0,"SplitTheGuts 2",0,0);

Intersections[0].Position = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
Intersections[0].Normal = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal;
Intersections[0].UV = fLerpFactorCA * (m_pTree->m_pMesh->m_Vertices.at(tri->ivC).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV;

int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

// FRONT = BCI
// BACK = BIA
baby = new Triangle(tri->iOriginalIndex, tri->ivB, tri->ivC, iIntersection1);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivB, iIntersection1, tri->ivA);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );

}
else
{
MessageBoxA(0,"Expected CA intersection not found",0,0);
exit(1);
}
}
else if(results[2]==COPLANAR)
{

MessageBoxA(0,"SplitTheGuts 3",0,0);
float fLerpFactorAB = this->IntersectLinePlane(&m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position,&m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position,&m_Plane);
if(fLerpFactorAB>0.0f && fLerpFactorAB<1.0f)
{
Intersections[0].Position = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
Intersections[0].Normal = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Normal - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Normal;
Intersections[0].UV = fLerpFactorAB * (m_pTree->m_pMesh->m_Vertices.at(tri->ivA).UV - m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV) + m_pTree->m_pMesh->m_Vertices.at(tri->ivB).UV;

int iIntersection1=m_pTree->m_pMesh->m_Vertices.size();
m_pTree->m_pMesh->m_Vertices.push_back(Intersections[0]);

baby = new Triangle(tri->iOriginalIndex, tri->ivC, tri->ivA, iIntersection1);
baby->Plane = tri->Plane;
pFrontOutput->push_back( baby );

baby = new Triangle(tri->iOriginalIndex, tri->ivC, iIntersection1, tri->ivB);
baby->Plane = tri->Plane;
pBackOutput->push_back( baby );
}
else
{
MessageBoxA(0,"Expected AB intersection not found",0,0);
exit(1);
}
}
else
{
MessageBoxA(0,"ouch",0,0);
exit(1);
}
}

}

}
// }

LOG("RETURNING FROM SPLITTER");
}

// Select a partitioning plane from the planes of all the input triangles
int dxBSPNode::Choose_Partitioning_Plane(int* bestfront, int* bestback)
{
int count = 0, absdifference = 1000000000, bestplane = -1, front, back, potentialplane, polytoclassify;
D3DXVECTOR3 temp;
int result;
int tricount = (int)m_pvTriangles->size();
LOG("CHOOSING PARTITIONING PLANE from " << tricount << " candidates");

// For splitting plane triangle = every Triangle in the input set
for(potentialplane = 0; potentialplane < tricount; potentialplane++)
{
Triangle* PLANETRI = m_pvTriangles->at(potentialplane);

// Look up the Plane of that triangle
D3DXVECTOR4* pPlane = &PLANETRI->Plane;
// Don't use planes that were already used
if(m_pTree->IsPlaneUsed(&PLANETRI->Plane)) continue;

// LOG("Test Plane #"<< potentialplane << "is (" <x<<", "<y<<", "<z<<", "<w<<")");

// Clear evaluation counters for the current triangle
front = back = 0;
// For subject triangle = every (other) triangle in the input set
for (polytoclassify = 0; polytoclassify < tricount; polytoclassify++)
{
// Get the true, original index of the subject triangle
Triangle* TESTTRI = m_pvTriangles->at(polytoclassify);

//Don't compare against same plane
if(polytoclassify!=potentialplane)
{

// classify the triangle against the plane
// This returns three enumerated results, squished into 6 bits of an integer
result = ClassifyTrianglePlane( TESTTRI, pPlane);

// tally the results
for(int i=0; i<3; i++)
{
int r = result & 3;
if(r == FRONT)
{
front++;
}
else if(r == BACK)
{
back++;
}
else if(r==COPLANAR) // COPLANAR
{
front++;
back++;
} else {
MessageBoxA(0,"UNEXPECTED RESULT from ClassifyTrianglePlane",0,0);
exit(1);
}

// check the next point/plane result
result = result >> 2;
}
}

}

// track the lowest absolute difference
if (abs(front - back) < absdifference)
{
absdifference = abs(front - back);
bestplane = potentialplane;
*bestfront = front;
*bestback = back;
}

// track the number of times we found a triangle totally on one side
if (front == 0 || back == 0) count++;

}

// If we failed to find any plane which partitions the triangles
if (count == tricount)
return -1;
// Otherwise, return the (index of the) best one we found
else
{
// If we chose a plane, collect it so we dont use it in future
if(bestplane!=-1) m_pTree->m_Planes.push_back(m_pvTriangles->at(bestplane)->Plane);
return bestplane;
}
}

// Classify a triangle and plane: return three enumerated results, packed into 6 bits
int dxBSPNode::ClassifyTrianglePlane(Triangle* pTriangle, D3DXVECTOR4* pPlane)
{
// Classify each of the three triangle vertices against the plane
PointPlaneResult resA = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivA).Position, pPlane);
PointPlaneResult resB = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivB).Position, pPlane);
PointPlaneResult resC = ClassifyPointPlane(&m_pTree->m_pMesh->m_Vertices.at(pTriangle->ivC).Position, pPlane);

// Return a compound result
// Each point result returns 0,1 or 2.. so takes a maximum of two bits.
// Therefore we can jam all three results into just six bits.
return ((int) resC << 4) | ((int)resB << 2) | ((int)resA);
}

// Calculate the axially aligned bounding box of the input set of triangles for this node.
void dxBSPNode::Calculate_Bounds()
{
D3DXVECTOR3* pVec;

// Initialize the bounds to the origin
m_Bounds.vMax = m_Bounds.vMin = D3DXVECTOR3(0,0,0);

// Find the axial maxima and minima of all the input triangle vertices
for(int i=0; i<(int)m_pvTriangles->size(); i++)
{
Triangle* tri = m_pvTriangles->at(i);
// Examine the axial components of the vertex's position,
// and expand our box bounds to enclose the vertex.
pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivA).Position;
if (pVec->x < m_Bounds.vMin.x) m_Bounds.vMin.x = pVec->x;
else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;
if (pVec->y < m_Bounds.vMin.y) m_Bounds.vMin.y = pVec->y;
else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;
if (pVec->z < m_Bounds.vMin.z) m_Bounds.vMin.z = pVec->z;
else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivB).Position;
if (pVec->x < m_Bounds.vMin.x) m_Bounds.vMin.x = pVec->x;
else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;
if (pVec->y < m_Bounds.vMin.y) m_Bounds.vMin.y = pVec->y;
else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;
if (pVec->z < m_Bounds.vMin.z) m_Bounds.vMin.z = pVec->z;
else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

pVec = &m_pTree->m_pMesh->m_Vertices.at(tri->ivC).Position;
if (pVec->x < m_Bounds.vMin.x) m_Bounds.vMin.x = pVec->x;
else if (pVec->x > m_Bounds.vMax.x) m_Bounds.vMax.x = pVec->x;
if (pVec->y < m_Bounds.vMin.y) m_Bounds.vMin.y = pVec->y;
else if (pVec->y > m_Bounds.vMax.y) m_Bounds.vMax.y = pVec->y;
if (pVec->z < m_Bounds.vMin.z) m_Bounds.vMin.z = pVec->z;
else if (pVec->z > m_Bounds.vMax.z) m_Bounds.vMax.z = pVec->z;

}
}

// Construct a big fat Quad apon this node's splitting plane
// This is the initial shape of each Portal geometry.
// We don't take too much care about whether the winding order is right since we'll never draw it.
void dxBSPNode::CreatePortal()
{
//LOG("CREATING NEW PORTAL plane = "< // create a new portal object
dxPortal* pOut = new dxPortal();

// find the primary axis plane
D3DXVECTOR3 vA, vB, vC, vD;
if (fabs(m_Plane.x) > fabs(m_Plane.y) && fabs(m_Plane.x) > fabs(m_Plane.z))
{
// LOG("Chose Major X");
vA.y = m_Bounds.vMin.y;
vA.z = m_Bounds.vMax.z;
vB.y = m_Bounds.vMin.y;
vB.z = m_Bounds.vMin.z;
vC.y = m_Bounds.vMax.y;
vC.z = m_Bounds.vMin.z;
vD.y = m_Bounds.vMax.y;
vD.z = m_Bounds.vMax.z;

vA.x = - ( m_Plane.y * m_Bounds.vMin.y + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.x;
vB.x = - ( m_Plane.y * m_Bounds.vMin.y + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.x;
vC.x = - ( m_Plane.y * m_Bounds.vMax.y + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.x;
vD.x = - ( m_Plane.y * m_Bounds.vMax.y + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.x;

}
else if (fabs(m_Plane.y) > fabs(m_Plane.x) && fabs(m_Plane.y) > fabs(m_Plane.z))
{
// LOG("Chose Major Y");
vA.x = m_Bounds.vMin.x;
vA.z = m_Bounds.vMax.z;
vB.x = m_Bounds.vMax.x;
vB.z = m_Bounds.vMax.z;
vC.x = m_Bounds.vMax.x;
vC.z = m_Bounds.vMin.z;
vD.x = m_Bounds.vMin.x;
vD.z = m_Bounds.vMin.z;

vA.y = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.y;
vB.y = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.z * m_Bounds.vMax.z + m_Plane.w ) / m_Plane.y;
vC.y = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.y;
vD.y = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.z * m_Bounds.vMin.z + m_Plane.w ) / m_Plane.y;
}
else
{
// LOG("Chose Major Z");
vA.x = m_Bounds.vMin.x;
vA.y = m_Bounds.vMin.y;
vB.x = m_Bounds.vMax.x;
vB.y = m_Bounds.vMin.y;
vC.x = m_Bounds.vMax.x;
vC.y = m_Bounds.vMax.y;
vD.x = m_Bounds.vMin.x;
vD.y = m_Bounds.vMax.y;

vA.z = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.y * m_Bounds.vMin.y + m_Plane.w ) / m_Plane.z;
vB.z = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.y * m_Bounds.vMin.y + m_Plane.w ) / m_Plane.z;
vC.z = - ( m_Plane.x * m_Bounds.vMax.x + m_Plane.y * m_Bounds.vMax.y + m_Plane.w ) / m_Plane.z;
vD.z = - ( m_Plane.x * m_Bounds.vMin.x + m_Plane.y * m_Bounds.vMax.y + m_Plane.w ) / m_Plane.z;

}

// Construct our big fat quad
dxPolygon* pPolygon = new dxPolygon(pOut);
pPolygon->m_Points.push_back(vA);
pPolygon->m_Points.push_back(vB);
pPolygon->m_Points.push_back(vC);
pPolygon->m_Points.push_back(vD);

// Add the new polygon to the portal
pOut->m_Polygons.push_back(pPolygon);

// Set Plane for the portal and its geometry
pOut->SetPlane(m_Plane);

// Add the portal to the tree container
m_pTree->m_Portals.push_back(pOut);

// for(int i=0; i<(int)pPolygon->m_Points.size();i++)
// {
// LOG("Point #" << i << " = " << pPolygon->m_Points.x << "," << pPolygon->m_Points.y << "," << pPolygon->m_Points.z);
// }

}

// This method attempts to find the intersection of a Line Segment and a Plane.
// Return value is interpolation factor, or 'normalized distance to plane' (0 to 1 if there is intersection).
// Formula courtesy of Paul Bourke, Canberra
// numerator = A x1 + B y1 + C z1 + D
// denominator= A (x1-x2) + B(y1-y2) + C(z1-z2)
float dxBSPNode::IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2,D3DXVECTOR4* pPlane)
{
D3DXVECTOR3* pPlaneNormal = (D3DXVECTOR3*) pPlane;
float numerator = D3DXVec3Dot(pPoint1,(D3DXVECTOR3*) pPlaneNormal) + pPlane->w;
float denominator = pPlane->x*(pPoint1->x-pPoint2->x)+pPlane->y*(pPoint1->y-pPoint2->y)+pPlane->z*(pPoint1->z-pPoint2->z);
// Ifthe denominator is 0 then the normal to the plane is perpendicular to the line.
// Thus the line is either parallel to the plane and there are no solutions or the line is on the plane in which case are infinite solutions.
if(denominator!=0) return numerator / denominator;

// Return value is meant to be a scalar, ie, always positive.
// Any negative value would indicate failure ;)
return -1.0f;

// if it is necessary to determine the intersection of the line segment between P1 and P2 then just check that u is between 0 and 1.
}


// Accessor methods
D3DXVECTOR4* dxBSPNode::Get_Plane()
{
return &m_Plane;
}

dxBSPNode* dxBSPNode::Get_Front_Child()
{
return m_pFrontChild;
}

dxBSPNode* dxBSPNode::Get_Back_Child()
{
return m_pBackChild;
}


// This method will shove the given polygon down the tree and into a leaf node.
// If we find it is coplanar with any splitting plane along the way,
// we will Clone the polygon, flipping its normal, and shove the two polygons
// into their respective child subtrees.
// Remarks:
// This method is handling POLYGONS - pieces of portals - NOT TRIANGLES !!!
void dxBSPNode::Quick_March(dxPolygon* poly)
{
if (Is_Leaf())
{
// I know, I know, downcasting from a baseclass to a derived class is a bad idea.
// However this won't be a problem for the implementation at hand.
dxBSPLeafNode* pthis = static_cast(this);
// The leaf node will collect this polgon
pthis->m_PortalFragments.push_back(poly);
}
else
{
dxBSPNode* front = Get_Front_Child();
dxBSPNode* back = Get_Back_Child();

// Classify points until we get a definitive result
for(int i=0; im_Points.size(); i++)
{
D3DXVECTOR3* pPoint = &poly->m_Points;

switch(ClassifyPointPlane(pPoint,&m_Plane))
{
case COPLANAR:
// Result not definitive - try next point
break;

case FRONT:
front->Quick_March(poly);
return;

case BACK:
back->Quick_March(poly);
return;
}
}


// Special case - all points were coplanar:
// Clone all Fragments of this Portal
dxPolygon* clone = new dxPolygon(poly->m_pPortal);

*clone = *poly; // copy all data
// Flip surface normal of clone's plane
clone->m_Plane.x = -clone->m_Plane.x;
clone->m_Plane.y = -clone->m_Plane.y;
clone->m_Plane.z = -clone->m_Plane.z;

// Send clone polygon to the back child
back->Quick_March(clone);

// Send this portal fragments to front child
front->Quick_March(poly);
}

}







#include "stdafx.h"
#include "dxBSPNode.h"

// Constructor for polygons will set 'construction portal' and 'construction plane' data.
dxPolygon::dxPolygon(dxPortal* pOwner):m_pPortal(pOwner), m_Plane(*m_pPortal->GetPlane()) { }

// This method will attempt to partition a portal's geometry with a splitting plane from a non-leaf bsp tree node.
// We do not attempt to preserve the WINDING ORDER of portal polygons, since they are not renderable geometry.
// This may be a problem, depending on your implementation.
// It is a known property of all convex polygons that bisecting them produces two convex childs.
// Since a portal begins life as a convex polygon, bisection will always result in convex polygons.
// Inputs:
// dxPolygon* SplitMe = polygon (member of this portal) being considered for splitting
// D3DXVECTOR4* pPlane = Splitting Plane
// Outputs:
// FRONT / BACK = The polygon could not be Split
// COPLANAR = The polygon was duplicated
// -1 = The polygon was split
PointPlaneResult dxPortal::Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane, vector* Outputs)//, PORTAL* front, PORTAL* back)
{
int numVerts = SplitMe->m_Points.size();
int count = 0;
PointPlaneResult sideA, sideB, side;
D3DXVECTOR3 polysNormal, edge1, edge2, temp;
//VERTEX ptA, ptB, intersection, outpts[MaxVerts], inpts[MaxVerts];
D3DXVECTOR3 intersection;

/*
LOG("*** ATTEMPT TO SPLIT PORTAL POLYGON:");
for(int i=0; i<(int)SplitMe->m_Points.size();i++)
{
LOG("Point #" << i << " = " << SplitMe->m_Points.x << "," << SplitMe->m_Points.y << "," << SplitMe->m_Points.z);
}
LOG("Plane = " << pPlane->x <<"," << pPlane->y <<"," << pPlane->z << "," << pPlane->w);
*/

////////////////////////////////////////////////////////////////////////////////
// Check whether the plane actually cuts through the portal geometry
////////////////////////////////////////////////////////////////////////////////
// Set up some quicky Vec3 pointers for dx api calls
D3DXVECTOR3* pSplitPlaneNormal = (D3DXVECTOR3*) pPlane;
D3DXVECTOR3* pThisPortalNormal = (D3DXVECTOR3*) &m_Plane;

// Classify the polgyon against the splitting plane
int frontcount = 0, backcount = 0, coplanarcount=0;
for (int loop = 0; loop < numVerts; loop++)
{
D3DXVECTOR3* pPoint = &SplitMe->m_Points[loop];
if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == COPLANAR)
coplanarcount++;
else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == FRONT)
frontcount++;
else if (dxBSPNode::ClassifyPointPlane(pPoint, pPlane) == BACK)
backcount++;
}

// Determine if the polygon is intersected by the plane

if (coplanarcount == numVerts)
{
// Polygon is totally coplanar - no intersection (caller can deal with it)
Outputs->push_back(SplitMe);
return COPLANAR;
}
if (frontcount+coplanarcount == numVerts)
{
// Polygon is on the front side of the plane - no intersection
Outputs->push_back(SplitMe);
return FRONT;
}
else if (backcount+coplanarcount == numVerts)
{
// Polygon is on the back side of the plane - no intersection
Outputs->push_back(SplitMe);
return BACK;
}
//LOG("frontcount="<;
sideB = dxBSPNode::ClassifyPointPlane(pPtB, pPlane);

float uIntersect;
switch(sideA)
{
case FRONT:
switch(sideB)
{
case FRONT:
//LOG("next front");
frontside->m_Points.push_back(SplitMe->m_Points);
break;

case BACK:
//LOG("front to back");
// find intersection
uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);
if(uIntersect<=0 || uIntersect>=1.0f)
{
MessageBoxA(0,0,0,0);
exit(1);
}
intersection = ((*pPtA-*pPtB) * uIntersect)+(*pPtB);
//LOG("Intersection = "< frontside->m_Points.push_back(intersection);
backside->m_Points.push_back(intersection);
backside->m_Points.push_back(SplitMe->m_Points);
side=BACK;
break;

case COPLANAR:
//LOG("front to coplanar");
frontside->m_Points.push_back(SplitMe->m_Points);
break;
}
break;

case BACK:
switch(sideB)
{
case FRONT:
//LOG("back to front");
// find intersection
uIntersect = IntersectLinePlane(pPtA,pPtB,pPlane);
if(uIntersect<=0 || uIntersect>=1.0f)
{
MessageBoxA(0,0,0,0);
exit(1);
}
intersection = ((*pPtA-*pPtB) * uIntersect)+(*pPtB);
//LOG("Intersection = "<
backside->m_Points.push_back(intersection);
frontside->m_Points.push_back(intersection);
frontside->m_Points.push_back(SplitMe->m_Points);
side=FRONT;
break;

case BACK:
//LOG("next back");
backside->m_Points.push_back(SplitMe->m_Points);
break;

case COPLANAR:
//LOG("back to coplanar");
backside->m_Points.push_back(SplitMe->m_Points);
break;
}
break;

case COPLANAR:
switch(sideB)
{
case FRONT:
//LOG("coplanar to front");
frontside->m_Points.push_back(SplitMe->m_Points);
side=FRONT;
break;

case BACK:
//LOG("coplanar to back");
backside->m_Points.push_back(SplitMe->m_Points);
side=BACK;
break;

case COPLANAR:
//LOG("next coplanar");
frontside->m_Points.push_back(SplitMe->m_Points);
backside->m_Points.push_back(SplitMe->m_Points);
break;

}
break;
}


// Let sideA (Current Point) = the Previous Point
pPtA = pPtB;
sideA = sideB;
}

// This shouldnt happen ??? It may be redundant
if ( frontside->m_Points.size()<3 || backside->m_Points.size()<3 )
{
// All the points fell into one side or the other - due to being coplanar?
for (int loop = 0; loop < numVerts; loop++)
{
side = dxBSPNode::ClassifyPointPlane(&SplitMe->m_Points[loop], pPlane);
if(side!=COPLANAR)
{
delete frontside;
delete backside;
Outputs->push_back(SplitMe);
return side;
}
}
}
else
{
// Yay, we cracked a polygon.
//LOG("*********** POLYGON SPLIT *************");
//LOG("front = "<m_Points.size()<<", back = "<m_Points.size());
// Add the two polygons resulting from the splitting operation
Outputs->push_back(frontside);
Outputs->push_back(backside);
// return special result: "POLYGON WAS SPLIT"
return (PointPlaneResult) -1;
}

// If we get here, we have apparently got a coplanar input polygon that escaped the early test for it :|
MessageBoxA(0,"COPLANAR POLYGON WAS UNEXPECTED",0,0);
exit(1);
MessageBoxA(0,"Something weird happened, we discovered a Coplanar result after the fact",0,0);
exit(1);
}

// This method attempts to find the intersection of a Line Segment and a Plane.
// Return value is interpolation factor, or 'normalized distance to plane' (0 to 1 if there is intersection).
// Formula courtesy of Paul Bourke, Canberra
// numerator = A x1 + B y1 + C z1 + D
// denominator= A (x1-x2) + B(y1-y2) + C(z1-z2)
float dxPortal::IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2,D3DXVECTOR4* pPlane)
{
LOG("Intersecting Line and Plane");
LOG("Point1 = "<x<<","<y<<","<z);
LOG("Point2 = "<x<<","<y<<","<z);
LOG("Plane = "<x<<","<y<<","<z<<","<w);

D3DXVECTOR3* pPlaneNormal = (D3DXVECTOR3*) pPlane;
float numerator = D3DXVec3Dot(pPoint1,(D3DXVECTOR3*) pPlaneNormal) + pPlane->w;
float denominator = pPlane->x*(pPoint1->x-pPoint2->x)+pPlane->y*(pPoint1->y-pPoint2->y)+pPlane->z*(pPoint1->z-pPoint2->z);
// Ifthe denominator is 0 then the normal to the plane is perpendicular to the line.
// Thus the line is either parallel to the plane and there are no solutions or the line is on the plane in which case are infinite solutions.
if(denominator!=0) return numerator / denominator;

// Return value is meant to be a scalar, ie, always positive.
// Any negative value would indicate failure ;)
return -1.0f;

// if it is necessary to determine the intersection of the line segment between P1 and P2 then just check that u is between 0 and 1.
}





Code has been added to tag each node with the bounds of its input set of triangles, in preparation for the 'portalizing' phase. These can be simple AABB's, ie, just find the maxima and minima of the vertices involved. For the root node, this box will be the world bounds And for leaf nodes, it means the bounds of the set of renderable faces in that subspace. The header has also been adjusted.

Note that this bounding volume does not take account of portals, and it is highly noteworthy that a subspace can consist MAINLY of portal surfaces !!
It's just the bounds of the actual renderable triangles in each subspace. We will probably have to expand some of these once we've found our portals.