CS::Geometry::KDTree< ChildType > Class Template Reference
A KD-tree. More...
Inherits CS::Geometry::SpatialTree< KDTree< ChildType >, ChildType >.
|typedef bool(||VisitFunc )(Self *treenode, void *userdata, uint32 timestamp, uint32 &frustum_mask)|
|A callback function for visiting a KD-tree node. |
Public Member Functions
|Distribute all objects in this node to its children. |
|void||Front2Back (const csVector3 &pos, VisitFunc *func, void *userdata, uint32 frustum_mask)|
|Traverse the tree from front to back. |
|Create a new empty KD-tree. |
|void||MoveObject (Child *object, BoundType const &bounds)|
|Move an object (give it a new bounding box). |
|Start a new traversal. |
|void||TraverseRandom (VisitFunc *func, void *userdata, uint32 frustum_mask)|
|Traverse the tree in random order. |
class CS::Geometry::KDTree< ChildType >
A KD-tree is a binary tree that organizes 3D space. This implementation is dynamic. It allows moving, adding, and removing of objects which will alter the tree dynamically. The main purpose of this tree is to provide for an approximate front to back ordering.
The KD-tree supports delayed insertion. When objects are inserted in the tree they are not immediatelly distributed over the nodes but instead they remain in the main node until it is really needed to distribute them. The advantage of this is that you can insert/remove a lot of objects in the tree and then do the distribution calculation only once. This is more efficient and it also generates a better tree as more information is available then.
Member Typedef Documentation
|typedef bool( CS::Geometry::KDTree< ChildType >::VisitFunc)(Self *treenode, void *userdata, uint32 timestamp, uint32 &frustum_mask)|
A callback function for visiting a KD-tree node.
If this function returns true the traversal will continue. Otherwise Front2Back() will stop.
This function is itself responsible for calling Distribute() on the given treenode to ensure that the objects in this node are properly distributed to the children. If the function doesn't want or need this functionality it doesn't have to do Distribute().
If this function decides to process the given node then it is also responsible for checking the timestamp of every child in this node with the timestamp given to this function. If this timestamp is different the child has not been processed before. This function should then update the timestamp of the child. If this is not done then some objects will be encountered multiple times. In some cases this may not be a problem or even desired.
'frustum_mask' can be modified by this function to reduce the number of plane tests (for frustum culling) that have to occur for children of this node.
Constructor & Destructor Documentation
Member Function Documentation
|void CS::Geometry::KDTree< ChildType >::Distribute||(||)||
|void CS::Geometry::KDTree< ChildType >::Front2Back||(||const csVector3 &||pos,|
|void CS::Geometry::KDTree< ChildType >::MoveObject||(||Child *||object,|
|BoundType const &||bounds|
|uint32 CS::Geometry::KDTree< ChildType >::NewTraversal||(||)||
Start a new traversal.
This will basically make a new timestamp and return it. You can then use that timestamp to check if objects have been visited already. This function is automatically called by Front2Back() but it can be useful to call this if you plan to do a manual traversal of the tree.
|void CS::Geometry::KDTree< ChildType >::TraverseRandom||(||VisitFunc *||func,|
The documentation for this class was generated from the following file:
Generated for Crystal Space 2.1 by doxygen 1.6.1