Cafu Engine
OrthoBspTreeT Class Reference

This class represents an orthogonal BSP tree (axis-aligned split planes) that spatially organizes MapElementT instances. More...

#include "OrthoBspTree.hpp"

Classes

class  NodeT
 

Public Member Functions

 OrthoBspTreeT (const ArrayT< MapElementT * > &Elems, const BoundingBox3fT &BB)
 The constructor. More...
 
 ~OrthoBspTreeT ()
 The destructor. More...
 
const NodeTGetRootNode () const
 Returns the BSP trees root node. More...
 
void Insert (MapElementT *Elem)
 Inserts the given element into the tree (the structure of the tree remains unchanged). More...
 
void Remove (MapElementT *Elem)
 Removes the given element from the tree (the structure of the tree remains unchanged). More...
 
unsigned long Update ()
 Removes and re-inserts map elements from and into the tree whose bounding-box changed so that it disagrees with the tree structure. More...
 

Detailed Description

This class represents an orthogonal BSP tree (axis-aligned split planes) that spatially organizes MapElementT instances.

A map element is generally linked in each leaf that it intersects, or instead whenever possible in the node closest to the root where the element intersects all children. Note that the latter is an optional feature that yields a tree that is logically equivalent to the pure "store all contents in leaves" strategy (where nodes generally remain empty and store no contents at all), but in comparison saves some storage. Also note the subtle difference to storing some contents in nodes (the elements that intersect a split plane) and some (the rest) in leaves, like ancient version of our CaBSP: Keeping some contents in nodes like this would make it impossible to determine the contents (the set of all map elements) that are inside a given node, because the set would be grossly oversized. Our "extended leaves-only" approach saves both storage and is able to produce for each node the exact set of map elements (required e.g. for view frustum tests).

Another feature of this implementation is that the bounding-box of a node is usually not the tight bounding-box over its contents, but typically larger: The bounding-box of the root node is the maximum bounds of the world, the bounding-box of its children is determined by subdividing it along the split plane, etc. As such, the bounding-boxes in the tree only depend on the split planes, but not directly on the contents of the nodes (and thus the BB member of the NodeT class is const).

Finally, note how these larger bounding-boxes affect the tree structure and size. There are two important differences:

  1. Where we would not have node planes at the outmost brush faces with a "tight" starting box, our approach definitively comes up with these outmost walls as split planes sooner or later. This enlarges the tree, but these extra nodes are fortunately not completely useless: When the user extends the map spatially, the extra nodes come in just handy.
  2. The center of our larger boxes is often different from the center of the tight bounding-boxes, as the tight boxes are usually not symmetric to the origin. This causes different split planes to be chosen when the tree is built. As with issue 1. though, this difference is not a principal or serious problem.

Constructor & Destructor Documentation

OrthoBspTreeT::OrthoBspTreeT ( const ArrayT< MapElementT * > &  Elems,
const BoundingBox3fT BB 
)

The constructor.

OrthoBspTreeT::~OrthoBspTreeT ( )

The destructor.

Member Function Documentation

const NodeT* OrthoBspTreeT::GetRootNode ( ) const
inline

Returns the BSP trees root node.

void OrthoBspTreeT::Insert ( MapElementT Elem)
inline

Inserts the given element into the tree (the structure of the tree remains unchanged).

void OrthoBspTreeT::Remove ( MapElementT Elem)
inline

Removes the given element from the tree (the structure of the tree remains unchanged).

unsigned long OrthoBspTreeT::Update ( )

Removes and re-inserts map elements from and into the tree whose bounding-box changed so that it disagrees with the tree structure.

This method is called once per "document frame" in ChildFrameT::OnIdle().

Returns
the number of map elements that have been updated.

The documentation for this class was generated from the following files: