HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GEO_PointTreeT< IDX_T > Class Template Reference

#include <GEO_PointTree.h>

+ Inheritance diagram for GEO_PointTreeT< IDX_T >:

Public Types

typedef IDX_T IdxType
 
typedef UT_ValArray< IdxTypeIdxArrayType
 

Public Member Functions

 GEO_PointTreeT ()
 
virtual ~GEO_PointTreeT ()
 
void build (const UT_Vector3Array &pts, bool enable_multithreading=true)
 
void build (const UT_Vector3Array &pts, const IdxArrayType &idx, bool enable_multithreading=true)
 
virtual void clear ()
 Clears out the tree, leaving it with no entries. More...
 
int entries () const
 Returns the number of actual points in the tree. More...
 
virtual int64 getMemoryUsage (bool inclusive=true) const
 Returns the amount of memory used by this tree. More...
 
IdxType findNearestIdx (const UT_Vector3 &pt)
 
IdxType findNearestIdx (const UT_Vector3 &pt, fpreal maxdist)
 
IdxType findNearestIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &q, fpreal maxdist=1e18f, bool wrapunitcube=false)
 
int findNearestGroupIdx (const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist)
 
int findNearestGroupIdxQueue (const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist, ut_KDPQueue &q, bool wrapunitcube=false)
 
int findAllCloseIdx (const UT_Vector3 &pt, fpreal maxdist, IdxArrayType &list)
 
int findAllCloseIdxQueue (const UT_Vector3 &pt, ut_KDPQueue &queue, fpreal maxdist, IdxArrayType &list)
 
int findAllInTubeIdx (const UT_Vector3 &pt, const UT_Vector3 &dir, fpreal radius, IdxArrayType &list)
 Find all of the points inside the given tube. More...
 
void setPointTransform (const UT_DMatrix4 &xform)
 
void ensureTreeBuilt ()
 
virtual void buildIfNeeded (bool enable_multithreading=true)
 This must be called before querying, to build and balance the tree. More...
 
void setBalancer (ut_KDBalancer balance)
 
void setMaxLeafNodes (int max_leaf_nodes)
 
void append (const UT_Vector3 &pt, IdxType idx, bool auto_rebalance=false)
 
void append (const UT_Vector3 &pt)
 
void appendPtRadius (const UT_Vector3 &pt, fpreal radius, IdxType idx, bool auto_rebalance=false)
 
void appendPtRadius (const UT_Vector3 &pt, fpreal radius)
 

Protected Member Functions

virtual int comparePosition (int idx0, int idx1, int dim) const
 These are used by KDTree: More...
 
virtual const float * getP (int idx) const
 Return the position associated with the given point. More...
 
virtual bool pointsHaveRadius () const
 These are used if the user adds points with radii. More...
 
virtual fpreal getRadius (int idx) const
 Return the radius associated with the point in question. More...
 
void updateKDTree (bool enablemultithread=true)
 
void dirtyKDTree ()
 Marks the kd tree as out of date. More...
 
void clearPointTransform ()
 Clears the myPointTransform member data. More...
 
- Protected Member Functions inherited from UT_KDTree
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)
 
 UT_KDTree (int dim=3, size_t size=0)
 
virtual ~UT_KDTree ()
 
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 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 ()
 

Protected Attributes

UT_DMatrix4myPointTransform
 
IdxArrayType myIndexList
 This is the mapping from the KD entries into the GDP numbers. More...
 
UT_Vector3Array myPointList
 The list of all the points. More...
 
UT_FloatArray myRadii
 List of radii for each pont. More...
 
bool myIsKDTreeDirty
 
- Protected Attributes inherited from UT_KDTree
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
 

Additional Inherited Members

- Protected Types inherited from UT_KDTree
enum  ut_KDBalancer { UT_KD_MEDIAN, UT_KD_SAH, UT_KD_CENTROID }
 KD Tree balancing algorithms. See setBalancer. More...
 
- Static Protected Member Functions inherited from UT_KDTree
static ut_KDPQueue * createQueue ()
 
static void destroyQueue (ut_KDPQueue *q)
 

Detailed Description

template<typename IDX_T>
class GEO_PointTreeT< IDX_T >

GEO_PointTreeT is a position tree used to accelerate lookups based on the index type IDX_T.

Definition at line 36 of file GEO_PointTree.h.

Member Typedef Documentation

template<typename IDX_T>
typedef UT_ValArray<IdxType> GEO_PointTreeT< IDX_T >::IdxArrayType

Definition at line 40 of file GEO_PointTree.h.

template<typename IDX_T>
typedef IDX_T GEO_PointTreeT< IDX_T >::IdxType

Definition at line 39 of file GEO_PointTree.h.

Constructor & Destructor Documentation

template<typename IDX_T >
GEO_PointTreeT< IDX_T >::GEO_PointTreeT ( )

