Public API Reference

               

---

csKDTree Class Reference

A KD-tree. More...

#include <kdtree.h>

Inheritance diagram for csKDTree:

List of all members.

Public Methods
	csKDTree (csKDTree *parent)
	Create a new empty KD-tree. More...
virtual	~csKDTree ()
	Destroy the KD-tree. More...
void	Clear ()
	Make the tree empty. More...
iBase *	GetUserObject () const
	Get the user object attached to this node. More...
void	SetUserObject (iBase *userobj)
	Set the user object for this node. More...
csKDTreeChild *	AddObject (const csBox3 &bbox, void *object)
	Add an object to this kd-tree node. More...
void	UnlinkObject (csKDTreeChild *object)
	Unlink an object from the kd-tree. More...
void	RemoveObject (csKDTreeChild *object)
	Remove an object from the kd-tree. More...
void	MoveObject (csKDTreeChild *object, const csBox3 &new_bbox)
	Move an object (give it a new bounding box). More...
void	Distribute ()
	Distribute all objects in this node to its children. More...
void	FullDistribute ()
	Do a full distribution of this node and all children. More...
void	Flatten ()
	Do a full flatten of this node. More...
void	Front2Back (const csVector3 &pos, csKDTreeVisitFunc *func, void *userdata, uint32 frustum_mask)
	Traverse the tree from front to back. More...
int	GetObjectCount () const
	Return the number of objects in this node. More...
csKDTreeChild **	GetObjects () const
	Return the array of objects in this node. More...
const csBox3 &	GetObjectBBox ()
	Return the bounding box of all objects in this node. More...
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). More...

---

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

---

Constructor & Destructor Documentation

csKDTree::csKDTree (  csKDTree *    parent )

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.

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

const csBox3& csKDTree::GetObjectBBox (    )

Return the bounding box of all objects in this node.

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 305 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::SetUserObject (  iBase *    userobj )

Set the user object for this node. Can be NULL 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:

• kdtree.h

---