CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

csKDTree Class Reference

A KD-tree. More...

#include <kdtree.h>

Inheritance diagram for csKDTree:

iBase List of all members.

Public Methods

 csKDTree ()
 Create a new empty KD-tree.

virtual ~csKDTree ()
 Destroy the KD-tree.

void SetParent (csKDTree *p)
 Set the parent.

void Clear ()
 Make the tree empty.

iBaseGetUserObject () const
 Get the user object attached to this node.

void SetUserObject (iBase *userobj)
 Set the user object for this node.

csKDTreeChildAddObject (const csBox3 &bbox, void *object)
 Add an object to this kd-tree node.

void UnlinkObject (csKDTreeChild *object)
 Unlink an object from the kd-tree.

void RemoveObject (csKDTreeChild *object)
 Remove an object from the kd-tree.

void MoveObject (csKDTreeChild *object, const csBox3 &new_bbox)
 Move an object (give it a new bounding box).

void Distribute ()
 Distribute all objects in this node to its children.

void FullDistribute ()
 Do a full distribution of this node and all children.

void Flatten ()
 Do a full flatten of this node.

void Front2Back (const csVector3 &pos, csKDTreeVisitFunc *func, void *userdata, uint32 frustum_mask)
 Traverse the tree from front to back.

int GetObjectCount () const
 Return the number of objects in this node.

int GetEstimatedObjectCount ()
 Get the estimated total number of objects in this node and all children.

csKDTreeChild ** GetObjects () const
 Return the array of objects in this node.

const csBox3GetNodeBBox () const
 Return the bounding box of the node itself (does not always contain all children since children are not split by the tree).


Detailed Description

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 129 of file kdtree.h.


Constructor & Destructor Documentation

csKDTree::csKDTree  
 

Create a new empty KD-tree.

virtual csKDTree::~csKDTree   [virtual]
 

Destroy the KD-tree.


Member Function Documentation

csKDTreeChild* csKDTree::AddObject const csBox3   bbox,
void *    object
 

Add an object to this kd-tree node.

Returns a csKDTreeChild pointer which represents the object inside the kd-tree. Object addition is delayed. This function will not yet alter the structure of the kd-tree. Distribute() will do that.

void csKDTree::Clear  
 

Make the tree empty.

void csKDTree::Distribute  
 

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.

void csKDTree::Flatten  
 

Do a full flatten of this node.

This means that all objects are put back in the object list of this node and the KD-tree children are removed.

void csKDTree::Front2Back const csVector3   pos,
csKDTreeVisitFunc *    func,
void *    userdata,
uint32    frustum_mask
 

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.

void csKDTree::FullDistribute  
 

Do a full distribution of this node and all children.

int csKDTree::GetEstimatedObjectCount   [inline]
 

Get the estimated total number of objects in this node and all children.

This is only an estimate as it isn't kept up-to-date constantly but it should give a rough idea about the complexity of this node.

Definition at line 308 of file kdtree.h.

const csBox3& csKDTree::GetNodeBBox   const [inline]
 

Return the bounding box of the node itself (does not always contain all children since children are not split by the tree).

Definition at line 319 of file kdtree.h.

int csKDTree::GetObjectCount   const [inline]
 

Return the number of objects in this node.

Definition at line 300 of file kdtree.h.

csKDTreeChild** csKDTree::GetObjects   const [inline]
 

Return the array of objects in this node.

Definition at line 313 of file kdtree.h.

iBase* csKDTree::GetUserObject   const [inline]
 

Get the user object attached to this node.

Definition at line 233 of file kdtree.h.

void csKDTree::MoveObject csKDTreeChild   object,
const csBox3   new_bbox
 

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

void csKDTree::RemoveObject csKDTreeChild   object
 

Remove an object from the kd-tree.

The 'csKDTreeChild' instance will be deleted.

void csKDTree::SetParent csKDTree *    p [inline]
 

Set the parent.

Definition at line 225 of file kdtree.h.

void csKDTree::SetUserObject iBase   userobj
 

Set the user object for this node.

Can be 0 to clear it. The old user object will be DecRef'ed and the (optional) new one will be IncRef'ed.

void csKDTree::UnlinkObject csKDTreeChild   object
 

Unlink an object from the kd-tree.

The 'csKDTreeChild' instance will NOT be deleted.


The documentation for this class was generated from the following file:
Generated for Crystal Space by doxygen 1.2.18