#include <KDTree.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 AABox &bounds)

void	getIntersectingMembers (const AABox &box, const Sphere &sphere, Array< T * > &members, bool useSphere) const

void	assignSplitBounds (const AABox &myBounds)

bool	intersects (const Ray &ray, float distance) const

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

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

Array< AABox >	boundsArray

Constructor & Destructor Documentation

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 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 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.

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

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.

  : valueArray(pt) {
  splitAxis = Vector3::X_AXIS;
  splitLocation = 0;
  for (int i = 0; i < 2; ++i) {
  child[i] = NULL;
  }
 
  boundsArray.resize(valueArray.size());
  for (int i = 0; i < valueArray.size(); ++i) {
  boundsArray[i] = valueArray[i]->bounds;
  }
  }

Here is the call graph for this function:

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)

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

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 >::Node::assignSplitBounds ( const AABox & myBounds )

inline

Recurse through the tree, assigning splitBounds fields.

  {
  splitBounds = myBounds;
 
  AABox childBounds[2];
  myBounds.split(splitAxis, splitLocation, childBounds[0], childBounds[1]);
 
 # if defined(G3D_DEBUG) && defined(VERIFY_TREE)
  // Verify the split
  for (int v = 0; v < boundsArray.size(); ++v) {
  const AABox& bounds = boundsArray[v];
  debugAssert(myBounds.contains(bounds));
  }
 # endif
 
  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 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

  {
  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 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.

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

  {
  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 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.

  {
 
  // Test all values at this node
  for (int v = 0; v < boundsArray.size(); ++v) {
  const AABox& bounds = boundsArray[v];
  if (bounds.intersects(box) &&
  (! useSphere || bounds.intersects(sphere))) {
  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:

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

inline

  {
  
  if (! intersects(ray, distance)) {
  // The ray doesn't hit this node, so it can't hit the children of the node.
  return;
  }
 
  // Test for intersection against every object at this node.
  for (int v = 0; v < valueArray.size(); ++v) { 
  bool canHitThisObject = true;
 
  if (! intersectCallbackIsFast) {
  // See if
  Vector3 location;
  const AABox& bounds = boundsArray[v];
  bool alreadyInsideBounds = false;
  bool rayWillHitBounds = 
  CollisionDetection::collisionLocationForMovingPointFixedAABox(
  ray.origin(), ray.direction(), bounds, location, alreadyInsideBounds);
 
  canHitThisObject = (alreadyInsideBounds || 
  (rayWillHitBounds && ((location - ray.origin()).squaredLength() < square(distance))));
  }
 
  if (canHitThisObject) {
  // It is possible that this ray hits this object. Look for the intersection using the
  // callback.
  const T& value = valueArray[v]->value;
  intersectCallback(ray, value, distance);
  }
  }
 
  // There are three cases to consider next:
  // 
  // 1. the ray can start on one side of the splitting plane and never enter the other,
  // 2. the ray can start on one side and enter the other, and
  // 3. the ray can travel exactly down the splitting plane
 
  enum {NONE = -1};
  int firstChild = NONE;
  int secondChild = NONE;
 
  if (ray.origin()[splitAxis] < splitLocation) {
  
  // The ray starts on the small side
  firstChild = 0;
 
  if (ray.direction()[splitAxis] > 0) {
  // The ray will eventually reach the other side
  secondChild = 1;
  }
 
  } else if (ray.origin()[splitAxis] > splitLocation) {
 
  // The ray starts on the large side
  firstChild = 1;
 
  if (ray.direction()[splitAxis] < 0) {
  secondChild = 0;
  }
  } else {
  // The ray starts on the splitting plane
  if (ray.direction()[splitAxis] < 0) {
  // ...and goes to the small side
  firstChild = 0;
  } else if (ray.direction()[splitAxis] > 0) {
  // ...and goes to the large side
  firstChild = 1;
  }
  }
 
  // Test on the side closer to the ray origin.
  if ((firstChild != NONE) && child[firstChild]) {
  child[firstChild]->intersectRay(ray, intersectCallback, distance, intersectCallbackIsFast);
  }
 
  if (ray.direction()[splitAxis] != 0) {
  // See if there was an intersection before hitting the splitting plane. 
  // If so, there is no need to look on the far side and recursion terminates.
  float distanceToSplittingPlane = (splitLocation - ray.origin()[splitAxis]) / ray.direction()[splitAxis];
  if (distanceToSplittingPlane > distance) {
  // We aren't going to hit anything else before hitting the splitting plane,
  // so don't bother looking on the far side of the splitting plane at the other
  // child.
  return;
  }
  }
 
  // Test on the side farther from the ray origin.
  if ((secondChild != NONE) && child[secondChild]) {
  child[secondChild]->intersectRay(ray, intersectCallback, distance, intersectCallbackIsFast);
  }
 
  }

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 >::Node::intersects	(	const Ray &	ray,
		float	distance
	)		const

inline

Returns true if the ray intersects this node

  {
  // See if the ray will ever hit this node or its children
  Vector3 location;
  bool alreadyInsideBounds = false;
  bool rayWillHitBounds = 
  CollisionDetection::collisionLocationForMovingPointFixedAABox(
  ray.origin(), ray.direction(), splitBounds, location, alreadyInsideBounds);
  
  bool canHitThisNode = (alreadyInsideBounds || 
  (rayWillHitBounds && ((location - ray.origin()).squaredLength() < square(distance))));
 
  return canHitThisNode;
  }

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 >::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 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.

  {
  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 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

  {
  // 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);
  
  debugAssertM(lo == splitBounds.low(),
  format("lo = %s, splitBounds.lo = %s",
  lo.toString().c_str(), splitBounds.low().toString().c_str()));
  debugAssert(hi == splitBounds.high());
  
  for (int i = 0; i < valueArray.length(); ++i) {
  const AABox& b = valueArray[i]->bounds;
  debugAssert(b == boundsArray[i]);
  (void)b;
  
  for(int axis = 0; axis < 3; ++axis) {
  debugAssert(b.low()[axis] <= b.high()[axis]);
  debugAssert(b.low()[axis] >= lo[axis]);
  debugAssert(b.high()[axis] <= hi[axis]);
  }
  }
  
  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 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.

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 NULL if there are not enough values to bother recursing.

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

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.

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

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.

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

dep/g3dlite/include/G3D/KDTree.h

Public Member Functions

Static Public Member Functions

Public Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation