OpenVDB  3.0.0
PointIndexGrid.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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(0.0)
666  , mVoxelDist2(0.0)
667  , mLeafNodeDist1(0.0)
668  , mLeafNodeDist2(0.0)
669  , mWSRadiusSqr(radius * xform.voxelSize()[0])
670  , mPoints(points)
671  , mSubvoxelAccuracy(subvoxelAccuracy)
672  {
673  const PointElementType voxelRadius = std::sqrt(3.0) * 0.5;
674  mVoxelDist1 = voxelRadius + radius;
675  mVoxelDist1 *= mVoxelDist1;
676 
677  if (radius > voxelRadius) {
678  mVoxelDist2 = radius - voxelRadius;
679  mVoxelDist2 *= mVoxelDist2;
680  }
681 
682  const PointElementType leafNodeRadius = leafNodeDim * std::sqrt(3.0) * 0.5;
683  mLeafNodeDist1 = leafNodeRadius + radius;
684  mLeafNodeDist1 *= mLeafNodeDist1;
685 
686  if (radius > leafNodeRadius) {
687  mLeafNodeDist2 = 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 RangeDeque::value_type Range;
845 
846  Index xPos(0), pos(0), zStride = Index(max[2] - min[2]);
847  const PointIndexT* dataPtr = &leaf.indices().front();
848  PointIndexT beginOffset(0), endOffset(0),
849  previousOffset = PointIndexT(leaf.indices().size() + size_t(1));
850  Coord ijk(0);
851 
852  for (ijk[0] = min[0]; ijk[0] <= max[0]; ++ijk[0]) {
853  xPos = (ijk[0] & (LeafNodeType::DIM - 1u)) << (2 * LeafNodeType::LOG2DIM);
854 
855  for (ijk[1] = min[1]; ijk[1] <= max[1]; ++ijk[1]) {
856  pos = xPos + ((ijk[1] & (LeafNodeType::DIM - 1u)) << LeafNodeType::LOG2DIM);
857  pos += (min[2] & (LeafNodeType::DIM - 1u));
858 
859  beginOffset = (pos == 0 ? PointIndexT(0) : leaf.getValue(pos - 1));
860  endOffset = leaf.getValue(pos+zStride);
861 
862  if (endOffset > beginOffset) {
863 
864  if (beginOffset == previousOffset) {
865  rangeList.back().second = dataPtr + endOffset;
866  } else {
867  rangeList.push_back(Range(dataPtr + beginOffset, dataPtr + endOffset));
868  }
869 
870  previousOffset = endOffset;
871  }
872  }
873  }
874 }
875 
876 
877 template<typename RangeDeque, typename ConstAccessor>
878 inline void
879 pointIndexSearch(RangeDeque& rangeList, ConstAccessor& acc, const CoordBBox& bbox)
880 {
881  typedef typename ConstAccessor::TreeType::LeafNodeType LeafNodeType;
882  typedef typename LeafNodeType::ValueType PointIndexT;
883  typedef typename RangeDeque::value_type Range;
884 
885  Coord ijk(0), ijkMax(0), ijkA(0), ijkB(0);
886  const Coord leafMin = bbox.min() & ~(LeafNodeType::DIM - 1);
887  const Coord leafMax = bbox.max() & ~(LeafNodeType::DIM - 1);
888 
889  for (ijk[0] = leafMin[0]; ijk[0] <= leafMax[0]; ijk[0] += LeafNodeType::DIM) {
890  for (ijk[1] = leafMin[1]; ijk[1] <= leafMax[1]; ijk[1] += LeafNodeType::DIM) {
891  for (ijk[2] = leafMin[2]; ijk[2] <= leafMax[2]; ijk[2] += LeafNodeType::DIM) {
892 
893  if (const LeafNodeType* leaf = acc.probeConstLeaf(ijk)) {
894  ijkMax = ijk;
895  ijkMax.offset(LeafNodeType::DIM - 1);
896 
897  // intersect leaf bbox with search region.
898  ijkA = Coord::maxComponent(bbox.min(), ijk);
899  ijkB = Coord::minComponent(bbox.max(), ijkMax);
900 
901  if (ijkA != ijk || ijkB != ijkMax) {
902  pointIndexSearchVoxels(rangeList, *leaf, ijkA, ijkB);
903  } else {
904  // leaf bbox is inside the search region, add all indices.
905  const PointIndexT* begin = &leaf->indices().front();
906  rangeList.push_back(Range(begin, (begin + leaf->indices().size())));
907  }
908  }
909  }
910  }
911  }
912 }
913 
914 
915 } // namespace point_index_grid_internal
916 
917 
918 // PointIndexIterator implementation
919 
920 template<typename TreeType>
921 inline
923  : mRange(static_cast<ValueType*>(NULL), static_cast<ValueType*>(NULL))
924  , mRangeList()
925  , mIter(mRangeList.begin())
926  , mIndexArray()
927  , mIndexArraySize(0)
928 {
929 }
930 
931 
932 template<typename TreeType>
933 inline
935  : mRange(rhs.mRange)
936  , mRangeList(rhs.mRangeList)
937  , mIter(mRangeList.begin())
938  , mIndexArray()
939  , mIndexArraySize(rhs.mIndexArraySize)
940 {
941  if (rhs.mIndexArray) {
942  mIndexArray.reset(new ValueType[mIndexArraySize]);
943  memcpy(mIndexArray.get(), rhs.mIndexArray.get(), mIndexArraySize * sizeof(ValueType));
944  }
945 }
946 
947 
948 template<typename TreeType>
951 {
952  if (&rhs != this) {
953  mRange = rhs.mRange;
954  mRangeList = rhs.mRangeList;
955  mIter = mRangeList.begin();
956  mIndexArray.reset();
957  mIndexArraySize = rhs.mIndexArraySize;
958 
959  if (rhs.mIndexArray) {
960  mIndexArray.reset(new ValueType[mIndexArraySize]);
961  memcpy(mIndexArray.get(), rhs.mIndexArray.get(), mIndexArraySize * sizeof(ValueType));
962  }
963  }
964  return *this;
965 }
966 
967 
968 template<typename TreeType>
969 inline
971  : mRange(static_cast<ValueType*>(NULL), static_cast<ValueType*>(NULL))
972  , mRangeList()
973  , mIter(mRangeList.begin())
974  , mIndexArray()
975  , mIndexArraySize(0)
976 {
977  const LeafNodeType* leaf = acc.probeConstLeaf(ijk);
978  if (leaf && leaf->getIndices(ijk, mRange.first, mRange.second)) {
979  mRangeList.push_back(mRange);
980  mIter = mRangeList.begin();
981  }
982 }
983 
984 
985 template<typename TreeType>
986 inline
988  : mRange(static_cast<ValueType*>(NULL), static_cast<ValueType*>(NULL))
989  , mRangeList()
990  , mIter(mRangeList.begin())
991  , mIndexArray()
992  , mIndexArraySize(0)
993 {
994  point_index_grid_internal::pointIndexSearch(mRangeList, acc, bbox);
995 
996  if (!mRangeList.empty()) {
997  mIter = mRangeList.begin();
998  mRange = mRangeList.front();
999  }
1000 }
1001 
1002 
1003 template<typename TreeType>
1004 inline void
1006 {
1007  mIter = mRangeList.begin();
1008  if (!mRangeList.empty()) {
1009  mRange = mRangeList.front();
1010  } else if (mIndexArray) {
1011  mRange.first = mIndexArray.get();
1012  mRange.second = mRange.first + mIndexArraySize;
1013  } else {
1014  mRange.first = static_cast<ValueType*>(NULL);
1015  mRange.second = static_cast<ValueType*>(NULL);
1016  }
1017 }
1018 
1019 
1020 template<typename TreeType>
1021 inline void
1023 {
1024  ++mRange.first;
1025  if (mRange.first >= mRange.second && mIter != mRangeList.end()) {
1026  ++mIter;
1027  if (mIter != mRangeList.end()) {
1028  mRange = *mIter;
1029  } else if (mIndexArray) {
1030  mRange.first = mIndexArray.get();
1031  mRange.second = mRange.first + mIndexArraySize;
1032  }
1033  }
1034 }
1035 
1036 
1037 template<typename TreeType>
1038 inline bool
1040 {
1041  if (!this->test()) return false;
1042  this->increment();
1043  return this->test();
1044 }
1045 
1046 
1047 template<typename TreeType>
1048 inline size_t
1050 {
1051  size_t count = 0;
1052  typename RangeDeque::const_iterator it = mRangeList.begin();
1053 
1054  for ( ; it != mRangeList.end(); ++it) {
1055  count += it->second - it->first;
1056  }
1057 
1058  return count + mIndexArraySize;
1059 }
1060 
1061 
1062 template<typename TreeType>
1063 inline void
1065 {
1066  mRange.first = static_cast<ValueType*>(NULL);
1067  mRange.second = static_cast<ValueType*>(NULL);
1068  mRangeList.clear();
1069  mIter = mRangeList.end();
1070  mIndexArray.reset();
1071  mIndexArraySize = 0;
1072 }
1073 
1074 
1075 template<typename TreeType>
1076 inline void
1078 {
1079  this->clear();
1080  const LeafNodeType* leaf = acc.probeConstLeaf(ijk);
1081  if (leaf && leaf->getIndices(ijk, mRange.first, mRange.second)) {
1082  mRangeList.push_back(mRange);
1083  mIter = mRangeList.begin();
1084  }
1085 }
1086 
1087 
1088 template<typename TreeType>
1089 inline void
1091 {
1092  this->clear();
1093  point_index_grid_internal::pointIndexSearch(mRangeList, acc, bbox);
1094 
1095  if (!mRangeList.empty()) {
1096  mIter = mRangeList.begin();
1097  mRange = mRangeList.front();
1098  }
1099 }
1100 
1101 
1102 template<typename TreeType>
1103 template<typename PointArray>
1104 inline void
1106  const PointArray& points, const math::Transform& xform)
1107 {
1108  this->clear();
1109 
1110  std::vector<CoordBBox> searchRegions;
1111  CoordBBox region(Coord::round(bbox.min()), Coord::round(bbox.max()));
1112 
1113  const Coord dim = region.dim();
1114  const int minExtent = std::min(dim[0], std::min(dim[1], dim[2]));
1115 
1116  if (minExtent > 2) {
1117  // collect indices that don't need to be tested
1118  CoordBBox ibox = region;
1119  ibox.expand(-1);
1120 
1121  point_index_grid_internal::pointIndexSearch(mRangeList, acc, ibox);
1122 
1123  // define regions for the filtered search
1124  ibox.expand(1);
1125  point_index_grid_internal::constructExclusiveRegions(searchRegions, region, ibox);
1126  } else {
1127  searchRegions.push_back(region);
1128  }
1129 
1130  // filtered search
1131  std::deque<ValueType> filteredIndices;
1133  filter(mRangeList, filteredIndices, bbox, points, xform);
1134 
1135  for (size_t n = 0, N = searchRegions.size(); n < N; ++n) {
1136  point_index_grid_internal::filteredPointIndexSearch(filter, acc, searchRegions[n]);
1137  }
1138 
1139  point_index_grid_internal::dequeToArray(filteredIndices, mIndexArray, mIndexArraySize);
1140 
1141  this->reset();
1142 }
1143 
1144 
1145 template<typename TreeType>
1146 template<typename PointArray>
1147 inline void
1149  ConstAccessor& acc, const PointArray& points, const math::Transform& xform,
1150  bool subvoxelAccuracy)
1151 {
1152  this->clear();
1153  std::vector<CoordBBox> searchRegions;
1154 
1155  // bounding box
1156  CoordBBox bbox(
1157  Coord::round(Vec3d(center[0] - radius, center[1] - radius, center[2] - radius)),
1158  Coord::round(Vec3d(center[0] + radius, center[1] + radius, center[2] + radius)));
1159  bbox.expand(1);
1160 
1161  const double iRadius = radius * double(1.0 / std::sqrt(3.0));
1162  if (iRadius > 2.0) {
1163  // inscribed box
1164  CoordBBox ibox(
1165  Coord::round(Vec3d(center[0] - iRadius, center[1] - iRadius, center[2] - iRadius)),
1166  Coord::round(Vec3d(center[0] + iRadius, center[1] + iRadius, center[2] + iRadius)));
1167  ibox.expand(-1);
1168 
1169  // collect indices that don't need to be tested
1170  point_index_grid_internal::pointIndexSearch(mRangeList, acc, ibox);
1171 
1172  ibox.expand(1);
1173  point_index_grid_internal::constructExclusiveRegions(searchRegions, bbox, ibox);
1174  } else {
1175  searchRegions.push_back(bbox);
1176  }
1177 
1178  // filtered search
1179  std::deque<ValueType> filteredIndices;
1180  const double leafNodeDim = double(TreeType::LeafNodeType::DIM);
1181 
1183 
1184  FilterT filter(mRangeList, filteredIndices,
1185  center, radius, points, xform, leafNodeDim, subvoxelAccuracy);
1186 
1187  for (size_t n = 0, N = searchRegions.size(); n < N; ++n) {
1188  point_index_grid_internal::filteredPointIndexSearch(filter, acc, searchRegions[n]);
1189  }
1190 
1191  point_index_grid_internal::dequeToArray(filteredIndices, mIndexArray, mIndexArraySize);
1192 
1193  this->reset();
1194 }
1195 
1196 
1197 template<typename TreeType>
1198 template<typename PointArray>
1199 inline void
1201  const PointArray& points, const math::Transform& xform)
1202 {
1203  this->searchAndUpdate(
1204  BBoxd(xform.worldToIndex(bbox.min()), xform.worldToIndex(bbox.max())), acc, points, xform);
1205 }
1206 
1207 
1208 template<typename TreeType>
1209 template<typename PointArray>
1210 inline void
1212  ConstAccessor& acc, const PointArray& points, const math::Transform& xform,
1213  bool subvoxelAccuracy)
1214 {
1215  this->searchAndUpdate(xform.worldToIndex(center),
1216  (radius / xform.voxelSize()[0]), acc, points, xform, subvoxelAccuracy);
1217 }
1218 
1219 
1221 
1222 // PointIndexFilter implementation
1223 
1224 template<typename PointArray, typename TreeType>
1225 inline
1227  const PointArray& points, const TreeType& tree, const math::Transform& xform)
1228  : mPoints(&points), mAcc(tree), mXform(xform), mInvVoxelSize(1.0/xform.voxelSize()[0])
1229 {
1230 }
1231 
1232 
1233 template<typename PointArray, typename TreeType>
1234 inline
1236  : mPoints(rhs.mPoints)
1237  , mAcc(rhs.mAcc.tree())
1238  , mXform(rhs.mXform)
1239  , mInvVoxelSize(rhs.mInvVoxelSize)
1240 {
1241 }
1242 
1243 
1244 template<typename PointArray, typename TreeType>
1245 template<typename FilterType>
1246 inline void
1248  const PointType& center, PointElementType radius, FilterType& op)
1249 {
1250  if (radius * mInvVoxelSize < PointElementType(8.0)) {
1251  mIter.searchAndUpdate(openvdb::CoordBBox(
1252  mXform.worldToIndexCellCentered(center - radius),
1253  mXform.worldToIndexCellCentered(center + radius)), mAcc);
1254  } else {
1255  mIter.worldSpaceSearchAndUpdate(
1256  center, radius, mAcc, *mPoints, mXform, /*subvoxelAccuracy=*/false);
1257  }
1258 
1259  const PointElementType radiusSqr = radius * radius;
1260  PointElementType distSqr = 0.0;
1261  PointType pos;
1262  for (; mIter; ++mIter) {
1263  mPoints->getPos(*mIter, pos);
1264  pos -= center;
1265  distSqr = pos.lengthSqr();
1266 
1267  if (distSqr < radiusSqr) {
1268  op(distSqr, *mIter);
1269  }
1270  }
1271 }
1272 
1273 
1275 
1276 
1277 template<typename GridT, typename PointArrayT>
1278 inline typename GridT::Ptr
1279 createPointIndexGrid(const PointArrayT& points, const math::Transform& xform)
1280 {
1281  typename GridT::Ptr grid = GridT::create(typename GridT::ValueType(0));
1282  grid->setTransform(xform.copy());
1283 
1284  if (points.size() > 0) {
1286  grid->tree(), grid->transform(), points);
1287  }
1288 
1289  return grid;
1290 }
1291 
1292 
1293 template<typename PointArrayT, typename GridT>
1294 inline bool
1295 isValidPartition(const PointArrayT& points, const GridT& grid)
1296 {
1298 
1299  size_t pointCount = 0;
1300  for (size_t n = 0, N = leafs.leafCount(); n < N; ++n) {
1301  pointCount += leafs.leaf(n).indices().size();
1302  }
1303 
1304  if (points.size() != pointCount) {
1305  return false;
1306  }
1307 
1308  tbb::atomic<bool> changed;
1309  changed = false;
1310 
1312  op(changed, points, grid.transform());
1313 
1314  leafs.foreach(op);
1315 
1316  return !bool(changed);
1317 }
1318 
1319 
1320 template<typename GridT, typename PointArrayT>
1321 inline typename GridT::ConstPtr
1322 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::ConstPtr& grid)
1323 {
1324  if (isValidPartition(points, *grid)) {
1325  return grid;
1326  }
1327 
1328  return createPointIndexGrid<GridT>(points, grid->transform());
1329 }
1330 
1331 
1332 template<typename GridT, typename PointArrayT>
1333 inline typename GridT::Ptr
1334 getValidPointIndexGrid(const PointArrayT& points, const typename GridT::Ptr& grid)
1335 {
1336  if (isValidPartition(points, *grid)) {
1337  return grid;
1338  }
1339 
1340  return createPointIndexGrid<GridT>(points, grid->transform());
1341 }
1342 
1343 
1345 
1346 
1347 template<typename T, Index Log2Dim>
1348 struct PointIndexLeafNode : public tree::LeafNode<T, Log2Dim>
1349 {
1351  typedef boost::shared_ptr<PointIndexLeafNode> Ptr;
1352 
1353  typedef T ValueType;
1354  typedef std::vector<ValueType> IndexArray;
1355 
1356 
1357  IndexArray& indices() { return mIndices; }
1358  const IndexArray& indices() const { return mIndices; }
1359 
1360  bool getIndices(const Coord& ijk, const ValueType*& begin, const ValueType*& end) const;
1361  bool getIndices(Index offset, const ValueType*& begin, const ValueType*& end) const;
1362 
1363  void setOffsetOn(Index offset, const ValueType& val);
1364  void setOffsetOnly(Index offset, const ValueType& val);
1365 
1366  bool isEmpty(const CoordBBox& bbox) const;
1367 
1368 private:
1369  IndexArray mIndices;
1370 
1372 
1373  // The following methods had to be copied from the LeafNode class
1374  // to make the derived PointIndexLeafNode class compatible with the tree structure.
1375 
1376 public:
1379 
1380  using BaseLeaf::LOG2DIM;
1381  using BaseLeaf::TOTAL;
1382  using BaseLeaf::DIM;
1383  using BaseLeaf::NUM_VALUES;
1384  using BaseLeaf::NUM_VOXELS;
1385  using BaseLeaf::SIZE;
1386  using BaseLeaf::LEVEL;
1387 
1389  PointIndexLeafNode() : BaseLeaf(), mIndices() {}
1390 
1391  explicit
1392  PointIndexLeafNode(const Coord& coords, const T& value = zeroVal<T>(), bool active = false)
1393  : BaseLeaf(coords, value, active)
1394  , mIndices()
1395  {
1396  }
1397 
1398 #ifndef OPENVDB_2_ABI_COMPATIBLE
1399  PointIndexLeafNode(PartialCreate, const Coord& coords,
1400  const T& value = zeroVal<T>(), bool active = false)
1401  : BaseLeaf(PartialCreate(), coords, value, active)
1402  , mIndices()
1403  {
1404  }
1405 #endif
1406 
1408  PointIndexLeafNode(const PointIndexLeafNode& rhs) : BaseLeaf(rhs), mIndices(rhs.mIndices) {}
1409 
1412  template<typename OtherType, Index OtherLog2Dim>
1414  return BaseLeaf::hasSameTopology(other);
1415  }
1416 
1418  bool operator==(const PointIndexLeafNode& other) const { return BaseLeaf::operator==(other); }
1419 
1420  bool operator!=(const PointIndexLeafNode& other) const { return !(other == *this); }
1421 
1422  template<MergePolicy Policy> void merge(const PointIndexLeafNode& rhs) {
1423  BaseLeaf::merge<Policy>(rhs);
1424  }
1425  template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive) {
1426  BaseLeaf::template merge<Policy>(tileValue, tileActive);
1427  }
1428 
1429  template<MergePolicy Policy>
1430  void merge(const PointIndexLeafNode& other,
1431  const ValueType& /*bg*/, const ValueType& /*otherBG*/)
1432  {
1433  BaseLeaf::template merge<Policy>(other);
1434  }
1435 
1437  template<typename AccessorT>
1438  void addLeafAndCache(PointIndexLeafNode*, AccessorT&) {}
1439 
1441  PointIndexLeafNode* touchLeaf(const Coord&) { return this; }
1443  template<typename AccessorT>
1444  PointIndexLeafNode* touchLeafAndCache(const Coord&, AccessorT&) { return this; }
1445 
1446  template<typename NodeT, typename AccessorT>
1447  NodeT* probeNodeAndCache(const Coord&, AccessorT&)
1448  {
1450  if (!(boost::is_same<NodeT,PointIndexLeafNode>::value)) return NULL;
1451  return reinterpret_cast<NodeT*>(this);
1453  }
1454  PointIndexLeafNode* probeLeaf(const Coord&) { return this; }
1455  template<typename AccessorT>
1456  PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) { return this; }
1458 
1460  const PointIndexLeafNode* probeConstLeaf(const Coord&) const { return this; }
1462  template<typename AccessorT>
1463  const PointIndexLeafNode* probeConstLeafAndCache(const Coord&, AccessorT&) const {return this;}
1464  template<typename AccessorT>
1465  const PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) const { return this; }
1466  const PointIndexLeafNode* probeLeaf(const Coord&) const { return this; }
1467  template<typename NodeT, typename AccessorT>
1468  const NodeT* probeConstNodeAndCache(const Coord&, AccessorT&) const
1469  {
1471  if (!(boost::is_same<NodeT,PointIndexLeafNode>::value)) return NULL;
1472  return reinterpret_cast<const NodeT*>(this);
1474  }
1476 
1477 
1478  // I/O methods
1479 
1480  void readBuffers(std::istream& is, bool fromHalf = false);
1481  void readBuffers(std::istream& is, const CoordBBox&, bool fromHalf = false);
1482  void writeBuffers(std::ostream& os, bool toHalf = false) const;
1483 
1484 
1485  Index64 memUsage() const;
1486 
1487 
1489 
1490  // Disable all write methods to avoid unintentional changes
1491  // to the point-array offsets.
1492 
1494  assert(false && "Cannot modify voxel values in a PointIndexTree.");
1495  }
1496 
1497  void setActiveState(const Coord&, bool) { assertNonmodifiable(); }
1499 
1500  void setValueOnly(const Coord&, const ValueType&) { assertNonmodifiable(); }
1501  void setValueOnly(Index, const ValueType&) { assertNonmodifiable(); }
1502 
1503  void setValueOff(const Coord&) { assertNonmodifiable(); }
1505 
1506  void setValueOff(const Coord&, const ValueType&) { assertNonmodifiable(); }
1507  void setValueOff(Index, const ValueType&) { assertNonmodifiable(); }
1508 
1509  void setValueOn(const Coord&) { assertNonmodifiable(); }
1511 
1512  void setValueOn(const Coord&, const ValueType&) { assertNonmodifiable(); }
1513  void setValueOn(Index, const ValueType&) { assertNonmodifiable(); }
1514 
1515  void setValue(const Coord&, const ValueType&) { assertNonmodifiable(); }
1516 
1519 
1520  template<typename ModifyOp>
1521  void modifyValue(Index, const ModifyOp&) { assertNonmodifiable(); }
1522 
1523  template<typename ModifyOp>
1524  void modifyValue(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1525 
1526  template<typename ModifyOp>
1527  void modifyValueAndActiveState(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1528 
1529  void clip(const CoordBBox&, const ValueType&) { assertNonmodifiable(); }
1530 
1531  void fill(const CoordBBox&, const ValueType&, bool) { assertNonmodifiable(); }
1532  void fill(const ValueType&) {}
1533  void fill(const ValueType&, bool) { assertNonmodifiable(); }
1534 
1535  template<typename AccessorT>
1536  void setValueOnlyAndCache(const Coord&, const ValueType&, AccessorT&) {assertNonmodifiable();}
1537 
1538  template<typename ModifyOp, typename AccessorT>
1539  void modifyValueAndActiveStateAndCache(const Coord&, const ModifyOp&, AccessorT&) {
1541  }
1542 
1543  template<typename AccessorT>
1544  void setValueOffAndCache(const Coord&, const ValueType&, AccessorT&) { assertNonmodifiable(); }
1545 
1546  template<typename AccessorT>
1547  void setActiveStateAndCache(const Coord&, bool, AccessorT&) { assertNonmodifiable(); }
1548 
1549  void resetBackground(const ValueType&, const ValueType&) { assertNonmodifiable(); }
1550 
1551  void signedFloodFill(const ValueType&) { assertNonmodifiable(); }
1552  void signedFloodFill(const ValueType&, const ValueType&) { assertNonmodifiable(); }
1553 
1555 
1556 protected:
1557  typedef typename BaseLeaf::ValueOn ValueOn;
1558  typedef typename BaseLeaf::ValueOff ValueOff;
1559  typedef typename BaseLeaf::ValueAll ValueAll;
1560  typedef typename BaseLeaf::ChildOn ChildOn;
1561  typedef typename BaseLeaf::ChildOff ChildOff;
1562  typedef typename BaseLeaf::ChildAll ChildAll;
1563 
1567 
1568  // During topology-only construction, access is needed
1569  // to protected/private members of other template instances.
1570  template<typename, Index> friend struct PointIndexLeafNode;
1571 
1572  friend class tree::IteratorBase<MaskOnIterator, PointIndexLeafNode>;
1573  friend class tree::IteratorBase<MaskOffIterator, PointIndexLeafNode>;
1574  friend class tree::IteratorBase<MaskDenseIterator, PointIndexLeafNode>;
1575 
1576 public:
1577 
1578 
1579  typedef typename BaseLeaf::template ValueIter<
1581  typedef typename BaseLeaf::template ValueIter<
1583  typedef typename BaseLeaf::template ValueIter<
1585  typedef typename BaseLeaf::template ValueIter<
1587  typedef typename BaseLeaf::template ValueIter<
1589  typedef typename BaseLeaf::template ValueIter<
1591  typedef typename BaseLeaf::template ChildIter<
1593  typedef typename BaseLeaf::template ChildIter<
1595  typedef typename BaseLeaf::template ChildIter<
1597  typedef typename BaseLeaf::template ChildIter<
1599  typedef typename BaseLeaf::template DenseIter<
1601  typedef typename BaseLeaf::template DenseIter<
1602  const PointIndexLeafNode, const ValueType, ChildAll> ChildAllCIter;
1603 
1604 #define VMASK_ this->getValueMask()
1605  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1606  ValueOnCIter beginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1607  ValueOnIter beginValueOn() { return ValueOnIter(VMASK_.beginOn(), this); }
1608  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1609  ValueOffCIter beginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1610  ValueOffIter beginValueOff() { return ValueOffIter(VMASK_.beginOff(), this); }
1611  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1612  ValueAllCIter beginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1613  ValueAllIter beginValueAll() { return ValueAllIter(VMASK_.beginDense(), this); }
1614 
1615  ValueOnCIter cendValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1616  ValueOnCIter endValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1617  ValueOnIter endValueOn() { return ValueOnIter(VMASK_.endOn(), this); }
1618  ValueOffCIter cendValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1619  ValueOffCIter endValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1620  ValueOffIter endValueOff() { return ValueOffIter(VMASK_.endOff(), this); }
1621  ValueAllCIter cendValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1622  ValueAllCIter endValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1623  ValueAllIter endValueAll() { return ValueAllIter(VMASK_.endDense(), this); }
1624 
1625  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1626  ChildOnCIter beginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1627  ChildOnIter beginChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1628  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1629  ChildOffCIter beginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1630  ChildOffIter beginChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1631  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1632  ChildAllCIter beginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1633  ChildAllIter beginChildAll() { return ChildAllIter(VMASK_.beginDense(), this); }
1634 
1635  ChildOnCIter cendChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1636  ChildOnCIter endChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1637  ChildOnIter endChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1638  ChildOffCIter cendChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1639  ChildOffCIter endChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1640  ChildOffIter endChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1641  ChildAllCIter cendChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1642  ChildAllCIter endChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1643  ChildAllIter endChildAll() { return ChildAllIter(VMASK_.endDense(), this); }
1644 #undef VMASK_
1645 }; // struct PointIndexLeafNode
1646 
1647 
1648 template<typename T, Index Log2Dim>
1649 inline bool
1651  const ValueType*& begin, const ValueType*& end) const
1652 {
1653  return getIndices(LeafNodeType::coordToOffset(ijk), begin, end);
1654 }
1655 
1656 
1657 template<typename T, Index Log2Dim>
1658 inline bool
1660  const ValueType*& begin, const ValueType*& end) const
1661 {
1662  if (this->isValueMaskOn(offset)) {
1663  const ValueType* dataPtr = &mIndices.front();
1664  begin = dataPtr + (offset == 0 ? ValueType(0) : this->buffer()[offset - 1]);
1665  end = dataPtr + this->buffer()[offset];
1666  return true;
1667  }
1668  return false;
1669 }
1670 
1671 
1672 template<typename T, Index Log2Dim>
1673 inline void
1675 {
1676  this->buffer().setValue(offset, val);
1677  this->setValueMaskOn(offset);
1678 }
1679 
1680 
1681 template<typename T, Index Log2Dim>
1682 inline void
1684 {
1685  this->buffer().setValue(offset, val);
1686 }
1687 
1688 
1689 template<typename T, Index Log2Dim>
1690 inline bool
1691 PointIndexLeafNode<T, Log2Dim>::isEmpty(const CoordBBox& bbox) const
1692 {
1693  Index xPos, pos, zStride = Index(bbox.max()[2] - bbox.min()[2]);
1694  Coord ijk;
1695 
1696  for (ijk[0] = bbox.min()[0]; ijk[0] <= bbox.max()[0]; ++ijk[0]) {
1697  xPos = (ijk[0] & (DIM - 1u)) << (2 * LOG2DIM);
1698 
1699  for (ijk[1] = bbox.min()[1]; ijk[1] <= bbox.max()[1]; ++ijk[1]) {
1700  pos = xPos + ((ijk[1] & (DIM - 1u)) << LOG2DIM);
1701  pos += (bbox.min()[2] & (DIM - 1u));
1702 
1703  if (this->buffer()[pos+zStride] > (pos == 0 ? T(0) : this->buffer()[pos - 1])) {
1704  return false;
1705  }
1706  }
1707  }
1708 
1709  return true;
1710 }
1711 
1712 
1713 template<typename T, Index Log2Dim>
1714 inline void
1715 PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
1716 {
1717  BaseLeaf::readBuffers(is, fromHalf);
1718 
1719  Index64 numIndices = Index64(0);
1720  is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1721 
1722  mIndices.resize(size_t(numIndices));
1723  is.read(reinterpret_cast<char*>(mIndices.data()), numIndices * sizeof(T));
1724 }
1725 
1726 
1727 template<typename T, Index Log2Dim>
1728 inline void
1729 PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, const CoordBBox& bbox, bool fromHalf)
1730 {
1731  // Read and clip voxel values.
1732  BaseLeaf::readBuffers(is, bbox, fromHalf);
1733 
1734  Index64 numIndices = Index64(0);
1735  is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1736 
1737  const Index64 numBytes = numIndices * sizeof(T);
1738 
1739  if (bbox.hasOverlap(this->getNodeBoundingBox())) {
1740  mIndices.resize(size_t(numIndices));
1741  is.read(reinterpret_cast<char*>(mIndices.data()), numBytes);
1742 
1745  } else {
1746  // Read and discard voxel values.
1747  boost::scoped_array<char> buf(new char[numBytes]);
1748  is.read(buf.get(), numBytes);
1749  }
1750 
1751  // Reserved for future use
1752  Index64 auxDataBytes = Index64(0);
1753  is.read(reinterpret_cast<char*>(&auxDataBytes), sizeof(Index64));
1754  if (auxDataBytes > 0) {
1755  // For now, read and discard any auxiliary data.
1756  boost::scoped_array<char> auxData(new char[auxDataBytes]);
1757  is.read(auxData.get(), auxDataBytes);
1758  }
1759 }
1760 
1761 
1762 template<typename T, Index Log2Dim>
1763 inline void
1764 PointIndexLeafNode<T, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
1765 {
1766  BaseLeaf::writeBuffers(os, toHalf);
1767 
1768  Index64 numIndices = Index64(mIndices.size());
1769  os.write(reinterpret_cast<const char*>(&numIndices), sizeof(Index64));
1770  os.write(reinterpret_cast<const char*>(mIndices.data()), numIndices * sizeof(T));
1771 
1772  // Reserved for future use
1773  const Index64 auxDataBytes = Index64(0);
1774  os.write(reinterpret_cast<const char*>(&auxDataBytes), sizeof(Index64));
1775 }
1776 
1777 
1778 template<typename T, Index Log2Dim>
1779 inline Index64
1781 {
1782  return BaseLeaf::memUsage() + Index64((sizeof(T)*mIndices.capacity()) + sizeof(mIndices));
1783 }
1784 
1785 } // namespace tools
1786 
1787 
1789 
1790 
1791 namespace tree {
1792 
1795 template<Index Dim1, typename T2>
1797 {
1798  static const bool value = true;
1799 };
1800 
1801 } // namespace tree
1802 } // namespace OPENVDB_VERSION_NAME
1803 } // namespace openvdb
1804 
1805 #endif // OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
1806 
1807 // Copyright (c) 2012-2014 DreamWorks Animation LLC
1808 // All rights reserved. This software is distributed under the
1809 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
ValueOnIter beginValueOn()
Definition: PointIndexGrid.h:1607
ValueAllCIter cendValueAll() const
Definition: PointIndexGrid.h:1621
ValueOffCIter endValueOff() const
Definition: PointIndexGrid.h:1619
void fill(const CoordBBox &, const ValueType &, bool)
Definition: PointIndexGrid.h:1531
void increment()
Advance iterator to next item.
Definition: PointIndexGrid.h:1022
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 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:328
PointArray::value_type PointType
Definition: PointIndexGrid.h:593
void searchAndUpdate(const Coord &ijk, ConstAccessor &acc)
Clear the iterator and update it with the result of the given voxel query.
Definition: PointIndexGrid.h:1077
ValueAllIter beginValueAll()
Definition: PointIndexGrid.h:1613
ChildAllCIter endChildAll() const
Definition: PointIndexGrid.h:1642
IndexArray & indices()
Definition: PointIndexGrid.h:1357
GridT::ConstPtr getValidPointIndexGrid(const PointArrayT &points, const typename GridT::ConstPtr &grid)
Repartition the points if needed, otherwise return the input grid.
Definition: PointIndexGrid.h:1322
void addLeafAndCache(PointIndexLeafNode *, AccessorT &)
Definition: PointIndexGrid.h:1438
TreeType::ValueType ValueType
Definition: PointIndexGrid.h:147
void modifyValueAndActiveState(const Coord &, const ModifyOp &)
Definition: PointIndexGrid.h:1527
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:497
void writeBuffers(std::ostream &os, bool toHalf=false) const
Definition: PointIndexGrid.h:1764
size_t size() const
Return the number of point indices in the iterator range.
Definition: PointIndexGrid.h:1049
Partitioner const *const mPartitioner
Definition: PointIndexGrid.h:492
const ValueType & operator*() const
Return a const reference to the item to which this iterator is pointing.
Definition: PointIndexGrid.h:240
Calculate an axis-aligned bounding box in index space from a bounding sphere in world space...
Definition: Transform.h:66
void clip(const CoordBBox &, const ValueType &)
Definition: PointIndexGrid.h:1529
bool operator==(const LeafNode &other) const
Check for buffer, state and origin equivalence.
Definition: LeafNode.h:1648
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:1444
void setValueOnly(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1500
static const Index LEVEL
Definition: LeafNode.h:80
void setValueOff(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1506
ChildOffIter endChildOff()
Definition: PointIndexGrid.h:1640
bool operator!=(const PointIndexIterator &p) const
Definition: PointIndexGrid.h:264
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 operator++()
Advance iterator to next item.
Definition: PointIndexGrid.h:252
void setValuesOff()
Definition: PointIndexGrid.h:1518
uint64_t Index64
Definition: Types.h:58
bool operator!=(const PointIndexLeafNode &other) const
Definition: PointIndexGrid.h:1420
bool isEmpty() const
Return true if this node has no active voxels.
Definition: LeafNode.h:414
void negate()
Definition: PointIndexGrid.h:1554
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:1247
const PointIndexLeafNode * probeConstLeaf(const Coord &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1461
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointIndexGrid.h:423
PointPartitioner< IndexT, LeafNodeT::LOG2DIM > Partitioner
Definition: PointIndexGrid.h:414
PointType::ValueType PointElementType
Definition: PointIndexGrid.h:318
void assertNonmodifiable()
Definition: PointIndexGrid.h:1493
const NodeT * probeConstNodeAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1468
void merge(const PointIndexLeafNode &rhs)
Definition: PointIndexGrid.h:1422
BaseLeaf::ChildOff ChildOff
Definition: PointIndexGrid.h:1561
Grid< PointIndexTree > PointIndexGrid
Point index grid.
Definition: PointIndexGrid.h:80
void setValueOn(Index)
Definition: PointIndexGrid.h:1510
void merge(const ValueType &tileValue, bool tileActive)
Definition: PointIndexGrid.h:1425
ValueOnIter endValueOn()
Definition: PointIndexGrid.h:1617
void constructPointTree(TreeType &tree, const math::Transform &xform, const PointArray &points)
Construct a PointIndexTree.
Definition: PointIndexGrid.h:499
void constructExclusiveRegions(std::vector< CoordBBox > &regions, const CoordBBox &bbox, const CoordBBox &ibox)
Definition: PointIndexGrid.h:540
void reset()
Reset the iterator to point to the first item.
Definition: PointIndexGrid.h:1005
BaseLeaf::ChildOn ChildOn
Definition: PointIndexGrid.h:1560
const PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1465
const IndexArray & indices() const
Definition: PointIndexGrid.h:1358
ValueOffIter beginValueOff()
Definition: PointIndexGrid.h:1610
NodeMaskType::OnIterator MaskOnIterator
Definition: PointIndexGrid.h:1564
PointArray::value_type PointType
Definition: PointIndexGrid.h:317
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
Vec2< T > maxComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise maximum of the two vectors.
Definition: Vec2.h:506
Vec3d worldToIndex(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:137
BaseLeaf::template DenseIter< PointIndexLeafNode, ValueType, ChildAll > ChildAllIter
Definition: PointIndexGrid.h:1600
std::vector< ValueType > IndexArray
Definition: PointIndexGrid.h:1354
T ValueType
Definition: PointIndexGrid.h:1353
void resetBackground(const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1549
BaseLeaf::template ValueIter< MaskOffIterator, const PointIndexLeafNode, const ValueType, ValueOff > ValueOffCIter
Definition: PointIndexGrid.h:1586
void setValueOff(const Coord &)
Definition: PointIndexGrid.h:1503
ChildOffCIter cbeginChildOff() const
Definition: PointIndexGrid.h:1628
GridT::Ptr getValidPointIndexGrid(const PointArrayT &points, const typename GridT::Ptr &grid)
Repartition the points if needed, otherwise return the input grid.
Definition: PointIndexGrid.h:1334
bool test() const
Return true if this iterator is not yet exhausted.
Definition: PointIndexGrid.h:244
Partitions points into Log2Dim aligned buckets.
Definition: PointPartitioner.h:92
PointIndexLeafNode * touchLeaf(const Coord &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1442
ValueAllCIter cbeginValueAll() const
Definition: PointIndexGrid.h:1611
void filterVoxel(const Coord &ijk, const IndexT *begin, const IndexT *end)
Definition: PointIndexGrid.h:724
void setValuesOn()
Definition: PointIndexGrid.h:1517
tree::ValueAccessor< const TreeType > ConstAccessor
Definition: PointIndexGrid.h:145
ChildOnCIter beginChildOn() const
Definition: PointIndexGrid.h:1626
NodeMaskType::OffIterator MaskOffIterator
Definition: PointIndexGrid.h:1565
ChildAllIter beginChildAll()
Definition: PointIndexGrid.h:1633
void modifyValue(Index, const ModifyOp &)
Definition: PointIndexGrid.h:1521
void setActiveStateAndCache(const Coord &, bool, AccessorT &)
Definition: PointIndexGrid.h:1547
Multi-threaded space-partitioning scheme for points.
bool hasSameTopology(const LeafNode< OtherType, OtherLog2Dim > *other) const
Return true if the given node (which may have a different ValueType than this node) has the same acti...
Definition: LeafNode.h:1686
ValueOnCIter cendValueOn() const
Definition: PointIndexGrid.h:1615
void merge(const PointIndexLeafNode &other, const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1430
std::deque< IndexT > IndexDeque
Definition: PointIndexGrid.h:597
NodeMaskType::DenseIterator MaskDenseIterator
Definition: PointIndexGrid.h:1566
void pointIndexSearchVoxels(RangeDeque &rangeList, const LeafNodeType &leaf, const Coord &min, const Coord &max)
Definition: PointIndexGrid.h:840
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
Selectively extract and filter point data using a custom filter operator.
ChildOffCIter beginChildOff() const
Definition: PointIndexGrid.h:1629
void setValueOn(const Coord &)
Definition: PointIndexGrid.h:1509
static const Index TOTAL
Definition: LeafNode.h:75
Templated block class to hold specific data types and a fixed number of values determined by Log2Dim...
Definition: LeafNode.h:65
util::NodeMask< Log2Dim > NodeMaskType
Definition: PointIndexGrid.h:1378
void modifyValueAndActiveStateAndCache(const Coord &, const ModifyOp &, AccessorT &)
Definition: PointIndexGrid.h:1539
BaseLeaf::ValueAll ValueAll
Definition: PointIndexGrid.h:1559
PointIndexLeafNode * probeLeaf(const Coord &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1454
ValueOffCIter cendValueOff() const
Definition: PointIndexGrid.h:1618
BaseLeaf::template ValueIter< MaskDenseIterator, PointIndexLeafNode, const ValueType, ValueAll > ValueAllIter
Definition: PointIndexGrid.h:1588
PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1456
ChildOnCIter cendChildOn() const
Definition: PointIndexGrid.h:1635
#define OPENVDB_VERSION_NAME
Definition: version.h:43
PointIndexIterator()
Definition: PointIndexGrid.h:922
bool operator==(const PointIndexIterator &p) const
Return true if both iterators point to the same element.
Definition: PointIndexGrid.h:263
BaseLeaf::template ValueIter< MaskDenseIterator, const PointIndexLeafNode, const ValueType, ValueAll > ValueAllCIter
Definition: PointIndexGrid.h:1590
Leaf nodes have no children, so their child iterators have no get/set accessors.
Definition: LeafNode.h:511
void setOffsetOn(Index offset, const ValueType &val)
Definition: PointIndexGrid.h:1674
void fill(const ValueType &, bool)
Definition: PointIndexGrid.h:1533
Index32 Index
Definition: Types.h:59
std::pair< const IndexT *, const IndexT * > Range
Definition: PointIndexGrid.h:654
std::deque< Range > RangeDeque
Definition: PointIndexGrid.h:655
PointIndexIterator & operator=(const PointIndexIterator &rhs)
Definition: PointIndexGrid.h:950
void operator()(LeafT &leaf, size_t) const
Definition: PointIndexGrid.h:366
BaseLeaf::template ValueIter< MaskOffIterator, PointIndexLeafNode, const ValueType, ValueOff > ValueOffIter
Definition: PointIndexGrid.h:1584
Ptr copy() const
Definition: Transform.h:77
#define VMASK_
Definition: PointIndexGrid.h:1604
ValueOnCIter cbeginValueOn() const
Definition: PointIndexGrid.h:1605
void filterLeafNode(const LeafNodeType &leaf)
Definition: PointIndexGrid.h:610
BaseLeaf::template ChildIter< MaskOnIterator, PointIndexLeafNode, ChildOn > ChildOnIter
Definition: PointIndexGrid.h:1592
static const Index NUM_VALUES
Definition: LeafNode.h:77
BaseLeaf::ValueOff ValueOff
Definition: PointIndexGrid.h:1558
PointIndexFilter(const PointArray &points, const TreeType &tree, const math::Transform &xform)
Constructor.
Definition: PointIndexGrid.h:1226
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:383
void construct(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false)
Partitions point indices into Log2Dim aligned buckets.
Definition: PointPartitioner.h:1082
ValueOffCIter beginValueOff() const
Definition: PointIndexGrid.h:1609
PointIndexLeafNode(const PointIndexLeafNode &rhs)
Deep copy constructor.
Definition: PointIndexGrid.h:1408
void readBuffers(std::istream &is, bool fromHalf=false)
Definition: PointIndexGrid.h:1715
void setOffsetOnly(Index offset, const ValueType &val)
Definition: PointIndexGrid.h:1683
ValueAllCIter beginValueAll() const
Definition: PointIndexGrid.h:1612
BaseLeaf::ValueOn ValueOn
Definition: PointIndexGrid.h:1557
BaseLeaf::template ChildIter< MaskOffIterator, PointIndexLeafNode, ChildOff > ChildOffIter
Definition: PointIndexGrid.h:1596
Definition: NodeMasks.h:236
Definition: Exceptions.h:39
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:121
void dequeToArray(const std::deque< T > &d, boost::scoped_array< T > &a, size_t &size)
Definition: PointIndexGrid.h:529
Accelerated range and nearest-neighbor searches for point index grids.
Definition: PointIndexGrid.h:143
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
ChildAllCIter cendChildAll() const
Definition: PointIndexGrid.h:1641
BaseLeaf::template DenseIter< const PointIndexLeafNode, const ValueType, ChildAll > ChildAllCIter
Definition: PointIndexGrid.h:1602
const PointIndexLeafNode * probeLeaf(const Coord &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1466
BaseLeaf::template ChildIter< MaskOnIterator, const PointIndexLeafNode, ChildOn > ChildOnCIter
Definition: PointIndexGrid.h:1594
ChildOnIter beginChildOn()
Definition: PointIndexGrid.h:1627
Vec3< double > Vec3d
Definition: Vec3.h:629
ValueOnCIter beginValueOn() const
Definition: PointIndexGrid.h:1606
ChildOnCIter cbeginChildOn() const
Definition: PointIndexGrid.h:1625
BBoxFilter(RangeDeque &ranges, IndexDeque &indices, const BBoxd &bbox, const PointArray &points, const math::Transform &xform)
Definition: PointIndexGrid.h:599
NodeT * probeNodeAndCache(const Coord &, AccessorT &)
Return a pointer to this node.
Definition: PointIndexGrid.h:1447
BaseLeaf::ChildAll ChildAll
Definition: PointIndexGrid.h:1562
PointArray::value_type PointType
Definition: PointIndexGrid.h:652
Definition: PointIndexGrid.h:315
bool getIndices(const Coord &ijk, const ValueType *&begin, const ValueType *&end) const
Definition: PointIndexGrid.h:1650
bool next()
Advance iterator to next item.
Definition: PointIndexGrid.h:1039
std::pair< const IndexT *, const IndexT * > Range
Definition: PointIndexGrid.h:595
void addLeaf(PointIndexLeafNode *)
Definition: PointIndexGrid.h:1436
Definition: NodeMasks.h:267
tree::ValueAccessor< const TreeType > ConstAccessor
Definition: PointIndexGrid.h:319
ValueOffCIter cbeginValueOff() const
Definition: PointIndexGrid.h:1608
void pointIndexSearch(RangeDeque &rangeList, ConstAccessor &acc, const CoordBBox &bbox)
Definition: PointIndexGrid.h:879
static const bool value
Definition: LeafNode.h:1099
PointIndexLeafNode(const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition: PointIndexGrid.h:1392
ChildOffCIter cendChildOff() const
Definition: PointIndexGrid.h:1638
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:1413
PointType::ValueType PointElementType
Definition: PointIndexGrid.h:653
bool operator==(const PointIndexLeafNode &other) const
Check for buffer, state and origin equivalence.
Definition: PointIndexGrid.h:1418
static const Index SIZE
Definition: LeafNode.h:79
Vec3d voxelSize() const
Return the size of a voxel using the linear component of the map.
Definition: Transform.h:120
boost::shared_ptr< PointIndexLeafNode > Ptr
Definition: PointIndexGrid.h:1351
Definition: InternalNode.h:63
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
void setActiveState(Index, bool)
Definition: PointIndexGrid.h:1498
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:122
std::deque< Range > RangeDeque
Definition: PointIndexGrid.h:596
Definition: NodeMasks.h:205
void setValueOnlyAndCache(const Coord &, const ValueType &, AccessorT &)
Definition: PointIndexGrid.h:1536
PopulateLeafNodesOp(boost::scoped_array< LeafNodeT * > &leafNodes, const Partitioner &partitioner)
Definition: PointIndexGrid.h:416
ChildOnIter endChildOn()
Definition: PointIndexGrid.h:1637
Abstract base class for maps.
Definition: Maps.h:159
void signedFloodFill(const ValueType &, const ValueType &)
Definition: PointIndexGrid.h:1552
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:1295
ValueOnCIter endValueOn() const
Definition: PointIndexGrid.h:1616
void worldSpaceSearchAndUpdate(const BBoxd &bbox, ConstAccessor &acc, const PointArray &points, const math::Transform &xform)
Clear the iterator and update it with the result of the given world-space bounding box query...
Definition: PointIndexGrid.h:1200
PointIndexLeafNode(PartialCreate, const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition: PointIndexGrid.h:1399
Definition: PointIndexGrid.h:68
Definition: Tree.h:203
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
void filterLeafNode(const LeafNodeType &leaf)
Definition: PointIndexGrid.h:695
ValueAllCIter endValueAll() const
Definition: PointIndexGrid.h:1622
BaseLeaf::template ValueIter< MaskOnIterator, PointIndexLeafNode, const ValueType, ValueOn > ValueOnIter
Definition: PointIndexGrid.h:1580
ChildAllCIter cbeginChildAll() const
Definition: PointIndexGrid.h:1631
void setValueOnly(Index, const ValueType &)
Definition: PointIndexGrid.h:1501
std::deque< IndexT > IndexDeque
Definition: PointIndexGrid.h:656
ValueOffIter endValueOff()
Definition: PointIndexGrid.h:1620
static const Index LOG2DIM
Definition: LeafNode.h:74
size_t size() const
Number of point indices in the iterator range.
Definition: PointPartitioner.h:189
ValueAllIter endValueAll()
Definition: PointIndexGrid.h:1623
void setValueOff(Index)
Definition: PointIndexGrid.h:1504
static const Index NUM_VOXELS
Definition: LeafNode.h:78
const Vec3T & min() const
Return a const reference to the minimum point of the BBox.
Definition: BBox.h:81
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation. ...
Definition: NodeMasks.h:304
void modifyValue(const Coord &, const ModifyOp &)
Definition: PointIndexGrid.h:1524
PointIndexLeafNode< T, Log2Dim > LeafNodeType
Definition: PointIndexGrid.h:1350
void setValueOn(Index, const ValueType &)
Definition: PointIndexGrid.h:1513
Definition: PointIndexGrid.h:73
void setValueOff(Index, const ValueType &)
Definition: PointIndexGrid.h:1507
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54
Definition: Types.h:426
float Round(float x)
Return x rounded to the nearest integer.
Definition: Math.h:751
const Vec3T & max() const
Return a const reference to the maximum point of the BBox.
Definition: BBox.h:84
tree::LeafNode< T, Log2Dim > BaseLeaf
Definition: PointIndexGrid.h:1377
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Definition: RootNode.h:75
GridT::Ptr createPointIndexGrid(const PointArrayT &points, const math::Transform &xform)
Partition points into a point index grid to accelerate range and nearest-neighbor searches...
Definition: PointIndexGrid.h:1279
PointType::ValueType PointElementType
Definition: PointIndexGrid.h:594
PointIndexLeafNode()
Default constructor.
Definition: PointIndexGrid.h:1389
size_t size() const
Returns the number of buckets.
Definition: PointPartitioner.h:133
math::BBox< Vec3d > BBoxd
Definition: Types.h:87
ChildAllCIter beginChildAll() const
Definition: PointIndexGrid.h:1632
void fill(const ValueType &)
Definition: PointIndexGrid.h:1532
TreeType::LeafNodeType LeafNodeType
Definition: PointIndexGrid.h:146
ChildOnCIter endChildOn() const
Definition: PointIndexGrid.h:1636
BaseLeaf::template ValueIter< MaskOnIterator, const PointIndexLeafNode, const ValueType, ValueOn > ValueOnCIter
Definition: PointIndexGrid.h:1582
ValidPartitioningOp(tbb::atomic< bool > &hasChanged, const PointArrayT &points, const math::Transform &xform)
Definition: PointIndexGrid.h:357
BaseLeaf::template ChildIter< MaskOffIterator, const PointIndexLeafNode, ChildOff > ChildOffCIter
Definition: PointIndexGrid.h:1598
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
static const Index DIM
Definition: LeafNode.h:76
const PointIndexLeafNode * probeConstLeafAndCache(const Coord &, AccessorT &) const
Return a const pointer to this node.
Definition: PointIndexGrid.h:1463
void signedFloodFill(const ValueType &)
Definition: PointIndexGrid.h:1551
void filteredPointIndexSearchVoxels(RangeFilterType &filter, const LeafNodeType &leaf, const Coord &min, const Coord &max)
Definition: PointIndexGrid.h:773
void filteredPointIndexSearch(RangeFilterType &filter, ConstAccessor &acc, const CoordBBox &bbox)
Definition: PointIndexGrid.h:804
Base class for iterators over internal and leaf nodes.
Definition: Iterator.h:58
void setActiveState(const Coord &, bool)
Definition: PointIndexGrid.h:1497
ChildAllIter endChildAll()
Definition: PointIndexGrid.h:1643
LeafNodeT **const mLeafNodes
Definition: PointIndexGrid.h:491
void setValueOn(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1512
void setValueOffAndCache(const Coord &, const ValueType &, AccessorT &)
Definition: PointIndexGrid.h:1544
ChildOffCIter endChildOff() const
Definition: PointIndexGrid.h:1639
ChildOffIter beginChildOff()
Definition: PointIndexGrid.h:1630
Index64 memUsage() const
Definition: PointIndexGrid.h:1780
boost::int_t< 1+(3 *Log2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:101
void setValue(const Coord &, const ValueType &)
Definition: PointIndexGrid.h:1515