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