CrystalSpace

Public API Reference

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

A Bounding Volume Hierachy (BVH). More...

#include <csgeom/bvh.h>

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

List of all members.

Public Types

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

Public Member Functions

 BVH ()
 Create a new empty BVH.
void Distribute ()
 Distribute all objects in this node to its children.
void Front2Back (csVector3 const &pos, VisitFunc *func, void *data, uint32 frustumMask)
 Traverse the tree in approximate front to back order.
void MoveObject (Child *obj, BoundType const &newBound)
 Move an object (give it a new bound).
void TraverseRandom (VisitFunc *func, void *data, uint32 frustumMask)
 Traverse the tree in random order.
virtual ~BVH ()
 Destroy the tree.

Detailed Description

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

A Bounding Volume Hierachy (BVH).

A BVH 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 fast approximate front to back ordering.

The BVH 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.

As this implementation is supposed to be as fast as possible sanity checks are only performed in debug mode, so those should be performed additionally if needed.

Definition at line 58 of file bvh.h.


Member Typedef Documentation

template<class ChildType >
typedef bool( CS::Geometry::BVH< ChildType >::VisitFunc)(Self *treenode, void *userdata, uint32 &frustum_mask)

A callback function for visiting a BVH node.

If this function returns true the traversal will continue. Otherwise Front2Back() will return to the next traversal point or 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().

'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 83 of file bvh.h.


Constructor & Destructor Documentation

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

Create a new empty BVH.

Definition at line 195 of file bvh.h.

template<class ChildType >
virtual CS::Geometry::BVH< ChildType >::~BVH (  )  [inline, virtual]

Destroy the tree.

Definition at line 202 of file bvh.h.


Member Function Documentation

template<class ChildType >
void CS::Geometry::BVH< 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 278 of file bvh.h.

template<class ChildType >
void CS::Geometry::BVH< ChildType >::Front2Back ( csVector3 const &  pos,
VisitFunc func,
void *  data,
uint32  frustumMask 
) [inline]

Traverse the tree in approximate front to back order.

Every node of the tree will be encountered at most once. Returns false if traversal in this branch should stop (may continue in an alternate branch that may have been in front of this one if there is any - i.e. if the childs of this node are overlapping). The mask parameter is optionally used for frustum checking. Front2Back will pass it to the tree nodes.

Definition at line 451 of file bvh.h.

template<class ChildType >
void CS::Geometry::BVH< ChildType >::MoveObject ( Child *  obj,
BoundType const &  newBound 
) [inline]

Move an object (give it a new bound).

Definition at line 210 of file bvh.h.

template<class ChildType >
void CS::Geometry::BVH< ChildType >::TraverseRandom ( VisitFunc func,
void *  data,
uint32  frustumMask 
) [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 419 of file bvh.h.


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

Generated for Crystal Space 2.1 by doxygen 1.6.1