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