KDTree Class Reference

List of all members.

Private Member Functions
void	deleteLeaves (unsigned int nodeID)
void	build (unsigned int nodeID, unsigned int *boundsArray, unsigned int nObjects, BoundingBox &limits, unsigned char axisNmask)
	recursive algorithm to build the tree bits 1,0 identify cut axis to be used
void	quickSort (unsigned int *lo0, unsigned int *hi0, unsigned char axis)
	qSort an array segment of object extremes
bool	compare (unsigned int aIndex, unsigned int bIndex, unsigned char axis)
	compare two object extrema according to the coordinate specified
float	getBoundValue (unsigned int *extremeIndex, unsigned char axis)
	return the value of the object extreme referenced
unsigned int *	findBound (unsigned int *extremeArrayStart, unsigned int nBounds, float loc, unsigned char axis)
	binary search: finds the position of value 'loc' in a sorted array partition
bool	isLeaf (unsigned int xnode)
	tell if a node is a leaf
bool	followChildren (unsigned int &parent, unsigned int &leftChild, unsigned int &rightChild)
bool	getFreeNodes (unsigned int parent, unsigned int &leftFree, unsigned int &rightFree)
void	createBoundingBox (Intersectable **iObjects, int nObjects)
	accumulate object extrema
unsigned int	makePointer (unsigned int originalNode)
Private Attributes
unsigned int	nCacheLines
	cache line sized memory segments used
unsigned int	maxNCacheLines
	nodes per cache line
unsigned int	nCacheLineNodes
	nodes per cache line
unsigned int	nCacheLineBytes
	bytes per cache line
BoundingBox	boundingBox
	bounding box containing all objects
float *	poolNodeTable
	memory allocated for nodes
float *	nodeTable
	array aligned on cache lines
unsigned int	nObjects
	objects
Intersectable **	objects
	array objects
Heap< unsigned int > *	freeNodes
	minimum heap to store indices of free nodes during the build
KDTree::TraverseStack *	traverseStack
	stack to implement the recursive traversal algorithm
Classes
struct	TraverseStack
	stack to implement the recursive traversal algorithm More...

---

Detailed Description

This class implements a kd-tree. Splitting, termination and cutting of empty space is based on cost estimation. Memory representation uses cache-line sized sub-trees and mapping of an unbalanced tree into an array.

---

Member Function Documentation

void KDTree::build (  unsigned int  nodeID, unsigned int *  boundsArray, unsigned int  nObjects, BoundingBox &  limits, unsigned char  axisNmask )  [private]

recursive algorithm to build the tree bits 1,0 identify cut axis to be used bits 5,4,3 indicate z,y,x failed cut attempts Parameters: nodeID  node index of kd-tree node to be created boundsArray  array of duplicated object indices, first bit tells mimima and maxima apart nObjects  objects (boundsArray's size is 2*nObjects) limits  kd-tree node volume

bool KDTree::compare (  unsigned int  aIndex, unsigned int  bIndex, unsigned char  axis )  [inline, private]

compare two object extrema according to the coordinate specified this is more complicated then one would predict. rules are: if values are significantly different, no problem the minimum of a patch is smaller than its maximum if a maximum and a minimum are near, the other extrema of the patches decide if all four extrema are near, the 2 ends of a patch have to be simultaneusly smaller or bigger than the other two ends

void KDTree::deleteLeaves (  unsigned int  nodeID  )  [private]

traces the tree defined by root node index 'nodeID', and frees the memory occupied by the object lists

bool KDTree::followChildren (  unsigned int &  parent, unsigned int &  leftChild, unsigned int &  rightChild )  [inline, private]

retrieve the node indices corresponding to the children of the specified node return false if the node is a leaf

bool KDTree::getFreeNodes (  unsigned int  parent, unsigned int &  leftFree, unsigned int &  rightFree )  [inline, private]

retrieve the node indices corresponding to the children of the specified node if they are not suitable to be the root of a free sub-tree, return false

unsigned int KDTree::makePointer (  unsigned int  originalNode  )  [inline, private]

If the node referenced by oNode is on the last level of a cache-line sized sub-tree, a pointer to a free node is placed, and the index of this free node is returned. Else, originalNode is returned.

---

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

• KDTree.hpp
• KDTree.cpp

---