HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_KDTree Class Referenceabstract

#include <UT_KDTree.h>

+ Inheritance diagram for UT_KDTree:

Classes

class  AggregateVolume
 
class  KDSplit
 
class  Visitor
 Interface for tree traversals. More...
 
class  VolumeData
 Interface for aggregate data used by volume filtering. More...
 

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 ()
 
virtual void buildIfNeeded (bool enable_multithreading=true)
 This must be called before querying, to build and balance the tree. More...
 
int64 getMemoryUsage (bool inclusive) const
 
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. More...
 
virtual bool pointsHaveRadius () const
 
virtual fpreal getRadius (int) const
 Return the radius associated with the point in question. More...
 
virtual bool isValid (int) const
 Returns whether the given index should be considered in searches. More...
 
virtual bool isValid (int idx, const UT_KDQueryPt &) const
 
virtual int getInvalidLimit (int maxn) const
 
template<typename QueryPoint >
int findClosest (const QueryPoint &pt, fpreal max_distance_squared)
 
template<typename QueryPoint >
int findClosestQueue (const QueryPoint &pt, ut_KDPQueue &queue, fpreal max_distance_squared)
 
template<typename QueryPoint >
int findClosest (UT_IntArray &list, const QueryPoint &pt, fpreal max_distance_squared, int max_nodes, bool sorted=true)
 
template<typename QueryPoint >
int findClosestQueue (UT_IntArray &list, const QueryPoint &pt, ut_KDPQueue &q, fpreal max_distance_squared, int max_nodes, bool sorted=true)
 
template<typename QueryPoint >
int findClosest (UT_IntArray &list, UT_FloatArray &dist, const QueryPoint &pt, fpreal max_distance_squared, int max_nodes, bool sorted=true)
 
template<typename QueryPoint >
int findClosestQueue (UT_IntArray &list, UT_FloatArray &dist, const QueryPoint &pt, ut_KDPQueue &q, fpreal max_distance_squared, int max_nodes, bool sorted=true)
 
template<typename QueryPoint >
int findNClosest (UT_IntArray &list, const QueryPoint &pt, int max_nodes)
 
template<typename QueryPoint >
int findAllClosest (UT_IntArray &list, const QueryPoint &pt, fpreal max_distance_squared)
 
void traverse (Visitor &visitor)
 
void filterVolume (VolumeData &data, const UT_Vector3 &pos, const UT_Filter &filter, const AggregateVolume &aggdata, int max_nodes)
 
const fprealgetBoxMin ()
 
const fprealgetBoxMax ()
 

Static Public Member Functions

static ut_KDPQueue * createQueue ()
 
static void destroyQueue (ut_KDPQueue *q)
 

Protected Member Functions

int getHead () const
 
bool isValid (int node, const UT_KDTubeQuery &) const
 
bool isValid (int node, const UT_KDLineQuery &) const
 
bool isValid (int node, const UT_KDTriQuery &) const
 
bool isValid (int node, const UT_KDTetQuery &) const
 
bool isValid (int node, const UT_KDQueryPtUnitWrap &) const
 
template<typename QueryPoint >
int findClosest (ut_KDPQueue &list, const QueryPoint &pt)
 