Definition at line 319 of file GEO_PointTree.h.

template<typename IDX_T >
GEO_PointTreeT< IDX_T >::~GEO_PointTreeT ( )
virtual

Definition at line 328 of file GEO_PointTree.h.

Member Function Documentation

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::append ( const UT_Vector3 pt,
IdxType  idx,
bool  auto_rebalance = false 
)

This will slowly build the tree in place. Balancing isn't done until the next lookup. Thus, it can provide a nicer way to initialize a tree. When auto_rebalance is true, the tree may choose not to rebalance on the next lookup, and will rebalance after a sufficient number of points have been added. This can be useful in cases where lookups and appends are interleaved. When it is false, the tree will be rebalanced on the next query.

Definition at line 386 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::append ( const UT_Vector3 pt)

This will slowly build the tree in place. Balancing isn't done until the next lookup. Thus, it can provide a nicer way to initialize a tree. When auto_rebalance is true, the tree may choose not to rebalance on the next lookup, and will rebalance after a sufficient number of points have been added. This can be useful in cases where lookups and appends are interleaved. When it is false, the tree will be rebalanced on the next query.

Definition at line 413 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::appendPtRadius ( const UT_Vector3 pt,
fpreal  radius,
IdxType  idx,
bool  auto_rebalance = false 
)

This builds a tree which has a per point radius. Note that this does not work with the tube testing code. Note that there is a large performance penalty for the findNearest methods, but no real penalty for the findAllClose methods If any points are added in radius mode, ALL must be added in radius mode. NOTE: If the tree is queried or built with zero entries, it will be stuck with non-radius mode. So if you are using the auto_rebalance, make sure the first point is not auto_rebalance and you call buildIfNeeded() after adding it.

Definition at line 420 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::appendPtRadius ( const UT_Vector3 pt,
fpreal  radius 
)

This builds a tree which has a per point radius. Note that this does not work with the tube testing code. Note that there is a large performance penalty for the findNearest methods, but no real penalty for the findAllClose methods If any points are added in radius mode, ALL must be added in radius mode. NOTE: If the tree is queried or built with zero entries, it will be stuck with non-radius mode. So if you are using the auto_rebalance, make sure the first point is not auto_rebalance and you call buildIfNeeded() after adding it.

Definition at line 442 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::build ( const UT_Vector3Array pts,
bool  enable_multithreading = true 
)

Rebuilds the point tree as a pure index based tree using the given vectors.

Definition at line 335 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::build ( const UT_Vector3Array pts,
const IdxArrayType idx,
bool  enable_multithreading = true 
)

Rebuilds the point tree as a pure index based tree using the given vector/index lookup.

Definition at line 361 of file GEO_PointTree.h.

template<typename IDX_T>
virtual void GEO_PointTreeT< IDX_T >::buildIfNeeded ( bool  enable_multithreading = true)
inlinevirtual

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

Reimplemented from UT_KDTree.

Definition at line 180 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::clear ( void  )
virtual

Clears out the tree, leaving it with no entries.

Definition at line 642 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::clearPointTransform ( )
protected

Clears the myPointTransform member data.

Definition at line 677 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::comparePosition ( int  idx0,
int  idx1,
int  dim 
) const
protectedvirtual

These are used by KDTree:

Implements UT_KDTree.

Definition at line 715 of file GEO_PointTree.h.

template<typename IDX_T>
void GEO_PointTreeT< IDX_T >::dirtyKDTree ( )
inlineprotected

Marks the kd tree as out of date.

Definition at line 216 of file GEO_PointTree.h.

template<typename IDX_T>
void GEO_PointTreeT< IDX_T >::ensureTreeBuilt ( )
inline

Ensures the KD tree has been fully built. If a KD tree is being shared among multiple threads, it is important it has first been compiled on one thread to avoid race conditions (GEO_PointTree is thread safe on read provided it has been built and provided no new points are added to it)

Definition at line 177 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::entries ( ) const

Returns the number of actual points in the tree.

Definition at line 656 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::findAllCloseIdx ( const UT_Vector3 pt,
fpreal  maxdist,
IdxArrayType list 
)

Finds all the points within the given radius of a point. The resulting points will not be sorted.

Definition at line 574 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::findAllCloseIdxQueue ( const UT_Vector3 pt,
ut_KDPQueue &  queue,
fpreal  maxdist,
IdxArrayType list 
)

Creates a search queue useful for findAll queries. You must destroy it with UT_KDTree::destroyQueue(q) when done.

Definition at line 596 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::findAllInTubeIdx ( const UT_Vector3 pt,
const UT_Vector3 dir,
fpreal  radius,
IdxArrayType list 
)

Find all of the points inside the given tube.

