G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc > Class Template Reference

#include <KDTree.h>

Classes
class	BoundsComparator
class	BoxIntersectionIterator
class	CenterComparator
class	Comparator
class	Handle
class	Iterator
class	Node

Public Member Functions
	KDTree ()
	KDTree (const KDTree &src)
KDTree &	operator= (const KDTree &src)
	~KDTree ()
void	clear ()
int	size () const
void	insert (const T &value)
void	insert (const Array< T > &valueArray)
bool	contains (const T &value)
void	remove (const T &value)
void	update (const T &value)
void	balance (int valuesPerNode=5, int numMeanSplits=3)
void	setContents (const Array< T > &array, int valuesPerNode=5, int numMeanSplits=3)
void	getIntersectingMembers (const Array< Plane > &plane, Array< T * > &members) const
void	getIntersectingMembers (const Array< Plane > &plane, Array< T > &members) const
void	getIntersectingMembers (const Frustum &frustum, Array< T * > &members) const
void	getIntersectingMembers (const Frustum &frustum, Array< T > &members) const
BoxIntersectionIterator	beginBoxIntersection (const AABox &box) const
BoxIntersectionIterator	endBoxIntersection () const
void	getIntersectingMembers (const AABox &box, Array< T * > &members) const
void	getIntersectingMembers (const AABox &box, Array< T > &members) const
template<typename RayCallback >
void	intersectRay (const Ray &ray, RayCallback &intersectCallback, float &distance, bool intersectCallbackIsFast=false) const
void	getIntersectingMembers (const Sphere &sphere, Array< T * > &members) const
	Finds all members whose bounding boxes intersect the sphere. The actual elements may not intersect the sphere. More...
void	getIntersectingMembers (const Sphere &sphere, Array< T > &members) const
void	serializeStructure (BinaryOutput &bo) const
void	deserializeStructure (BinaryInput &bi)
void	getMembers (Array< T > &members) const
const T *	getPointer (const T &value) const
Iterator	begin () const
Iterator	end () const

Protected Types
typedef _internal::Indirector < Handle >	Member
typedef Table< Member, Node * >	MemberTable

Protected Member Functions
Node *	makeNode (Array< Handle * > &source, int valuesPerNode, int numMeanSplits, Array< Handle * > &temp)
Node *	cloneTree (Node *src)

Static Protected Member Functions
static AABox	computeBounds (const Array< Handle * > &point, int beginIndex, int endIndex)
static void	getIntersectingMembers (const Array< Plane > &plane, Array< T * > &members, Node *node, uint32 parentMask)

Protected Attributes
MemberTable	memberTable
Node *	root

Detailed Description

template<class T, class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>
class G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >

A set that supports spatial queries using a KD tree (axis-aligned BSP tree) for speed.

KDTree allows you to quickly find objects in 3D that lie within a box or along a ray. For large sets of objects it is much faster than testing each object for a collision.

KDTree is as powerful as but more general than a Quad Tree, Oct Tree, or regular KD tree that cycles through axes, but less general than an unconstrained BSP tree (which is much slower to create).

Internally, objects are arranged into a tree according to their axis-aligned bounds. This increases the cost of insertion to O(log n) but allows fast overlap queries.

Template Parameters

The template parameter T must be one for which the following functions are all overloaded:

 T::T(); // public constructor of no arguments
 template <> struct HashTrait<T> { static size_t hashCode(int key); };
 template<> struct BoundsTrait<T> { static void getBounds(const T& obj, G3D::AABox& out); };

G3D provides these for common classes like G3D::Vector3 and G3D::Sphere. If you use a custom class, or a pointer to a custom class, you will need to define those functions.

Moving Set Members

It is important that objects do not move without updating the KDTree. If the axis-aligned bounds of an object are about to change, KDTree::remove it before they change and KDTree::insert it again afterward. For objects where the hashCode and == operator are invariant with respect to the 3D position, you can use the KDTree::update method as a shortcut to insert/remove an object in one step after it has moved.

Note: Do not mutate any value once it has been inserted into KDTree. Values are copied interally. All KDTree iterators convert to pointers to constant values to reinforce this.

If you want to mutate the objects you intend to store in a KDTree simply insert pointers to your objects instead of the objects themselves, and ensure that the above operations are defined. (And actually, because values are copied, if your values are large you may want to insert pointers anyway, to save space and make the balance operation faster.)