template<typename QueryPoint >
void recurseFind (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const
 
template<typename QueryPoint >
void recurseFindTube (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const
 
template<typename QueryPoint >
void recurseFindTri (ut_KDPQueue &list, const QueryPoint &pt, int split, int lo, int hi) const
 
template<typename QueryPoint >
void findInLeaf (ut_KDPQueue &list, const QueryPoint &pt, int lo, int hi, int invalid_limit, int &invalid) const
 
bool isBalanced () const
 
void traverseRecursive (Visitor &visitor, int split, int nodeid, UT_BoundingBox &box, int lo, int hi)
 
void computeBox (int start_index=0)
 
bool isBoxClose (const fpreal *P, fpreal qd, fpreal r) const
 
void balance (bool enable_multithreading=true)
 
void balanceSet (int &split, fpreal &radius, int *list, int entries, fpreal *boxmin, fpreal *boxmax, UT_Lock *splitlock)
 

Protected Attributes

fpreal myBMin [UT_KD_MAXDIM]
 
fpreal myBMax [UT_KD_MAXDIM]
 
intmyList
 
UT_Array< KDSplitmySplits
 
UT_Lock myLock
 For protecting tree balancing and bounding box computation. More...
 
size_t myEntries
 This marks the number of entries that have been added to our tree. More...
 
size_t myFullEntries
 
size_t myRebalanceCount
 
int myDim
 
int myMaxLeafNodes
 
bool myBalanced
 
bool myBoxComputed
 
bool myHasRadius
 A faster way to evaluate pointsHaveRadius() at runtime. More...
 
ut_KDBalancer myBalancer
 

Detailed Description

Definition at line 458 of file UT_KDTree.h.

Member Enumeration Documentation

KD Tree balancing algorithms. See setBalancer.

Enumerator
UT_KD_MEDIAN 
UT_KD_SAH 
UT_KD_CENTROID 

Definition at line 462 of file UT_KDTree.h.

Constructor & Destructor Documentation

UT_KDTree::UT_KDTree ( int  dim = 3,
size_t  size = 0 
)
inline

Definition at line 469 of file UT_KDTree.h.

virtual UT_KDTree::~UT_KDTree ( )
virtual

Member Function Documentation

void UT_KDTree::balance ( bool  enable_multithreading = true)
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.

void UT_KDTree::balanceSet ( int split,
fpreal radius,
int list,
int  entries,
fpreal boxmin,
fpreal boxmax,
UT_Lock splitlock 
)
protected

Balances a subset, returning the maximum radius of that subset. If splitlock is NULL, the balancing will all be done serially instead of in parallel.

virtual void UT_KDTree::buildIfNeeded ( bool  enable_multithreading = true)
inlinevirtual

This must be called before querying, to build and balance the tree.

Reimplemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GEO_2DTree.

Definition at line 482 of file UT_KDTree.h.

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_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GU_SortKDTree.

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_squared IS SQUARED DISTANCE.

static void UT_KDTree::destroyQueue ( ut_KDPQueue *  q)
static
void UT_KDTree::filterVolume ( VolumeData data,
const UT_Vector3 pos,
const UT_Filter filter,
const AggregateVolume aggdata,
int  max_nodes 
)

Filtered evaluation for 3D volumes. This method interprets the KD-Tree as a volume, and filters aggregate point data using the volumetric coverage for aggregate nodes in the tree. The max_nodes parameter controls the approximate number of points that should be averaged to produce the filtered result. The actual filter radius used will depend on max_nodes and on the size of KD-Tree nodes close to the query point. Since this is an approximate query, the actual number of points that contribute to the result may be larger than max_nodes.

This method relies on implemented subclasses for AggregateVolume and for VolumeData. You must compute aggregate volume data before calling this method.

UT_KDTree tree; AggregateVolumeSubclass aggdata; VolumeDataSubclass data;

// Store aggregate values (do this once) kdtree.traverse(aggdata);

// Filter aggregate data (do this many times) kdtree.filterVolume(data, pos, filter, aggdata, max_nodes);

template<typename QueryPoint >
int UT_KDTree::findAllClosest ( UT_IntArray list,
const QueryPoint &  pt,
fpreal  max_distance_squared 
)
inline

Definition at line 639 of file UT_KDTree.h.

template<typename QueryPoint >
int UT_KDTree::findClosest ( const QueryPoint &  pt,
fpreal  max_distance_squared 
)

Find the closest node to the position specified. This method returns -1 if no photon is found. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >
int UT_KDTree::findClosest ( UT_IntArray list,
const QueryPoint &  pt,
fpreal  max_distance_squared,
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_squared will be considered. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >
int UT_KDTree::findClosest ( UT_IntArray list,
UT_FloatArray dist,
const QueryPoint &  pt,
fpreal  max_distance_squared,
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_squared will be considered. NOTE THAT max_distance_squared IS SQUARED DISTANCE.

template<typename QueryPoint >
int UT_KDTree::findClosest ( ut_KDPQueue &  list,
const QueryPoint &  pt 
)
protected
template<typename QueryPoint >
int UT_KDTree::findClosestQueue ( const QueryPoint &  pt,
ut_KDPQueue &  queue,
fpreal  max_distance_squared 
)
template<typename QueryPoint >
int UT_KDTree::findClosestQueue ( UT_IntArray list,
const QueryPoint &  pt,
ut_KDPQueue &  q,
fpreal  max_distance_squared,
int  max_nodes,
bool  sorted = true 
)
template<typename QueryPoint >
int UT_KDTree::findClosestQueue ( UT_IntArray list,
UT_FloatArray dist,
const QueryPoint &  pt,
ut_KDPQueue &  q,
fpreal  max_distance_squared,
int  max_nodes,
bool  sorted = true 
)
template<typename QueryPoint >
void UT_KDTree::findInLeaf ( ut_KDPQueue &  list,
const QueryPoint &  pt,
int  lo,
int  hi,
int  invalid_limit,
int invalid 
) const
protected
template<typename QueryPoint >
int UT_KDTree::findNClosest ( UT_IntArray list,
const QueryPoint &  pt,
int  max_nodes 
)
inline

Definition at line 632 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 549 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 506 of file UT_KDTree.h.

int UT_KDTree::getHead ( ) const
inlineprotected

Definition at line 780 of file UT_KDTree.h.

virtual int UT_KDTree::getInvalidLimit ( int  maxn) const
inlinevirtual

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 583 of file UT_KDTree.h.

int64 UT_KDTree::getMemoryUsage ( bool  inclusive) const
inline

Definition at line 487 of file UT_KDTree.h.

virtual const float* UT_KDTree::getP ( int  idx) const
pure virtual

Return the position associated with the given point.

Implemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, GEO_PointTreeT< GA_Offset >, and GU_SortKDTree.

virtual fpreal UT_KDTree::getRadius ( int  ) const
inlinevirtual

Return the radius associated with the point in question.

Reimplemented in GEO_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, and GEO_PointTreeT< GA_Offset >.

Definition at line 572 of file UT_KDTree.h.

size_t UT_KDTree::getRebalanceCount ( ) const
inline

Definition at line 522 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
inlineprotected

Definition at line 826 of file UT_KDTree.h.

bool UT_KDTree::isBoxClose ( const fpreal P,
fpreal  qd,
fpreal  r 
) const
protected
virtual bool UT_KDTree::isValid ( int  ) const
inlinevirtual

Returns whether the given index should be considered in searches.

Definition at line 575 of file UT_KDTree.h.

virtual bool UT_KDTree::isValid ( int  idx,
const UT_KDQueryPt  
) const
inlinevirtual

Definition at line 577 of file UT_KDTree.h.

bool UT_KDTree::isValid ( int  node,
const UT_KDTubeQuery  
) const
inlineprotected

Definition at line 783 of file UT_KDTree.h.

bool UT_KDTree::isValid ( int  node,
const UT_KDLineQuery  
) const
inlineprotected

Definition at line 785 of file UT_KDTree.h.

bool UT_KDTree::isValid ( int  node,
const UT_KDTriQuery  
) const
inlineprotected

Definition at line 787 of file UT_KDTree.h.

bool UT_KDTree::isValid ( int  node,
const UT_KDTetQuery  
) const
inlineprotected

Definition at line 789 of file UT_KDTree.h.

bool UT_KDTree::isValid ( int  node,
const UT_KDQueryPtUnitWrap  
) const
inlineprotected

Definition at line 791 of file UT_KDTree.h.

virtual bool UT_KDTree::pointsHaveRadius ( ) const
inlinevirtual

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_PointTreeT< IDX_T >, GEO_PointTreeT< GA_Index >, GEO_PointTreeT< int >, and GEO_PointTreeT< GA_Offset >.

Definition at line 570 of file UT_KDTree.h.

template<typename QueryPoint >
void UT_KDTree::recurseFind ( ut_KDPQueue &  list,
const QueryPoint &  pt,
int  split,
int  lo,
int  hi 
) const
protected
template<typename QueryPoint >
void UT_KDTree::recurseFindTri ( ut_KDPQueue &  list,
const QueryPoint &  pt,
int  split,
int  lo,
int  hi 
) const
protected
template<typename QueryPoint >
void UT_KDTree::recurseFindTube ( ut_KDPQueue &  list,
const QueryPoint &  pt,
int  split,
int  lo,
int  hi 
) 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 535 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 541 of file UT_KDTree.h.

void UT_KDTree::setRebalanceCount ( size_t  count)
void UT_KDTree::traverse ( Visitor visitor)

Traverse the KD Tree in depth first order. This routine only works on 3D trees. NOTE: This will call balance() if the tree isn't balanced.

void UT_KDTree::traverseRecursive ( Visitor visitor,
int  split,
int  nodeid,
UT_BoundingBox box,
int  lo,
int  hi 
)
protected

Member Data Documentation

bool UT_KDTree::myBalanced
protected

Definition at line 883 of file UT_KDTree.h.

ut_KDBalancer UT_KDTree::myBalancer
protected

Definition at line 888 of file UT_KDTree.h.

fpreal UT_KDTree::myBMax[UT_KD_MAXDIM]
protected

Definition at line 857 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 856 of file UT_KDTree.h.

bool UT_KDTree::myBoxComputed
protected

Definition at line 884 of file UT_KDTree.h.

int UT_KDTree::myDim
protected

Definition at line 881 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 874 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 879 of file UT_KDTree.h.

bool UT_KDTree::myHasRadius
protected

A faster way to evaluate pointsHaveRadius() at runtime.

Definition at line 887 of file UT_KDTree.h.

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 864 of file UT_KDTree.h.

UT_Lock UT_KDTree::myLock
protected

For protecting tree balancing and bounding box computation.

Definition at line 871 of file UT_KDTree.h.

int UT_KDTree::myMaxLeafNodes
protected

Definition at line 882 of file UT_KDTree.h.

size_t UT_KDTree::myRebalanceCount
protected

Definition at line 880 of file UT_KDTree.h.

UT_Array<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 868 of file UT_KDTree.h.


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