HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GEO_PointTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GEO_PointTree.h ( GEO Library, C++)
7  *
8  * COMMENTS: This provides a method to index points inside of a
9  * geometry.
10  */
11 
12 #ifndef __GEO_PointTree__
13 #define __GEO_PointTree__
14 
15 #include "GEO_API.h"
16 #include "GEO_Detail.h"
17 #include <GA/GA_Types.h>
18 #include <UT/UT_Assert.h>
19 #include <UT/UT_DMatrix4.h>
20 #include <UT/UT_FloatArray.h>
21 #include <UT/UT_IntArray.h>
22 #include <UT/UT_KDTree.h>
23 #include <UT/UT_Vector3Array.h>
24 #include <SYS/SYS_TypeDecorate.h>
25 #include <stddef.h>
26 
27 class GA_PointGroup;
28 
29 
30 ///////////////////////////////////////////////////////////////////////////////
31 // GEO_PointTreeT<IDX_T>
32 //
33 
34 /// GEO_PointTreeT is a position tree used to accelerate lookups based on
35 /// the index type IDX_T.
36 template <typename IDX_T>
37 class GEO_PointTreeT : protected UT_KDTree
38 {
39 public:
40  typedef IDX_T IdxType;
42 
44  ~GEO_PointTreeT() override;
45 
46  /// Rebuilds the point tree as a pure index based tree using the
47  /// given vectors.
48  void build(const UT_Vector3Array &pts,
49  bool enable_multithreading = true);
50 
51  /// Rebuilds the point tree as a pure index based tree using the
52  /// given vector/index lookup.
53  void build(
54  const UT_Vector3Array &pts,
55  const IdxArrayType &idx,
56  bool enable_multithreading = true);
57 
58  /// This will slowly build the tree in place. Balancing isn't done
59  /// until the next lookup. Thus, it can provide a nicer way to
60  /// initialize a tree. When auto_rebalance is true, the tree may choose
61  /// not to rebalance on the next lookup, and will rebalance after a
62  /// sufficient number of points have been added. This can be useful in
63  /// cases where lookups and appends are interleaved. When it is false,
64  /// the tree will be rebalanced on the next query.
65  /// @{
66  void append(
67  const UT_Vector3 &pt,
68  IdxType idx,
69  bool auto_rebalance=false);
70  void append(const UT_Vector3 &pt);
71  /// @}
72 
73  /// This builds a tree which has a per point radius.
74  /// Note that this does not work with the tube testing code.
75  /// Note that there is a large performance penalty for the
76  /// findNearest methods, but no real penalty for the findAllClose
77  /// methods
78  /// If any points are added in radius mode, ALL must be added in
79  /// radius mode.
80  /// NOTE: If the tree is queried or built with zero entries, it
81  /// will be stuck with non-radius mode. So if you are using the
82  /// auto_rebalance, make sure the first point is *not* auto_rebalance
83  /// and you call buildIfNeeded() after adding it.
84  /// @{
85  void appendPtRadius(
86  const UT_Vector3 &pt,
87  fpreal radius,
88  IdxType idx,
89  bool auto_rebalance=false);
90  void appendPtRadius(
91  const UT_Vector3 &pt,
92  fpreal radius);
93  /// @}
94 
95  /// Clears out the tree, leaving it with no entries.
96  virtual void clear();
97 
98  /// Returns the number of actual points in the tree.
99  int entries() const;
100 
101  /// Returns the amount of memory used by this tree.
102  virtual int64 getMemoryUsage(bool inclusive=true) const;
103 
104  /// Finds the nearest index to the given value. Returns -1 on no
105  /// such point.
106  IdxType findNearestIdx(const UT_Vector3 &pt);
107 
108  /// Finds the nearest index to the given value. Returns -1 on no
109  /// such point. The point must be within the given range.
110  /// NOTE: findNearestPt() will fail if it has not been built with a gdp
111  IdxType findNearestIdx(const UT_Vector3 &pt, fpreal maxdist);
112 
113  /// This uses a pre-built queue to reduce memory allocation
115  const UT_Vector3 &pt,
116  ut_KDPQueue &q,
117  fpreal maxdist = 1e18f,
118  bool wrapunitcube = false);
119 
120  /// Find the nearest [groupsize] points not more than maxdist
121  /// away.
122  /// Returns the number of points found. Found points will be
123  /// stored in the group array.
124  /// @{
125  /// The resulting points will be sorted by their distance.
127  const UT_Vector3 &pt,
128  fpreal maxdist,
129  int groupsize,
130  IdxArrayType &group,
131  UT_FloatArray &groupdist);
132 
133  /// This uses a pre-built queue to reduce memory allocation
135  const UT_Vector3 &pt,
136  fpreal maxdist,
137  int groupsize,
138  IdxArrayType &group,
139  UT_FloatArray &groupdist,
140  ut_KDPQueue &q,
141  bool wrapunitcube = false);
142  /// @}
143 
144  /// Finds all the points within the given radius of a point.
145  /// The resulting points will *not* be sorted.
146  int findAllCloseIdx(
147  const UT_Vector3 &pt,
148  fpreal maxdist,
149  IdxArrayType &list);
150 
151  /// Creates a search queue useful for findAll queries.
153  const UT_Vector3 &pt,
154  ut_KDPQueue &queue,
155  fpreal maxdist,
156  IdxArrayType &list);
157 
158  /// Find all of the points inside the given tube.
159  int findAllInTubeIdx(
160  const UT_Vector3 &pt,
161  const UT_Vector3 &dir,
162  fpreal radius,
163  IdxArrayType &list);
164 
165  /// Sets the myPointTransform member so that we can build our tree from
166  /// a piece of geometry with an implicit transform on it.
167  void setPointTransform(const UT_DMatrix4 &xform);
168 
169  /// Ensures the KD tree has been fully built. If a KD tree
170  /// is being shared among multiple threads, it is important it
171  /// has first been compiled on one thread to avoid race conditions
172  /// (GEO_PointTree is thread safe on read provided it has been built
173  /// and provided no new points are added to it)
176 
177  /// This must be called before querying, to build and balance the tree.
179  bool enable_multithreading = true) override
180  {
181  updateKDTree(enable_multithreading);
182  }
183 
184  /// Sets the KD-tree balancing algorithm.
185  /// - UT_KD_MEDIAN: splits at the median point
186  /// - UT_KD_CENTROID: splits at the spatial centroid
187  /// - UT_KD_SAH: splits at SAH optimal splitting point
188  /// The UT_KD_SAH (surface area heuristic) algorithm builds more
189  /// efficient trees but they are slower to construct. The default is
190  /// UT_KD_MEDIAN.
192  { UT_KDTree::setBalancer(balance); }
193 
194  /// Sets the maximum number of nodes to be stored in a leaf. Smaller
195  /// values will produce deeper and more memory-hungry trees.
196  void setMaxLeafNodes(int max_leaf_nodes)
197  { UT_KDTree::setMaxLeafNodes(max_leaf_nodes); }
198 
199 protected:
200  /// These are used by KDTree:
201  int comparePosition(
202  int idx0, int idx1, int dim) const override;
203  const float *getP(int idx) const override;
204 
205  /// These are used if the user adds points with radii.
206  bool pointsHaveRadius() const override;
207  fpreal getRadius(int idx) const override;
208 
209 
210  /// Should be called prior to any invocation of KD Tree methods
211  /// as it ensures the KDTree knows about the current number of
212  /// entries.
213  void updateKDTree(bool enablemultithread=true);
214 
215  /// Marks the kd tree as out of date.
216  void dirtyKDTree() { myIsKDTreeDirty = true; }
217 
218 protected:
219  /// Clears the myPointTransform member data.
220  void clearPointTransform();
221 
222  /// If this pointer is set, then before adding any GEO_Points to
223  /// our point list, we transform their position with this matrix.
225 
226  /// This is the mapping from the KD entries into the GDP numbers.
228 
229  /// The list of all the points.
231 
232  /// List of radii for each pont.
234 
235  /// Tracks if the underlying KDtree has knowledge of our current
236  /// size.
238 
239 };
240 
241 
242 ///////////////////////////////////////////////////////////////////////////////
243 //
244 // GEO_PointTreeInt
245 //
246 
247 /// For basic opaque integer id trees, use GEO_PointTreeInt
249 
250 
251 ///////////////////////////////////////////////////////////////////////////////
252 //
253 // GEO_PointTreeGAOffset
254 //
255 
256 /// GEO_PointTreeGAOffset is mostly a pure GEO_PointTreeT<GA_Offset>.
257 /// It additionally provides a build() method from a GA_PointGroup.
259 {
260 public:
262 
263  /// Rebuilds the PointTree with the given detail and point group. If
264  /// ptgroup is NULL, then all points are used.
265  /// It will make its own internal vector3 array of the points and
266  /// original indices.
267  void build(const GEO_Detail *gdp, const GA_PointGroup *ptgroup = NULL,
268  bool enable_multithreading = true);
269  void build(const GEO_Detail *gdp, const GA_PointGroup *ptgroup,
270  const char *attrib, bool enable_multithreading = true);
271 
272  /// Rebuilds the PointTree given a list of point offsets.
273  /// It will make its own internal vector3 array of the points and
274  /// original indices.
275  void build(const GEO_Detail *gdp, const GA_OffsetArray &ptoffsets,
276  bool enable_multithreading = true);
277 };
278 
279 
280 ///////////////////////////////////////////////////////////////////////////////
281 //
282 // GEO_PointTree
283 //
284 
285 /// GEO_PointTree is a position tree use to accelerate lookups based by
286 /// point number (GA_Index).
287 class GEO_API GEO_PointTree : public GEO_PointTreeT<GA_Index>
288 {
289 public:
291 
292  /// Rebuilds the PointTree with the given detail and values.
293  /// It will make its own internal vector3 array of the points and
294  /// original indices.
295  void build(const GEO_Detail *gdp, const GA_PointGroup *ptgroup = NULL,
296  bool enable_multithreading = true);
297  void build(const GEO_Detail *gdp, const GA_PointGroup *ptgroup,
298  const char *attrib, bool enable_multithreading = true);
299  void build(const GEO_Detail *gdp, const GA_PointGroup *ptgroup,
300  const char *attrib, const char *radattrib, fpreal radscale,
301  bool enable_multithreading = true);
302 
303  /// Methods that must delegate to base class due to overloads
304  /// @{
305  void build(const UT_Vector3Array &pts, bool enable_multithreading = true)
306  { Super::build(pts, enable_multithreading); }
307  void build(const UT_Vector3Array &pts, const GA_IndexArray &idx, bool enable_multithreading = true)
308  { Super::build(pts, idx, enable_multithreading); }
309  /// @}
310 };
311 
312 
313 ////////////////////////////////////////////////////////////////////////////
314 //
315 // GEO_PointTreeT<IDX_T> Implementation
316 //
317 
318 template <typename IDX_T>
320  : UT_KDTree()
321  , myPointTransform(NULL)
322  , myIsKDTreeDirty(false)
323 {
324  // Our entries by default as both are zero.
325 }
326 
327 template <typename IDX_T>
329 {
330  clearPointTransform();
331 }
332 
333 template <typename IDX_T>
334 void
335 GEO_PointTreeT<IDX_T>::build(const UT_Vector3Array &pts, bool enable_multithreading)
336 {
337  // Empty the kd tree.
338  setEntries(0);
339 
340  myPointList = pts;
341  exint n = myPointList.size();
342  if (myPointTransform)
343  {
344  for (exint ptnum = 0; ptnum < n; ++ptnum)
345  myPointList(ptnum) *= *myPointTransform;
346  }
347 
348  // This has a very simple lookup relationship.
349  myIndexList.setSize(n);
350 
351  for (exint i = 0; i < n; i++)
352  myIndexList(i) = IdxType(i);
353 
354  // Build the tree.
355  dirtyKDTree();
356  buildIfNeeded(enable_multithreading);
357 }
358 
359 template <typename IDX_T>
360 void
362  const UT_Vector3Array &pts,
363  const IdxArrayType &idx,
364  bool enable_multithreading)
365 {
366  clear();
367 
368  UT_ASSERT(myPointList.size() == myIndexList.size());
369 
370  myPointList = pts;
371  if (myPointTransform)
372  {
373  exint n = myPointList.size();
374  for (exint ptnum = 0; ptnum < n; ++ptnum)
375  myPointList(ptnum) *= *myPointTransform;
376  }
377  myIndexList = idx;
378 
379  // Build the tree.
380  dirtyKDTree();
381  buildIfNeeded(enable_multithreading);
382 }
383 
384 template <typename IDX_T>
385 void
387  const UT_Vector3 &pt,
388  IdxType idx,
389  bool auto_rebalance)
390 {
391  // If we want to take advantage of auto balancing, we want
392  // to first ensure the KD tree is up to date.
393  if (auto_rebalance)
394  updateKDTree();
395 
396  if( myPointTransform )
397  myPointList.append(pt * (*myPointTransform));
398  else
399  myPointList.append(pt);
400  myIndexList.append(idx);
401 
402  // GrowEntries will only trigger a rebalance after a critical
403  // number is added.
404  // Tests with RBD shows setEntries is still faster.
405  if (auto_rebalance)
406  growEntries(1);
407  else
408  dirtyKDTree();
409 }
410 
411 template <typename IDX_T>
412 void
414 {
415  append(pt, IdxType(myPointList.size()), false);
416 }
417 
418 template <typename IDX_T>
419 void
421  const UT_Vector3 &pt,
422  fpreal radius,
423  IdxType idx,
424  bool auto_rebalance)
425 {
426  // Verify we are in radius mode.
427  UT_ASSERT(myRadii.size() == myPointList.size());
428 
429  // Ignore the points if we have mixed points.
430  if (myRadii.size() != myPointList.size())
431  {
432  UT_ASSERT(!"Adding radius points to a non-radius based point tree");
433  return;
434  }
435 
436  myRadii.append(radius);
437  append(pt, idx, auto_rebalance);
438 }
439 
440 template <typename IDX_T>
441 void
443 {
444  appendPtRadius(pt, radius, IdxType(myPointList.size()), false);
445 }
446 
447 template <typename IDX_T>
448 IDX_T
450 {
451  int idx;
452  UT_KDQueryPt qpt(pt.vec);
453 
454  updateKDTree();
455 
456  idx = findClosest(qpt, 1e37F);
457 
458  if (idx < 0)
459  return IdxType(-1);
460 
461  return myIndexList(idx);
462 }
463 
464 template <typename IDX_T>
465 IDX_T
467 {
468  UT_IntArray idxlist;
469  UT_KDQueryPt qpt(pt.vec);
470 
471  updateKDTree();
472 
473  (void) findClosest(idxlist, qpt, maxdist*maxdist, 1);
474  if (idxlist.size())
475  return myIndexList(idxlist(0));
476  else
477  return IdxType(-1);
478 }
479 
480 template <typename IDX_T>
481 IDX_T
483  const UT_Vector3 &pt, ut_KDPQueue &q, fpreal maxdist,
484  bool wrapunitcube)
485 {
486 
487  updateKDTree();
488 
489  int i;
490  if (!wrapunitcube)
491  {
492  UT_KDQueryPt qpt(pt.vec);
493  i = findClosestQueue(qpt, q, maxdist * maxdist);
494  }
495  else
496  {
497  UT_KDQueryPtUnitWrap qpt(pt.vec,3);
498  i = findClosestQueue(qpt, q, maxdist * maxdist);
499  }
500 
501  if (i < 0)
502  return IdxType(-1);
503  else
504  return myIndexList(i);
505 }
506 
507 template <typename IDX_T>
508 int
510  const UT_Vector3 &pt,
511  fpreal maxdist,
512  int groupsize,
513  IdxArrayType &list,
514  UT_FloatArray &groupdist)
515 {
516  UT_KDQueryPt qpt(pt.vec);
517  UT_IntArray group;
518 
519  updateKDTree();
520 
521  int numnear = findClosest(group, groupdist, qpt,
522  maxdist * maxdist,
523  groupsize);
524 
525  list.setSize(numnear);
526  for (int i = 0; i < numnear; i++)
527  {
528  list(i) = myIndexList(group(i));
529  }
530 
531  return numnear;
532 }
533 
534 template <typename IDX_T>
535 int
537  const UT_Vector3 &pt,
538  fpreal maxdist,
539  int groupsize,
540  IdxArrayType &list,
541  UT_FloatArray &groupdist,
542  ut_KDPQueue &q,
543  bool wrapunitcube)
544 {
545 
546  updateKDTree();
547 
548  UT_IntArray group;
549  exint numnear;
550  if (!wrapunitcube)
551  {
552  UT_KDQueryPt qpt(pt.vec);
553  numnear = findClosestQueue(
554  group, groupdist, qpt, q, maxdist * maxdist, groupsize);
555  }
556  else
557  {
558  UT_KDQueryPtUnitWrap qpt(pt.vec,3);
559  numnear = findClosestQueue(
560  group, groupdist, qpt, q, maxdist * maxdist, groupsize);
561  }
562 
563  list.setSize(numnear);
564  for (exint i = 0; i < numnear; i++)
565  {
566  list(i) = myIndexList(group(i));
567  }
568 
569  return numnear;
570 }
571 
572 template <typename IDX_T>
573 int
575  const UT_Vector3 &pt,
576  fpreal maxdist,
577  IdxArrayType &list)
578 {
579  updateKDTree();
580 
581  UT_IntArray idxlist;
582  exint numnear = findAllClosest(idxlist, UT_KDQueryPt(pt.data()),
583  maxdist * maxdist);
584 
585  list.setSize(numnear);
586  for (exint i = 0; i < numnear; i++)
587  {
588  list(i) = myIndexList(idxlist(i));
589  }
590 
591  return numnear;
592 }
593 
594 template <typename IDX_T>
595 int
597  const UT_Vector3 &pt,
598  ut_KDPQueue &queue,
599  fpreal maxdist,
600  IdxArrayType &list)
601 {
602  updateKDTree();
603 
604  UT_IntArray idxlist;
605  exint numnear = findClosestQueue(idxlist, UT_KDQueryPt(pt.data()),
606  queue, maxdist * maxdist, getEntries());
607 
608  list.setSize(numnear);
609  for (exint i = 0; i < numnear; i++)
610  {
611  list(i) = myIndexList(idxlist(i));
612  }
613 
614  return numnear;
615 }
616 
617 template <typename IDX_T>
618 int
620  const UT_Vector3 &orig,
621  const UT_Vector3 &dir,
622  fpreal radius,
623  IdxArrayType &list)
624 {
625  updateKDTree();
626 
627  UT_IntArray idxlist;
628  UT_KDLineQuery pt(orig, dir);
629  exint numnear = findAllClosest(idxlist, pt, radius*radius);
630 
631  list.setSize(numnear);
632  for (exint i = 0; i < numnear; i++)
633  {
634  list(i) = myIndexList(idxlist(i));
635  }
636 
637  return numnear;
638 }
639 
640 template <typename IDX_T>
641 void
643 {
644  myPointList.setSize(0);
645  myIndexList.setSize(0);
646  myRadii.setSize(0);
647 
648  // Empty the KD tree. We want to free the memory
649  // quickly so update immediately.
650  dirtyKDTree();
651  updateKDTree();
652 }
653 
654 template <typename IDX_T>
655 int
657 {
658  return myPointList.size();
659 }
660 
661 template <typename IDX_T>
662 int64
664 {
665  int64 mem = inclusive ? sizeof(*this) : false;
666  mem += UT_KDTree::getMemoryUsage(false);
667  if (myPointTransform)
668  mem += sizeof(*myPointTransform);
669  mem += myPointList.getMemoryUsage(false);
670  mem += myIndexList.getMemoryUsage(false);
671  mem += myRadii.getMemoryUsage(false);
672  return mem;
673 }
674 
675 template <typename IDX_T>
676 void
678 {
679  delete myPointTransform;
680  myPointTransform = 0;
681 }
682 
683 template <typename IDX_T>
684 void
686 {
687  clearPointTransform();
688  if( !xform.isIdentity() )
689  myPointTransform = new UT_DMatrix4(xform);
690 }
691 
692 template <typename IDX_T>
693 void
694 GEO_PointTreeT<IDX_T>::updateKDTree(bool enable_multithreading)
695 {
696  if (myIsKDTreeDirty)
697  {
698  // Size the kd tree.
699  setEntries(myPointList.size());
700 
701  // Override the balancer to be centroid, it should behave nicer
702  // for very large data sets. (Mantra uses centroid for photons already)
703  setBalancer(UT_KD_CENTROID);
704 
705  // Doing this prior to forking to multithreaded code
706  // avoids extra locks.
707  balance(enable_multithreading);
708 
709  myIsKDTreeDirty = false;
710  }
711 }
712 
713 template <typename IDX_T>
714 int
715 GEO_PointTreeT<IDX_T>::comparePosition(int idx0, int idx1, int dim) const
716 {
717  float delta = myPointList(idx0)(dim) - myPointList(idx1)(dim);
718  if (delta < 0)
719  return -1;
720  else if (delta > 0)
721  return 1;
722  else
723  return 0;
724 }
725 
726 template <typename IDX_T>
727 const float *
729 {
730  return myPointList(idx).data();
731 }
732 
733 template <typename IDX_T>
734 bool
736 {
737  if (myRadii.size())
738  return true;
739 
740  return false;
741 }
742 
743 template <typename IDX_T>
744 fpreal
746 {
747  return myRadii(idx);
748 }
749 
751 
752 #endif
void build(const UT_Vector3Array &pts, bool enable_multithreading=true)
void setBalancer(ut_KDBalancer balance)
Definition: UT_KDTree.h:542
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)
Definition: UT_KDTree.h:355
~GEO_PointTreeT() override
GEO_PointTreeT< int > GEO_PointTreeInt
For basic opaque integer id trees, use GEO_PointTreeInt.
void
Definition: png.h:1083
void setMaxLeafNodes(int max_leaf_nodes)
Definition: UT_KDTree.h:548
void build(const UT_Vector3Array &pts, bool enable_multithreading=true)
void ensureTreeBuilt()
T vec[tuple_size]
Definition: UT_Vector3.h:774
int findAllCloseIdx(const UT_Vector3 &pt, fpreal maxdist, IdxArrayType &list)
bool isIdentity() const
Definition: UT_Matrix4.h:1132
int64 exint
Definition: SYS_Types.h:125
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
Definition: UT_KDTree.h:494
GLdouble GLdouble GLdouble q
Definition: glad.h:2445
void updateKDTree(bool enablemultithread=true)
exint size() const
Definition: UT_Array.h:646
void setSize(exint newsize)
Definition: UT_Array.h:666
constexpr SYS_FORCE_INLINE const T * data() const noexcept
Definition: UT_Vector3.h:292
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)
GLdouble n
Definition: glcorearb.h:2008
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.
Definition: UT_KDTree.h:50
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.
#define GEO_API
Definition: GEO_API.h:14
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
Definition: thread.h:623
long long int64
Definition: SYS_Types.h:116
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:
fpreal64 fpreal
Definition: SYS_Types.h:277
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.
Definition: UT_KDTree.h:469
const float * getP(int idx) const override
Return the position associated with the given point.
UT_Array< IdxType > IdxArrayType
Definition: GEO_PointTree.h:41
UT_FloatArray myRadii
List of radii for each pont.
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
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.