OpenVDB  11.0.0
PointIndexGrid.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /// @file PointIndexGrid.h
5 ///
6 /// @brief Space-partitioning acceleration structure for points. Partitions
7 /// the points into voxels to accelerate range and nearest neighbor
8 /// searches.
9 ///
10 /// @note Leaf nodes store a single point-index array and the voxels are only
11 /// integer offsets into that array. The actual points are never stored
12 /// in the acceleration structure, only offsets into an external array.
13 ///
14 /// @author Mihai Alden
15 
16 #ifndef OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
17 #define OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
18 
19 #include "PointPartitioner.h"
20 
21 #include <openvdb/thread/Threading.h>
22 #include <openvdb/version.h>
23 #include <openvdb/Exceptions.h>
24 #include <openvdb/Grid.h>
25 #include <openvdb/Types.h>
26 #include <openvdb/math/Transform.h>
28 #include <openvdb/tree/LeafNode.h>
29 #include <openvdb/tree/Tree.h>
30 
31 #include <tbb/blocked_range.h>
32 #include <tbb/parallel_for.h>
33 #include <atomic>
34 #include <algorithm> // for std::min(), std::max()
35 #include <cmath> // for std::sqrt()
36 #include <deque>
37 #include <iostream>
38 #include <type_traits> // for std::is_same
39 #include <utility> // for std::pair
40 #include <vector>
41 
42 
43 namespace openvdb {
45 namespace OPENVDB_VERSION_NAME {
46 
47 namespace tree {
48 template<Index, typename> struct SameLeafConfig; // forward declaration
49 }
50 
51 namespace tools {
52 
53 template<typename T, Index Log2Dim> struct PointIndexLeafNode; // forward declaration
54 
55 /// Point index tree configured to match the default OpenVDB tree configuration
58 
59 /// Point index grid
61 
62 
63 ////////////////////////////////////////
64 
65 
66 /// @interface PointArray
67 /// Expected interface for the PointArray container:
68 /// @code
69 /// template<typename VectorType>
70 /// struct PointArray
71 /// {
72 /// // The type used to represent world-space point positions
73 /// using PosType = VectorType;
74 ///
75 /// // Return the number of points in the array
76 /// size_t size() const;
77 ///
78 /// // Return the world-space position of the nth point in the array.
79 /// void getPos(size_t n, PosType& xyz) const;
80 /// };
81 /// @endcode
82 
83 
84 ////////////////////////////////////////
85 
86 
87 /// @brief Partition points into a point index grid to accelerate range and
88 /// nearest-neighbor searches.
89 ///
90 /// @param points world-space point array conforming to the PointArray interface
91 /// @param voxelSize voxel size in world units
92 template<typename GridT, typename PointArrayT>
93 inline typename GridT::Ptr
94 createPointIndexGrid(const PointArrayT& points, double voxelSize);
95 
96 
97 /// @brief Partition points into a point index grid to accelerate range and
98 /// nearest-neighbor searches.
99 ///
100 /// @param points world-space point array conforming to the PointArray interface
101 /// @param xform world-to-index-space transform
102 template<typename GridT, typename PointArrayT>
103 inline typename GridT::Ptr
104 createPointIndexGrid(const PointArrayT& points, const math::Transform& xform);
105 
106 
107 /// @brief Return @c true if the given point index grid represents a valid partitioning
108 /// of the given point array.
109 ///
110 /// @param points world-space point array conforming to the PointArray interface
111 /// @param grid point index grid to validate
112 template<typename PointArrayT, typename GridT>
113 inline bool
114 isValidPartition(const PointArrayT& points, const GridT& grid);
115 
116 
117 /// Repartition the @a points if needed, otherwise return the input @a grid.
118 template<typename GridT, typename PointArrayT>
119 inline typename GridT::ConstPtr
120 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::ConstPtr& grid);
121 
122 /// Repartition the @a points if needed, otherwise return the input @a grid.
123 template<typename GridT, typename PointArrayT>
124 inline typename GridT::Ptr
125 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::Ptr& grid);
126 
127 
128 ////////////////////////////////////////
129 
130 
131 /// Accelerated range and nearest-neighbor searches for point index grids
132 template<typename TreeType = PointIndexTree>
134 {
136  using LeafNodeType = typename TreeType::LeafNodeType;
137  using ValueType = typename TreeType::ValueType;
138 
139 
142  PointIndexIterator& operator=(const PointIndexIterator& rhs);
143 
144 
145  /// @brief Construct an iterator over the indices of the points contained in voxel (i, j, k).
146  /// @param ijk the voxel containing the points over which to iterate
147  /// @param acc an accessor for the grid or tree that holds the point indices
148  PointIndexIterator(const Coord& ijk, ConstAccessor& acc);
149 
150 
151  /// @brief Construct an iterator over the indices of the points contained in
152  /// the given bounding box.
153  /// @param bbox the bounding box of the voxels containing the points over which to iterate
154  /// @param acc an accessor for the grid or tree that holds the point indices
155  /// @note The range of the @a bbox is inclusive. Thus, a bounding box with
156  /// min = max is not empty but rather encloses a single voxel.
157  PointIndexIterator(const CoordBBox& bbox, ConstAccessor& acc);
158 
159 
160  /// @brief Clear the iterator and update it with the result of the given voxel query.
161  /// @param ijk the voxel containing the points over which to iterate
162  /// @param acc an accessor for the grid or tree that holds the point indices
163  void searchAndUpdate(const Coord& ijk, ConstAccessor& acc);
164 
165 
166  /// @brief Clear the iterator and update it with the result of the given voxel region query.
167  /// @param bbox the bounding box of the voxels containing the points over which to iterate
168  /// @param acc an accessor for the grid or tree that holds the point indices
169  /// @note The range of the @a bbox is inclusive. Thus, a bounding box with
170  /// min = max is not empty but rather encloses a single voxel.
171  void searchAndUpdate(const CoordBBox& bbox, ConstAccessor& acc);
172 
173 
174  /// @brief Clear the iterator and update it with the result of the given
175  /// index-space bounding box query.
176  /// @param bbox index-space bounding box
177  /// @param acc an accessor for the grid or tree that holds the point indices
178  /// @param points world-space point array conforming to the PointArray interface
179  /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
180  template<typename PointArray>
181  void searchAndUpdate(const BBoxd& bbox, ConstAccessor& acc,
182  const PointArray& points, const math::Transform& xform);
183 
184 
185  /// @brief Clear the iterator and update it with the result of the given
186  /// index-space radial query.
187  /// @param center index-space center
188  /// @param radius index-space radius
189  /// @param acc an accessor for the grid or tree that holds the point indices
190  /// @param points world-space point array conforming to the PointArray interface
191  /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
192  /// @param subvoxelAccuracy if true, check individual points against the search region,
193  /// otherwise return all points that reside in voxels that are inside
194  /// or intersect the search region
195  template<typename PointArray>
196  void searchAndUpdate(const Vec3d& center, double radius, ConstAccessor& acc,
197  const PointArray& points, const math::Transform& xform, bool subvoxelAccuracy = true);
198 
199 
200  /// @brief Clear the iterator and update it with the result of the given
201  /// world-space bounding box query.
202  /// @param bbox world-space bounding box
203  /// @param acc an accessor for the grid or tree that holds the point indices
204  /// @param points world-space point array conforming to the PointArray interface
205  /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
206  template<typename PointArray>
207  void worldSpaceSearchAndUpdate(const BBoxd& bbox, ConstAccessor& acc,
208  const PointArray& points, const math::Transform& xform);
209 
210 
211  /// @brief Clear the iterator and update it with the result of the given
212  /// world-space radial query.
213  /// @param center world-space center
214  /// @param radius world-space radius
215  /// @param acc an accessor for the grid or tree that holds the point indices
216  /// @param points world-space point array conforming to the PointArray interface
217  /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
218  /// @param subvoxelAccuracy if true, check individual points against the search region,
219  /// otherwise return all points that reside in voxels that are inside
220  /// or intersect the search region
221  template<typename PointArray>
222  void worldSpaceSearchAndUpdate(const Vec3d& center, double radius, ConstAccessor& acc,
223  const PointArray& points, const math::Transform& xform, bool subvoxelAccuracy = true);
224 
225 
226  /// Reset the iterator to point to the first item.
227  void reset();
228 
229  /// Return a const reference to the item to which this iterator is pointing.
230  const ValueType& operator*() const { return *mRange.first; }
231 
232  /// @{
233  /// @brief Return @c true if this iterator is not yet exhausted.
234  bool test() const { return mRange.first < mRange.second || mIter != mRangeList.end(); }
235  operator bool() const { return this->test(); }
236  /// @}
237 
238  /// Advance iterator to next item.
239  void increment();
240 
241  /// Advance iterator to next item.
242  void operator++() { this->increment(); }
243 
244 
245  /// @brief Advance iterator to next item.
246  /// @return @c true if this iterator is not yet exhausted.
247  bool next();
248 
249  /// Return the number of point indices in the iterator range.
250  size_t size() const;
251 
252  /// Return @c true if both iterators point to the same element.
253  bool operator==(const PointIndexIterator& p) const { return mRange.first == p.mRange.first; }
254  bool operator!=(const PointIndexIterator& p) const { return !this->operator==(p); }
255 
256 
257 private:
258  using Range = std::pair<const ValueType*, const ValueType*>;
259  using RangeDeque = std::deque<Range>;
260  using RangeDequeCIter = typename RangeDeque::const_iterator;
261  using IndexArray = std::unique_ptr<ValueType[]>;
262 
263  void clear();
264 
265  // Primary index collection
266  Range mRange;
267  RangeDeque mRangeList;
268  RangeDequeCIter mIter;
269  // Secondary index collection
270  IndexArray mIndexArray;
271  size_t mIndexArraySize;
272 }; // struct PointIndexIterator
273 
274 
275 /// @brief Selectively extract and filter point data using a custom filter operator.
276 ///
277 /// @par FilterType example:
278 /// @interface FilterType
279 /// @code
280 /// template<typename T>
281 /// struct WeightedAverageAccumulator {
282 /// using ValueType = T;
283 ///
284 /// WeightedAverageAccumulator(T const * const array, const T radius)
285 /// : mValues(array), mInvRadius(1.0/radius), mWeightSum(0.0), mValueSum(0.0) {}
286 ///
287 /// void reset() { mWeightSum = mValueSum = T(0.0); }
288 ///
289 /// // the following method is invoked by the PointIndexFilter
290 /// void operator()(const T distSqr, const size_t pointIndex) {
291 /// const T weight = T(1.0) - openvdb::math::Sqrt(distSqr) * mInvRadius;
292 /// mWeightSum += weight;
293 /// mValueSum += weight * mValues[pointIndex];
294 /// }
295 ///
296 /// T result() const { return mWeightSum > T(0.0) ? mValueSum / mWeightSum : T(0.0); }
297 ///
298 /// private:
299 /// T const * const mValues;
300 /// const T mInvRadius;
301 /// T mWeightSum, mValueSum;
302 /// }; // struct WeightedAverageAccumulator
303 /// @endcode
304 template<typename PointArray, typename TreeType = PointIndexTree>
306 {
307  using PosType = typename PointArray::PosType;
308  using ScalarType = typename PosType::value_type;
310 
311  /// @brief Constructor
312  /// @param points world-space point array conforming to the PointArray interface
313  /// @param tree a point index tree
314  /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
315  PointIndexFilter(const PointArray& points, const TreeType& tree, const math::Transform& xform);
316 
317  /// Thread safe copy constructor
319 
320  /// @brief Perform a radial search query and apply the given filter
321  /// operator to the selected points.
322  /// @param center world-space center
323  /// @param radius world-space radius
324  /// @param op custom filter operator (see the FilterType example for interface details)
325  template<typename FilterType>
326  void searchAndApply(const PosType& center, ScalarType radius, FilterType& op);
327 
328 private:
329  PointArray const * const mPoints;
330  ConstAccessor mAcc;
331  const math::Transform mXform;
332  const ScalarType mInvVoxelSize;
334 }; // struct PointIndexFilter
335 
336 
337 ////////////////////////////////////////
338 
339 // Internal operators and implementation details
340 
341 /// @cond OPENVDB_DOCS_INTERNAL
342 
343 namespace point_index_grid_internal {
344 
345 template<typename PointArrayT>
346 struct ValidPartitioningOp
347 {
348  ValidPartitioningOp(std::atomic<bool>& hasChanged,
349  const PointArrayT& points, const math::Transform& xform)
350  : mPoints(&points)
351  , mTransform(&xform)
352  , mHasChanged(&hasChanged)
353  {
354  }
355 
356  template <typename LeafT>
357  void operator()(LeafT &leaf, size_t /*leafIndex*/) const
358  {
359  if ((*mHasChanged)) {
360  thread::cancelGroupExecution();
361  return;
362  }
363 
364  using IndexArrayT = typename LeafT::IndexArray;
365  using IndexT = typename IndexArrayT::value_type;
366  using PosType = typename PointArrayT::PosType;
367 
368  typename LeafT::ValueOnCIter iter;
369  Coord voxelCoord;
370  PosType point;
371 
372  const IndexT
373  *begin = static_cast<IndexT*>(nullptr),
374  *end = static_cast<IndexT*>(nullptr);
375 
376  for (iter = leaf.cbeginValueOn(); iter; ++iter) {
377 
378  if ((*mHasChanged)) break;
379 
380  voxelCoord = iter.getCoord();
381  leaf.getIndices(iter.pos(), begin, end);
382 
383  while (begin < end) {
384 
385  mPoints->getPos(*begin, point);
386  if (voxelCoord != mTransform->worldToIndexCellCentered(point)) {
387  mHasChanged->store(true);
388  break;
389  }
390 
391  ++begin;
392  }
393  }
394  }
395 
396 private:
397  PointArrayT const * const mPoints;
398  math::Transform const * const mTransform;
399  std::atomic<bool> * const mHasChanged;
400 };
401 
402 
403 template<typename LeafNodeT>
404 struct PopulateLeafNodesOp
405 {
406  using IndexT = uint32_t;
408 
409  PopulateLeafNodesOp(std::unique_ptr<LeafNodeT*[]>& leafNodes,
410  const Partitioner& partitioner)
411  : mLeafNodes(leafNodes.get())
412  , mPartitioner(&partitioner)
413  {
414  }
415 
416  void operator()(const tbb::blocked_range<size_t>& range) const {
417 
418  using VoxelOffsetT = typename Partitioner::VoxelOffsetType;
419 
420  size_t maxPointCount = 0;
421  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
422  maxPointCount = std::max(maxPointCount, mPartitioner->indices(n).size());
423  }
424 
425  const IndexT voxelCount = LeafNodeT::SIZE;
426 
427  // allocate histogram buffers
428  std::unique_ptr<VoxelOffsetT[]> offsets{new VoxelOffsetT[maxPointCount]};
429  std::unique_ptr<IndexT[]> histogram{new IndexT[voxelCount]};
430 
431  VoxelOffsetT const * const voxelOffsets = mPartitioner->voxelOffsets().get();
432 
433  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
434 
435  LeafNodeT* node = new LeafNodeT();
436  node->setOrigin(mPartitioner->origin(n));
437 
438  typename Partitioner::IndexIterator it = mPartitioner->indices(n);
439 
440  const size_t pointCount = it.size();
441  IndexT const * const indices = &*it;
442 
443  // local copy of voxel offsets.
444  for (IndexT i = 0; i < pointCount; ++i) {
445  offsets[i] = voxelOffsets[ indices[i] ];
446  }
447 
448  // compute voxel-offset histogram
449  memset(&histogram[0], 0, voxelCount * sizeof(IndexT));
450  for (IndexT i = 0; i < pointCount; ++i) {
451  ++histogram[ offsets[i] ];
452  }
453 
454  typename LeafNodeT::NodeMaskType& mask = node->getValueMask();
455  typename LeafNodeT::Buffer& buffer = node->buffer();
456 
457  // scan histogram (all-prefix-sums)
458  IndexT count = 0, startOffset;
459  for (int i = 0; i < int(voxelCount); ++i) {
460  if (histogram[i] > 0) {
461  startOffset = count;
462  count += histogram[i];
463  histogram[i] = startOffset;
464  mask.setOn(i);
465  }
466  buffer.setValue(i, count);
467  }
468 
469  // allocate point-index array
470  node->indices().resize(pointCount);
471  typename LeafNodeT::ValueType * const orderedIndices = node->indices().data();
472 
473  // rank and permute
474  for (IndexT i = 0; i < pointCount; ++i) {
475  orderedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
476  }
477 
478  mLeafNodes[n] = node;
479  }
480  }
481 
482  //////////
483 
484  LeafNodeT* * const mLeafNodes;
485  Partitioner const * const mPartitioner;
486 };
487 
488 
489 /// Construct a @c PointIndexTree
490 template<typename TreeType, typename PointArray>
491 inline void
492 constructPointTree(TreeType& tree, const math::Transform& xform, const PointArray& points)
493 {
494  using LeafType = typename TreeType::LeafNodeType;
495 
496  std::unique_ptr<LeafType*[]> leafNodes;
497  size_t leafNodeCount = 0;
498 
499  {
500  // Important: Do not disable the cell-centered transform in the PointPartitioner.
501  // This interpretation is assumed in the PointIndexGrid and all related
502  // search algorithms.
504  partitioner.construct(points, xform, /*voxelOrder=*/false, /*recordVoxelOffsets=*/true);
505 
506  if (!partitioner.usingCellCenteredTransform()) {
507  OPENVDB_THROW(LookupError, "The PointIndexGrid requires a "
508  "cell-centered transform.");
509  }
510 
511  leafNodeCount = partitioner.size();
512  leafNodes.reset(new LeafType*[leafNodeCount]);
513 
514  const tbb::blocked_range<size_t> range(0, leafNodeCount);
515  tbb::parallel_for(range, PopulateLeafNodesOp<LeafType>(leafNodes, partitioner));
516  }
517 
519  for (size_t n = 0; n < leafNodeCount; ++n) {
520  acc.addLeaf(leafNodes[n]);
521  }
522 }
523 
524 
525 ////////////////////////////////////////
526 
527 
528 template<typename T>
529 inline void
530 dequeToArray(const std::deque<T>& d, std::unique_ptr<T[]>& a, size_t& size)
531 {
532  size = d.size();
533  a.reset(new T[size]);
534  typename std::deque<T>::const_iterator it = d.begin(), itEnd = d.end();
535  T* item = a.get();
536  for ( ; it != itEnd; ++it, ++item) *item = *it;
537 }
538 
539 
540 inline void
541 constructExclusiveRegions(std::vector<CoordBBox>& regions,
542  const CoordBBox& bbox, const CoordBBox& ibox)
543 {
544  regions.clear();
545  regions.reserve(6);
546  Coord cmin = ibox.min();
547  Coord cmax = ibox.max();
548 
549  // left-face bbox
550  regions.push_back(bbox);
551  regions.back().max().z() = cmin.z();
552 
553  // right-face bbox
554  regions.push_back(bbox);
555  regions.back().min().z() = cmax.z();
556 
557  --cmax.z(); // accounting for cell centered bucketing.
558  ++cmin.z();
559 
560  // front-face bbox
561  regions.push_back(bbox);
562  CoordBBox* lastRegion = &regions.back();
563  lastRegion->min().z() = cmin.z();
564  lastRegion->max().z() = cmax.z();
565  lastRegion->max().x() = cmin.x();
566 
567  // back-face bbox
568  regions.push_back(*lastRegion);
569  lastRegion = &regions.back();
570  lastRegion->min().x() = cmax.x();
571  lastRegion->max().x() = bbox.max().x();
572 
573  --cmax.x();
574  ++cmin.x();
575 
576  // bottom-face bbox
577  regions.push_back(*lastRegion);
578  lastRegion = &regions.back();
579  lastRegion->min().x() = cmin.x();
580  lastRegion->max().x() = cmax.x();
581  lastRegion->max().y() = cmin.y();
582 
583  // top-face bbox
584  regions.push_back(*lastRegion);
585  lastRegion = &regions.back();
586  lastRegion->min().y() = cmax.y();
587  lastRegion->max().y() = bbox.max().y();
588 }
589 
590 
591 template<typename PointArray, typename IndexT>
592 struct BBoxFilter
593 {
594  using PosType = typename PointArray::PosType;
595  using ScalarType = typename PosType::value_type;
596  using Range = std::pair<const IndexT*, const IndexT*>;
597  using RangeDeque = std::deque<Range>;
598  using IndexDeque = std::deque<IndexT>;
599 
600  BBoxFilter(RangeDeque& ranges, IndexDeque& indices, const BBoxd& bbox,
601  const PointArray& points, const math::Transform& xform)
602  : mRanges(ranges)
603  , mIndices(indices)
604  , mRegion(bbox)
605  , mPoints(points)
606  , mMap(*xform.baseMap())
607  {
608  }
609 
610  template <typename LeafNodeType>
611  void filterLeafNode(const LeafNodeType& leaf)
612  {
613  typename LeafNodeType::ValueOnCIter iter;
614  const IndexT
615  *begin = static_cast<IndexT*>(nullptr),
616  *end = static_cast<IndexT*>(nullptr);
617  for (iter = leaf.cbeginValueOn(); iter; ++iter) {
618  leaf.getIndices(iter.pos(), begin, end);
619  filterVoxel(iter.getCoord(), begin, end);
620  }
621  }
622 
623  void filterVoxel(const Coord&, const IndexT* begin, const IndexT* end)
624  {
625  PosType vec;
626 
627  for (; begin < end; ++begin) {
628  mPoints.getPos(*begin, vec);
629 
630  if (mRegion.isInside(mMap.applyInverseMap(vec))) {
631  mIndices.push_back(*begin);
632  }
633  }
634  }
635 
636 private:
637  RangeDeque& mRanges;
638  IndexDeque& mIndices;
639  const BBoxd mRegion;
640  const PointArray& mPoints;
641  const math::MapBase& mMap;
642 };
643 
644 
645 template<typename PointArray, typename IndexT>
646 struct RadialRangeFilter
647 {
648  using PosType = typename PointArray::PosType;
649  using ScalarType = typename PosType::value_type;
650  using Range = std::pair<const IndexT*, const IndexT*>;
651  using RangeDeque = std::deque<Range>;
652  using IndexDeque = std::deque<IndexT>;
653 
654  RadialRangeFilter(RangeDeque& ranges, IndexDeque& indices, const Vec3d& xyz, double radius,
655  const PointArray& points, const math::Transform& xform,
656  const double leafNodeDim, const bool subvoxelAccuracy)
657  : mRanges(ranges)
658  , mIndices(indices)
659  , mCenter(xyz)
660  , mWSCenter(xform.indexToWorld(xyz))
661  , mVoxelDist1(ScalarType(0.0))
662  , mVoxelDist2(ScalarType(0.0))
663  , mLeafNodeDist1(ScalarType(0.0))
664  , mLeafNodeDist2(ScalarType(0.0))
665  , mWSRadiusSqr(ScalarType(radius * xform.voxelSize()[0]))
666  , mPoints(points)
667  , mSubvoxelAccuracy(subvoxelAccuracy)
668  {
669  const ScalarType voxelRadius = ScalarType(std::sqrt(3.0) * 0.5);
670  mVoxelDist1 = voxelRadius + ScalarType(radius);
671  mVoxelDist1 *= mVoxelDist1;
672 
673  if (radius > voxelRadius) {
674  mVoxelDist2 = ScalarType(radius) - voxelRadius;
675  mVoxelDist2 *= mVoxelDist2;
676  }
677 
678  const ScalarType leafNodeRadius = ScalarType(leafNodeDim * std::sqrt(3.0) * 0.5);
679  mLeafNodeDist1 = leafNodeRadius + ScalarType(radius);
680  mLeafNodeDist1 *= mLeafNodeDist1;
681 
682  if (radius > leafNodeRadius) {
683  mLeafNodeDist2 = ScalarType(radius) - leafNodeRadius;
684  mLeafNodeDist2 *= mLeafNodeDist2;
685  }
686 
687  mWSRadiusSqr *= mWSRadiusSqr;
688  }
689 
690  template <typename LeafNodeType>
691  void filterLeafNode(const LeafNodeType& leaf)
692  {
693  {
694  const Coord& ijk = leaf.origin();
695  PosType vec;
696  vec[0] = ScalarType(ijk[0]);
697  vec[1] = ScalarType(ijk[1]);
698  vec[2] = ScalarType(ijk[2]);
699  vec += ScalarType(LeafNodeType::DIM - 1) * 0.5;
700  vec -= mCenter;
701 
702  const ScalarType dist = vec.lengthSqr();
703  if (dist > mLeafNodeDist1) return;
704 
705  if (mLeafNodeDist2 > 0.0 && dist < mLeafNodeDist2) {
706  const IndexT* begin = &leaf.indices().front();
707  mRanges.push_back(Range(begin, begin + leaf.indices().size()));
708  return;
709  }
710  }
711 
712  typename LeafNodeType::ValueOnCIter iter;
713  const IndexT
714  *begin = static_cast<IndexT*>(nullptr),
715  *end = static_cast<IndexT*>(nullptr);
716  for (iter = leaf.cbeginValueOn(); iter; ++iter) {
717  leaf.getIndices(iter.pos(), begin, end);
718  filterVoxel(iter.getCoord(), begin, end);
719  }
720  }
721 
722  void filterVoxel(const Coord& ijk, const IndexT* begin, const IndexT* end)
723  {
724  PosType vec;
725 
726  {
727  vec[0] = mCenter[0] - ScalarType(ijk[0]);
728  vec[1] = mCenter[1] - ScalarType(ijk[1]);
729  vec[2] = mCenter[2] - ScalarType(ijk[2]);
730 
731  const ScalarType dist = vec.lengthSqr();
732  if (dist > mVoxelDist1) return;
733 
734  if (!mSubvoxelAccuracy || (mVoxelDist2 > 0.0 && dist < mVoxelDist2)) {
735  if (!mRanges.empty() && mRanges.back().second == begin) {
736  mRanges.back().second = end;
737  } else {
738  mRanges.push_back(Range(begin, end));
739  }
740  return;
741  }
742  }
743 
744 
745  while (begin < end) {
746  mPoints.getPos(*begin, vec);
747  vec = mWSCenter - vec;
748 
749  if (vec.lengthSqr() < mWSRadiusSqr) {
750  mIndices.push_back(*begin);
751  }
752  ++begin;
753  }
754  }
755 
756 private:
757  RangeDeque& mRanges;
758  IndexDeque& mIndices;
759  const PosType mCenter, mWSCenter;
760  ScalarType mVoxelDist1, mVoxelDist2, mLeafNodeDist1, mLeafNodeDist2, mWSRadiusSqr;
761  const PointArray& mPoints;
762  const bool mSubvoxelAccuracy;
763 }; // struct RadialRangeFilter
764 
765 
766 ////////////////////////////////////////
767 
768 
769 template<typename RangeFilterType, typename LeafNodeType>
770 inline void
771 filteredPointIndexSearchVoxels(RangeFilterType& filter,
772  const LeafNodeType& leaf, const Coord& min, const Coord& max)
773 {
774  using PointIndexT = typename LeafNodeType::ValueType;
775  Index xPos(0), yPos(0), pos(0);
776  Coord ijk(0);
777 
778  const PointIndexT* dataPtr = &leaf.indices().front();
779  PointIndexT beginOffset, endOffset;
780 
781  for (ijk[0] = min[0]; ijk[0] <= max[0]; ++ijk[0]) {
782  xPos = (ijk[0] & (LeafNodeType::DIM - 1u)) << (2 * LeafNodeType::LOG2DIM);
783  for (ijk[1] = min[1]; ijk[1] <= max[1]; ++ijk[1]) {
784  yPos = xPos + ((ijk[1] & (LeafNodeType::DIM - 1u)) << LeafNodeType::LOG2DIM);
785  for (ijk[2] = min[2]; ijk[2] <= max[2]; ++ijk[2]) {
786  pos = yPos + (ijk[2] & (LeafNodeType::DIM - 1u));
787 
788  beginOffset = (pos == 0 ? PointIndexT(0) : leaf.getValue(pos - 1));
789  endOffset = leaf.getValue(pos);
790 
791  if (endOffset > beginOffset) {
792  filter.filterVoxel(ijk, dataPtr + beginOffset, dataPtr + endOffset);
793  }
794  }
795  }
796  }
797 }
798 
799 
800 template<typename RangeFilterType, typename ConstAccessor>
801 inline void
802 filteredPointIndexSearch(RangeFilterType& filter, ConstAccessor& acc, const CoordBBox& bbox)
803 {
804  using LeafNodeType = typename ConstAccessor::TreeType::LeafNodeType;
805  Coord ijk(0), ijkMax(0), ijkA(0), ijkB(0);
806  const Coord leafMin = bbox.min() & ~(LeafNodeType::DIM - 1);
807  const Coord leafMax = bbox.max() & ~(LeafNodeType::DIM - 1);
808 
809  for (ijk[0] = leafMin[0]; ijk[0] <= leafMax[0]; ijk[0] += LeafNodeType::DIM) {
810  for (ijk[1] = leafMin[1]; ijk[1] <= leafMax[1]; ijk[1] += LeafNodeType::DIM) {
811  for (ijk[2] = leafMin[2]; ijk[2] <= leafMax[2]; ijk[2] += LeafNodeType::DIM) {
812 
813  if (const LeafNodeType* leaf = acc.probeConstLeaf(ijk)) {
814  ijkMax = ijk;
815  ijkMax.offset(LeafNodeType::DIM - 1);
816 
817  // intersect leaf bbox with search region.
818  ijkA = Coord::maxComponent(bbox.min(), ijk);
819  ijkB = Coord::minComponent(bbox.max(), ijkMax);
820 
821  if (ijkA != ijk || ijkB != ijkMax) {
822  filteredPointIndexSearchVoxels(filter, *leaf, ijkA, ijkB);
823  } else { // leaf bbox is inside the search region
824  filter.filterLeafNode(*leaf);
825  }
826  }
827  }
828  }
829  }
830 }
831 
832 
833 ////////////////////////////////////////
834 
835 
836 template<typename RangeDeque, typename LeafNodeType>
837 inline void
838 pointIndexSearchVoxels(RangeDeque& rangeList,
839  const LeafNodeType& leaf, const Coord& min, const Coord& max)
840 {
841  using PointIndexT = typename LeafNodeType::ValueType;
842  using IntT = typename PointIndexT::IntType;
843  using Range = typename RangeDeque::value_type;
844 
845  Index xPos(0), pos(0), zStride = Index(max[2] - min[2]);
846  const PointIndexT* dataPtr = &leaf.indices().front();
847  PointIndexT beginOffset(0), endOffset(0),
848  previousOffset(static_cast<IntT>(leaf.indices().size() + 1u));
849  Coord ijk(0);
850 
851  for (ijk[0] = min[0]; ijk[0] <= max[0]; ++ijk[0]) {
852  xPos = (ijk[0] & (LeafNodeType::DIM - 1u)) << (2 * LeafNodeType::LOG2DIM);
853 
854  for (ijk[1] = min[1]; ijk[1] <= max[1]; ++ijk[1]) {
855  pos = xPos + ((ijk[1] & (LeafNodeType::DIM - 1u)) << LeafNodeType::LOG2DIM);
856  pos += (min[2] & (LeafNodeType::DIM - 1u));
857 
858  beginOffset = (pos == 0 ? PointIndexT(0) : leaf.getValue(pos - 1));
859  endOffset = leaf.getValue(pos+zStride);
860 
861  if (endOffset > beginOffset) {
862 
863  if (beginOffset == previousOffset) {
864  rangeList.back().second = dataPtr + endOffset;
865  } else {
866  rangeList.push_back(Range(dataPtr + beginOffset, dataPtr + endOffset));
867  }
868 
869  previousOffset = endOffset;
870  }
871  }
872  }
873 }
874 
875 
876 template<typename RangeDeque, typename ConstAccessor>
877 inline void
878 pointIndexSearch(RangeDeque& rangeList, ConstAccessor& acc, const CoordBBox& bbox)
879 {
880  using LeafNodeType = typename ConstAccessor::TreeType::LeafNodeType;
881  using PointIndexT = typename LeafNodeType::ValueType;
882  using Range = typename RangeDeque::value_type;
883 
884  Coord ijk(0), ijkMax(0), ijkA(0), ijkB(0);
885  const Coord leafMin = bbox.min() & ~(LeafNodeType::DIM - 1);
886  const Coord leafMax = bbox.max() & ~(LeafNodeType::DIM - 1);
887 
888  for (ijk[0] = leafMin[0]; ijk[0] <= leafMax[0]; ijk[0] += LeafNodeType::DIM) {
889  for (ijk[1] = leafMin[1]; ijk[1] <= leafMax[1]; ijk[1] += LeafNodeType::DIM) {
890  for (ijk[2] = leafMin[2]; ijk[2] <= leafMax[2]; ijk[2] += LeafNodeType::DIM) {
891 
892  if (const LeafNodeType* leaf = acc.probeConstLeaf(ijk)) {
893  ijkMax = ijk;
894  ijkMax.offset(LeafNodeType::DIM - 1);
895 
896  // intersect leaf bbox with search region.
897  ijkA = Coord::maxComponent(bbox.min(), ijk);
898  ijkB = Coord::minComponent(bbox.max(), ijkMax);
899 
900  if (ijkA != ijk || ijkB != ijkMax) {
901  pointIndexSearchVoxels(rangeList, *leaf, ijkA, ijkB);
902  } else {
903  // leaf bbox is inside the search region, add all indices.
904  const PointIndexT* begin = &leaf->indices().front();
905  rangeList.push_back(Range(begin, (begin + leaf->indices().size())));
906  }
907  }
908  }
909  }
910  }
911 }
912 
913 
914 } // namespace point_index_grid_internal
915 
916 /// @endcond
917 
918 // PointIndexIterator implementation
919 
920 template<typename TreeType>
921 inline
923  : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
924  , mRangeList()
925  , mIter(mRangeList.begin())
926  , mIndexArray()
927  , mIndexArraySize(0)
928 {
929 }
930 
931 
932 template<typename TreeType>
933 inline
935  : mRange(rhs.mRange)
936  , mRangeList(rhs.mRangeList)
937  , mIter(mRangeList.begin())
938  , mIndexArray()
939  , mIndexArraySize(rhs.mIndexArraySize)
940 {
941  if (rhs.mIndexArray) {
942  mIndexArray.reset(new ValueType[mIndexArraySize]);
943  memcpy(mIndexArray.get(), rhs.mIndexArray.get(), mIndexArraySize * sizeof(ValueType));
944  }
945 }
946 
947 
948 template<typename TreeType>
951 {
952  if (&rhs != this) {
953  mRange = rhs.mRange;
954  mRangeList = rhs.mRangeList;
955  mIter = mRangeList.begin();
956  mIndexArray.reset();
957  mIndexArraySize = rhs.mIndexArraySize;
958 
959  if (rhs.mIndexArray) {
960  mIndexArray.reset(new ValueType[mIndexArraySize]);
961  memcpy(mIndexArray.get(), rhs.mIndexArray.get(), mIndexArraySize * sizeof(ValueType));
962  }
963  }
964  return *this;
965 }
966 
967 
968 template<typename TreeType>
969 inline
971  : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
972  , mRangeList()
973  , mIter(mRangeList.begin())
974  , mIndexArray()
975  , mIndexArraySize(0)
976 {
977  const LeafNodeType* leaf = acc.probeConstLeaf(ijk);
978  if (leaf && leaf->getIndices(ijk, mRange.first, mRange.second)) {
979  mRangeList.push_back(mRange);
980  mIter = mRangeList.begin();
981  }
982 }
983 
984 
985 template<typename TreeType>
986 inline
988  : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
989  , mRangeList()
990  , mIter(mRangeList.begin())
991  , mIndexArray()
992  , mIndexArraySize(0)
993 {
994  point_index_grid_internal::pointIndexSearch(mRangeList, acc, bbox);
995 
996  if (!mRangeList.empty()) {
997  mIter = mRangeList.begin();
998  mRange = mRangeList.front();
999  }
1000 }
1001 
1002 
1003 template<typename TreeType>
1004 inline void
1006 {
1007  mIter = mRangeList.begin();
1008  if (!mRangeList.empty()) {
1009  mRange = mRangeList.front();
1010  } else if (mIndexArray) {
1011  mRange.first = mIndexArray.get();
1012  mRange.second = mRange.first + mIndexArraySize;
1013  } else {
1014  mRange.first = static_cast<ValueType*>(nullptr);
1015  mRange.second = static_cast<ValueType*>(nullptr);
1016  }
1017 }
1018 
1019 
1020 template<typename TreeType>
1021 inline void
1023 {
1024  ++mRange.first;
1025  if (mRange.first >= mRange.second && mIter != mRangeList.end()) {
1026  ++mIter;
1027  if (mIter != mRangeList.end()) {
1028  mRange = *mIter;
1029  } else if (mIndexArray) {
1030  mRange.first = mIndexArray.get();
1031  mRange.second = mRange.first + mIndexArraySize;
1032  }
1033  }
1034 }
1035 
1036 
1037 template<typename TreeType>
1038 inline bool
1040 {
1041  if (!this->test()) return false;
1042  this->increment();
1043  return this->test();
1044 }
1045 
1046 
1047 template<typename TreeType>
1048 inline size_t
1050 {
1051  size_t count = 0;
1052  typename RangeDeque::const_iterator it = mRangeList.begin();
1053 
1054  for ( ; it != mRangeList.end(); ++it) {
1055  count += it->second - it->first;
1056  }
1057 
1058  return count + mIndexArraySize;
1059 }
1060 
1061 
1062 template<typename TreeType>
1063 inline void
1065 {
1066  mRange.first = static_cast<ValueType*>(nullptr);
1067  mRange.second = static_cast<ValueType*>(nullptr);
1068  mRangeList.clear();
1069  mIter = mRangeList.end();
1070  mIndexArray.reset();
1071  mIndexArraySize = 0;
1072 }
1073 
1074 
1075 template<typename TreeType>
1076 inline void
1078 {
1079  this->clear();
1080  const LeafNodeType* leaf = acc.probeConstLeaf(ijk);
1081  if (leaf && leaf->getIndices(ijk, mRange.first, mRange.second)) {
1082  mRangeList.push_back(mRange);
1083  mIter = mRangeList.begin();
1084  }
1085 }
1086 
1087 
1088 template<typename TreeType>
1089 inline void
1091 {
1092  this->clear();
1093  point_index_grid_internal::pointIndexSearch(mRangeList, acc, bbox);
1094 
1095  if (!mRangeList.empty()) {
1096  mIter = mRangeList.begin();
1097  mRange = mRangeList.front();
1098  }
1099 }
1100 
1101 
1102 template<typename TreeType>
1103 template<typename PointArray>
1104 inline void
1106  const PointArray& points, const math::Transform& xform)
1107 {
1108  this->clear();
1109 
1110  std::vector<CoordBBox> searchRegions;
1111  CoordBBox region(Coord::round(bbox.min()), Coord::round(bbox.max()));
1112 
1113  const Coord dim = region.dim();
1114  const int minExtent = std::min(dim[0], std::min(dim[1], dim[2]));
1115 
1116  if (minExtent > 2) {
1117  // collect indices that don't need to be tested
1118  CoordBBox ibox = region;
1119  ibox.expand(-1);
1120 
1121  point_index_grid_internal::pointIndexSearch(mRangeList, acc, ibox);
1122 
1123  // define regions for the filtered search
1124  ibox.expand(1);
1125  point_index_grid_internal::constructExclusiveRegions(searchRegions, region, ibox);
1126  } else {
1127  searchRegions.push_back(region);
1128  }
1129 
1130  // filtered search
1131  std::deque<ValueType> filteredIndices;
1132  point_index_grid_internal::BBoxFilter<PointArray, ValueType>
1133  filter(mRangeList, filteredIndices, bbox, points, xform);
1134 
1135  for (size_t n = 0, N = searchRegions.size(); n < N; ++n) {
1136  point_index_grid_internal::filteredPointIndexSearch(filter, acc, searchRegions[n]);
1137  }
1138 
1139  point_index_grid_internal::dequeToArray(filteredIndices, mIndexArray, mIndexArraySize);
1140 
1141  this->reset();
1142 }
1143 
1144 
1145 template<typename TreeType>
1146 template<typename PointArray>
1147 inline void
1148 PointIndexIterator<TreeType>::searchAndUpdate(const Vec3d& center, double radius,
1149  ConstAccessor& acc, const PointArray& points, const math::Transform& xform,
1150  bool subvoxelAccuracy)
1151 {
1152  this->clear();
1153  std::vector<CoordBBox> searchRegions;
1154 
1155  // bounding box
1156  CoordBBox bbox(
1157  Coord::round(Vec3d(center[0] - radius, center[1] - radius, center[2] - radius)),
1158  Coord::round(Vec3d(center[0] + radius, center[1] + radius, center[2] + radius)));
1159  bbox.expand(1);
1160 
1161  const double iRadius = radius * double(1.0 / std::sqrt(3.0));
1162  if (iRadius > 2.0) {
1163  // inscribed box
1164  CoordBBox ibox(
1165  Coord::round(Vec3d(center[0] - iRadius, center[1] - iRadius, center[2] - iRadius)),
1166  Coord::round(Vec3d(center[0] + iRadius, center[1] + iRadius, center[2] + iRadius)));
1167  ibox.expand(-1);
1168 
1169  // collect indices that don't need to be tested
1170  point_index_grid_internal::pointIndexSearch(mRangeList, acc, ibox);
1171 
1172  ibox.expand(1);
1173  point_index_grid_internal::constructExclusiveRegions(searchRegions, bbox, ibox);
1174  } else {
1175  searchRegions.push_back(bbox);
1176  }
1177 
1178  // filtered search
1179  std::deque<ValueType> filteredIndices;
1180  const double leafNodeDim = double(TreeType::LeafNodeType::DIM);
1181 
1182  using FilterT = point_index_grid_internal::RadialRangeFilter<PointArray, ValueType>;
1183 
1184  FilterT filter(mRangeList, filteredIndices,
1185  center, radius, points, xform, leafNodeDim, subvoxelAccuracy);
1186 
1187  for (size_t n = 0, N = searchRegions.size(); n < N; ++n) {
1188  point_index_grid_internal::filteredPointIndexSearch(filter, acc, searchRegions[n]);
1189  }
1190 
1191  point_index_grid_internal::dequeToArray(filteredIndices, mIndexArray, mIndexArraySize);
1192 
1193  this->reset();
1194 }
1195 
1196 
1197 template<typename TreeType>
1198 template<typename PointArray>
1199 inline void
1201  const PointArray& points, const math::Transform& xform)
1202 {
1203  this->searchAndUpdate(
1204  BBoxd(xform.worldToIndex(bbox.min()), xform.worldToIndex(bbox.max())), acc, points, xform);
1205 }
1206 
1207 
1208 template<typename TreeType>
1209 template<typename PointArray>
1210 inline void
1212  ConstAccessor& acc, const PointArray& points, const math::Transform& xform,
1213  bool subvoxelAccuracy)
1214 {
1215  this->searchAndUpdate(xform.worldToIndex(center),
1216  (radius / xform.voxelSize()[0]), acc, points, xform, subvoxelAccuracy);
1217 }
1218 
1219 
1220 ////////////////////////////////////////
1221 
1222 // PointIndexFilter implementation
1223 
1224 template<typename PointArray, typename TreeType>
1225 inline
1227  const PointArray& points, const TreeType& tree, const math::Transform& xform)
1228  : mPoints(&points), mAcc(tree), mXform(xform), mInvVoxelSize(1.0/xform.voxelSize()[0])
1229 {
1230 }
1231 
1232 
1233 template<typename PointArray, typename TreeType>
1234 inline
1236  : mPoints(rhs.mPoints)
1237  , mAcc(rhs.mAcc.tree())
1238  , mXform(rhs.mXform)
1239  , mInvVoxelSize(rhs.mInvVoxelSize)
1240 {
1241 }
1242 
1243 
1244 template<typename PointArray, typename TreeType>
1245 template<typename FilterType>
1246 inline void
1248  const PosType& center, ScalarType radius, FilterType& op)
1249 {
1250  if (radius * mInvVoxelSize < ScalarType(8.0)) {
1251  mIter.searchAndUpdate(openvdb::CoordBBox(
1252  mXform.worldToIndexCellCentered(center - radius),
1253  mXform.worldToIndexCellCentered(center + radius)), mAcc);
1254  } else {
1255  mIter.worldSpaceSearchAndUpdate(
1256  center, radius, mAcc, *mPoints, mXform, /*subvoxelAccuracy=*/false);
1257  }
1258 
1259  const ScalarType radiusSqr = radius * radius;
1260  ScalarType distSqr = 0.0;
1261  PosType pos;
1262  for (; mIter; ++mIter) {
1263  mPoints->getPos(*mIter, pos);
1264  pos -= center;
1265  distSqr = pos.lengthSqr();
1266 
1267  if (distSqr < radiusSqr) {
1268  op(distSqr, *mIter);
1269  }
1270  }
1271 }
1272 
1273 
1274 ////////////////////////////////////////
1275 
1276 
1277 template<typename GridT, typename PointArrayT>
1278 inline typename GridT::Ptr
1279 createPointIndexGrid(const PointArrayT& points, const math::Transform& xform)
1280 {
1281  typename GridT::Ptr grid = GridT::create(typename GridT::ValueType(0));
1282  grid->setTransform(xform.copy());
1283 
1284  if (points.size() > 0) {
1285  point_index_grid_internal::constructPointTree(
1286  grid->tree(), grid->transform(), points);
1287  }
1288 
1289  return grid;
1290 }
1291 
1292 
1293 template<typename GridT, typename PointArrayT>
1294 inline typename GridT::Ptr
1295 createPointIndexGrid(const PointArrayT& points, double voxelSize)
1296 {
1298  return createPointIndexGrid<GridT>(points, *xform);
1299 }
1300 
1301 
1302 template<typename PointArrayT, typename GridT>
1303 inline bool
1304 isValidPartition(const PointArrayT& points, const GridT& grid)
1305 {
1307 
1308  size_t pointCount = 0;
1309  for (size_t n = 0, N = leafs.leafCount(); n < N; ++n) {
1310  pointCount += leafs.leaf(n).indices().size();
1311  }
1312 
1313  if (points.size() != pointCount) {
1314  return false;
1315  }
1316 
1317  std::atomic<bool> changed;
1318  changed = false;
1319 
1320  point_index_grid_internal::ValidPartitioningOp<PointArrayT>
1321  op(changed, points, grid.transform());
1322 
1323  leafs.foreach(op);
1324 
1325  return !bool(changed);
1326 }
1327 
1328 
1329 template<typename GridT, typename PointArrayT>
1330 inline typename GridT::ConstPtr
1331 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::ConstPtr& grid)
1332 {
1333  if (isValidPartition(points, *grid)) {
1334  return grid;
1335  }
1336 
1337  return createPointIndexGrid<GridT>(points, grid->transform());
1338 }
1339 
1340 
1341 template<typename GridT, typename PointArrayT>
1342 inline typename GridT::Ptr
1343 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::Ptr& grid)
1344 {
1345  if (isValidPartition(points, *grid)) {
1346  return grid;
1347  }
1348 
1349  return createPointIndexGrid<GridT>(points, grid->transform());
1350 }
1351 
1352 
1353 ////////////////////////////////////////
1354 
1355 
1356 template<typename T, Index Log2Dim>
1357 struct PointIndexLeafNode : public tree::LeafNode<T, Log2Dim>
1358 {
1361 
1362  using ValueType = T;
1363  using IndexArray = std::vector<ValueType>;
1364 
1365 
1366  IndexArray& indices() { return mIndices; }
1367  const IndexArray& indices() const { return mIndices; }
1368 
1369  bool getIndices(const Coord& ijk, const ValueType*& begin, const ValueType*& end) const;
1370  bool getIndices(Index offset, const ValueType*& begin, const ValueType*& end) const;
1371 
1372  void setOffsetOn(Index offset, const ValueType& val);
1373  void setOffsetOnly(Index offset, const ValueType& val);
1374 
1375  bool isEmpty(const CoordBBox& bbox) const;
1376 
1377 private:
1378  IndexArray mIndices;
1379 
1380  ////////////////////////////////////////
1381 
1382  // The following methods had to be copied from the LeafNode class
1383  // to make the derived PointIndexLeafNode class compatible with the tree structure.
1384 
1385 public:
1388 
1389  using BaseLeaf::LOG2DIM;
1390  using BaseLeaf::TOTAL;
1391  using BaseLeaf::DIM;
1392  using BaseLeaf::NUM_VALUES;
1393  using BaseLeaf::NUM_VOXELS;
1394  using BaseLeaf::SIZE;
1395  using BaseLeaf::LEVEL;
1396 
1397  /// Default constructor
1398  PointIndexLeafNode() : BaseLeaf(), mIndices() {}
1399 
1400  explicit
1401  PointIndexLeafNode(const Coord& coords, const T& value = zeroVal<T>(), bool active = false)
1402  : BaseLeaf(coords, value, active)
1403  , mIndices()
1404  {
1405  }
1406 
1407  PointIndexLeafNode(PartialCreate, const Coord& coords,
1408  const T& value = zeroVal<T>(), bool active = false)
1409  : BaseLeaf(PartialCreate(), coords, value, active)
1410  , mIndices()
1411  {
1412  }
1413 
1414  /// Deep copy constructor
1415  PointIndexLeafNode(const PointIndexLeafNode& rhs) : BaseLeaf(rhs), mIndices(rhs.mIndices) {}
1416 
1417  /// @brief Return @c true if the given node (which may have a different @c ValueType
1418  /// than this node) has the same active value topology as this node.
1419  template<typename OtherType, Index OtherLog2Dim>
1421  return BaseLeaf::hasSameTopology(other);
1422  }
1423 
1424  /// Check for buffer, state and origin equivalence.
1425  bool operator==(const PointIndexLeafNode& other) const { return BaseLeaf::operator==(other); }
1426 
1427  bool operator!=(const PointIndexLeafNode& other) const { return !(other == *this); }
1428 
1429  template<MergePolicy Policy> void merge(const PointIndexLeafNode& rhs) {
1430  BaseLeaf::template merge<Policy>(rhs);
1431  }
1432  template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive) {
1433  BaseLeaf::template merge<Policy>(tileValue, tileActive);
1434  }
1435 
1436  template<MergePolicy Policy>
1437  void merge(const PointIndexLeafNode& other,
1438  const ValueType& /*bg*/, const ValueType& /*otherBG*/)
1439  {
1440  BaseLeaf::template merge<Policy>(other);
1441  }
1442 
1444  template<typename AccessorT>
1445  void addLeafAndCache(PointIndexLeafNode*, AccessorT&) {}
1446 
1447  //@{
1448  /// @brief Return a pointer to this node.
1449  PointIndexLeafNode* touchLeaf(const Coord&) { return this; }
1450  template<typename AccessorT>
1451  PointIndexLeafNode* touchLeafAndCache(const Coord&, AccessorT&) { return this; }
1452 
1453  template<typename NodeT, typename AccessorT>
1454  NodeT* probeNodeAndCache(const Coord&, AccessorT&)
1455  {
1457  if (!(std::is_same<NodeT, PointIndexLeafNode>::value)) return nullptr;
1458  return reinterpret_cast<NodeT*>(this);
1460  }
1461  PointIndexLeafNode* probeLeaf(const Coord&) { return this; }
1462  template<typename AccessorT>
1463  PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) { return this; }
1464  //@}
1465 
1466  //@{
1467  /// @brief Return a @const pointer to this node.
1468  const PointIndexLeafNode* probeConstLeaf(const Coord&) const { return this; }
1469  template<typename AccessorT>
1470  const PointIndexLeafNode* probeConstLeafAndCache(const Coord&, AccessorT&) const {return this;}
1471  template<typename AccessorT>
1472  const PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) const { return this; }
1473  const PointIndexLeafNode* probeLeaf(const Coord&) const { return this; }
1474  template<typename NodeT, typename AccessorT>
1475  const NodeT* probeConstNodeAndCache(const Coord&, AccessorT&) const
1476  {
1478  if (!(std::is_same<NodeT, PointIndexLeafNode>::value)) return nullptr;
1479  return reinterpret_cast<const NodeT*>(this);
1481  }
1482  //@}
1483 
1484 
1485  // I/O methods
1486 
1487  void readBuffers(std::istream& is, bool fromHalf = false);
1488  void readBuffers(std::istream& is, const CoordBBox&, bool fromHalf = false);
1489  void writeBuffers(std::ostream& os, bool toHalf = false) const;
1490 
1491 
1492  Index64 memUsage() const;
1493  Index64 memUsageIfLoaded() const;
1494 
1495 
1496  ////////////////////////////////////////
1497 
1498  // Disable all write methods to avoid unintentional changes
1499  // to the point-array offsets.
1500 
1502  assert(false && "Cannot modify voxel values in a PointIndexTree.");
1503  }
1504 
1505  void setActiveState(const Coord&, bool) { assertNonmodifiable(); }
1506  void setActiveState(Index, bool) { assertNonmodifiable(); }
1507 
1508  void setValueOnly(const Coord&, const ValueType&) { assertNonmodifiable(); }
1509  void setValueOnly(Index, const ValueType&) { assertNonmodifiable(); }
1510 
1511  void setValueOff(const Coord&) { assertNonmodifiable(); }
1512  void setValueOff(Index) { assertNonmodifiable(); }
1513 
1514  void setValueOff(const Coord&, const ValueType&) { assertNonmodifiable(); }
1515  void setValueOff(Index, const ValueType&) { assertNonmodifiable(); }
1516 
1517  void setValueOn(const Coord&) { assertNonmodifiable(); }
1518  void setValueOn(Index) { assertNonmodifiable(); }
1519 
1520  void setValueOn(const Coord&, const ValueType&) { assertNonmodifiable(); }
1521  void setValueOn(Index, const ValueType&) { assertNonmodifiable(); }
1522 
1523  void setValue(const Coord&, const ValueType&) { assertNonmodifiable(); }
1524 
1525  void setValuesOn() { assertNonmodifiable(); }
1526  void setValuesOff() { assertNonmodifiable(); }
1527 
1528  template<typename ModifyOp>
1529  void modifyValue(Index, const ModifyOp&) { assertNonmodifiable(); }
1530 
1531  template<typename ModifyOp>
1532  void modifyValue(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1533 
1534  template<typename ModifyOp>
1535  void modifyValueAndActiveState(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1536 
1537  void clip(const CoordBBox&, const ValueType&) { assertNonmodifiable(); }
1538 
1539  void fill(const CoordBBox&, const ValueType&, bool) { assertNonmodifiable(); }
1540  void fill(const ValueType&) {}
1541  void fill(const ValueType&, bool) { assertNonmodifiable(); }
1542 
1543  template<typename AccessorT>
1544  void setValueOnlyAndCache(const Coord&, const ValueType&, AccessorT&) {assertNonmodifiable();}
1545 
1546  template<typename ModifyOp, typename AccessorT>
1547  void modifyValueAndActiveStateAndCache(const Coord&, const ModifyOp&, AccessorT&) {
1548  assertNonmodifiable();
1549  }
1550 
1551  template<typename AccessorT>
1552  void setValueOffAndCache(const Coord&, const ValueType&, AccessorT&) { assertNonmodifiable(); }
1553 
1554  template<typename AccessorT>
1555  void setActiveStateAndCache(const Coord&, bool, AccessorT&) { assertNonmodifiable(); }
1556 
1557  void resetBackground(const ValueType&, const ValueType&) { assertNonmodifiable(); }
1558 
1559  void signedFloodFill(const ValueType&) { assertNonmodifiable(); }
1560  void signedFloodFill(const ValueType&, const ValueType&) { assertNonmodifiable(); }
1561 
1562  void negate() { assertNonmodifiable(); }
1563 
1564 protected:
1565  using ValueOn = typename BaseLeaf::ValueOn;
1566  using ValueOff = typename BaseLeaf::ValueOff;
1567  using ValueAll = typename BaseLeaf::ValueAll;
1568  using ChildOn = typename BaseLeaf::ChildOn;
1569  using ChildOff = typename BaseLeaf::ChildOff;
1570  using ChildAll = typename BaseLeaf::ChildAll;
1571 
1575 
1576  // During topology-only construction, access is needed
1577  // to protected/private members of other template instances.
1578  template<typename, Index> friend struct PointIndexLeafNode;
1579 
1583 
1584 public:
1585  using ValueOnIter = typename BaseLeaf::template ValueIter<
1587  using ValueOnCIter = typename BaseLeaf::template ValueIter<
1588  MaskOnIterator, const PointIndexLeafNode, const ValueType, ValueOn>;
1589  using ValueOffIter = typename BaseLeaf::template ValueIter<
1590  MaskOffIterator, PointIndexLeafNode, const ValueType, ValueOff>;
1591  using ValueOffCIter = typename BaseLeaf::template ValueIter<
1592  MaskOffIterator,const PointIndexLeafNode,const ValueType, ValueOff>;
1593  using ValueAllIter = typename BaseLeaf::template ValueIter<
1594  MaskDenseIterator, PointIndexLeafNode, const ValueType, ValueAll>;
1595  using ValueAllCIter = typename BaseLeaf::template ValueIter<
1596  MaskDenseIterator,const PointIndexLeafNode,const ValueType, ValueAll>;
1597  using ChildOnIter = typename BaseLeaf::template ChildIter<
1598  MaskOnIterator, PointIndexLeafNode, ChildOn>;
1599  using ChildOnCIter = typename BaseLeaf::template ChildIter<
1600  MaskOnIterator, const PointIndexLeafNode, ChildOn>;
1601  using ChildOffIter = typename BaseLeaf::template ChildIter<
1602  MaskOffIterator, PointIndexLeafNode, ChildOff>;
1603  using ChildOffCIter = typename BaseLeaf::template ChildIter<
1604  MaskOffIterator, const PointIndexLeafNode, ChildOff>;
1605  using ChildAllIter = typename BaseLeaf::template DenseIter<
1606  PointIndexLeafNode, ValueType, ChildAll>;
1607  using ChildAllCIter = typename BaseLeaf::template DenseIter<
1608  const PointIndexLeafNode, const ValueType, ChildAll>;
1609 
1610 #define VMASK_ this->getValueMask()
1611  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1612  ValueOnCIter beginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1613  ValueOnIter beginValueOn() { return ValueOnIter(VMASK_.beginOn(), this); }
1614  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1615  ValueOffCIter beginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1616  ValueOffIter beginValueOff() { return ValueOffIter(VMASK_.beginOff(), this); }
1617  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1618  ValueAllCIter beginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1619  ValueAllIter beginValueAll() { return ValueAllIter(VMASK_.beginDense(), this); }
1620 
1621  ValueOnCIter cendValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1622  ValueOnCIter endValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1623  ValueOnIter endValueOn() { return ValueOnIter(VMASK_.endOn(), this); }
1624  ValueOffCIter cendValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1625  ValueOffCIter endValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1626  ValueOffIter endValueOff() { return ValueOffIter(VMASK_.endOff(), this); }
1627  ValueAllCIter cendValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1628  ValueAllCIter endValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1629  ValueAllIter endValueAll() { return ValueAllIter(VMASK_.endDense(), this); }
1630 
1631  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1632  ChildOnCIter beginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1633  ChildOnIter beginChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1634  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1635  ChildOffCIter beginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1636  ChildOffIter beginChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1637  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1638  ChildAllCIter beginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1639  ChildAllIter beginChildAll() { return ChildAllIter(VMASK_.beginDense(), this); }
1640 
1641  ChildOnCIter cendChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1642  ChildOnCIter endChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1643  ChildOnIter endChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1644  ChildOffCIter cendChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1645  ChildOffCIter endChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1646  ChildOffIter endChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1647  ChildAllCIter cendChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1648  ChildAllCIter endChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1649  ChildAllIter endChildAll() { return ChildAllIter(VMASK_.endDense(), this); }
1650 #undef VMASK_
1651 }; // struct PointIndexLeafNode
1652 
1653 
1654 template<typename T, Index Log2Dim>
1655 inline bool
1657  const ValueType*& begin, const ValueType*& end) const
1658 {
1659  return getIndices(LeafNodeType::coordToOffset(ijk), begin, end);
1660 }
1661 
1662 
1663 template<typename T, Index Log2Dim>
1664 inline bool
1666  const ValueType*& begin, const ValueType*& end) const
1667 {
1668  if (this->isValueMaskOn(offset)) {
1669  const ValueType* dataPtr = &mIndices.front();
1670  begin = dataPtr + (offset == 0 ? ValueType(0) : this->buffer()[offset - 1]);
1671  end = dataPtr + this->buffer()[offset];
1672  return true;
1673  }
1674  return false;
1675 }
1676 
1677 
1678 template<typename T, Index Log2Dim>
1679 inline void
1681 {
1682  this->buffer().setValue(offset, val);
1683  this->setValueMaskOn(offset);
1684 }
1685 
1686 
1687 template<typename T, Index Log2Dim>
1688 inline void
1690 {
1691  this->buffer().setValue(offset, val);
1692 }
1693 
1694 
1695 template<typename T, Index Log2Dim>
1696 inline bool
1698 {
1699  Index xPos, pos, zStride = Index(bbox.max()[2] - bbox.min()[2]);
1700  Coord ijk;
1701 
1702  for (ijk[0] = bbox.min()[0]; ijk[0] <= bbox.max()[0]; ++ijk[0]) {
1703  xPos = (ijk[0] & (DIM - 1u)) << (2 * LOG2DIM);
1704 
1705  for (ijk[1] = bbox.min()[1]; ijk[1] <= bbox.max()[1]; ++ijk[1]) {
1706  pos = xPos + ((ijk[1] & (DIM - 1u)) << LOG2DIM);
1707  pos += (bbox.min()[2] & (DIM - 1u));
1708 
1709  if (this->buffer()[pos+zStride] > (pos == 0 ? T(0) : this->buffer()[pos - 1])) {
1710  return false;
1711  }
1712  }
1713  }
1714 
1715  return true;
1716 }
1717 
1718 
1719 template<typename T, Index Log2Dim>
1720 inline void
1721 PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
1722 {
1723  BaseLeaf::readBuffers(is, fromHalf);
1724 
1725  Index64 numIndices = Index64(0);
1726  is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1727 
1728  mIndices.resize(size_t(numIndices));
1729  is.read(reinterpret_cast<char*>(mIndices.data()), numIndices * sizeof(T));
1730 }
1731 
1732 
1733 template<typename T, Index Log2Dim>
1734 inline void
1735 PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, const CoordBBox& bbox, bool fromHalf)
1736 {
1737  // Read and clip voxel values.
1738  BaseLeaf::readBuffers(is, bbox, fromHalf);
1739 
1740  Index64 numIndices = Index64(0);
1741  is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1742 
1743  const Index64 numBytes = numIndices * sizeof(T);
1744 
1745  if (bbox.hasOverlap(this->getNodeBoundingBox())) {
1746  mIndices.resize(size_t(numIndices));
1747  is.read(reinterpret_cast<char*>(mIndices.data()), numBytes);
1748 
1749  /// @todo If any voxels were deactivated as a result of clipping in the call to
1750  /// BaseLeaf::readBuffers(), the point index list will need to be regenerated.
1751  } else {
1752  // Read and discard voxel values.
1753  std::unique_ptr<char[]> buf{new char[numBytes]};
1754  is.read(buf.get(), numBytes);
1755  }
1756 
1757  // Reserved for future use
1758  Index64 auxDataBytes = Index64(0);
1759  is.read(reinterpret_cast<char*>(&auxDataBytes), sizeof(Index64));
1760  if (auxDataBytes > 0) {
1761  // For now, read and discard any auxiliary data.
1762  std::unique_ptr<char[]> auxData{new char[auxDataBytes]};
1763  is.read(auxData.get(), auxDataBytes);
1764  }
1765 }
1766 
1767 
1768 template<typename T, Index Log2Dim>
1769 inline void
1770 PointIndexLeafNode<T, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
1771 {
1772  BaseLeaf::writeBuffers(os, toHalf);
1773 
1774  Index64 numIndices = Index64(mIndices.size());
1775  os.write(reinterpret_cast<const char*>(&numIndices), sizeof(Index64));
1776  os.write(reinterpret_cast<const char*>(mIndices.data()), numIndices * sizeof(T));
1777 
1778  // Reserved for future use
1779  const Index64 auxDataBytes = Index64(0);
1780  os.write(reinterpret_cast<const char*>(&auxDataBytes), sizeof(Index64));
1781 }
1782 
1783 
1784 template<typename T, Index Log2Dim>
1785 inline Index64
1787 {
1788  return BaseLeaf::memUsage() + Index64((sizeof(T)*mIndices.capacity()) + sizeof(mIndices));
1789 }
1790 
1791 template<typename T, Index Log2Dim>
1792 inline Index64
1794 {
1795  return BaseLeaf::memUsageIfLoaded() + Index64((sizeof(T)*mIndices.capacity()) + sizeof(mIndices));
1796 }
1797 
1798 } // namespace tools
1799 
1800 
1801 ////////////////////////////////////////
1802 
1803 
1804 namespace tree {
1805 
1806 /// Helper metafunction used to implement LeafNode::SameConfiguration
1807 /// (which, as an inner class, can't be independently specialized)
1808 template<Index Dim1, typename T2>
1810 {
1811  static const bool value = true;
1812 };
1813 
1814 } // namespace tree
1815 } // namespace OPENVDB_VERSION_NAME
1816 } // namespace openvdb
1817 
1818 #endif // OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
void setValueOnly(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1508
size_t size() const
Returns the number of buckets.
Definition: PointPartitioner.h:130
ValueOnCIter cbeginValueOn() const
Definition: PointIndexGrid.h:1611
ChildOnCIter cbeginChildOn() const
Definition: PointIndexGrid.h:1631
PointIndexLeafNode()
Default constructor.
Definition: PointIndexGrid.h:1398
math::Histogram histogram(const IterT &iter, double minVal, double maxVal, size_t numBins=10, bool threaded=true)
Iterate over a scalar grid and compute a histogram of the values of the voxels that are visited...
Definition: Statistics.h:343
void addLeaf(PointIndexLeafNode *)
Definition: PointIndexGrid.h:1443
typename BaseLeaf::template DenseIter< PointIndexLeafNode, ValueType, ChildAll > ChildAllIter
Definition: PointIndexGrid.h:1606
ValueOffCIter cbeginValueOff() const
Definition: PointIndexGrid.h:1614
ChildOffCIter endChildOff() const
Definition: PointIndexGrid.h:1645
ChildOnCIter beginChildOn() const
Definition: PointIndexGrid.h:1632
IndexArray & indices()
Definition: PointIndexGrid.h:1366
ValueAllCIter endValueAll() const
Definition: PointIndexGrid.h:1628
bool test() const
Return true if this iterator is not yet exhausted.
Definition: PointIndexGrid.h:234
GridT::Ptr createPointIndexGrid(const PointArrayT &points, const math::Transform &xform)
Partition points into a point index grid to accelerate range and nearest-neighbor searches...
Definition: PointIndexGrid.h:1279
Index64 pointCount(const PointDataTreeT &tree, const FilterT &filter=NullFilter(), const bool inCoreOnly=false, const bool threaded=true)
Count the total number of points in a PointDataTree.
Definition: PointCountImpl.h:18
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:504
void fill(const CoordBBox &, const ValueType &, bool)
Definition: PointIndexGrid.h:1539
The Value Accessor Implementation and API methods. The majoirty of the API matches the API of a compa...
Definition: ValueAccessor.h:68
void setActiveState(Index, bool)
Definition: PointIndexGrid.h:1506
const PointIndexLeafNode * probeConstLeafAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1470
Definition: NodeMasks.h:208
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
void setValueOnlyAndCache(const Coord &, const ValueType &, AccessorT &)
Definition: PointIndexGrid.h:1544
typename BaseLeaf::ValueOff ValueOff
Definition: PointIndexGrid.h:1566
void signedFloodFill(const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1560
typename BaseLeaf::template ValueIter< MaskDenseIterator, const PointIndexLeafNode, const ValueType, ValueAll > ValueAllCIter
Definition: PointIndexGrid.h:1596
bool operator!=(const PointIndexIterator &p) const
Definition: PointIndexGrid.h:254
typename BaseLeaf::template ValueIter< MaskOnIterator, PointIndexLeafNode, const ValueType, ValueOn > ValueOnIter
Definition: PointIndexGrid.h:1586
typename BaseLeaf::template ValueIter< MaskOffIterator, const PointIndexLeafNode, const ValueType, ValueOff > ValueOffCIter
Definition: PointIndexGrid.h:1592
ValueOnCIter endValueOn() const
Definition: PointIndexGrid.h:1622
ChildOffIter endChildOff()
Definition: PointIndexGrid.h:1646
Definition: InternalNode.h:33
const PointIndexLeafNode * probeConstLeaf(const Coord &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1468
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:29
Index64 memUsageIfLoaded() const
Definition: PointIndexGrid.h:1793
bool getIndices(const Coord &ijk, const ValueType *&begin, const ValueType *&end) const
Definition: PointIndexGrid.h:1656
PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1463
void fill(const ValueType &, bool)
Definition: PointIndexGrid.h:1541
typename BaseLeaf::template ChildIter< MaskOffIterator, const PointIndexLeafNode, ChildOff > ChildOffCIter
Definition: PointIndexGrid.h:1604
std::shared_ptr< T > SharedPtr
Definition: Types.h:114
Definition: RootNode.h:38
Definition: NodeMasks.h:270
typename BaseLeaf::template ChildIter< MaskOnIterator, const PointIndexLeafNode, ChildOn > ChildOnCIter
Definition: PointIndexGrid.h:1600
ValueOffCIter beginValueOff() const
Definition: PointIndexGrid.h:1615
void modifyValue(Index, const ModifyOp &)
Definition: PointIndexGrid.h:1529
bool next()
Advance iterator to next item.
Definition: PointIndexGrid.h:1039
SharedPtr< Transform > Ptr
Definition: Transform.h:42
bool operator==(const PointIndexLeafNode &other) const
Check for buffer, state and origin equivalence.
Definition: PointIndexGrid.h:1425
PointIndexLeafNode * probeLeaf(const Coord &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1461
void resetBackground(const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1557
void setValueOn(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1520
void modifyValueAndActiveStateAndCache(const Coord &, const ModifyOp &, AccessorT &)
Definition: PointIndexGrid.h:1547
typename PosType::value_type ScalarType
Definition: PointIndexGrid.h:308
void writeBuffers(std::ostream &os, bool toHalf=false) const
Definition: PointIndexGrid.h:1770
typename BaseLeaf::ValueAll ValueAll
Definition: PointIndexGrid.h:1567
ChildAllCIter cendChildAll() const
Definition: PointIndexGrid.h:1647
Accelerated range and nearest-neighbor searches for point index grids.
Definition: PointIndexGrid.h:133
PointIndexLeafNode(const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition: PointIndexGrid.h:1401
typename BaseLeaf::template ChildIter< MaskOffIterator, PointIndexLeafNode, ChildOff > ChildOffIter
Definition: PointIndexGrid.h:1602
ValueOffCIter cendValueOff() const
Definition: PointIndexGrid.h:1624
typename BaseLeaf::ValueOn ValueOn
Definition: PointIndexGrid.h:1565
void searchAndUpdate(const Coord &ijk, ConstAccessor &acc)
Clear the iterator and update it with the result of the given voxel query.
Definition: PointIndexGrid.h:1077
void increment()
Advance iterator to next item.
Definition: PointIndexGrid.h:1022
void searchAndApply(const PosType &center, ScalarType radius, FilterType &op)
Perform a radial search query and apply the given filter operator to the selected points...
Definition: PointIndexGrid.h:1247
typename BaseLeaf::ChildOff ChildOff
Definition: PointIndexGrid.h:1569
Index64 memUsageIfLoaded(const TreeT &tree, bool threaded=true)
Return the deserialized memory usage of this tree. This is not necessarily equal to the current memor...
Definition: Count.h:502
void merge(const PointIndexLeafNode &other, const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1437
ChildOnCIter cendChildOn() const
Definition: PointIndexGrid.h:1641
Spatially partitions points using a parallel radix-based sorting algorithm.
typename BaseLeaf::template ValueIter< MaskOnIterator, const PointIndexLeafNode, const ValueType, ValueOn > ValueOnCIter
Definition: PointIndexGrid.h:1588
ChildOnIter beginChildOn()
Definition: PointIndexGrid.h:1633
const PointIndexLeafNode * probeLeaf(const Coord &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1473
void setValueOn(const Coord &)
Definition: PointIndexGrid.h:1517
BBox< Coord > CoordBBox
Definition: NanoVDB.h:2535
const ValueType & operator*() const
Return a const reference to the item to which this iterator is pointing.
Definition: PointIndexGrid.h:230
typename NodeMaskType::OnIterator MaskOnIterator
Definition: PointIndexGrid.h:1572
Selectively extract and filter point data using a custom filter operator.
typename BaseLeaf::template ValueIter< MaskOffIterator, PointIndexLeafNode, const ValueType, ValueOff > ValueOffIter
Definition: PointIndexGrid.h:1590
ValueOnCIter beginValueOn() const
Definition: PointIndexGrid.h:1612
uint64_t Index64
Definition: Types.h:53
Definition: PointIndexGrid.h:305
size_t size() const
Return the number of point indices in the iterator range.
Definition: PointIndexGrid.h:1049
void setValueOnly(Index, const ValueType &)
Definition: PointIndexGrid.h:1509
void readBuffers(std::istream &is, bool fromHalf=false)
Definition: PointIndexGrid.h:1721
void addLeafAndCache(PointIndexLeafNode *, AccessorT &)
Definition: PointIndexGrid.h:1445
void setValueOff(Index, const ValueType &)
Definition: PointIndexGrid.h:1515
typename BaseLeaf::ChildAll ChildAll
Definition: PointIndexGrid.h:1570
PointIndexLeafNode * touchLeaf(const Coord &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1449
Vec3d worldToIndex(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:110
PointIndexFilter(const PointArray &points, const TreeType &tree, const math::Transform &xform)
Constructor.
Definition: PointIndexGrid.h:1226
Templated block class to hold specific data types and a fixed number of values determined by Log2Dim...
Definition: LeafNode.h:37
void construct(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false, bool cellCenteredTransform=true)
Partitions point indices into BucketLog2Dim aligned buckets.
Definition: PointPartitioner.h:1001
ValueOnCIter cendValueOn() const
Definition: PointIndexGrid.h:1621
SharedPtr< PointIndexLeafNode > Ptr
Definition: PointIndexGrid.h:1360
Ptr copy() const
Definition: Transform.h:50
Index64 memUsage(const TreeT &tree, bool threaded=true)
Return the total amount of memory in bytes occupied by this tree.
Definition: Count.h:493
ChildOffCIter beginChildOff() const
Definition: PointIndexGrid.h:1635
std::vector< ValueType > IndexArray
Definition: PointIndexGrid.h:1363
void setValuesOn()
Definition: PointIndexGrid.h:1525
PointIndexLeafNode(const PointIndexLeafNode &rhs)
Deep copy constructor.
Definition: PointIndexGrid.h:1415
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:28
#define VMASK_
Definition: PointIndexGrid.h:1610
Definition: PointPartitioner.h:76
typename PointArray::PosType PosType
Definition: PointIndexGrid.h:307
ValueOnIter beginValueOn()
Definition: PointIndexGrid.h:1613
typename NodeMaskType::DenseIterator MaskDenseIterator
Definition: PointIndexGrid.h:1574
std::vector< Index > IndexArray
Definition: PointMoveImpl.h:88
void setValueOff(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1514
Definition: Exceptions.h:13
void merge(const ValueType &tileValue, bool tileActive)
Definition: PointIndexGrid.h:1432
GridT::Ptr createPointIndexGrid(const PointArrayT &points, double voxelSize)
Partition points into a point index grid to accelerate range and nearest-neighbor searches...
Definition: PointIndexGrid.h:1295
void setValue(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1523
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:140
Definition: Transform.h:39
void assertNonmodifiable()
Definition: PointIndexGrid.h:1501
Definition: Tree.h:177
Definition: PointDataGrid.h:170
typename BaseLeaf::template ChildIter< MaskOnIterator, PointIndexLeafNode, ChildOn > ChildOnIter
Definition: PointIndexGrid.h:1598
Definition: LeafNode.h:210
typename NodeMaskType::OffIterator MaskOffIterator
Definition: PointIndexGrid.h:1573
PointIndexIterator & operator=(const PointIndexIterator &rhs)
Definition: PointIndexGrid.h:950
void merge(const PointIndexLeafNode &rhs)
Definition: PointIndexGrid.h:1429
bool operator==(const PointIndexIterator &p) const
Return true if both iterators point to the same element.
Definition: PointIndexGrid.h:253
const Vec3T & max() const
Return a const reference to the maximum point of this bounding box.
Definition: BBox.h:64
ChildOnCIter endChildOn() const
Definition: PointIndexGrid.h:1642
bool isEmpty() const
Return true if this node has no active voxels.
Definition: LeafNode.h:148
T ValueType
Definition: PointIndexGrid.h:1362
ValueOffIter beginValueOff()
Definition: PointIndexGrid.h:1616
bool usingCellCenteredTransform() const
Returns true if this point partitioning was constructed using a cell-centered transform.
Definition: PointPartitioner.h:159
Index32 Index
Definition: Types.h:54
ChildAllIter beginChildAll()
Definition: PointIndexGrid.h:1639
ValueOffCIter endValueOff() const
Definition: PointIndexGrid.h:1625
void setValuesOff()
Definition: PointIndexGrid.h:1526
ChildOnIter endChildOn()
Definition: PointIndexGrid.h:1643
Vec2< T > maxComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise maximum of the two vectors.
Definition: Vec2.h:513
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
bool isValidPartition(const PointArrayT &points, const GridT &grid)
Return true if the given point index grid represents a valid partitioning of the given point array...
Definition: PointIndexGrid.h:1304
Abstract base class for maps.
Definition: Maps.h:134
typename BaseLeaf::template ValueIter< MaskDenseIterator, PointIndexLeafNode, const ValueType, ValueAll > ValueAllIter
Definition: PointIndexGrid.h:1594
ValueAllCIter cbeginValueAll() const
Definition: PointIndexGrid.h:1617
const Vec3T & min() const
Return a const reference to the minimum point of this bounding box.
Definition: BBox.h:62
const PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1472
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:141
void setValueOff(const Coord &)
Definition: PointIndexGrid.h:1511
void setActiveStateAndCache(const Coord &, bool, AccessorT &)
Definition: PointIndexGrid.h:1555
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:307
void reset()
Reset the iterator to point to the first item.
Definition: PointIndexGrid.h:1005
void setActiveState(const Coord &, bool)
Definition: PointIndexGrid.h:1505
void setValueOn(Index, const ValueType &)
Definition: PointIndexGrid.h:1521
ValueAllIter beginValueAll()
Definition: PointIndexGrid.h:1619
void signedFloodFill(const ValueType &)
Definition: PointIndexGrid.h:1559
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains the voxel coordinate xyz. If no LeafNode exists...
Definition: ValueAccessor.h:838
const IndexArray & indices() const
Definition: PointIndexGrid.h:1367
ValueOnIter endValueOn()
Definition: PointIndexGrid.h:1623
void negate()
Definition: PointIndexGrid.h:1562
void setValueOffAndCache(const Coord &, const ValueType &, AccessorT &)
Definition: PointIndexGrid.h:1552
void setOffsetOn(Index offset, const ValueType &val)
Definition: PointIndexGrid.h:1680
void clip(const CoordBBox &, const ValueType &)
Definition: PointIndexGrid.h:1537
Index64 memUsage() const
Definition: PointIndexGrid.h:1786
typename TreeType::ValueType ValueType
Definition: PointIndexGrid.h:137
void worldSpaceSearchAndUpdate(const BBoxd &bbox, ConstAccessor &acc, const PointArray &points, const math::Transform &xform)
Clear the iterator and update it with the result of the given world-space bounding box query...
Definition: PointIndexGrid.h:1200
bool operator!=(const PointIndexLeafNode &other) const
Definition: PointIndexGrid.h:1427
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:84
const NodeT * probeConstNodeAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1475
ChildAllCIter beginChildAll() const
Definition: PointIndexGrid.h:1638
Vec3d voxelSize() const
Return the size of a voxel using the linear component of the map.
Definition: Transform.h:93
ValueAllIter endValueAll()
Definition: PointIndexGrid.h:1629
void modifyValueAndActiveState(const Coord &, const ModifyOp &)
Definition: PointIndexGrid.h:1535
PointIndexLeafNode(PartialCreate, const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition: PointIndexGrid.h:1407
typename BaseLeaf::ChildOn ChildOn
Definition: PointIndexGrid.h:1568
math::BBox< Vec3d > BBoxd
Definition: Types.h:84
ValueOffIter endValueOff()
Definition: PointIndexGrid.h:1626
Definition: PointIndexGrid.h:53
ChildAllCIter endChildAll() const
Definition: PointIndexGrid.h:1648
bool hasSameTopology(const PointIndexLeafNode< OtherType, OtherLog2Dim > *other) const
Return true if the given node (which may have a different ValueType than this node) has the same acti...
Definition: PointIndexGrid.h:1420
Coord worldToIndexCellCentered(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:111
Leaf nodes have no children, so their child iterators have no get/set accessors.
Definition: LeafNode.h:248
typename TreeType::LeafNodeType LeafNodeType
Definition: PointIndexGrid.h:136
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:110
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
void setValueOff(Index)
Definition: PointIndexGrid.h:1512
ChildOffIter beginChildOff()
Definition: PointIndexGrid.h:1636
Definition: NodeMasks.h:239
GridT::Ptr getValidPointIndexGrid(const PointArrayT &points, const typename GridT::Ptr &grid)
Repartition the points if needed, otherwise return the input grid.
Definition: PointIndexGrid.h:1343
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
void operator++()
Advance iterator to next item.
Definition: PointIndexGrid.h:242
ChildAllCIter cbeginChildAll() const
Definition: PointIndexGrid.h:1637
NodeT * probeNodeAndCache(const Coord &, AccessorT &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1454
ValueAllCIter beginValueAll() const
Definition: PointIndexGrid.h:1618
ValueAllCIter cendValueAll() const
Definition: PointIndexGrid.h:1627
void modifyValue(const Coord &, const ModifyOp &)
Definition: PointIndexGrid.h:1532
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:106
Definition: LeafNode.h:209
GridT::ConstPtr getValidPointIndexGrid(const PointArrayT &points, const typename GridT::ConstPtr &grid)
Repartition the points if needed, otherwise return the input grid.
Definition: PointIndexGrid.h:1331
PointIndexLeafNode * touchLeafAndCache(const Coord &, AccessorT &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1451
ChildOffCIter cendChildOff() const
Definition: PointIndexGrid.h:1644
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:473
ChildOffCIter cbeginChildOff() const
Definition: PointIndexGrid.h:1634
void fill(const ValueType &)
Definition: PointIndexGrid.h:1540
typename BaseLeaf::template DenseIter< const PointIndexLeafNode, const ValueType, ChildAll > ChildAllCIter
Definition: PointIndexGrid.h:1608
static Transform::Ptr createLinearTransform(double voxelSize=1.0)
Create and return a shared pointer to a new transform.
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
void setValueOn(Index)
Definition: PointIndexGrid.h:1518
void setOffsetOnly(Index offset, const ValueType &val)
Definition: PointIndexGrid.h:1689
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:689
PointIndexIterator()
Definition: PointIndexGrid.h:922
Definition: Exceptions.h:60
ChildAllIter endChildAll()
Definition: PointIndexGrid.h:1649