HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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  virtual ~GEO_PointTreeT();
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
113  /// You must call UT_KDTree::destroyQueue() when you are done with
114  /// the queue.
116  const UT_Vector3 &pt,
117  ut_KDPQueue &q,
118  fpreal maxdist = 1e18f,
119  bool wrapunitcube = false);
120 
121  /// Find the nearest [groupsize] points not more than maxdist
122  /// away.
123  /// Returns the number of points found. Found points will be
124  /// stored in the group array.
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
134  /// You must call UT_KDTree::destroyQueue() when you are done with
135  /// the queue.
137  const UT_Vector3 &pt,
138  fpreal maxdist,
139  int groupsize,
140  IdxArrayType &group,
141  UT_FloatArray &groupdist,
142  ut_KDPQueue &q,
143  bool wrapunitcube = false);
144 
145  /// Finds all the points within the given radius of a point.
146  /// The resulting points will *not* be sorted.
147  int findAllCloseIdx(
148  const UT_Vector3 &pt,
149  fpreal maxdist,
150  IdxArrayType &list);
151 
152  /// Creates a search queue useful for findAll queries. You
153  /// must destroy it with UT_KDTree::destroyQueue(q) when done.
155  const UT_Vector3 &pt,
156  ut_KDPQueue &queue,
157  fpreal maxdist,
158  IdxArrayType &list);
159 
160  /// Find all of the points inside the given tube.
161  int findAllInTubeIdx(
162  const UT_Vector3 &pt,
163  const UT_Vector3 &dir,
164  fpreal radius,
165  IdxArrayType &list);
166 
167  /// Sets the myPointTransform member so that we can build our tree from
168  /// a piece of geometry with an implicit transform on it.
169  void setPointTransform(const UT_DMatrix4 &xform);
170 
171  /// Ensures the KD tree has been fully built. If a KD tree
172  /// is being shared among multiple threads, it is important it
173  /// has first been compiled on one thread to avoid race conditions
174  /// (GEO_PointTree is thread safe on read provided it has been built
175  /// and provided no new points are added to it)
178 
179  /// This must be called before querying, to build and balance the tree.
180  virtual void buildIfNeeded(bool enable_multithreading = true)
181  {
182  updateKDTree(enable_multithreading);
183  }
184 
185  /// Sets the KD-tree balancing algorithm.
186  /// - UT_KD_MEDIAN: splits at the median point
187  /// - UT_KD_CENTROID: splits at the spatial centroid
188  /// - UT_KD_SAH: splits at SAH optimal splitting point
189  /// The UT_KD_SAH (surface area heuristic) algorithm builds more
190  /// efficient trees but they are slower to construct. The default is
191  /// UT_KD_MEDIAN.
193  { UT_KDTree::setBalancer(balance); }
194 
195  /// Sets the maximum number of nodes to be stored in a leaf. Smaller
196  /// values will produce deeper and more memory-hungry trees.
197  void setMaxLeafNodes(int max_leaf_nodes)
198  { UT_KDTree::setMaxLeafNodes(max_leaf_nodes); }
199 
200 protected:
201  /// These are used by KDTree:
202  virtual int comparePosition(int idx0, int idx1, int dim) const;
203  virtual const float *getP(int idx) const;
204 
205  /// These are used if the user adds points with radii.
206  virtual bool pointsHaveRadius() const;
207  virtual fpreal getRadius(int idx) const;
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 
750 
751 #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:531
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:344
GEO_PointTreeT< int > GEO_PointTreeInt
For basic opaque integer id trees, use GEO_PointTreeInt.
void setMaxLeafNodes(int max_leaf_nodes)
Definition: UT_KDTree.h:537
void build(const UT_Vector3Array &pts, bool enable_multithreading=true)
void ensureTreeBuilt()
typedef void(APIENTRYP PFNGLCULLFACEPROC)(GLenum mode)
int findAllCloseIdx(const UT_Vector3 &pt, fpreal maxdist, IdxArrayType &list)
virtual void buildIfNeeded(bool enable_multithreading=true)
This must be called before querying, to build and balance the tree.
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)
int64 getMemoryUsage(bool inclusive) const
Definition: UT_KDTree.h:483
void updateKDTree(bool enablemultithread=true)
png_uint_32 i
Definition: png.h:2877
exint size() const
Definition: UT_Array.h:444
void setSize(exint newsize)
Definition: UT_Array.h:462
void setPointTransform(const UT_DMatrix4 &xform)
UT_ValArray< IdxType > IdxArrayType
Definition: GEO_PointTree.h:40
virtual fpreal getRadius(int idx) const
Return the radius associated with the point in question.
#define SYS_DEPRECATED_REPLACE(__V__, __R__)
UT_Vector3Array myPointList
The list of all the points.
UT_DMatrix4 * myPointTransform
long long int64
Definition: SYS_Types.h:100
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:2007
void setMaxLeafNodes(int max_leaf_nodes)
GEO_PointTreeT< GA_Index > Super
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
int64 exint
Definition: SYS_Types.h:109
Lookup point information to be passed to the query functions.
Definition: UT_KDTree.h:43
IdxArrayType myIndexList
This is the mapping from the KD entries into the GDP numbers.
#define GEO_API
Definition: GEO_API.h:10
int entries() const
Returns the number of actual points in the tree.
int isIdentity() const
Definition: UT_Matrix4.h:928
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
virtual bool pointsHaveRadius() const
These are used if the user adds points with radii.
double fpreal
Definition: SYS_Types.h:263
int findNearestGroupIdxQueue(const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist, ut_KDPQueue &q, bool wrapunitcube=false)
int findNearestGroupIdx(const UT_Vector3 &pt, fpreal maxdist, int groupsize, IdxArrayType &group, UT_FloatArray &groupdist)
ut_KDBalancer
KD Tree balancing algorithms. See setBalancer.
Definition: UT_KDTree.h:458
UT_FloatArray myRadii
List of radii for each pont.
virtual int comparePosition(int idx0, int idx1, int dim) const
These are used by KDTree:
void balance(bool enable_multithreading=true)
IdxType findNearestIdxQueue(const UT_Vector3 &pt, ut_KDPQueue &q, fpreal maxdist=1e18f, bool wrapunitcube=false)
virtual ~GEO_PointTreeT()
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.
virtual const float * getP(int idx) const
Return the position associated with the given point.