A set data structure that supports spatial queries using an axis-aligned BSP tree for speed. More...

Classes
class	AxisComparator

class	BoxIntersectionIterator
	C++ STL style iterator variable. More...

class	Handle

class	Iterator
	C++ STL style iterator variable. More...

class	Node

Public Member Functions
	PointKDTree ()
	To construct a balanced tree, insert the elements and then call PointKDTree::balance(). More...

	PointKDTree (const PointKDTree &src)

	~PointKDTree ()

void	balance (int valuesPerNode=40, int numMeanSplits=3)
	Rebalances the tree (slow). More...

Iterator	begin () const
	C++ STL style iterator method. More...

BoxIntersectionIterator	beginBoxIntersection (const AABox &box) const
	Iterates through the members that intersect the box More...

void	clear ()
	Throws out all elements of the set and erases the structure of the tree. More...

void	clearData ()
	Removes all elements of the set while maintaining the structure of the tree. More...

bool	contains (const T &value)
	Returns true if this object is in the set, otherwise returns false. More...

void	deserializeStructure (BinaryInput &bi)
	Clears the member table. More...

Iterator	end () const
	C++ STL style iterator method. More...

BoxIntersectionIterator	endBoxIntersection () const

void	getIntersectingMembers (const Array< Plane > &plane, Array< T > &members) const
	Returns all members inside the set of planes. More...

void	getIntersectingMembers (const Frustum &frustum, Array< T > &members) const
	Typically used to find all visible objects inside the view frustum (see also Camera::getClipPlanes)... More...

void	getIntersectingMembers (const AABox &box, Array< T > &members) const
	Appends all members whose bounds intersect the box. More...

void	getIntersectingMembers (const Sphere &sphere, Array< T > &members) const

void	getMembers (Array< T > &members) const
	Returns an array of all members of the set. More...

void	insert (const T &value)
	Inserts an object into the set if it is not already present. More...

void	insert (const Array< T > &valueArray)
	Inserts each elements in the array in turn. More...

PointKDTree &	operator= (const PointKDTree &src)

void	remove (const T &value)
	Removes an object from the set in O(1) time. More...

void	serializeStructure (BinaryOutput &bo) const
	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. More...

size_t	size () const

void	update (const T &value)
	If the element is in the set, it is removed. More...

Protected Types
typedef Table< T, Node *, HashFunc, EqualsFunc >	MemberTable
	Maps members to the node containing them. More...

Protected Member Functions
Node *	cloneTree (Node *src)
	Recursively clone the passed in node tree, setting pointers for members in the memberTable as appropriate. More...

Node *	makeNode (Array< Handle > &source, Array< Handle > &temp, int valuesPerNode, int numMeanSplits)
	Recursively subdivides the subarray. More...

Static Protected Member Functions
static AABox	computeBounds (const Array< Handle > &point)
	Returns the bounds of the sub array. More...

Protected Attributes
MemberTable	memberTable

Node *	root

Detailed Description

template<class T, class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>
class G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >

A set data structure that supports spatial queries using an axis-aligned BSP tree for speed.

PointKDTree allows you to quickly find points in 3D that lie within a box or sphere. For large sets of objects it is much faster than testing each object for a collision. See also G3D::KDTree; this class is optimized for point sets, e.g.,for use in photon mapping and mesh processing.

Template Parameters

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

     T::T(); (public constructor of no arguments)

      template<> struct PositionTrait<class T> {
        static void getPosition(const T& v, G3D::Vector3& p);};

      template <> struct HashTrait<class T> {
        static size_t hashCode(const T& key);};

      template<> struct EqualsTrait<class T> {
          static bool equals(const T& a, const T& b); };

G3D provides these for the Vector2, Vector3, and Vector4 classes. 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 PointKDTree. If the position of an object is about to change, PointKDTree::remove it before they change and PointKDTree::insert it again afterward. For objects where the hashCode and == operator are invariant with respect to the 3D position, you can use the PointKDTree::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 PointKDTree. Values are copied interally. All PointKDTree iterators convert to pointers to constant values to reinforce this.

If you want to mutate the objects you intend to store in a PointKDTree 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 PointKDTree for data distributed along 2 or 1 axes by simply returning bounds that are always zero along one or more dimensions.

