CrystalSpace

Public API Reference

CS::Geometry::KDTree< ChildType > Class Template Reference

A KD-tree. More...

#include <csgeom/kdtree.h>

Inherits CS::Geometry::SpatialTree< KDTree< ChildType >, ChildType >.

List of all members.

Public Types

typedef bool( VisitFunc )(Self *treenode, void *userdata, uint32 timestamp, uint32 &frustum_mask)
 A callback function for visiting a KD-tree node.

Public Member Functions

void Distribute ()
 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.
 KDTree ()
 Create a new empty KD-tree.
void MoveObject (Child *object, BoundType const &bounds)
 Move an object (give it a new bounding box).
uint32 NewTraversal ()
 Start a new traversal.
void TraverseRandom (VisitFunc *func, void *userdata, uint32 frustum_mask)
 Traverse the tree in random order.

Detailed Description

template<class ChildType>
class CS::Geometry::KDTree< ChildType >

A KD-tree.

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.

Definition at line 65 of file kdtree.h.


Member Typedef Documentation

template<class ChildType >
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.

Definition at line 98 of file kdtree.h.


Constructor & Destructor Documentation

template<class ChildType >
CS::Geometry::KDTree< ChildType >::KDTree (  )  [inline]

Create a new empty KD-tree.

Definition at line 482 of file kdtree.h.


Member Function Documentation

template<class ChildType >
void CS::Geometry::KDTree< ChildType >::Distribute (  )  [inline]

Distribute all objects in this node to its children.

This may also create new children if needed. Note that this will only distribute one level (this node) and will not recurse into the children.

Definition at line 556 of file kdtree.h.

template<class ChildType >
void CS::Geometry::KDTree< ChildType >::Front2Back ( const csVector3 pos,
VisitFunc func,
void *  userdata,
uint32  frustum_mask 
) [inline]

Traverse the tree from front to back.

Every node of the tree will be encountered. The mask parameter is optionally used for frustum checking. Front2Back will pass it to the tree nodes.

Definition at line 684 of file kdtree.h.

template<class ChildType >
void CS::Geometry::KDTree< ChildType >::MoveObject ( Child *  object,
BoundType const &  bounds 
) [inline]

Move an object (give it a new bounding box).

Definition at line 494 of file kdtree.h.

template<class ChildType >
uint32 CS::Geometry::KDTree< ChildType >::NewTraversal (  )  [inline]

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.

Definition at line 697 of file kdtree.h.

template<class ChildType >
void CS::Geometry::KDTree< ChildType >::TraverseRandom ( VisitFunc func,
void *  userdata,
uint32  frustum_mask 
) [inline]

Traverse the tree in random order.

The mask parameter is optionally used for frustum checking. TraverseRandom will pass it to the tree nodes.

Definition at line 672 of file kdtree.h.


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

Generated for Crystal Space 2.1 by doxygen 1.6.1