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