Dimensions Although designed as a 3D-data structure, you can use the KDTree for data distributed along 2 or 1 axes by simply returning bounds that are always zero along one or more dimensions.

Member Typedef Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

typedef _internal::Indirector<Handle> G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Member

protected

Wrapper for a Handle; used to create a memberTable that acts like Table<Handle, Node*> but stores only Handle* internally to avoid memory copies.

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

typedef Table<Member, Node*> G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::MemberTable

protected

Constructor & Destructor Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::KDTree ( )

inline

To construct a balanced tree, insert the elements and then call KDTree::balance().

: root(NULL) {}

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::KDTree ( const KDTree< T, BoundsFunc, HashFunc, EqualsFunc > &  src )

inline

 : root(NULL) {
 *this = src;
 }

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::~KDTree ( )

inline

 {
 clear();
 }

Here is the call graph for this function:

Member Function Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::balance ( int  valuesPerNode = 5, int  numMeanSplits = 3  )

inline

Rebalances the tree (slow). Call when objects have moved substantially from their original positions (which unbalances the tree and causes the spatial queries to be slow).

Parameters

valuesPerNode	Maximum number of elements to put at a node.
numMeanSplits	numMeanSplits = 0 gives a fully axis aligned BSP-tree, where the balance operation attempts to balance the tree so that every splitting plane has an equal number of left and right children (i.e. it is a median split along that axis). This tends to maximize average performance.

