CS::Geometry::KDTree Class Reference
A KD-tree. More...
#include <csgeom/kdtreex.h>
Public Member Functions | |
| KDTreeChild * | AddObject (const csSphere &bsphere, 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. | |
| 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< iString > | Dump () |
| 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, KDTreeVisitFunc *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. | |
| KDTree * | GetChild1 () const |
| Get child one. | |
| KDTree * | GetChild2 () const |
| Get child two. | |
| int | GetEstimatedObjectCount () |
| Get the estimated total number of objects in this node and all children. | |
| const csBox3 & | GetNodeBBox () 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. | |
| KDTreeChild ** | 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. | |
| iKDTreeUserData * | GetUserObject () const |
| Get the user object attached to this node. | |
| KDTree () | |
| Create a new empty KD-tree. | |
| void | MoveObject (KDTreeChild *object, const csSphere &new_bsphere) |
| Move an object (give it a new bounding box). | |
| uint32 | NewTraversal () |
| Start a new traversal. | |
| void | RemoveObject (KDTreeChild *object) |
| Remove an object from the kd-tree. | |
| void | SetMinimumSplitAmount (int m) |
| Set the minimum amount of objects before we consider splitting this tree. | |
| void | SetObjectDescriptor (iObjectDescriptor *descriptor) |
| For debugging: set the object descriptor. | |
| void | SetParent (KDTree *p) |
| Set the parent. | |
| void | SetUserObject (iKDTreeUserData *userobj) |
| Set the user object for this node. | |
| virtual csPtr< iString > | StateTest () |
| Perform a state test. | |
| void | TraverseRandom (KDTreeVisitFunc *func, void *userdata, uint32 frustum_mask) |
| Traverse the tree in random order. | |
| void | UnlinkObject (KDTreeChild *object) |
| Unlink an object from the kd-tree. | |
| virtual | ~KDTree () |
| Destroy the KD-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 166 of file kdtreex.h.
Constructor & Destructor Documentation
| CS::Geometry::KDTree::KDTree | ( | ) |
Create a new empty KD-tree.
| virtual CS::Geometry::KDTree::~KDTree | ( | ) | [virtual] |
Destroy the KD-tree.
Member Function Documentation
| KDTreeChild* CS::Geometry::KDTree::AddObject | ( | const csSphere & | bsphere, | |
| void * | object | |||
| ) |
Add an object to this kd-tree node.
Returns a KDTreeChild 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 CS::Geometry::KDTree::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.
| void CS::Geometry::KDTree::Clear | ( | ) |
Make the tree empty.
| virtual bool CS::Geometry::KDTree::DebugCommand | ( | const char * | cmd | ) | [inline, virtual] |
Perform a debug command as defined by the module itself.
Returns 'false' if the command was not recognized.
Implements iDebugHelper.
| void CS::Geometry::KDTree::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 CS::Geometry::KDTree::Dump | ( | iGraphics3D * | g3d | ) | [inline, virtual] |
Do a graphical dump of the current state of this object.
Implements iDebugHelper.
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.
| void CS::Geometry::KDTree::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 CS::Geometry::KDTree::Front2Back | ( | const csVector3 & | pos, | |
| KDTreeVisitFunc * | 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 CS::Geometry::KDTree::FullDistribute | ( | ) |
Do a full distribution of this node and all children.
| KDTree* CS::Geometry::KDTree::GetChild1 | ( | ) | const [inline] |
| KDTree* CS::Geometry::KDTree::GetChild2 | ( | ) | const [inline] |
| int CS::Geometry::KDTree::GetEstimatedObjectCount | ( | ) | [inline] |
| const csBox3& CS::Geometry::KDTree::GetNodeBBox | ( | ) | const [inline] |
| int CS::Geometry::KDTree::GetObjectCount | ( | ) | const [inline] |
| KDTreeChild** CS::Geometry::KDTree::GetObjects | ( | ) | const [inline] |
| virtual int CS::Geometry::KDTree::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.
| iKDTreeUserData* CS::Geometry::KDTree::GetUserObject | ( | ) | const [inline] |
| void CS::Geometry::KDTree::MoveObject | ( | KDTreeChild * | object, | |
| const csSphere & | new_bsphere | |||
| ) |
Move an object (give it a new bounding box).
| uint32 CS::Geometry::KDTree::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 CS::Geometry::KDTree::RemoveObject | ( | KDTreeChild * | object | ) |
Remove an object from the kd-tree.
The 'KDTreeChild' instance will be deleted.
| void CS::Geometry::KDTree::SetMinimumSplitAmount | ( | int | m | ) | [inline] |
| void CS::Geometry::KDTree::SetObjectDescriptor | ( | iObjectDescriptor * | descriptor | ) | [inline] |
| void CS::Geometry::KDTree::SetParent | ( | KDTree * | p | ) | [inline] |
| void CS::Geometry::KDTree::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.
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.
| void CS::Geometry::KDTree::TraverseRandom | ( | KDTreeVisitFunc * | 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.
| void CS::Geometry::KDTree::UnlinkObject | ( | KDTreeChild * | object | ) |
Unlink an object from the kd-tree.
The 'KDTreeChild' instance will NOT be deleted.
The documentation for this class was generated from the following file:
- csgeom/kdtreex.h
Generated for Crystal Space 2.0 by doxygen 1.6.1