ok, im understanding how this works, but how the hell do you code it??
please help me out here.
ok, im understanding how this works, but how the hell do you code it??
please help me out here.
Wow, this is an old thread.
Coding a BSP tree is quite easy if you know how to program a “Tree” data structure. A tree is a basic data structure which all programmers should know. Maybe you should learn how to make some tree data structures before diving into a BSP tree.
-SirKnight
Oh neato, I just found this:
/*******************************************************************
- Title: BSP.h
- Desc: Excessively generic implementation of a
node-based BSP tree.
- copyright (c) 2000 by Adrian Perez
******************************************************************//***
REVISION HISTORY11/02/00 : Cuban
Gave adaptor control over HP selection, added serialization
support using the iostream library.
***/#include
#include
#include
#include <assert.h>
// One of the inputs to the tree constructor is an adaptor that
// implements the three operations required to build
// a BSP tree:
//
// () Classifying an element against a hyperplane
// (ex: polygon->plane testing)
// () Splitting an element by a hyperplane
// (ex: polygon->plane => front/back pieces)
// () Choosing a hyperplane to partition a set of elements,
// given said set of elements
//
// struct sTreeAdaptor
// {
// eBspRelation Classify(
// const T_hyperplane& plane,
// const T_element& elem ) const;
//
// void Split(
// const T_hyperplane& plane,
// const T_element& elem,
// T_element pFront,
// T_element* pBack ) const;
//
// void ChooseHyperplane(
// std::vector<T_element>& toProcess,
// T_hyperplane* pPlane ) const;
// };
// Returned by the Classify method of the tree adaptor.
enum eBspRelation
{
BSP_RELAT_IN_FRONT,
BSP_RELAT_IN_BACK,
BSP_RELAT_SPLIT,
BSP_RELAT_COPLANAR
};
// This is a non-brep tree. Used just for classification of
// polygons. No leaves.
template< class T_element, class T_hyperplane, class T_treeAdaptor >
class cNodeBSP
{
// Other objects need to see what a node looks like.
public:
struct sNode
{
typedef std::vector< T_element > elemVec;sNode* m_pFront; sNode* m_pBack; elemVec m_contents; T_hyperplane m_hp; sNode( elemVec& toProcess, const T_treeAdaptor& adap ) : m_pFront( NULL ) , m_pBack( NULL ) { // Setup elemVec frontVec, backVec; frontVec.reserve( toProcess.size() ); backVec.reserve( toProcess.size() ); // Choose which node we're going to use. adap.ChooseHyperplane( toProcess, &m_hp ); // Iterate across the rest of the polygons elemVec::iterator iter = toProcess.begin(); for( ; iter != toProcess.end(); ++iter ) { T_element front, back; switch( adap.Classify( m_hp, *iter ) ) { case BSP_RELAT_IN_FRONT: frontVec.push_back( *iter ); break; case BSP_RELAT_IN_BACK: backVec.push_back( *iter ); break; case BSP_RELAT_COPLANAR: m_contents.push_back( *iter ); break; case BSP_RELAT_SPLIT: adap.Split( m_hp, *iter, &front, &back ); frontVec.push_back( front ); backVec.push_back( back ); break; default: break; } } // Now recurse if necessary if( !frontVec.empty() ) m_pFront = new sNode( frontVec, adap ); if( !backVec.empty() ) m_pBack = new sNode( backVec, adap ); } sNode( std::istream& in ) { // First char is the child state // (0x1 means front child, 0x2 means back child) int childState; in >> childState; // Next is the hyperplane for the node in >> m_hp; // Next is the number of elements in the node unsigned int nElem; in >> nElem; m_contents.reserve( nElem ); while( nElem-- ) { T_element elem; in >> elem; m_contents.push_back( elem ); } // recurse if we have children. if( childState & 0x1 ) m_pFront = new sNode( in ); else m_pFront = NULL; if( childState & 0x2 ) m_pBack = new sNode( in ); else m_pBack = NULL; } void Write( std: [img]http://www.opengl.org/discussion_boards/ubb/redface.gif[/img]stream& out ) { // What is our child state? int childState = 0; if( m_pFront ) childState += 1; if( m_pBack ) childState += 2; // write it out out << childState << " "; // Write out hp out << m_hp << " "; // now take care of the contents unsigned int nElem = m_contents.size(); out << nElem << " "; while( nElem-- ) out << m_contents[nElem] << " "; // Finally deal with the children if( m_pFront ) m_pFront->Write( out ); if( m_pBack ) m_pBack->Write( out ); } ~sNode() { delete m_pFront; delete m_pBack; } };
protected:
sNode* m_pRoot; T_treeAdaptor m_adap; std::vector< T_element > m_toBuild;
public:
cNodeBSP( T_treeAdaptor& adaptor = T_treeAdaptor() ) : m_adap( adaptor ) , m_pRoot( NULL ) {} sNode* GetRoot(){ return m_pRoot; } void AddElement( const T_element& elem ) { bool bTreeAlreadyBuilt = (m_pRoot != NULL); assert( !bTreeAlreadyBuilt ); m_toBuild.push_back( elem ); } void BuildTree() { assert( m_toBuild.size() ); m_pRoot = new sNode( m_toBuild, m_adap ); } void Read( std::istream& in ) { // Shouldn't read in over a tree. assert( !m_pRoot ); m_pRoot = new sNode( in ); } void Write( std: [img]http://www.opengl.org/discussion_boards/ubb/redface.gif[/img]stream& out ) { // Shouldn't write out a null tree assert( m_pRoot ); m_pRoot->Write( out ); }
};
/* As an example, with a completed tree that used my polygon structure as
an element and a plane as a hyperplane, this is a function that was
written to do inorder traversal, initially called with the root of the
tree (s3DTreeAdaptor not included for brevity):typedef cNodeBSP< polygon, plane3, s3DTreeAdaptor > polyTree;
void InOrderTraversal( polyTree::sNode* pNode, point3 camLoc )
{
std::vector< polygon >::iterator iter=pNode->m_contents.begin();
switch( pNode->m_hp.TestPoint( camLoc ) )
{
case ptFront:
if( pNode->m_pBack ) InOrderTraversal( pNode->m_pBack, camLoc );for( ; iter != pNode->m_contents.end(); ++iter ) DrawPoly( *iter ); if( pNode->m_pFront ) InOrderTraversal( pNode->m_pFront, camLoc ); break; default: if( pNode->m_pFront ) InOrderTraversal( pNode->m_pFront, camLoc ); for( ; iter != pNode->m_contents.end(); ++iter ) DrawPoly( *iter ); if( pNode->m_pBack ) InOrderTraversal( pNode->m_pBack, camLoc ); break; }
};
*/
Maybe that will be usefull to anyone looking for a basic BSP tree implementation.
-SirKnight