BSP tree ?

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 HISTORY

11/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