CrystalSpace

Public API Reference

csKDTree Class Reference
[Geometry utilities]

A KD-tree. More...

#include <csgeom/kdtree.h>

Inheritance diagram for csKDTree:

Inheritance graph
[legend]
List of all members.

Public Member Functions

csKDTreeChildAddObject (const csBox3 &bbox, void *object)
 Add an object to this kd-tree node.
virtual csTicks Benchmark (int num_iterations)
 Perform a benchmark.
void Clear ()
 Make the tree empty.
 csKDTree ()
 Create a new empty KD-tree.
virtual bool DebugCommand (const char *)
 Perform a debug command as defined by the module itself.
void Distribute ()
 Distribute all objects in this node to its children.
virtual void Dump (iGraphics3D *)
 Do a graphical dump of the current state of this object.
virtual csPtr< iStringDump ()
 Do a text dump of the current state of this object.
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.
void FullDistribute ()
 Do a full distribution of this node and all children.
csKDTreeGetChild1 () const
 Get child one.
csKDTreeGetChild2 () const
 Get child two.
int GetEstimatedObjectCount ()
 Get the estimated total number of objects in this node and all children.
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).
int GetObjectCount () const
 Return the number of objects in this node.
csKDTreeChild ** GetObjects () const
 Return the array of objects in this node.
virtual int GetSupportedTests () const
 Return a bit field indicating what types of functions this specific unit test implementation supports.
iKDTreeUserDataGetUserObject () const
 Get the user object attached to this node.
void MoveObject (csKDTreeChild *object, const csBox3 &new_bbox)
 Move an object (give it a new bounding box).
uint32 NewTraversal ()
 Start a new traversal.
void RemoveObject (csKDTreeChild *object)
 Remove an object from the kd-tree.
void SetObjectDescriptor (iKDTreeObjectDescriptor *descriptor)
 For debugging: set the object descriptor.
void SetParent (csKDTree *p)
 Set the parent.
void SetUserObject (iKDTreeUserData *userobj)
 Set the user object for this node.
virtual csPtr< iStringStateTest ()
 Perform a state test.
void TraverseRandom (csKDTreeVisitFunc *func, void *userdata, uint32 frustum_mask)
 Traverse the tree in random order.
virtual csPtr< iStringUnitTest ()
 Perform a unit test.
void UnlinkObject (csKDTreeChild *object)
 Unlink an object from the kd-tree.
virtual ~csKDTree ()
 Destroy the KD-tree.

Public Attributes

csRef< iKDTreeObjectDescriptordescriptor

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 167 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.

virtual csTicks csKDTree::Benchmark ( int  num_iterations  )  [inline, virtual]

Perform a benchmark.

This function will return a number indicating how long the benchmark lasted in milliseconds.

Implements iDebugHelper.

Definition at line 437 of file kdtree.h.

void csKDTree::Clear (  ) 

Make the tree empty.

virtual bool csKDTree::DebugCommand ( const char *   )  [inline, virtual]

Perform a debug command as defined by the module itself.

Returns 'false' if the command was not recognized.

Implements iDebugHelper.

Definition at line 450 of file kdtree.h.

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.

virtual void csKDTree::Dump ( iGraphics3D  )  [inline, virtual]

Do a graphical dump of the current state of this object.

Implements iDebugHelper.

Definition at line 449 of file kdtree.h.

virtual csPtr<iString> csKDTree::Dump (  )  [inline, virtual]

Do a text dump of the current state of this object.

Returns 0 if not supported or else a string which you should DecRef() after use.

Implements iDebugHelper.

Definition at line 442 of file kdtree.h.

References scfString::GetCsString().

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.

csKDTree* csKDTree::GetChild1 (  )  const [inline]

Get child one.

Definition at line 376 of file kdtree.h.

csKDTree* csKDTree::GetChild2 (  )  const [inline]

Get child two.

Definition at line 381 of file kdtree.h.

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

int csKDTree::GetObjectCount (  )  const [inline]

Return the number of objects in this node.

Definition at line 386 of file kdtree.h.

csKDTreeChild** csKDTree::GetObjects (  )  const [inline]

Return the array of objects in this node.

Definition at line 399 of file kdtree.h.

virtual int csKDTree::GetSupportedTests (  )  const [inline, virtual]

Return a bit field indicating what types of functions this specific unit test implementation supports.

This will return a combination of the CS_DBGHELP_... flags:

Implements iDebugHelper.

Definition at line 417 of file kdtree.h.

References CS_DBGHELP_BENCHMARK, CS_DBGHELP_STATETEST, CS_DBGHELP_TXTDUMP, and CS_DBGHELP_UNITTEST.

iKDTreeUserData* csKDTree::GetUserObject (  )  const [inline]

Get the user object attached to this node.

Definition at line 292 of file kdtree.h.

void csKDTree::MoveObject ( csKDTreeChild object,
const csBox3 new_bbox 
)

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

uint32 csKDTree::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 csKDTree::RemoveObject ( csKDTreeChild object  ) 

Remove an object from the kd-tree.

The 'csKDTreeChild' instance will be deleted.

void csKDTree::SetObjectDescriptor ( iKDTreeObjectDescriptor descriptor  )  [inline]

For debugging: set the object descriptor.

Definition at line 283 of file kdtree.h.

References descriptor.

void csKDTree::SetParent ( csKDTree p  )  [inline]

Set the parent.

Definition at line 280 of file kdtree.h.

void csKDTree::SetUserObject ( iKDTreeUserData 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.

virtual csPtr<iString> csKDTree::StateTest (  )  [inline, virtual]

Perform a state test.

This function will test if the current state of the object is ok. It will return 0 if it is ok. Otherwise an iString is returned containing some information about the errors. DecRef() this returned string after using it.

Implements iDebugHelper.

Definition at line 428 of file kdtree.h.

References scfString::GetCsString().

void csKDTree::TraverseRandom ( csKDTreeVisitFunc func,
void *  userdata,
uint32  frustum_mask 
)

Traverse the tree in random order.

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

virtual csPtr<iString> csKDTree::UnitTest (  )  [inline, virtual]

Perform a unit test.

This function will try to test as much as possible of the given module. This function returns 0 if the test succeeded. Otherwise an iString is returned containing some information about the errors. DecRef() this returned string after using it.

Implements iDebugHelper.

Definition at line 423 of file kdtree.h.

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 1.0.2 by doxygen 1.4.7