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 NodeT * | GetRootNode () 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... | |
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:
OrthoBspTreeT::OrthoBspTreeT | ( | const ArrayT< MapElementT * > & | Elems, |
const BoundingBox3fT & | BB | ||
) |
The constructor.
OrthoBspTreeT::~OrthoBspTreeT | ( | ) |
The destructor.
|
inline |
Returns the BSP trees root node.
|
inline |
Inserts the given element into the tree (the structure of the tree remains unchanged).
|
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().