Member Typedef Documentation

◆ MemberTable

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

typedef Table<T, Node*, HashFunc, EqualsFunc> G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::MemberTable

protected

Maps members to the node containing them.

Constructor & Destructor Documentation

◆ PointKDTree() [1/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::PointKDTree ( )

inline

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

◆ PointKDTree() [2/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::PointKDTree ( const PointKDTree< T, PositionFunc, HashFunc, EqualsFunc > & src )

inline

◆ ~PointKDTree()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::~PointKDTree ( )

inline

Member Function Documentation

◆ balance()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance	(	int	valuesPerNode = `40`,
		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; all querries will return in the same amount of time.

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 (some areas of the scene will terminate after few recursive splits) at the expense of peak performance.

◆ begin()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Iterator G3D::PointKDTree< T, PositionFunc, 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.

◆ beginBoxIntersection()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

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

inline

Iterates through the members that intersect the box

◆ clear()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clear ( )

inline

Throws out all elements of the set and erases the structure of the tree.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::deserializeStructure(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::~PointKDTree().

◆ clearData()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData ( )

inline

Removes all elements of the set while maintaining the structure of the tree.

◆ cloneTree()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::PointKDTree< T, PositionFunc, 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.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::operator=().

◆ computeBounds()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

static AABox G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::computeBounds ( const Array< Handle > & point )

inlinestaticprotected

Returns the bounds of the sub array.

Used by makeNode.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode().

◆ contains()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

bool G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::contains ( const T & value )

inline

Returns true if this object is in the set, otherwise returns false.

O(1) time.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::remove(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::update().

◆ deserializeStructure()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::deserializeStructure ( BinaryInput & bi )

inline

Clears the member table.

◆ end()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Iterator G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::end ( ) const

inline

C++ STL style iterator method.

Returns one after the last iterator element.

◆ endBoxIntersection()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

BoxIntersectionIterator G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::endBoxIntersection ( ) const

inline

◆ getIntersectingMembers() [1/4]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

◆ getIntersectingMembers() [2/4]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

◆ getIntersectingMembers() [3/4]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

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

inline

Appends all members whose bounds intersect the box.

◆ getIntersectingMembers() [4/4]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

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

inline

Parameters

members The results are appended to this array.

◆ getMembers()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

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

inline

Returns an array of all members of the set.

◆ insert() [1/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert(), and G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::update().

◆ insert() [2/2]

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

◆ makeNode()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

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

inlineprotected

Recursively subdivides the subarray.

The source array will be cleared after it is used

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

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance().

◆ operator=()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

PointKDTree& G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::operator= ( const PointKDTree< T, PositionFunc, HashFunc, EqualsFunc > & src )

inline

◆ remove()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

◆ serializeStructure()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

◆ size()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

size_t G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::size ( ) const

inline

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert().

◆ update()

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

void G3D::PointKDTree< T, PositionFunc, 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.

Member Data Documentation

◆ memberTable

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

MemberTable G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::memberTable

protected

◆ root

template<class T , class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>

Node* G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::root

protected

Classes

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<class T, class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>> class G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >

Member Typedef Documentation

◆ MemberTable

Constructor & Destructor Documentation

◆ PointKDTree() [1/2]

◆ PointKDTree() [2/2]

◆ ~PointKDTree()

Member Function Documentation

◆ balance()

◆ begin()

◆ beginBoxIntersection()

◆ clear()

◆ clearData()

◆ cloneTree()

◆ computeBounds()

◆ contains()

◆ deserializeStructure()

◆ end()

◆ endBoxIntersection()

◆ getIntersectingMembers() [1/4]

◆ getIntersectingMembers() [2/4]

◆ getIntersectingMembers() [3/4]

◆ getIntersectingMembers() [4/4]

◆ getMembers()

◆ insert() [1/2]

◆ insert() [2/2]

◆ makeNode()

◆ operator=()

◆ remove()

◆ serializeStructure()

◆ size()

◆ update()

Member Data Documentation

◆ memberTable

◆ root

template<class T, class PositionFunc = PositionTrait<T>, class HashFunc = HashTrait<T>, class EqualsFunc = EqualsTrait<T>>
class G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >