G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node Class Reference

#include <PointKDTree.h>

Public Member Functions
	Node ()
	Node (const Node &other)
	Node (const Array< Handle > &pt)
	~Node ()
bool	isLeaf () const
void	getHandles (Array< Handle > &handleArray) const
void	verifyNode (const Vector3 &lo, const Vector3 &hi)
Node *	findDeepestContainingNode (const Vector3 &point)
void	getIntersectingMembers (const AABox &sphereBounds, const Sphere &sphere, Array< T > &members) const
void	getIntersectingMembers (const AABox &box, const Sphere &sphere, Array< T > &members, bool useSphere) const
void	assignSplitBounds (const AABox &myBounds)

Static Public Member Functions
static void	serializeStructure (const Node *n, BinaryOutput &bo)
static Node *	deserializeStructure (BinaryInput &bi)

Public Attributes
AABox	splitBounds
Vector3::Axis	splitAxis
float	splitLocation
Node *	child [2]
Array< Handle >	valueArray

Constructor & Destructor Documentation

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

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

inline

Creates node with NULL children

 {
 splitAxis = Vector3::X_AXIS;
 splitLocation = 0;
 splitBounds = AABox(-Vector3::inf(), Vector3::inf());
 for (int i = 0; i < 2; ++i) {
 child[i] = NULL;
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

inline

Doesn't clone children.

 : valueArray(other.valueArray) {
 splitAxis = other.splitAxis;
 splitLocation = other.splitLocation;
 splitBounds = other.splitBounds; 
 for (int i = 0; i < 2; ++i) {
 child[i] = NULL;
 }
 }

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

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

 {
 splitAxis = Vector3::X_AXIS;
 splitLocation = 0;
 for (int i = 0; i < 2; ++i) {
 child[i] = NULL;
 }
 valueArray = pt;
 }

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

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

inline

Deletes the children (but not the values)

 {
 for (int i = 0; i < 2; ++i) {
 delete child[i];
 }
 }

Member Function Documentation

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

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

inline

Recurse through the tree, assigning splitBounds fields.

 {
 splitBounds = myBounds;

# ifdef G3D_DEBUG
 if (child[0] || child[1]) {
 debugAssert(splitBounds.high()[splitAxis] > splitLocation);
 debugAssert(splitBounds.low()[splitAxis] < splitLocation);
 }
# endif

 AABox childBounds[2];
 myBounds.split(splitAxis, splitLocation, childBounds[0], childBounds[1]);

 for (int c = 0; c < 2; ++c) {
 if (child[c]) {
 child[c]->assignSplitBounds(childBounds[c]);
 }
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

inlinestatic

Clears the member table

 {
 if (bi.readUInt8() == 0) {
 return NULL;
 } else {
 Node* n = new Node();
 n->splitBounds.deserialize(bi);
 deserialize(n->splitAxis, bi);
 n->splitLocation = bi.readFloat32();
 for (int c = 0; c < 2; ++c) {
 n->child[c] = deserializeStructure(bi);
 }
 return n;
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Node* G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::findDeepestContainingNode ( const Vector3 &  point )

inline

Returns the deepest node that completely contains bounds.

 {

 // See which side of the splitting plane the bounds are on
 if (point[splitAxis] < splitLocation) {
 // Point is on the low side. Recurse into the child
 // if it exists.
 if (child[0] != NULL) {
 return child[0]->findDeepestContainingNode(point);
 }
 } else if (point[splitAxis] > splitLocation) {
 // Point is on the high side, recurse into the child
 // if it exists.
 if (child[1] != NULL) {
 return child[1]->findDeepestContainingNode(point);
 }
 }

 // There was no containing child, so this node is the
 // deepest containing node.
 return this;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

void G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles ( Array< Handle > &  handleArray ) const

inline

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

 {
 handleArray.append(valueArray);
 for (int i = 0; i < 2; ++i) {
 if (child[i] != NULL) {
 child[i]->getHandles(handleArray);
 }
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

inline

Appends all members that intersect the box. If useSphere is true, members are tested against the sphere instead.

 {

 // Test all values at this node. Extract the
 // underlying C array for speed
 const int N = valueArray.size();
 const Handle* handleArray = valueArray.getCArray();
 
 const float r2 = square(sphere.radius);

 // Copy the sphere center so that it is on the stack near the radius
 const Vector3 center = sphere.center; 
 for (int v = 0; v < N; ++v) {
 if ((center - handleArray[v].position()).squaredLength() <= r2) {
 members.append(handleArray[v].value);
 }
 }

 // If the left child overlaps the box, recurse into it
 if (child[0] && (sphereBounds.low()[splitAxis] < splitLocation)) {
 child[0]->getIntersectingMembers(sphereBounds, sphere, members);
 }

 // If the right child overlaps the box, recurse into it
 if (child[1] && (sphereBounds.high()[splitAxis] > splitLocation)) {
 child[1]->getIntersectingMembers(sphereBounds, sphere, members);
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

void G3D::PointKDTree< T, PositionFunc, 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 are tested against the sphere instead.

Implemented using both box and sphere tests to simplify the implementation of a future beginSphereInteresection iterator using the same underlying BoxIterator class.

 {

 // Test all values at this node
 for (int v = 0; v < valueArray.size(); ++v) {
 if ((useSphere && sphere.contains(valueArray[v].position())) ||
 (! useSphere && box.contains(valueArray[v].position()))) {
 members.append(valueArray[v].value);
 }
 }

 // If the left child overlaps the box, recurse into it
 if ((child[0] != NULL) && (box.low()[splitAxis] < splitLocation)) {
 child[0]->getIntersectingMembers(box, sphere, members, useSphere);
 }

 // If the right child overlaps the box, recurse into it
 if ((child[1] != NULL) && (box.high()[splitAxis] > splitLocation)) {
 child[1]->getIntersectingMembers(box, sphere, members, useSphere);
 }
 }

Here is the call graph for this function:

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

bool G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::isLeaf ( ) const

inline

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

 {
 return (child[0] == NULL) && (child[1] == NULL);
 }

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

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

 {
 if (n == NULL) {
 bo.writeUInt8(0);
 } else {
 bo.writeUInt8(1);
 n->splitBounds.serialize(bo);
 serialize(n->splitAxis, bo);
 bo.writeFloat32(n->splitLocation);
 for (int c = 0; c < 2; ++c) {
 serializeStructure(n->child[c], bo);
 }
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

inline

 {
 // debugPrintf("Verifying: split %d @ %f [%f, %f, %f], [%f, %f, %f]\n",
 // splitAxis, splitLocation, lo.x, lo.y, lo.z, hi.x, hi.y, hi.z);

 debugAssert(lo == splitBounds.low());
 debugAssert(hi == splitBounds.high());

# ifdef G3D_DEBUG
 for (int i = 0; i < valueArray.length(); ++i) {
 const Vector3& b = valueArray[i].position();
 debugAssert(splitBounds.contains(b));
 }
# endif

 if (child[0] || child[1]) {
 debugAssert(lo[splitAxis] < splitLocation);
 debugAssert(hi[splitAxis] > splitLocation);
 }

 Vector3 newLo = lo;
 newLo[splitAxis] = splitLocation;
 Vector3 newHi = hi;
 newHi[splitAxis] = splitLocation;

 if (child[0] != NULL) {
 child[0]->verifyNode(lo, newHi);
 }

 if (child[1] != NULL) {
 child[1]->verifyNode(newLo, hi);
 }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

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

Node* G3D::PointKDTree< T, PositionFunc, 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 NULL if there are not enough values to bother recursing.

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

Vector3::Axis G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::splitAxis

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

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

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

float G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::splitLocation

Location along the specified axis

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

Array<Handle> G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::valueArray

Values if this is a leaf node).

---

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

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