Definition at line 619 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::findNearestGroupIdx ( const UT_Vector3 pt,
fpreal  maxdist,
int  groupsize,
IdxArrayType group,
UT_FloatArray groupdist 
)

Find the nearest [groupsize] points not more than maxdist away. Returns the number of points found. Found points will be stored in the group array. The resulting points will be sorted by their distance.

Definition at line 509 of file GEO_PointTree.h.

template<typename IDX_T >
int GEO_PointTreeT< IDX_T >::findNearestGroupIdxQueue ( const UT_Vector3 pt,
fpreal  maxdist,
int  groupsize,
IdxArrayType group,
UT_FloatArray groupdist,
ut_KDPQueue &  q,
bool  wrapunitcube = false 
)

This uses a pre-built queue to reduce memory allocation You must call UT_KDTree::destroyQueue() when you are done with the queue.

Definition at line 536 of file GEO_PointTree.h.

template<typename IDX_T >
IDX_T GEO_PointTreeT< IDX_T >::findNearestIdx ( const UT_Vector3 pt)

Finds the nearest index to the given value. Returns -1 on no such point.

Definition at line 449 of file GEO_PointTree.h.

template<typename IDX_T >
IDX_T GEO_PointTreeT< IDX_T >::findNearestIdx ( const UT_Vector3 pt,
fpreal  maxdist 
)

Finds the nearest index to the given value. Returns -1 on no such point. The point must be within the given range. NOTE: findNearestPt() will fail if it has not been built with a gdp

Definition at line 466 of file GEO_PointTree.h.

template<typename IDX_T >
IDX_T GEO_PointTreeT< IDX_T >::findNearestIdxQueue ( const UT_Vector3 pt,
ut_KDPQueue &  q,
fpreal  maxdist = 1e18f,
bool  wrapunitcube = false 
)

This uses a pre-built queue to reduce memory allocation You must call UT_KDTree::destroyQueue() when you are done with the queue.

Definition at line 482 of file GEO_PointTree.h.

template<typename IDX_T >
int64 GEO_PointTreeT< IDX_T >::getMemoryUsage ( bool  inclusive = true) const
virtual

Returns the amount of memory used by this tree.

Definition at line 663 of file GEO_PointTree.h.

template<typename IDX_T >
const float * GEO_PointTreeT< IDX_T >::getP ( int  idx) const
protectedvirtual

Return the position associated with the given point.

Implements UT_KDTree.

Definition at line 728 of file GEO_PointTree.h.

template<typename IDX_T >
fpreal GEO_PointTreeT< IDX_T >::getRadius ( int  ) const
protectedvirtual

Return the radius associated with the point in question.

Reimplemented from UT_KDTree.

Definition at line 745 of file GEO_PointTree.h.

template<typename IDX_T >
bool GEO_PointTreeT< IDX_T >::pointsHaveRadius ( ) const
protectedvirtual

These are used if the user adds points with radii.

Reimplemented from UT_KDTree.

Definition at line 735 of file GEO_PointTree.h.

template<typename IDX_T>
void GEO_PointTreeT< IDX_T >::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 192 of file GEO_PointTree.h.

template<typename IDX_T>
void GEO_PointTreeT< IDX_T >::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 197 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::setPointTransform ( const UT_DMatrix4 xform)

Sets the myPointTransform member so that we can build our tree from a piece of geometry with an implicit transform on it.

Definition at line 685 of file GEO_PointTree.h.

template<typename IDX_T >
void GEO_PointTreeT< IDX_T >::updateKDTree ( bool  enablemultithread = true)
protected

Should be called prior to any invocation of KD Tree methods as it ensures the KDTree knows about the current number of entries.

Definition at line 694 of file GEO_PointTree.h.

Member Data Documentation

template<typename IDX_T>
IdxArrayType GEO_PointTreeT< IDX_T >::myIndexList
protected

This is the mapping from the KD entries into the GDP numbers.

Definition at line 227 of file GEO_PointTree.h.

template<typename IDX_T>
bool GEO_PointTreeT< IDX_T >::myIsKDTreeDirty
protected

Tracks if the underlying KDtree has knowledge of our current size.

Definition at line 237 of file GEO_PointTree.h.

template<typename IDX_T>
UT_Vector3Array GEO_PointTreeT< IDX_T >::myPointList
protected

The list of all the points.

Definition at line 230 of file GEO_PointTree.h.

template<typename IDX_T>
UT_DMatrix4* GEO_PointTreeT< IDX_T >::myPointTransform
protected

If this pointer is set, then before adding any GEO_Points to our point list, we transform their position with this matrix.

Definition at line 224 of file GEO_PointTree.h.

template<typename IDX_T>
UT_FloatArray GEO_PointTreeT< IDX_T >::myRadii
protected

List of radii for each pont.

Definition at line 233 of file GEO_PointTree.h.


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