CrystalSpace

Public API Reference

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

A Bounding Intervall Hierachy (BIH). More...

#include <csgeom/bih.h>

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

List of all members.

Public Types

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

Public Member Functions

 BIH ()
 Create a new empty BIH.
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.

Detailed Description

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

A Bounding Intervall Hierachy (BIH).

A BIH 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 BIH 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 66 of file bih.h.


Member Typedef Documentation

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

A callback function for visiting a BIH 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 91 of file bih.h.


Constructor & Destructor Documentation

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

Create a new empty BIH.

Definition at line 352 of file bih.h.


Member Function Documentation

template<class ChildType >
void CS::Geometry::BIH< 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 437 of file bih.h.

template<class ChildType >
void CS::Geometry::BIH< 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 622 of file bih.h.

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

Move an object (give it a new bound).

Definition at line 366 of file bih.h.

template<class ChildType >
void CS::Geometry::BIH< 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 589 of file bih.h.


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

Generated for Crystal Space 2.1 by doxygen 1.6.1