Public Member Functions
	Node ()
	Creates node with nullptr children. More...

	Node (const Node &other)
	Doesn't clone children. More...

	Node (const Array< Handle *> &pt)
	Copies the specified subarray of pt into point, NULLs the children. More...

	~Node ()
	Deletes the children (but not the values) More...

void	assignSplitBounds (const AABox &myBounds)
	Recurse through the tree, assigning splitBounds fields. More...

Node *	findDeepestContainingNode (const AABox &bounds)
	Returns the deepest node that completely contains bounds. More...

void	getHandles (Array< Handle *> &handleArray) const
	Recursively appends all handles and children's handles to the array. More...

void	getIntersectingMembers (const AABox &box, const Sphere &sphere, Array< T *> &members, bool useSphere) const
	Appends all members that intersect the box. More...

template<typename RayCallback >
void	intersectRay (const Ray &ray, RayCallback &intersectCallback, float &distance, bool intersectCallbackIsFast) const

bool	intersects (const Ray &ray, float distance) const
	Returns true if the ray intersects this node. More...

bool	isLeaf () const
	Returns true if this node is a leaf (no children) More...

void	verifyNode (const Vector3 &lo, const Vector3 &hi)

Static Public Member Functions
static Node *	deserializeStructure (BinaryInput &bi)
	Clears the member table. More...

static void	serializeStructure (const Node *n, BinaryOutput &bo)
	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...

Public Attributes
Array< AABox >	boundsArray
	For each object in the value array, a copy of its bounds. More...

Node *	child [2]
	child[0] contains all values strictly smaller than splitLocation along splitAxis. More...

Vector3::Axis	splitAxis

AABox	splitBounds
	Spatial bounds on all values at this node and its children, based purely on the parent's splitting planes. More...

float	splitLocation
	Location along the specified axis. More...

Array< Handle * >	valueArray
	Array of values at this node (i.e., values straddling the split plane + all values if this is a leaf node). More...

Constructor & Destructor Documentation

◆ Node() [1/3]

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

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

inline

Creates node with nullptr children.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::deserializeStructure().

◆ Node() [2/3]

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

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

inline

Doesn't clone children.

◆ Node() [3/3]

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

G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::Node ( const Array< Handle *> & pt )

inline

Copies the specified subarray of pt into point, NULLs the children.

Assumes a second pass will set splitBounds.

◆ ~Node()

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

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

inline

Deletes the children (but not the values)

Member Function Documentation

◆ assignSplitBounds()

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

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds ( const AABox & myBounds )

inline

Recurse through the tree, assigning splitBounds fields.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::balance().

◆ deserializeStructure()

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

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

inlinestatic

Clears the member table.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::deserializeStructure().

◆ findDeepestContainingNode()

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

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode ( const AABox & bounds )

inline

Returns the deepest node that completely contains bounds.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::insert().

◆ getHandles()

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

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::getHandles ( Array< Handle *> & handleArray ) const

inline

Recursively appends all handles and children's handles to the array.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::balance(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::getHandles().

◆ getIntersectingMembers()

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

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

inline

Appends all members that intersect the box.

If useSphere is true, members that pass the box test face a second test against the sphere.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers().

◆ intersectRay()

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 >::Node::intersectRay	(	const Ray &	ray,
		RayCallback &	intersectCallback,
		float &	distance,
		bool	intersectCallbackIsFast
	)		const

inline

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::intersectRay(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::intersectRay().

◆ intersects()

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

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::intersects	(	const Ray &	ray,
		float	distance
	)		const

inline

Returns true if the ray intersects this node.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::intersectRay().

◆ isLeaf()

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

bool G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::isLeaf ( ) const

inline

Returns true if this node is a leaf (no children)

◆ serializeStructure()

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

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

inlinestatic

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.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::serializeStructure().

◆ verifyNode()

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

void G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::verifyNode	(	const Vector3 &	lo,
		const Vector3 &	hi
	)

inline

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::balance(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::verifyNode().

Member Data Documentation

◆ boundsArray

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

Array<AABox> G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::boundsArray

For each object in the value array, a copy of its bounds.

Packing these into an array at the node level instead putting them in the valueArray improves cache coherence, which is about a 3x performance increase when performing intersection computations.

◆ child

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

Node* G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::child[2]

child[0] contains all values strictly smaller than splitLocation along splitAxis.

child[1] contains all values strictly larger.

Both may be nullptr if there are not enough values to bother recursing.

◆ splitAxis

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

Vector3::Axis G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::splitAxis

◆ splitBounds

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

AABox G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::splitBounds

Spatial bounds on all values at this node and its children, based purely on the parent's splitting planes.

May be infinite.

Referenced by G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::assignSplitBounds(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::deserializeStructure(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::getIntersectingMembers(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::intersects(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::Node(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::serializeStructure(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::verifyNode().

◆ splitLocation

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

float G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::splitLocation

Location along the specified axis.

◆ valueArray

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

Array<Handle*> G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::valueArray

Array of values at this node (i.e., values straddling the split plane + all values if this is a leaf node).

This is an array of pointers because that minimizes data movement during tree building, which accounts for about 15% of the time cost of tree building.

Public Member Functions

Static Public Member Functions

Public Attributes

Constructor & Destructor Documentation

◆ Node() [1/3]

◆ Node() [2/3]

◆ Node() [3/3]

◆ ~Node()

Member Function Documentation

◆ assignSplitBounds()

◆ deserializeStructure()

◆ findDeepestContainingNode()

◆ getHandles()

◆ getIntersectingMembers()

◆ intersectRay()

◆ intersects()

◆ isLeaf()

◆ serializeStructure()

◆ verifyNode()

Member Data Documentation

◆ boundsArray

◆ child

◆ splitAxis

◆ splitBounds

◆ splitLocation

◆ valueArray