12 #ifndef __GEO_PointTree__
13 #define __GEO_PointTree__
35 template <
typename IDX_T>
48 bool enable_multithreading =
true);
55 bool enable_multithreading =
true);
68 bool auto_rebalance=
false);
88 bool auto_rebalance=
false);
117 bool wrapunitcube =
false);
140 bool wrapunitcube =
false);
178 bool enable_multithreading =
true)
override
201 int idx0,
int idx1,
int dim)
const override;
202 const float *
getP(
int idx)
const override;
267 bool enable_multithreading =
true);
269 const char *attrib,
bool enable_multithreading =
true);
275 bool enable_multithreading =
true);
295 bool enable_multithreading =
true);
297 const char *attrib,
bool enable_multithreading =
true);
299 const char *attrib,
const char *radattrib,
fpreal radscale,
300 bool enable_multithreading =
true);
305 { Super::build(pts, enable_multithreading); }
307 { Super::build(pts, idx, enable_multithreading); }
317 template <
typename IDX_T>
320 , myPointTransform(NULL)
321 , myIsKDTreeDirty(false)
326 template <
typename IDX_T>
329 clearPointTransform();
332 template <
typename IDX_T>
341 if (myPointTransform)
343 for (
exint ptnum = 0; ptnum <
n; ++ptnum)
344 myPointList(ptnum) *= *myPointTransform;
348 myIndexList.setSize(n);
350 for (
exint i = 0; i <
n; i++)
355 buildIfNeeded(enable_multithreading);
358 template <
typename IDX_T>
363 bool enable_multithreading)
367 UT_ASSERT(myPointList.size() == myIndexList.size());
370 if (myPointTransform)
373 for (
exint ptnum = 0; ptnum <
n; ++ptnum)
374 myPointList(ptnum) *= *myPointTransform;
380 buildIfNeeded(enable_multithreading);
383 template <
typename IDX_T>
395 if( myPointTransform )
396 myPointList.append(pt * (*myPointTransform));
398 myPointList.append(pt);
399 myIndexList.append(idx);
410 template <
typename IDX_T>
414 append(pt,
IdxType(myPointList.size()),
false);
417 template <
typename IDX_T>
426 UT_ASSERT(myRadii.size() == myPointList.size());
429 if (myRadii.size() != myPointList.size())
431 UT_ASSERT(!
"Adding radius points to a non-radius based point tree");
435 myRadii.append(radius);
436 append(pt, idx, auto_rebalance);
439 template <
typename IDX_T>
443 appendPtRadius(pt, radius,
IdxType(myPointList.size()),
false);
446 template <
typename IDX_T>
455 idx = findClosest(qpt, 1e37F);
460 return myIndexList(idx);
463 template <
typename IDX_T>
472 (
void) findClosest(idxlist, qpt, maxdist*maxdist, 1);
474 return myIndexList(idxlist(0));
479 template <
typename IDX_T>
492 i = findClosestQueue(qpt, q, maxdist * maxdist);
497 i = findClosestQueue(qpt, q, maxdist * maxdist);
503 return myIndexList(i);
506 template <
typename IDX_T>
520 int numnear = findClosest(group, groupdist, qpt,
525 for (
int i = 0; i < numnear; i++)
527 list(i) = myIndexList(
group(i));
533 template <
typename IDX_T>
552 numnear = findClosestQueue(
553 group, groupdist, qpt, q, maxdist * maxdist, groupsize);
558 numnear = findClosestQueue(
559 group, groupdist, qpt, q, maxdist * maxdist, groupsize);
563 for (
exint i = 0; i < numnear; i++)
565 list(i) = myIndexList(
group(i));
571 template <
typename IDX_T>
585 for (
exint i = 0; i < numnear; i++)
587 list(i) = myIndexList(idxlist(i));
593 template <
typename IDX_T>
605 queue, maxdist * maxdist, getEntries());
608 for (
exint i = 0; i < numnear; i++)
610 list(i) = myIndexList(idxlist(i));
616 template <
typename IDX_T>
628 exint numnear = findAllClosest(idxlist, pt, radius*radius);
631 for (
exint i = 0; i < numnear; i++)
633 list(i) = myIndexList(idxlist(i));
639 template <
typename IDX_T>
643 myPointList.setSize(0);
644 myIndexList.setSize(0);
653 template <
typename IDX_T>
657 return myPointList.size();
660 template <
typename IDX_T>
664 int64 mem = inclusive ?
sizeof(*this) :
false;
666 if (myPointTransform)
667 mem +=
sizeof(*myPointTransform);
668 mem += myPointList.getMemoryUsage(
false);
669 mem += myIndexList.getMemoryUsage(
false);
670 mem += myRadii.getMemoryUsage(
false);
674 template <
typename IDX_T>
678 delete myPointTransform;
679 myPointTransform = 0;
682 template <
typename IDX_T>
686 clearPointTransform();
691 template <
typename IDX_T>
698 setEntries(myPointList.size());
702 setBalancer(UT_KD_CENTROID);
706 balance(enable_multithreading);
708 myIsKDTreeDirty =
false;
712 template <
typename IDX_T>
716 float delta = myPointList(idx0)(dim) - myPointList(idx1)(dim);
725 template <
typename IDX_T>
729 return myPointList(idx).data();
732 template <
typename IDX_T>
742 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
void updateKDTree(bool enablemultithread=true)
void setSize(exint newsize)
constexpr SYS_FORCE_INLINE const T * data() const noexcept
void setPointTransform(const UT_DMatrix4 &xform)
UT_ValArray< IdxType > IdxArrayType
#define SYS_DEPRECATED_REPLACE(__V__, __R__)
UT_Vector3Array myPointList
The list of all the points.
GLdouble GLdouble GLdouble GLdouble q
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)
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_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.