UT_KDTree Class Reference
#include <UT_KDTree.h>
Public Types | |
| enum | ut_KDBalancer { UT_KD_MEDIAN, UT_KD_SAH, UT_KD_CENTROID } |
| KD Tree balancing algorithms. See setBalancer. More... | |
Public Member Functions | |
| UT_KDTree (int dim=3, size_t size=0) | |
| virtual | ~UT_KDTree () |
| void | setEntries (size_t size) |
| size_t | getEntries () const |
| void | growEntries (size_t amount) |
| size_t | getRebalanceCount () const |
| void | setRebalanceCount (size_t count) |
| void | setBalancer (ut_KDBalancer balance) |
| void | setMaxLeafNodes (int max_leaf_nodes) |
| void | flagDirty () |
| virtual int | comparePosition (int idx0, int idx1, int dim) const =0 |
| virtual const float * | getP (int idx) const =0 |
| Return the position associated with the given point. | |
| virtual bool | pointsHaveRadius () const |
| virtual fpreal | getRadius (int) const |
| Return the radius associated with the point in question. | |
| virtual bool | isValid (int) const |
| Returns whether the given index should be considered in searches. | |
| virtual bool | isValid (int idx, const UT_KDQueryPt &) const |
| virtual int | getInvalidLimit (int maxn) const |
| int | findClosest (const UT_KDQueryPt &pt, fpreal max_distance) |
| int | findClosestQueue (const UT_KDQueryPt &pt, ut_KDPQueue &queue, fpreal max_distance) |
| int | findClosest (UT_IntArray &list, const UT_KDQueryPt &pt, fpreal max_distance, int max_nodes, bool sorted=true) |
| int | findClosestQueue (UT_IntArray &list, const UT_KDQueryPt &pt, ut_KDPQueue &q, fpreal max_distance, int max_nodes, bool sorted=true) |
| int | findClosest (UT_IntArray &list, UT_FloatArray &dist, const UT_KDQueryPt &pt, fpreal max_distance, int max_nodes, bool sorted=true) |
| int | findClosestQueue (UT_IntArray &list, UT_FloatArray &dist, const UT_KDQueryPt &pt, ut_KDPQueue &q, fpreal max_distance, int max_nodes, bool sorted=true) |
| int | findNClosest (UT_IntArray &list, const UT_KDQueryPt &pt, int max_nodes) |
| int | findAllClosest (UT_IntArray &list, const UT_KDQueryPt &pt, fpreal max_distance) |
| int | findTubeClosest (const UT_Vector3 &orig, const UT_Vector3 &dir) |
| int | findTubeClosest (UT_IntArray &list, const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal tube_radius, int max_nodes, bool sorted=true) |
| int | findTubeClosest (UT_IntArray &list, UT_FloatArray &dlist, const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal tube_radius, int max_nodes, bool sorted=true) |
| int | findTubeNClosest (UT_IntArray &list, const UT_Vector3 &orig, const UT_Vector3 &dir, int max_nodes) |
| int | findTubeAllClosest (UT_IntArray &list, const UT_Vector3 &orig, const UT_Vector3 &dir, fpreal radius) |
| const fpreal * | getBoxMin () |
| const fpreal * | getBoxMax () |
Static Public Member Functions | |
| static ut_KDPQueue * | createQueue () |
| static void | destroyQueue (ut_KDPQueue *q) |
Protected Member Functions | |
| int | findClosest (ut_KDPQueue &list, const UT_KDQueryPt &pt) |
| int | findTubeClosest (ut_KDPQueue &list, const UT_Vector3 &orig, const UT_Vector3 &dir) |
| void | recurseFind (ut_KDPQueue &list, const UT_KDQueryPt &pt, ut_KDSplit *split, int lo, int hi) const |
| void | recurseTubeFind (ut_KDPQueue &q, ut_KDSplit *split, int lo, int hi, const UT_Vector3 &orig, const UT_Vector3 &dir, UT_BoundingBox &box) const |
| bool | isBalanced () const |
| void | computeBox (int start_index=0) |
| bool | isBoxClose (const fpreal *P, fpreal qd, fpreal r) const |
| void | balance () |
| ut_KDSplit * | balanceSet (fpreal &radius, int *list, int entries, int axis) |
| Balances a subset, returning the maximum radius of that subset. | |
Protected Attributes | |
| fpreal | myBMin [UT_KD_MAXDIM] |
| fpreal | myBMax [UT_KD_MAXDIM] |
| int * | myList |
| ut_KDSplit * | mySplits |
| size_t | myEntries |
| This marks the number of entries that have been added to our tree. | |
| size_t | myFullEntries |
| size_t | myRebalanceCount |
| int | myDim |
| int | myMaxLeafNodes |
| bool | myBalanced |
| bool | myBoxComputed |
| bool | myHasRadius |
| A faster way to evaluate pointsHaveRadius() at runtime. | |
| ut_KDBalancer | myBalancer |
Detailed Description
Definition at line 57 of file UT_KDTree.h.
Member Enumeration Documentation
Constructor & Destructor Documentation
| UT_KDTree::UT_KDTree | ( | int | dim = 3, |
|
| size_t | size = 0 | |||
| ) | [inline] |
Definition at line 68 of file UT_KDTree.h.
| virtual UT_KDTree::~UT_KDTree | ( | ) | [virtual] |
Member Function Documentation
| void UT_KDTree::balance | ( | ) | [protected] |
Creates a KD tree from an unsorted set of points. Given a list of points, we: 1) Find the dimension in which there is most change. 2) Use the balancing algorithm to choose a splitting plane and partition myList into left and right portions. 3) Store the splitting information in mySplits 4) Recurse on the two halves. This is repeated until myMaxLeafNodes is reached where we just leave it as a linear list.
| ut_KDSplit* UT_KDTree::balanceSet | ( | fpreal & | radius, | |
| int * | list, | |||
| int | entries, | |||
| int | axis | |||
| ) | [protected] |
Balances a subset, returning the maximum radius of that subset.
| virtual int UT_KDTree::comparePosition | ( | int | idx0, | |
| int | idx1, | |||
| int | dim | |||
| ) | const [pure virtual] |
The compare function should compare the distance between two points (given by idx0 and idx1) in the dimension specified. The dimension will be between 0 and 3. For example, comparePosition(...) { fpreal delta = myP[idx0](dim) - myP[idx1](dim); return delta < 0 ? -1 : (delta > 0 ? 1 : 0); }
Implemented in GEO_PointTree.
| void UT_KDTree::computeBox | ( | int | start_index = 0 |
) | [protected] |
| static ut_KDPQueue* UT_KDTree::createQueue | ( | ) | [static] |
This allows you to create a search queue so you can maintain it over time, avoiding the cost of reallocing for each search. NOTE THAT max_distance IS SQUARED DISTANCE.
| static void UT_KDTree::destroyQueue | ( | ut_KDPQueue * | q | ) | [static] |
| int UT_KDTree::findAllClosest | ( | UT_IntArray & | list, | |
| const UT_KDQueryPt & | pt, | |||
| fpreal | max_distance | |||
| ) | [inline] |
Definition at line 216 of file UT_KDTree.h.
| int UT_KDTree::findClosest | ( | ut_KDPQueue & | list, | |
| const UT_KDQueryPt & | pt | |||
| ) | [protected] |
| int UT_KDTree::findClosest | ( | UT_IntArray & | list, | |
| UT_FloatArray & | dist, | |||
| const UT_KDQueryPt & | pt, | |||
| fpreal | max_distance, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
Find the closest N (max_nodes) nodes to the position given. Only points within the sphere defined by max_distance will be considered. NOTE THAT max_distance IS SQUARED DISTANCE.
| int UT_KDTree::findClosest | ( | UT_IntArray & | list, | |
| const UT_KDQueryPt & | pt, | |||
| fpreal | max_distance, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
Find the closest N (max_nodes) nodes to the position given. Only points within the sphere defined by max_distance will be considered. NOTE THAT max_distance IS SQUARED DISTANCE.
| int UT_KDTree::findClosest | ( | const UT_KDQueryPt & | pt, | |
| fpreal | max_distance | |||
| ) |
Find the closest node to the position specified. This method returns -1 if no photon is found. NOTE THAT max_distance IS SQUARED DISTANCE.
| int UT_KDTree::findClosestQueue | ( | UT_IntArray & | list, | |
| UT_FloatArray & | dist, | |||
| const UT_KDQueryPt & | pt, | |||
| ut_KDPQueue & | q, | |||
| fpreal | max_distance, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
| int UT_KDTree::findClosestQueue | ( | UT_IntArray & | list, | |
| const UT_KDQueryPt & | pt, | |||
| ut_KDPQueue & | q, | |||
| fpreal | max_distance, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
| int UT_KDTree::findClosestQueue | ( | const UT_KDQueryPt & | pt, | |
| ut_KDPQueue & | queue, | |||
| fpreal | max_distance | |||
| ) |
| int UT_KDTree::findNClosest | ( | UT_IntArray & | list, | |
| const UT_KDQueryPt & | pt, | |||
| int | max_nodes | |||
| ) | [inline] |
Definition at line 210 of file UT_KDTree.h.
| int UT_KDTree::findTubeAllClosest | ( | UT_IntArray & | list, | |
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir, | |||
| fpreal | radius | |||
| ) | [inline] |
Definition at line 250 of file UT_KDTree.h.
| int UT_KDTree::findTubeClosest | ( | ut_KDPQueue & | list, | |
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir | |||
| ) | [protected] |
| int UT_KDTree::findTubeClosest | ( | UT_IntArray & | list, | |
| UT_FloatArray & | dlist, | |||
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir, | |||
| fpreal | tube_radius, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
| int UT_KDTree::findTubeClosest | ( | UT_IntArray & | list, | |
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir, | |||
| fpreal | tube_radius, | |||
| int | max_nodes, | |||
| bool | sorted = true | |||
| ) |
| int UT_KDTree::findTubeClosest | ( | const UT_Vector3 & | orig, | |
| const UT_Vector3 & | dir | |||
| ) |
Tube queries (i.e. find the nearest N points to the line specified by the origin and direction)
| int UT_KDTree::findTubeNClosest | ( | UT_IntArray & | list, | |
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir, | |||
| int | max_nodes | |||
| ) | [inline] |
Definition at line 242 of file UT_KDTree.h.
| void UT_KDTree::flagDirty | ( | ) | [inline] |
Marks the tree as dirty. Note, however, that this has O(size) time cost.
Definition at line 133 of file UT_KDTree.h.
| const fpreal* UT_KDTree::getBoxMax | ( | ) |
| const fpreal* UT_KDTree::getBoxMin | ( | ) |
| size_t UT_KDTree::getEntries | ( | ) | const [inline] |
Definition at line 90 of file UT_KDTree.h.
| virtual int UT_KDTree::getInvalidLimit | ( | int | maxn | ) | const [inline, virtual] |
Return the maximum number of invalid indices that should be considered before bailing. Return -1 for no limit. maxn - the search limit
Definition at line 167 of file UT_KDTree.h.
| virtual const float* UT_KDTree::getP | ( | int | idx | ) | const [pure virtual] |
| virtual fpreal UT_KDTree::getRadius | ( | int | ) | const [inline, virtual] |
Return the radius associated with the point in question.
Reimplemented in GEO_PointTree.
Definition at line 156 of file UT_KDTree.h.
| size_t UT_KDTree::getRebalanceCount | ( | ) | const [inline] |
Definition at line 106 of file UT_KDTree.h.
| void UT_KDTree::growEntries | ( | size_t | amount | ) |
Sometimes, a tree might have new points added since it's construction. Rather than re-balancing the tree (which can be relatively expensive), we have allow N points to be added to the tree without re-balancing. To add entries to the tree, simply call "growEntries" with the number of points being added. If the size of the unsorted pool exceeds the re-balance count, then the tree will be re-balanced.
The rebalance count is automatically scaled as the tree is constructed, so it shouldn't be required to set the count (unless you know what you're doing).
To force a re-build of the tree, simply call setEntries(), or flag the tree as dirty.
| bool UT_KDTree::isBalanced | ( | ) | const [inline, protected] |
Definition at line 281 of file UT_KDTree.h.
| virtual bool UT_KDTree::isValid | ( | int | idx, | |
| const UT_KDQueryPt & | ||||
| ) | const [inline, virtual] |
Definition at line 161 of file UT_KDTree.h.
| virtual bool UT_KDTree::isValid | ( | int | ) | const [inline, virtual] |
Returns whether the given index should be considered in searches.
Reimplemented in GEO_PointTree.
Definition at line 159 of file UT_KDTree.h.
| virtual bool UT_KDTree::pointsHaveRadius | ( | ) | const [inline, virtual] |
If each point in the KD Tree has a radius associated with it, then this method should return true. Adding a per-point radius can affect performance adversely.
Reimplemented in GEO_PointTree.
Definition at line 154 of file UT_KDTree.h.
| void UT_KDTree::recurseFind | ( | ut_KDPQueue & | list, | |
| const UT_KDQueryPt & | pt, | |||
| ut_KDSplit * | split, | |||
| int | lo, | |||
| int | hi | |||
| ) | const [protected] |
| void UT_KDTree::recurseTubeFind | ( | ut_KDPQueue & | q, | |
| ut_KDSplit * | split, | |||
| int | lo, | |||
| int | hi, | |||
| const UT_Vector3 & | orig, | |||
| const UT_Vector3 & | dir, | |||
| UT_BoundingBox & | box | |||
| ) | const [protected] |
| void UT_KDTree::setBalancer | ( | ut_KDBalancer | balance | ) | [inline] |
Sets the KD-tree balancing algorithm.
- UT_KD_MEDIAN: splits at the median point
- UT_KD_CENTROID: splits at the spatial centroid
- UT_KD_SAH: splits at SAH optimal splitting point The UT_KD_SAH (surface area heuristic) algorithm builds more efficient trees but they are slower to construct. The default is UT_KD_MEDIAN.
Definition at line 119 of file UT_KDTree.h.
| void UT_KDTree::setEntries | ( | size_t | size | ) |
setEntries instructs the KD Tree about the number of points that it should read back from its callbacks. Note that each call to setEntries has O(size) cost! Thus, for (i = 0; i < n; i++) tree.setEntries(i); is O(n^2). There isn't a good reason for this (as one could instead just mark the tree as dirty until the next query, much like already happens with rebalancing) but it is the way things are so be
| void UT_KDTree::setMaxLeafNodes | ( | int | max_leaf_nodes | ) | [inline] |
Sets the maximum number of nodes to be stored in a leaf. Smaller values will produce deeper and more memory-hungry trees.
Definition at line 125 of file UT_KDTree.h.
| void UT_KDTree::setRebalanceCount | ( | size_t | count | ) |
Member Data Documentation
bool UT_KDTree::myBalanced [protected] |
Definition at line 328 of file UT_KDTree.h.
ut_KDBalancer UT_KDTree::myBalancer [protected] |
Definition at line 333 of file UT_KDTree.h.
fpreal UT_KDTree::myBMax[UT_KD_MAXDIM] [protected] |
Definition at line 305 of file UT_KDTree.h.
fpreal UT_KDTree::myBMin[UT_KD_MAXDIM] [protected] |
Stores the bounding box of all of the points in the KD tree, including their individual radii, in each of the possible dimensions. Note that during balanceSet these values are temporarily altered before recursion, so don't be too shocked.
Definition at line 304 of file UT_KDTree.h.
bool UT_KDTree::myBoxComputed [protected] |
Definition at line 329 of file UT_KDTree.h.
int UT_KDTree::myDim [protected] |
Definition at line 326 of file UT_KDTree.h.
size_t UT_KDTree::myEntries [protected] |
This marks the number of entries that have been added to our tree.
Definition at line 319 of file UT_KDTree.h.
size_t UT_KDTree::myFullEntries [protected] |
This marks the total number of entries in this data structure. The difference between this and myEntries is the unsorted chaff at the end.
Definition at line 324 of file UT_KDTree.h.
bool UT_KDTree::myHasRadius [protected] |
int* UT_KDTree::myList [protected] |
Nodes in a KD tree have two indices. One is the index that they were added in. This is the index used in getP, for example. The other is there location in the binary heap. myList takes a binary heap location and returns the index useable for getP().
Definition at line 312 of file UT_KDTree.h.
int UT_KDTree::myMaxLeafNodes [protected] |
Definition at line 327 of file UT_KDTree.h.
size_t UT_KDTree::myRebalanceCount [protected] |
Definition at line 325 of file UT_KDTree.h.
ut_KDSplit* UT_KDTree::mySplits [protected] |
Split information stored as a tree structure. This stores the midpoints, splitting offset, axis, and max radius.
Definition at line 316 of file UT_KDTree.h.
The documentation for this class was generated from the following file:
- UT/UT_KDTree.h
