# Let's get a-crackalackin', it's crunch time.

[subheading]Organic Code Warning[/subheading]

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

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?

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?

Sign in to follow this

Followers
0

## 1 Comment

## Recommended Comments

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now