12 #ifndef __GEO_PointTree__
13 #define __GEO_PointTree__
36 template <
typename IDX_T>
49 bool enable_multithreading =
true);
56 bool enable_multithreading =
true);
69 bool auto_rebalance=
false);
89 bool auto_rebalance=
false);
118 bool wrapunitcube =
false);
141 bool wrapunitcube =
false);
179 bool enable_multithreading =
true)
override
202 int idx0,
int idx1,
int dim)
const override;
203 const float *
getP(
int idx)
const override;
268 bool enable_multithreading =
true);
270 const char *attrib,
bool enable_multithreading =
true);
276 bool enable_multithreading =
true);
296 bool enable_multithreading =
true);
298 const char *attrib,
bool enable_multithreading =
true);
300 const char *attrib,
const char *radattrib,
fpreal radscale,
301 bool enable_multithreading =
true);
306 { Super::build(pts, enable_multithreading); }
308 { Super::build(pts, idx, enable_multithreading); }
318 template <
typename IDX_T>
321 , myPointTransform(NULL)
322 , myIsKDTreeDirty(false)
327 template <
typename IDX_T>
330 clearPointTransform();
333 template <
typename IDX_T>
342 if (myPointTransform)
344 for (
exint ptnum = 0; ptnum <
n; ++ptnum)
345 myPointList(ptnum) *= *myPointTransform;
349 myIndexList.setSize(n);
351 for (
exint i = 0; i <
n; i++)
356 buildIfNeeded(enable_multithreading);
359 template <
typename IDX_T>
364 bool enable_multithreading)
368 UT_ASSERT(myPointList.size() == myIndexList.size());
371 if (myPointTransform)
374 for (
exint ptnum = 0; ptnum <
n; ++ptnum)
375 myPointList(ptnum) *= *myPointTransform;
381 buildIfNeeded(enable_multithreading);
384 template <
typename IDX_T>
396 if( myPointTransform )
397 myPointList.append(pt * (*myPointTransform));
399 myPointList.append(pt);
400 myIndexList.append(idx);
411 template <
typename IDX_T>
415 append(pt,
IdxType(myPointList.size()),
false);
418 template <
typename IDX_T>
427 UT_ASSERT(myRadii.size() == myPointList.size());
430 if (myRadii.size() != myPointList.size())
432 UT_ASSERT(!
"Adding radius points to a non-radius based point tree");
436 myRadii.append(radius);
437 append(pt, idx, auto_rebalance);
440 template <
typename IDX_T>
444 appendPtRadius(pt, radius,
IdxType(myPointList.size()),
false);
447 template <
typename IDX_T>
456 idx = findClosest(qpt, 1e37F);
461 return myIndexList(idx);
464 template <
typename IDX_T>
473 (
void) findClosest(idxlist, qpt, maxdist*maxdist, 1);
475 return myIndexList(idxlist(0));
480 template <
typename IDX_T>
493 i = findClosestQueue(qpt, q, maxdist * maxdist);
498 i = findClosestQueue(qpt, q, maxdist * maxdist);
504 return myIndexList(i);
507 template <
typename IDX_T>
521 int numnear = findClosest(group, groupdist, qpt,
526 for (
int i = 0; i < numnear; i++)
528 list(i) = myIndexList(group(i));
534 template <
typename IDX_T>
553 numnear = findClosestQueue(
554 group, groupdist, qpt, q, maxdist * maxdist, groupsize);
559 numnear = findClosestQueue(
560 group, groupdist, qpt, q, maxdist * maxdist, groupsize);
564 for (
exint i = 0; i < numnear; i++)
566 list(i) = myIndexList(group(i));
572 template <
typename IDX_T>
586 for (
exint i = 0; i < numnear; i++)
588 list(i) = myIndexList(idxlist(i));
594 template <
typename IDX_T>
606 queue, maxdist * maxdist, getEntries());
609 for (
exint i = 0; i < numnear; i++)
611 list(i) = myIndexList(idxlist(i));
617 template <
typename IDX_T>
629 exint numnear = findAllClosest(idxlist, pt, radius*radius);
632 for (
exint i = 0; i < numnear; i++)
634 list(i) = myIndexList(idxlist(i));
640 template <
typename IDX_T>
644 myPointList.setSize(0);
645 myIndexList.setSize(0);
654 template <
typename IDX_T>
658 return myPointList.size();
661 template <
typename IDX_T>
665 int64 mem = inclusive ?
sizeof(*this) :
false;
667 if (myPointTransform)
668 mem +=
sizeof(*myPointTransform);
669 mem += myPointList.getMemoryUsage(
false);
670 mem += myIndexList.getMemoryUsage(
false);
671 mem += myRadii.getMemoryUsage(
false);
675 template <
typename IDX_T>
679 delete myPointTransform;
680 myPointTransform = 0;
683 template <
typename IDX_T>
687 clearPointTransform();
692 template <
typename IDX_T>
699 setEntries(myPointList.size());
703 setBalancer(UT_KD_CENTROID);
707 balance(enable_multithreading);
709 myIsKDTreeDirty =
false;
713 template <
typename IDX_T>
717 float delta = myPointList(idx0)(dim) - myPointList(idx1)(dim);
726 template <
typename IDX_T>
730 return myPointList(idx).data();
733 template <
typename IDX_T>
743 template <
typename IDX_T>
void build(const UT_Vector3Array &pts, bool enable_multithreading=true)
void setBalancer(ut_KDBalancer balance)
void dirtyKDTree()
Marks the kd tree as out of date.
UT_Matrix4T< double > UT_DMatrix4
void setBalancer(ut_KDBalancer balance)
Queries for infinite lines (infinite tubes)
~GEO_PointTreeT() override
GEO_PointTreeT< int > GEO_PointTreeInt
For basic opaque integer id trees, use GEO_PointTreeInt.
void setMaxLeafNodes(int max_leaf_nodes)
void build(const UT_Vector3Array &pts, bool enable_multithreading=true)
int findAllCloseIdx(const UT_Vector3 &pt, fpreal maxdist, IdxArrayType &list)
virtual int64 getMemoryUsage(bool inclusive=true) const
Returns the amount of memory used by this tree.
int findAllCloseIdxQueue(const UT_Vector3 &pt, ut_KDPQueue &queue, fpreal maxdist, IdxArrayType &list)
Creates a search queue useful for findAll queries.
int64 getMemoryUsage(bool inclusive) const
GLdouble GLdouble GLdouble q
void updateKDTree(bool enablemultithread=true)
void setSize(exint newsize)
constexpr SYS_FORCE_INLINE const T * data() const noexcept
void setPointTransform(const UT_DMatrix4 &xform)
#define SYS_DEPRECATED_REPLACE(__V__, __R__)
UT_Vector3Array myPointList
The list of all the points.
UT_DMatrix4 * myPointTransform
virtual void clear()
Clears out the tree, leaving it with no entries.
void append(const UT_Vector3 &pt, IdxType idx, bool auto_rebalance=false)
void setMaxLeafNodes(int max_leaf_nodes)
bool pointsHaveRadius() const override
These are used if the user adds points with radii.
GEO_PointTreeT< GA_Index > Super
Lookup point information to be passed to the query functions.
fpreal getRadius(int idx) const override
Return the radius associated with the point in question.
IdxArrayType myIndexList
This is the mapping from the KD entries into the GDP numbers.
int entries() const
Returns the number of actual points in the tree.
*get result *(waiting if necessary)*A common idiom is to fire a bunch of sub tasks at the queue
void appendPtRadius(const UT_Vector3 &pt, fpreal radius, IdxType idx, bool auto_rebalance=false)
SYS_DECLARE_LEGACY_TR(GU_Detail)
int findAllInTubeIdx(const UT_Vector3 &pt, const UT_Vector3 &dir, fpreal radius, IdxArrayType &list)
Find all of the points inside the given tube.
GEO_PointTreeT< GA_Offset > Super
int comparePosition(int idx0, int idx1, int dim) const override
These are used by KDTree:
int 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.
int findNearestGroupIdx(const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist)
void buildIfNeeded(bool enable_multithreading=true) override
This must be called before querying, to build and balance the tree.
ut_KDBalancer
KD Tree balancing algorithms. See setBalancer.
const float * getP(int idx) const override
Return the position associated with the given point.
UT_Array< IdxType > IdxArrayType
UT_FloatArray myRadii
List of radii for each pont.
void balance(bool enable_multithreading=true)
IdxType findNearestIdxQueue(const UT_Vector3 &pt, ut_KDPQueue &q, fpreal maxdist=1e18f, bool wrapunitcube=false)
This uses a pre-built queue to reduce memory allocation.
void build(const UT_Vector3Array &pts, const GA_IndexArray &idx, bool enable_multithreading=true)
IdxType findNearestIdx(const UT_Vector3 &pt)
void clearPointTransform()
Clears the myPointTransform member data.