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