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