You can override this behavior by setting a number of mean (average) splits. numMeanSplits = MAX_INT creates a full oct-tree, which tends to optimize peak performance at the expense of average performance. It tends to have better clustering behavior when members are not uniformly distributed.

 {
 if (root == NULL) {
 // Tree is empty
 return;
 }

 // Get all handles and delete the old tree structure
 Node* oldRoot = root;
 for (int c = 0; c < 2; ++c) {
 if (root->child[c] != NULL) {
 root->child[c]->getHandles(root->valueArray);

 // Delete the child; this will delete all structure below it
 delete root->child[c];
 root->child[c] = NULL;
 }
 }

 Array<Handle*> temp;
 // Make a new root. Work with a copy of the value array because 
 // makeNode clears the source array as it progresses
 Array<Handle*> copy(oldRoot->valueArray);
 root = makeNode(copy, valuesPerNode, numMeanSplits, temp);

 // Throw away the old root node
 delete oldRoot;
 oldRoot = NULL;

 // Walk the tree, assigning splitBounds. We start with unbounded
 // space. This will override the current member table.
 const AABox& LARGE = AABox::large();
 root->assignSplitBounds(LARGE);

# ifdef _DEBUG
 {
 // Ensure that the balanced tree is still correct
 root->verifyNode(LARGE.low(), LARGE.high());
 }
# endif
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Iterator G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::begin ( ) const

inline

C++ STL style iterator method. Returns the first member. Use preincrement (++entry) to get to the next element (iteration order is arbitrary). Do not modify the set while iterating.

 {
 return Iterator(memberTable.begin());
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

BoxIntersectionIterator G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::beginBoxIntersection ( const AABox &  box ) const

inline

Iterates through the members that intersect the box

 {
 return BoxIntersectionIterator(box, root);
 }

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::clear ( )

inline

Throws out all elements of the set.

 {
 typedef typename Table<_internal::Indirector<Handle>, Node*>::Iterator It;
 
 // Delete all handles stored in the member table
 It cur = memberTable.begin();
 It end = memberTable.end();
 while (cur != end) {
 delete cur->key.handle;
 cur->key.handle = NULL;
 ++cur;
 }
 memberTable.clear();

 // Delete the tree structure itself
 delete root;
 root = NULL;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::cloneTree ( Node *  src )

inlineprotected

Recursively clone the passed in node tree, setting pointers for members in the memberTable as appropriate. called by the assignment operator.

 {
 Node* dst = new Node(*src);

 // Make back pointers
 for (int i = 0; i < dst->valueArray.size(); ++i) {
 memberTable.set(Member(dst->valueArray[i]), dst);
 }

 // Clone children
 for (int i = 0; i < 2; ++i) {
 if (src->child[i] != NULL) {
 dst->child[i] = cloneTree(src->child[i]);
 }
 }

 return dst;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

static AABox G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::computeBounds ( const Array< Handle * > &  point, int  beginIndex, int  endIndex  )

inlinestaticprotected

Returns the bounds of the sub array. Used by makeNode.

 {
 
 Vector3 lo = Vector3::inf();
 Vector3 hi = -lo;

 debugAssertM(beginIndex <= endIndex, "No points");
 for (int p = beginIndex; p <= endIndex; ++p) {
 // This code is written with the vector min and max expanded
 // because otherwise it compiles incorrectly with -O3 on
 // gcc 3.4 

 const Vector3& pLo = point[p]->bounds.low();
 const Vector3& pHi = point[p]->bounds.high();
 for (int a = 0; a < 3; ++a) {
 lo[a] = G3D::min(lo[a], pLo[a]);
 hi[a] = G3D::max(hi[a], pHi[a]);
 }
 }

 return AABox(lo, hi);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::contains ( const T &  value )

inline

Returns true if this object is in the set, otherwise returns false. O(1) time.

 {
 // Temporarily create a handle and member
 Handle h(value);
 return memberTable.containsKey(Member(&h));
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::deserializeStructure ( BinaryInput &  bi )

inline

Clears the member table

 {
 clear();
 root = Node::deserializeStructure(bi);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Iterator G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::end ( ) const

inline

C++ STL style iterator method. Returns one after the last iterator element.

 {
 return Iterator(memberTable.end());
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

BoxIntersectionIterator G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::endBoxIntersection ( ) const

inline

 {
 // The "end" iterator instance
 return BoxIntersectionIterator();
 }

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

static void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Array< Plane > &  plane, Array< T * > &  members, Node *  node, uint32  parentMask  )

inlinestaticprotected

Parameters

parentMask

The mask that this node returned from culledBy.

 {

 int dummy;

 if (parentMask == 0) {
 // None of these planes can cull anything
 for (int v = node->valueArray.size() - 1; v >= 0; --v) {
 members.append(& (node->valueArray[v]->value));
 }

 // Iterate through child nodes
 for (int c = 0; c < 2; ++c) {
 if (node->child[c]) {
 getIntersectingMembers(plane, members, node->child[c], 0);
 }
 }
 } else {

 // Test values at this node against remaining planes
 for (int v = node->boundsArray.size() - 1; v >= 0; --v) {
 if (! node->boundsArray[v].culledBy(plane, dummy, parentMask)) {
 members.append(&(node->valueArray[v]->value));
 }
 }

 uint32 childMask = 0xFFFFFF;

 // Iterate through child nodes
 for (int c = 0; c < 2; ++c) {
 if (node->child[c] &&
 ! node->child[c]->splitBounds.culledBy(plane, dummy, parentMask, childMask)) {
 // This node was not culled
 getIntersectingMembers(plane, members, node->child[c], childMask);
 }
 }
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Array< Plane > &  plane, Array< T * > &  members  ) const

inline

Returns all members inside the set of planes.

Parameters

members

The results are appended to this array.

 {
 if (root == NULL) {
 return;
 }

 getIntersectingMembers(plane, members, root, 0xFFFFFF);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Array< Plane > &  plane, Array< T > &  members  ) const

inline

 {
 Array<T*> temp;
 getIntersectingMembers(plane, temp, root, 0xFFFFFF);
 for (int i = 0; i < temp.size(); ++i) {
 members.append(*temp[i]);
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Frustum &  frustum, Array< T * > &  members  ) const

inline

Typically used to find all visible objects inside the view frustum (see also Camera::getClipPlanes)... i.e. all objects not culled by frustum.

Example:

   Array<Object*>  visible;
   tree.getIntersectingMembers(camera.frustum(), visible);
   // ... Draw all objects in the visible array.
 

Parameters

members

The results are appended to this array.

 {
 Array<Plane> plane;
 
 for (int i = 0; i < frustum.faceArray.size(); ++i) {
 plane.append(frustum.faceArray[i].plane);
 }

 getIntersectingMembers(plane, members);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Frustum &  frustum, Array< T > &  members  ) const

inline

 {
 Array<T*> temp;
 getIntersectingMembers(frustum, temp);
 for (int i = 0; i < temp.size(); ++i) {
 members.append(*temp[i]);
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const AABox &  box, Array< T * > &  members  ) const

inline

Appends all members whose bounds intersect the box. See also KDTree::beginBoxIntersection.

 {
 if (root == NULL) {
 return;
 }
 root->getIntersectingMembers(box, Sphere(Vector3::zero(), 0), members, false);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const AABox &  box, Array< T > &  members  ) const

inline

 {
 Array<T*> temp;
 getIntersectingMembers(box, temp);
 for (int i = 0; i < temp.size(); ++i) {
 members.append(*temp[i]);
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Sphere &  sphere, Array< T * > &  members  ) const

inline

Finds all members whose bounding boxes intersect the sphere. The actual elements may not intersect the sphere.

Parameters

members

The results are appended to this array.

 {
 if (root == NULL) {
 return;
 }

 AABox box;
 sphere.getBounds(box);
 root->getIntersectingMembers(box, sphere, members, true);
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers ( const Sphere &  sphere, Array< T > &  members  ) const

inline

 {
 Array<T*> temp;
 getIntersectingMembers(sphere, temp);
 for (int i = 0; i < temp.size(); ++i) {
 members.append(*temp[i]);
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getMembers ( Array< T > &  members ) const

inline

Returns an array of all members of the set. See also KDTree::begin.

 {
 Array<Member> temp;
 memberTable.getKeys(temp);
 for (int i = 0; i < temp.size(); ++i) {
 members.append(*(temp.handle));
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

const T* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getPointer ( const T &  value ) const

inline

If a value that is EqualsFunc to value is present, returns a pointer to the version stored in the data structure, otherwise returns NULL.

 {
 // Temporarily create a handle and member
 Handle h(value);
 const Member* member = memberTable.getKeyPointer(Member(&h));
 if (member == NULL) {
 // Not found
 return NULL;
 } else {
 return &(member->handle->value);
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::insert ( const T &  value )

inline

Inserts an object into the set if it is not already present. O(log n) time. Does not cause the tree to be balanced.

 {
 if (contains(value)) {
 // Already in the set
 return;
 }

 Handle* h = new Handle(value);

 if (root == NULL) {
 // This is the first node; create a root node
 root = new Node();
 }

 Node* node = root->findDeepestContainingNode(h->bounds);

 // Insert into the node
 node->valueArray.append(h);
 node->boundsArray.append(h->bounds);
 
 // Insert into the node table
 Member m(h);
 memberTable.set(m, node);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::insert ( const Array< T > &  valueArray )

inline

Inserts each elements in the array in turn. If the tree begins empty (no structure and no elements), this is faster than inserting each element in turn. You still need to balance the tree at the end.

 {
 if (root == NULL) {
 // Optimized case for an empty tree; don't bother
 // searching or reallocating the root node's valueArray
 // as we incrementally insert.
 root = new Node();
 root->valueArray.resize(valueArray.size());
 root->boundsArray.resize(root->valueArray.size());
 for (int i = 0; i < valueArray.size(); ++i) {
 // Insert in opposite order so that we have the exact same
 // data structure as if we inserted each (i.e., order is reversed
 // from array).
 Handle* h = new Handle(valueArray[i]);
 int j = valueArray.size() - i - 1;
 root->valueArray[j] = h;
 root->boundsArray[j] = h->bounds;
 memberTable.set(Member(h), root);
 }

 } else {
 // Insert at appropriate tree depth.
 for (int i = 0; i < valueArray.size(); ++i) {
 insert(valueArray[i]);
 }
 }
 }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

template<typename RayCallback >

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::intersectRay ( const Ray &  ray, RayCallback &  intersectCallback, float &  distance, bool  intersectCallbackIsFast = false  ) const

inline

Invoke a callback for every member along a ray until the closest intersection is found.

Parameters

intersectCallback	Either a function or an instance of a class with an overloaded operator() of the form: void callback(const Ray& ray, const T& object, float& distance). If the ray hits the object before travelling distance distance, updates distance with the new distance to the intersection, otherwise leaves it unmodified. A common example is: class Entity { public: void intersect(const Ray& ray, float& maxDist, Vector3& outLocation, Vector3& outNormal) { float d = maxDist; // ... search for intersection distance d if ((d > 0) && (d < maxDist)) { // Intersection occured maxDist = d; outLocation = ...; outNormal = ...; } } }; // Finds the surface normal and location of the first intersection with the scene class Intersection { public: Entity* closestEntity; Vector3 hitLocation; Vector3 hitNormal; void operator()(const Ray& ray, const Entity* entity, float& distance) { entity->intersect(ray, distance, hitLocation, hitNormal); } }; KDTree scene; Intersection intersection; float distance = finf(); scene.intersectRay(camera.worldRay(x, y), intersection, distance);
distance	When the method is invoked, this is the maximum distance that the tree should search for an intersection. On return, this is set to the distance to the first intersection encountered.
intersectCallbackIsFast	If false, each object's bounds are tested before the intersectCallback is invoked. If the intersect callback runs at the same speed or faster than AABox-ray intersection, set this to true.

                                                    {
        
        root->intersectRay(ray, intersectCallback, distance, intersectCallbackIsFast);
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::makeNode ( Array< Handle * > &  source, int  valuesPerNode, int  numMeanSplits, Array< Handle * > &  temp  )

inlineprotected

Recursively subdivides the subarray.

Clears the source array as soon as it is no longer needed.

Call assignSplitBounds() on the root node after making a tree.

                               {

        Node* node = NULL;
        
        if (source.size() <= valuesPerNode) {
            // Make a new leaf node
            node = new Node(source);
            
            // Set the pointers in the memberTable
            for (int i = 0; i < source.size(); ++i) {
                memberTable.set(Member(source[i]), node);
            }
            source.clear();
            
        } else {
            // Make a new internal node
            node = new Node();
            
            const AABox& bounds = computeBounds(source, 0, source.size() - 1);
            const Vector3& extent = bounds.high() - bounds.low();
            
            Vector3::Axis splitAxis = extent.primaryAxis();
            
            float splitLocation;

            // Arrays for holding the children
            Array<Handle*> lt, gt;
                
            if (numMeanSplits <= 0) {

                source.medianPartition(lt, node->valueArray, gt, temp, CenterComparator(splitAxis));

                // Choose the split location to be the center of whatever fell in the center
                splitLocation = node->valueArray[0]->center[splitAxis];

                // Some of the elements in the lt or gt array might really overlap the split location.
                // Move them as needed.
                for (int i = 0; i < lt.size(); ++i) {
                    const AABox& bounds = lt[i]->bounds;
                    if ((bounds.low()[splitAxis] <= splitLocation) && (bounds.high()[splitAxis] >= splitLocation)) {
                        node->valueArray.append(lt[i]);
                        // Remove this element and process the new one that
                        // is swapped in in its place.
                        lt.fastRemove(i); --i;
                    }
                }

                for (int i = 0; i < gt.size(); ++i) {
                    const AABox& bounds = gt[i]->bounds;
                    if ((bounds.low()[splitAxis] <= splitLocation) && (bounds.high()[splitAxis] >= splitLocation)) {
                        node->valueArray.append(gt[i]);
                        // Remove this element and process the new one that
                        // is swapped in in its place.
                        gt.fastRemove(i); --i;
                    }
                }            

                if ((node->valueArray.size() > (source.size() / 2)) &&
                    (source.size() > 6)) {
                    // This was a bad partition; we ended up putting the splitting plane right in the middle of most of the 
                    // objects.  We could try to split on a different axis, or use a different partition (e.g., the extents mean, 
                    // or geometric mean).  This implementation falls back on the extents mean, since that case is already handled 
                    // below.
                    numMeanSplits = 1;
                }
            }

            // Note: numMeanSplits may have been increased by the code in the previous case above in order to
            // force a re-partition.

            if (numMeanSplits > 0) {
                // Split along the mean
                splitLocation = 
                    bounds.high()[splitAxis] * 0.5f + 
                    bounds.low()[splitAxis] * 0.5f;
                
                debugAssertM(isFinite(splitLocation),
                            "Internal error: split location must be finite.");

                source.partition(NULL, lt, node->valueArray, gt, Comparator(splitAxis, splitLocation));

                // The Comparator ensures that elements are strictly on the correct side of the split
            }


#           if defined(G3D_DEBUG) && defined(VERIFY_TREE)
                debugAssert(lt.size() + node->valueArray.size() + gt.size() == source.size());
                // Verify that all objects ended up on the correct side of the split.
                // (i.e., make sure that the Array partition was correct) 
                for (int i = 0; i < lt.size(); ++i) {
                    const AABox& bounds  = lt[i]->bounds;
                    debugAssert(bounds.high()[splitAxis] < splitLocation);
                }

                for (int i = 0; i < gt.size(); ++i) {
                    const AABox& bounds  = gt[i]->bounds;
                    debugAssert(bounds.low()[splitAxis] > splitLocation);
                }

                for (int i = 0; i < node->valueArray.size(); ++i) {
                    const AABox& bounds  = node->valueArray[i]->bounds;
                    debugAssert(bounds.high()[splitAxis] >= splitLocation);
                    debugAssert(bounds.low()[splitAxis] <= splitLocation);
                }
#           endif

            // The source array is no longer needed
            source.clear();

            node->splitAxis = splitAxis;
            node->splitLocation = splitLocation;

            // Update the bounds array and member table
            node->boundsArray.resize(node->valueArray.size());
            for (int i = 0; i < node->valueArray.size(); ++i) {
                Handle* v = node->valueArray[i];
                node->boundsArray[i] = v->bounds;
                memberTable.set(Member(v), node);
            }

            if (lt.size() > 0) {            
                node->child[0] = makeNode(lt, valuesPerNode, numMeanSplits - 1, temp);
            }
            
            if (gt.size() > 0) {
                node->child[1] = makeNode(gt, valuesPerNode, numMeanSplits - 1, temp);
            }
            
        }
        
        return node;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

KDTree& G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::operator= ( const KDTree< T, BoundsFunc, HashFunc, EqualsFunc > &  src )

inline

                                         {
        delete root;
        // Clone tree takes care of filling out the memberTable.
        root = cloneTree(src.root);
        return *this;
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::remove ( const T &  value )

inline

Removes an object from the set in O(1) time. It is an error to remove members that are not already present. May unbalance the tree.

Removing an element never causes a node (split plane) to be removed... nodes are only changed when the tree is rebalanced. This behavior is desirable because it allows the split planes to be serialized, and then deserialized into an empty tree which can be repopulated.

                                {
        debugAssertM(contains(value),
            "Tried to remove an element from a "
            "KDTree that was not present");

        // Get the list of elements at the node
        Handle h(value);
        Member m(&h);

        Array<Handle*>& list = memberTable[m]->valueArray;

        Handle* ptr = NULL;

        // Find the element and remove it
        for (int i = list.length() - 1; i >= 0; --i) {
            if (list[i]->value == value) {
                // This was the element.  Grab the pointer so that
                // we can delete it below
                ptr = list[i];

                // Remove the handle from the node
                list.fastRemove(i);

                // Remove the corresponding bounds
                memberTable[m]->boundsArray.fastRemove(i);
                break;
            }
        }

        // Remove the member
        memberTable.remove(m);

        // Delete the handle data structure
        delete ptr;
        ptr = NULL;
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::serializeStructure ( BinaryOutput &  bo ) const

inline

Stores the locations of the splitting planes (the structure but not the content) so that the tree can be quickly rebuilt from a previous configuration without calling balance.

                                                    {
        Node::serializeStructure(root, bo);
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::setContents ( const Array< T > &  array, int  valuesPerNode = 5, int  numMeanSplits = 3  )

inline

Clear, set the contents to the values in the array, and then balance

                                                                                          {
        clear();
        insert(array);
        balance(valuesPerNode, numMeanSplits);
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

int G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::size ( ) const

inline

                     {
        return memberTable.size();
    }

Here is the call graph for this function:

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::update ( const T &  value )

inline

If the element is in the set, it is removed. The element is then inserted.

This is useful when the == and hashCode methods on T are independent of the bounds. In that case, you may call update(v) to insert an element for the first time and call update(v) again every time it moves to keep the tree up to date.

                                {
        if (contains(value)) {
            remove(value);
        }
        insert(value);
    }

Here is the call graph for this function:

Member Data Documentation

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

MemberTable G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::memberTable

protected

Maps members to the node containing them

template<class T , class BoundsFunc = BoundsTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::root

protected

---

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

• dep/g3dlite/include/G3D/KDTree.h