The following sourcecode is subject to change without notice.
Expect that I will adjust and extend this code as I see fit.
Here you can find the Class Definitions for the BSPTree container class, and my two BSPNode classes.
There is a BSPNode class for internal nodes, and a specialized BSPLeaf node for the terminal nodes, since I will be extending this work well beyond the mere generating of a BSP Tree as outlined in previous posts.
I will not be posting a handful of classes mentioned within the sourcecode, for example, my Mesh class (dxMeshResource) - I'm sure you're clever enough to find or write some code to load mesh geometry.
This code will be omitted mainly because it is outside the scope of this project, W.R.T. mesh loading, all you need to know is that the vertices should be loaded into one vertex buffer, and the vertex indices into one index buffer in the TriangleList style - ie, as a flat array of three indices per triangle.
I will blab inanely about various aspects of the code as I roll it out, these headers will provide a common point of reference.
So without further ado, we can finally get our hands dirty
// The dxBSPTree class implements a BSP Tree, generated from an input 3D model.
#pragma once
// Result of classifying a point and a plane
enum PointPlaneResult
{
FRONT,
BACK,
COPLANAR
};
#include "dxBSPNode.h" // Structural Node class for BSP Trees
#include "dxPortal.h"
#include "dxMeshResource.h" // This is my mesh class, use your own
class dxBSPNode;
class dxPortal;
class Triangle;
class dxBSPTree
{
public:
// Constructor expects an initialized Mesh to be handed in
dxBSPTree(dxMeshResource* LoadedMesh): m_pRootNode(NULL), m_pMesh(LoadedMesh) {}
// Generate BSP Tree from Triangle Soup
void Generate_Tree();
// This list will contain the global list of planes (one per input triangle)
// from which we will select our Splitting Planes during tree construction
vector m_Planes;
// This list will contain the global list of portals which were constructed apon
// the non leaf nodes of the BSP Tree during its construction phase.
vector m_Portals;
// Object representing loaded mesh resource, managed outside this class
dxMeshResource* m_pMesh;
// Check if a plane has been previously selected as splitting plane
bool dxBSPTree::IsPlaneUsed(D3DXVECTOR4* pPlane);
// Determine which subspace encloses a given point
dxBSPLeafNode* Find_Containing_Leaf(D3DXVECTOR3* pvPoint);
private:
// Calculate surface normal and PlaneD for the given triangle
D3DXVECTOR4 Calculate_Plane(Triangle* t);
// Send the shattered portal fragment polygons down the tree
void FrogMarch_Portal_Polygons(dxBSPNode* pStartNode, dxPortal* portal);
// Root Node of BSP Tree
dxBSPNode* m_pRootNode;
};
int typedef TriangleIndex;
#ifndef __dxBSPNode_H_
#define __dxBSPNode_H_
// The dxBSPNode class represents the structural node for a BSP Tree (see dxBSPTree.h)
// Each node can have up to two Children.
//////////////////////////////////////////////////////////////////////////
#include
#include
#include
#include
#include "dxBSPTree.h"
#include "dxMeshResource.h"
#define PLANAR_HALF_EPSILON 0.0005f
//fwd refs
class dxBSPLeafNode;
class dxBSPTree;
class dxPortal;
class dxPolygon;
// Defines a renderable triangle during tree generation
class Triangle
{
public:
Triangle(int iOrig, int iA, int iB, int iC):iOriginalIndex(iOrig), ivA(iA),ivB(iB),ivC(iC) { }
~Triangle() {};
// Vertex Indices
int ivA, ivB, ivC;
// Index of original triangle (since this triangle may have been 'fragmented' during tree generation)
int iOriginalIndex;
D3DXVECTOR4 Plane;
};
using namespace std;
class dxBSPNode
{
public:
// This constructor is mainly used to create new nodes during tree generation.
// It can also be used to construct the root node, if we hand in pParent=NULL.
dxBSPNode(dxBSPTree* pTree, dxBSPNode* pParent, vector* pTriangles): m_pTree(pTree),m_pParent(pParent),m_pvTriangles(pTriangles),m_pFrontChild(0),m_pBackChild(0) { }
// recursive destructor
~dxBSPNode()
{
if(m_pFrontChild) delete m_pFrontChild;
if(m_pBackChild) delete m_pBackChild;
}
// Check if the node is a leaf (ie terminal node)
bool Is_Leaf()
{
if(m_pFrontChild || m_pBackChild) return true;
return false;
}
// Compare a point and a plane
static PointPlaneResult ClassifyPointPlane(D3DXVECTOR3* pPt, D3DXVECTOR4* pPlane);
// Classify a Triangle against a Plane
// This returns three enumerated values, packed into 6 bits
int ClassifyTrianglePlane(Triangle* pTriangle, D3DXVECTOR4* iPlane);
// Test for intersection of a Line and a Plane
// On success, returns the interpolation factor for the intersection (ie, 0.0 to 1.0 means intersection)
// On failure, returns a negative value
float IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2, D3DXVECTOR4* pPlane);
// recursive polygon partitioner
void Generate_Tree();
// Find the best partitioning plane from the planes of the node's input triangles
int Choose_Partitioning_Plane(int*, int*);
// Partition the triangles
void Split_Triangles(vector* FrontOutput, vector* BackOutput);
// After 'shattering' our large planar quads, we send resulting fragments thru the tree:
// We push a polygon to the top of the hill, and let it fall where it may.
void dxBSPNode::Quick_March(dxPolygon* poly);
// Accessors
D3DXVECTOR4* Get_Plane();
dxBSPNode* Get_Front_Child();
dxBSPNode* Get_Back_Child();
private:
// Calculate bounds of input triangles
void Calculate_Bounds();
// Create big fat quad on this node
void dxBSPNode::CreatePortal();
// Set the Parent of this node
void inline SetParent(dxBSPNode* pParent) { m_pParent = pParent; }
// Attach FRONT child
void inline Attach_Front_Child(dxBSPNode* pChild)
{
m_pFrontChild = pChild;
m_pFrontChild->SetParent(this);
}
// Attach BACK child
void inline Attach_Back_Child(dxBSPNode* pChild)
{
m_pBackChild = pChild;
m_pBackChild->SetParent(this);
}
protected:
dxBSPNode* m_pFrontChild;
dxBSPNode* m_pBackChild;
dxBSPNode* m_pParent;
private:
// this list will contain the input list of triangles when a node is created during tree construction,
// and will contain the final list of triangles for leaf nodes (non-leaf nodes should have an empty list, yes?)
vector* m_pvTriangles;
D3DXVECTOR4 m_Plane; // Plane selected to split children
dxBSPTree* m_pTree; // pointer to container of the root node
// AABB of node's input triangle list
struct BoxBounds
{
D3DXVECTOR3 vMin;
D3DXVECTOR3 vMax;
} m_Bounds;
};
#endif
class dxBSPLeafNode: public dxBSPNode
{
public:
dxBSPLeafNode(dxBSPTree* pTree, dxBSPNode* pParent, vector* pTriangles): dxBSPNode(pTree,pParent,pTriangles)
{
}
// Collects fragments from portals
vector m_PortalFragments;
private:
vector m_Portals;
};
#pragma once
using namespace std;
#include "dxBSPNode.h"
#include "dxPortal.h"
#include "dxBSPTree.h"
// Some fwd refs
class dxBSPLeafNode;
class dxPortal;
// The dxPolygon class represents a fragment of portal geometry.
// This is a circular list of 3D points which share a common plane,
// forming a closed, convex, planar polygon in 3-space.
class dxPolygon
{
public:
// Constructor expects ptr to construction portal,
// and will tag the new polygon with that portal's Plane data.
dxPolygon(dxPortal* pOwner);
~dxPolygon(){};
// Polygons can be constructed from 3 or more points
vector m_Points;
// Polygons are tagged with pointer to (or identity of) their 'construction portal'
dxPortal* m_pPortal;
// Polygons are tagged with a Plane, which is typically the same as that of their construction portal
// We flip the plane normal for 'cloned fragments' during 'fragment frogmarch phase',
// therefore each polygon carries its own plane data.
D3DXVECTOR4 m_Plane;
};
// The dxPortal class represents a portal which connects exactly two convex subspaces.
// Subspaces may contain multiple portals however, thus a connectivity graph may be formed.
// Portal geometry can be quite complex, depending on the world geometry involved.
class dxPortal
{
public:
dxPortal():m_pFrontLeaf(0), m_pBackLeaf(0) {};
~dxPortal()
{
// clean polygons
while(!m_Polygons.empty())
{
dxPolygon* p = m_Polygons.back();
delete p;
m_Polygons.pop_back();
}
};
// Accessors
D3DXVECTOR4* GetPlane() { return &m_Plane;}
void SetPlane(D3DXVECTOR4& plane) { m_Plane = plane; }
// Attempt to bisect a (convex) polygon with a given splitting plane.
// Any resulting polygons are also convex.
// Inputs:
// dxPolygon* SplitMe = the polygon to be split
// pPlane = the splitting plane
// Outputs = output list of polygons (receives all resulting polygonal fragments)
// Returns: -1 (polygon was split) or enumerated point/plane result (reason polygon was not split)
// Remarks: Coplanar polygons are simply returned intact.
PointPlaneResult Split(dxPolygon* SplitMe, D3DXVECTOR4* pPlane, vector* Outputs);
// A portal has some unique Geometry:
vector m_Polygons;
private:
// Parametize the intersection of a Line Segment and a Plane.
// Returns -1.0f for failure, or returns a float value.
// Only a return value between 0.0f and 1.0f indicates a true intersection, in which case
// we can then interpolate with this value and the EndPoints to find the intersection point itself.
float IntersectLinePlane(D3DXVECTOR3* pPoint1, D3DXVECTOR3* pPoint2, D3DXVECTOR4* pPlane);
// A portal connects two subspaces:
dxBSPLeafNode* m_pFrontLeaf;
dxBSPLeafNode* m_pBackLeaf;
// A portal has a unique plane:
D3DXVECTOR4 m_Plane;
};
Take some time to look over the headers, as I will begin to spew forth sourcecode for these classes in chunks (any Peter Jackson fans?)
Please feel free to ask any questions, even at this early stage.
Just curious - why are files with a dot H extension not a permitted filetype for uploading here? What is the reasoning behind that?
