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