OpenVDB 10.0.1
Loading...
Searching...
No Matches
PointIndexGrid.h
Go to the documentation of this file.
1// Copyright Contributors to the OpenVDB Project
2// SPDX-License-Identifier: MPL-2.0
3
4/// @file PointIndexGrid.h
5///
6/// @brief Space-partitioning acceleration structure for points. Partitions
7/// the points into voxels to accelerate range and nearest neighbor
8/// searches.
9///
10/// @note Leaf nodes store a single point-index array and the voxels are only
11/// integer offsets into that array. The actual points are never stored
12/// in the acceleration structure, only offsets into an external array.
13///
14/// @author Mihai Alden
15
16#ifndef OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
17#define OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
18
19#include "PointPartitioner.h"
20
21#include <openvdb/thread/Threading.h>
22#include <openvdb/version.h>
23#include <openvdb/Exceptions.h>
24#include <openvdb/Grid.h>
25#include <openvdb/Types.h>
29#include <openvdb/tree/Tree.h>
30
31#include <tbb/blocked_range.h>
32#include <tbb/parallel_for.h>
33#include <atomic>
34#include <algorithm> // for std::min(), std::max()
35#include <cmath> // for std::sqrt()
36#include <deque>
37#include <iostream>
38#include <type_traits> // for std::is_same
39#include <utility> // for std::pair
40#include <vector>
41
42
43namespace openvdb {
45namespace OPENVDB_VERSION_NAME {
46
47namespace tree {
48template<Index, typename> struct SameLeafConfig; // forward declaration
49}
50
51namespace tools {
52
53template<typename T, Index Log2Dim> struct PointIndexLeafNode; // forward declaration
54
55/// Point index tree configured to match the default OpenVDB tree configuration
58
59/// Point index grid
61
62
63////////////////////////////////////////
64
65
66/// @interface PointArray
67/// Expected interface for the PointArray container:
68/// @code
69/// template<typename VectorType>
70/// struct PointArray
71/// {
72/// // The type used to represent world-space point positions
73/// using PosType = VectorType;
74///
75/// // Return the number of points in the array
76/// size_t size() const;
77///
78/// // Return the world-space position of the nth point in the array.
79/// void getPos(size_t n, PosType& xyz) const;
80/// };
81/// @endcode
82
83
84////////////////////////////////////////
85
86
87/// @brief Partition points into a point index grid to accelerate range and
88/// nearest-neighbor searches.
89///
90/// @param points world-space point array conforming to the PointArray interface
91/// @param voxelSize voxel size in world units
92template<typename GridT, typename PointArrayT>
93inline typename GridT::Ptr
94createPointIndexGrid(const PointArrayT& points, double voxelSize);
95
96
97/// @brief Partition points into a point index grid to accelerate range and
98/// nearest-neighbor searches.
99///
100/// @param points world-space point array conforming to the PointArray interface
101/// @param xform world-to-index-space transform
102template<typename GridT, typename PointArrayT>
103inline typename GridT::Ptr
104createPointIndexGrid(const PointArrayT& points, const math::Transform& xform);
105
106
107/// @brief Return @c true if the given point index grid represents a valid partitioning
108/// of the given point array.
109///
110/// @param points world-space point array conforming to the PointArray interface
111/// @param grid point index grid to validate
112template<typename PointArrayT, typename GridT>
113inline bool
114isValidPartition(const PointArrayT& points, const GridT& grid);
115
116
117/// Repartition the @a points if needed, otherwise return the input @a grid.
118template<typename GridT, typename PointArrayT>
119inline typename GridT::ConstPtr
120getValidPointIndexGrid(const PointArrayT& points, const typename GridT::ConstPtr& grid);
121
122/// Repartition the @a points if needed, otherwise return the input @a grid.
123template<typename GridT, typename PointArrayT>
124inline typename GridT::Ptr
125getValidPointIndexGrid(const PointArrayT& points, const typename GridT::Ptr& grid);
126
127
128////////////////////////////////////////
129
130
131/// Accelerated range and nearest-neighbor searches for point index grids
132template<typename TreeType = PointIndexTree>
134{
136 using LeafNodeType = typename TreeType::LeafNodeType;
137 using ValueType = typename TreeType::ValueType;
138
139
143
144
145 /// @brief Construct an iterator over the indices of the points contained in voxel (i, j, k).
146 /// @param ijk the voxel containing the points over which to iterate
147 /// @param acc an accessor for the grid or tree that holds the point indices
149
150
151 /// @brief Construct an iterator over the indices of the points contained in
152 /// the given bounding box.
153 /// @param bbox the bounding box of the voxels containing the points over which to iterate
154 /// @param acc an accessor for the grid or tree that holds the point indices
155 /// @note The range of the @a bbox is inclusive. Thus, a bounding box with
156 /// min = max is not empty but rather encloses a single voxel.
158
159
160 /// @brief Clear the iterator and update it with the result of the given voxel query.
161 /// @param ijk the voxel containing the points over which to iterate
162 /// @param acc an accessor for the grid or tree that holds the point indices
163 void searchAndUpdate(const Coord& ijk, ConstAccessor& acc);
164
165
166 /// @brief Clear the iterator and update it with the result of the given voxel region query.
167 /// @param bbox the bounding box of the voxels containing the points over which to iterate
168 /// @param acc an accessor for the grid or tree that holds the point indices
169 /// @note The range of the @a bbox is inclusive. Thus, a bounding box with
170 /// min = max is not empty but rather encloses a single voxel.
171 void searchAndUpdate(const CoordBBox& bbox, ConstAccessor& acc);
172
173
174 /// @brief Clear the iterator and update it with the result of the given
175 /// index-space bounding box query.
176 /// @param bbox index-space bounding box
177 /// @param acc an accessor for the grid or tree that holds the point indices
178 /// @param points world-space point array conforming to the PointArray interface
179 /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
180 template<typename PointArray>
181 void searchAndUpdate(const BBoxd& bbox, ConstAccessor& acc,
182 const PointArray& points, const math::Transform& xform);
183
184
185 /// @brief Clear the iterator and update it with the result of the given
186 /// index-space radial query.
187 /// @param center index-space center
188 /// @param radius index-space radius
189 /// @param acc an accessor for the grid or tree that holds the point indices
190 /// @param points world-space point array conforming to the PointArray interface
191 /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
192 /// @param subvoxelAccuracy if true, check individual points against the search region,
193 /// otherwise return all points that reside in voxels that are inside
194 /// or intersect the search region
195 template<typename PointArray>
196 void searchAndUpdate(const Vec3d& center, double radius, ConstAccessor& acc,
197 const PointArray& points, const math::Transform& xform, bool subvoxelAccuracy = true);
198
199
200 /// @brief Clear the iterator and update it with the result of the given
201 /// world-space bounding box query.
202 /// @param bbox world-space bounding box
203 /// @param acc an accessor for the grid or tree that holds the point indices
204 /// @param points world-space point array conforming to the PointArray interface
205 /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
206 template<typename PointArray>
208 const PointArray& points, const math::Transform& xform);
209
210
211 /// @brief Clear the iterator and update it with the result of the given
212 /// world-space radial query.
213 /// @param center world-space center
214 /// @param radius world-space radius
215 /// @param acc an accessor for the grid or tree that holds the point indices
216 /// @param points world-space point array conforming to the PointArray interface
217 /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
218 /// @param subvoxelAccuracy if true, check individual points against the search region,
219 /// otherwise return all points that reside in voxels that are inside
220 /// or intersect the search region
221 template<typename PointArray>
222 void worldSpaceSearchAndUpdate(const Vec3d& center, double radius, ConstAccessor& acc,
223 const PointArray& points, const math::Transform& xform, bool subvoxelAccuracy = true);
224
225
226 /// Reset the iterator to point to the first item.
227 void reset();
228
229 /// Return a const reference to the item to which this iterator is pointing.
230 const ValueType& operator*() const { return *mRange.first; }
231
232 /// @{
233 /// @brief Return @c true if this iterator is not yet exhausted.
234 bool test() const { return mRange.first < mRange.second || mIter != mRangeList.end(); }
235 operator bool() const { return this->test(); }
236 /// @}
237
238 /// Advance iterator to next item.
239 void increment();
240
241 /// Advance iterator to next item.
242 void operator++() { this->increment(); }
243
244
245 /// @brief Advance iterator to next item.
246 /// @return @c true if this iterator is not yet exhausted.
247 bool next();
248
249 /// Return the number of point indices in the iterator range.
250 size_t size() const;
251
252 /// Return @c true if both iterators point to the same element.
253 bool operator==(const PointIndexIterator& p) const { return mRange.first == p.mRange.first; }
254 bool operator!=(const PointIndexIterator& p) const { return !this->operator==(p); }
255
256
257private:
258 using Range = std::pair<const ValueType*, const ValueType*>;
259 using RangeDeque = std::deque<Range>;
260 using RangeDequeCIter = typename RangeDeque::const_iterator;
261 using IndexArray = std::unique_ptr<ValueType[]>;
262
263 void clear();
264
265 // Primary index collection
266 Range mRange;
267 RangeDeque mRangeList;
268 RangeDequeCIter mIter;
269 // Secondary index collection
270 IndexArray mIndexArray;
271 size_t mIndexArraySize;
272}; // struct PointIndexIterator
273
274
275/// @brief Selectively extract and filter point data using a custom filter operator.
276///
277/// @par FilterType example:
278/// @interface FilterType
279/// @code
280/// template<typename T>
281/// struct WeightedAverageAccumulator {
282/// using ValueType = T;
283///
284/// WeightedAverageAccumulator(T const * const array, const T radius)
285/// : mValues(array), mInvRadius(1.0/radius), mWeightSum(0.0), mValueSum(0.0) {}
286///
287/// void reset() { mWeightSum = mValueSum = T(0.0); }
288///
289/// // the following method is invoked by the PointIndexFilter
290/// void operator()(const T distSqr, const size_t pointIndex) {
291/// const T weight = T(1.0) - openvdb::math::Sqrt(distSqr) * mInvRadius;
292/// mWeightSum += weight;
293/// mValueSum += weight * mValues[pointIndex];
294/// }
295///
296/// T result() const { return mWeightSum > T(0.0) ? mValueSum / mWeightSum : T(0.0); }
297///
298/// private:
299/// T const * const mValues;
300/// const T mInvRadius;
301/// T mWeightSum, mValueSum;
302/// }; // struct WeightedAverageAccumulator
303/// @endcode
304template<typename PointArray, typename TreeType = PointIndexTree>
306{
307 using PosType = typename PointArray::PosType;
308 using ScalarType = typename PosType::value_type;
310
311 /// @brief Constructor
312 /// @param points world-space point array conforming to the PointArray interface
313 /// @param tree a point index tree
314 /// @param xform linear, uniform-scale transform (i.e., cubical voxels)
315 PointIndexFilter(const PointArray& points, const TreeType& tree, const math::Transform& xform);
316
317 /// Thread safe copy constructor
319
320 /// @brief Perform a radial search query and apply the given filter
321 /// operator to the selected points.
322 /// @param center world-space center
323 /// @param radius world-space radius
324 /// @param op custom filter operator (see the FilterType example for interface details)
325 template<typename FilterType>
326 void searchAndApply(const PosType& center, ScalarType radius, FilterType& op);
327
328private:
329 PointArray const * const mPoints;
330 ConstAccessor mAcc;
331 const math::Transform mXform;
332 const ScalarType mInvVoxelSize;
334}; // struct PointIndexFilter
335
336
337////////////////////////////////////////
338
339// Internal operators and implementation details
340
341/// @cond OPENVDB_DOCS_INTERNAL
342
343namespace point_index_grid_internal {
344
345template<typename PointArrayT>
346struct ValidPartitioningOp
347{
348 ValidPartitioningOp(std::atomic<bool>& hasChanged,
349 const PointArrayT& points, const math::Transform& xform)
350 : mPoints(&points)
351 , mTransform(&xform)
352 , mHasChanged(&hasChanged)
353 {
354 }
355
356 template <typename LeafT>
357 void operator()(LeafT &leaf, size_t /*leafIndex*/) const
358 {
359 if ((*mHasChanged)) {
360 thread::cancelGroupExecution();
361 return;
362 }
363
364 using IndexArrayT = typename LeafT::IndexArray;
365 using IndexT = typename IndexArrayT::value_type;
366 using PosType = typename PointArrayT::PosType;
367
368 typename LeafT::ValueOnCIter iter;
369 Coord voxelCoord;
370 PosType point;
371
372 const IndexT
373 *begin = static_cast<IndexT*>(nullptr),
374 *end = static_cast<IndexT*>(nullptr);
375
376 for (iter = leaf.cbeginValueOn(); iter; ++iter) {
377
378 if ((*mHasChanged)) break;
379
380 voxelCoord = iter.getCoord();
381 leaf.getIndices(iter.pos(), begin, end);
382
383 while (begin < end) {
384
385 mPoints->getPos(*begin, point);
386 if (voxelCoord != mTransform->worldToIndexCellCentered(point)) {
387 mHasChanged->store(true);
388 break;
389 }
390
391 ++begin;
392 }
393 }
394 }
395
396private:
397 PointArrayT const * const mPoints;
398 math::Transform const * const mTransform;
399 std::atomic<bool> * const mHasChanged;
400};
401
402
403template<typename LeafNodeT>
404struct PopulateLeafNodesOp
405{
406 using IndexT = uint32_t;
407 using Partitioner = PointPartitioner<IndexT, LeafNodeT::LOG2DIM>;
408
409 PopulateLeafNodesOp(std::unique_ptr<LeafNodeT*[]>& leafNodes,
410 const Partitioner& partitioner)
411 : mLeafNodes(leafNodes.get())
412 , mPartitioner(&partitioner)
413 {
414 }
415
416 void operator()(const tbb::blocked_range<size_t>& range) const {
417
418 using VoxelOffsetT = typename Partitioner::VoxelOffsetType;
419
420 size_t maxPointCount = 0;
421 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
422 maxPointCount = std::max(maxPointCount, mPartitioner->indices(n).size());
423 }
424
425 const IndexT voxelCount = LeafNodeT::SIZE;
426
427 // allocate histogram buffers
428 std::unique_ptr<VoxelOffsetT[]> offsets{new VoxelOffsetT[maxPointCount]};
429 std::unique_ptr<IndexT[]> histogram{new IndexT[voxelCount]};
430
431 VoxelOffsetT const * const voxelOffsets = mPartitioner->voxelOffsets().get();
432
433 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
434
435 LeafNodeT* node = new LeafNodeT();
436 node->setOrigin(mPartitioner->origin(n));
437
438 typename Partitioner::IndexIterator it = mPartitioner->indices(n);
439
440 const size_t pointCount = it.size();
441 IndexT const * const indices = &*it;
442
443 // local copy of voxel offsets.
444 for (IndexT i = 0; i < pointCount; ++i) {
445 offsets[i] = voxelOffsets[ indices[i] ];
446 }
447
448 // compute voxel-offset histogram
449 memset(&histogram[0], 0, voxelCount * sizeof(IndexT));
450 for (IndexT i = 0; i < pointCount; ++i) {
451 ++histogram[ offsets[i] ];
452 }
453
454 typename LeafNodeT::NodeMaskType& mask = node->getValueMask();
455 typename LeafNodeT::Buffer& buffer = node->buffer();
456
457 // scan histogram (all-prefix-sums)
458 IndexT count = 0, startOffset;
459 for (int i = 0; i < int(voxelCount); ++i) {
460 if (histogram[i] > 0) {
461 startOffset = count;
462 count += histogram[i];
463 histogram[i] = startOffset;
464 mask.setOn(i);
465 }
466 buffer.setValue(i, count);
467 }
468
469 // allocate point-index array
470 node->indices().resize(pointCount);
471 typename LeafNodeT::ValueType * const orderedIndices = node->indices().data();
472
473 // rank and permute
474 for (IndexT i = 0; i < pointCount; ++i) {
475 orderedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
476 }
477
478 mLeafNodes[n] = node;
479 }
480 }
481
482 //////////
483
484 LeafNodeT* * const mLeafNodes;
485 Partitioner const * const mPartitioner;
486};
487
488
489/// Construct a @c PointIndexTree
490template<typename TreeType, typename PointArray>
491inline void
492constructPointTree(TreeType& tree, const math::Transform& xform, const PointArray& points)
493{
494 using LeafType = typename TreeType::LeafNodeType;
495
496 std::unique_ptr<LeafType*[]> leafNodes;
497 size_t leafNodeCount = 0;
498
499 {
500 // Important: Do not disable the cell-centered transform in the PointPartitioner.
501 // This interpretation is assumed in the PointIndexGrid and all related
502 // search algorithms.
503 PointPartitioner<uint32_t, LeafType::LOG2DIM> partitioner;
504 partitioner.construct(points, xform, /*voxelOrder=*/false, /*recordVoxelOffsets=*/true);
505
506 if (!partitioner.usingCellCenteredTransform()) {
507 OPENVDB_THROW(LookupError, "The PointIndexGrid requires a "
508 "cell-centered transform.");
509 }
510
511 leafNodeCount = partitioner.size();
512 leafNodes.reset(new LeafType*[leafNodeCount]);
513
514 const tbb::blocked_range<size_t> range(0, leafNodeCount);
515 tbb::parallel_for(range, PopulateLeafNodesOp<LeafType>(leafNodes, partitioner));
516 }
517
518 tree::ValueAccessor<TreeType> acc(tree);
519 for (size_t n = 0; n < leafNodeCount; ++n) {
520 acc.addLeaf(leafNodes[n]);
521 }
522}
523
524
525////////////////////////////////////////
526
527
528template<typename T>
529inline void
530dequeToArray(const std::deque<T>& d, std::unique_ptr<T[]>& a, size_t& size)
531{
532 size = d.size();
533 a.reset(new T[size]);
534 typename std::deque<T>::const_iterator it = d.begin(), itEnd = d.end();
535 T* item = a.get();
536 for ( ; it != itEnd; ++it, ++item) *item = *it;
537}
538
539
540inline void
541constructExclusiveRegions(std::vector<CoordBBox>& regions,
542 const CoordBBox& bbox, const CoordBBox& ibox)
543{
544 regions.clear();
545 regions.reserve(6);
546 Coord cmin = ibox.min();
547 Coord cmax = ibox.max();
548
549 // left-face bbox
550 regions.push_back(bbox);
551 regions.back().max().z() = cmin.z();
552
553 // right-face bbox
554 regions.push_back(bbox);
555 regions.back().min().z() = cmax.z();
556
557 --cmax.z(); // accounting for cell centered bucketing.
558 ++cmin.z();
559
560 // front-face bbox
561 regions.push_back(bbox);
562 CoordBBox* lastRegion = &regions.back();
563 lastRegion->min().z() = cmin.z();
564 lastRegion->max().z() = cmax.z();
565 lastRegion->max().x() = cmin.x();
566
567 // back-face bbox
568 regions.push_back(*lastRegion);
569 lastRegion = &regions.back();
570 lastRegion->min().x() = cmax.x();
571 lastRegion->max().x() = bbox.max().x();
572
573 --cmax.x();
574 ++cmin.x();
575
576 // bottom-face bbox
577 regions.push_back(*lastRegion);
578 lastRegion = &regions.back();
579 lastRegion->min().x() = cmin.x();
580 lastRegion->max().x() = cmax.x();
581 lastRegion->max().y() = cmin.y();
582
583 // top-face bbox
584 regions.push_back(*lastRegion);
585 lastRegion = &regions.back();
586 lastRegion->min().y() = cmax.y();
587 lastRegion->max().y() = bbox.max().y();
588}
589
590
591template<typename PointArray, typename IndexT>
592struct BBoxFilter
593{
594 using PosType = typename PointArray::PosType;
595 using ScalarType = typename PosType::value_type;
596 using Range = std::pair<const IndexT*, const IndexT*>;
597 using RangeDeque = std::deque<Range>;
598 using IndexDeque = std::deque<IndexT>;
599
600 BBoxFilter(RangeDeque& ranges, IndexDeque& indices, const BBoxd& bbox,
601 const PointArray& points, const math::Transform& xform)
602 : mRanges(ranges)
603 , mIndices(indices)
604 , mRegion(bbox)
605 , mPoints(points)
606 , mMap(*xform.baseMap())
607 {
608 }
609
610 template <typename LeafNodeType>
611 void filterLeafNode(const LeafNodeType& leaf)
612 {
613 typename LeafNodeType::ValueOnCIter iter;
614 const IndexT
615 *begin = static_cast<IndexT*>(nullptr),
616 *end = static_cast<IndexT*>(nullptr);
617 for (iter = leaf.cbeginValueOn(); iter; ++iter) {
618 leaf.getIndices(iter.pos(), begin, end);
619 filterVoxel(iter.getCoord(), begin, end);
620 }
621 }
622
623 void filterVoxel(const Coord&, const IndexT* begin, const IndexT* end)
624 {
625 PosType vec;
626
627 for (; begin < end; ++begin) {
628 mPoints.getPos(*begin, vec);
629
630 if (mRegion.isInside(mMap.applyInverseMap(vec))) {
631 mIndices.push_back(*begin);
632 }
633 }
634 }
635
636private:
637 RangeDeque& mRanges;
638 IndexDeque& mIndices;
639 const BBoxd mRegion;
640 const PointArray& mPoints;
641 const math::MapBase& mMap;
642};
643
644
645template<typename PointArray, typename IndexT>
646struct RadialRangeFilter
647{
648 using PosType = typename PointArray::PosType;
649 using ScalarType = typename PosType::value_type;
650 using Range = std::pair<const IndexT*, const IndexT*>;
651 using RangeDeque = std::deque<Range>;
652 using IndexDeque = std::deque<IndexT>;
653
654 RadialRangeFilter(RangeDeque& ranges, IndexDeque& indices, const Vec3d& xyz, double radius,
655 const PointArray& points, const math::Transform& xform,
656 const double leafNodeDim, const bool subvoxelAccuracy)
657 : mRanges(ranges)
658 , mIndices(indices)
659 , mCenter(xyz)
660 , mWSCenter(xform.indexToWorld(xyz))
661 , mVoxelDist1(ScalarType(0.0))
662 , mVoxelDist2(ScalarType(0.0))
663 , mLeafNodeDist1(ScalarType(0.0))
664 , mLeafNodeDist2(ScalarType(0.0))
665 , mWSRadiusSqr(ScalarType(radius * xform.voxelSize()[0]))
666 , mPoints(points)
667 , mSubvoxelAccuracy(subvoxelAccuracy)
668 {
669 const ScalarType voxelRadius = ScalarType(std::sqrt(3.0) * 0.5);
670 mVoxelDist1 = voxelRadius + ScalarType(radius);
671 mVoxelDist1 *= mVoxelDist1;
672
673 if (radius > voxelRadius) {
674 mVoxelDist2 = ScalarType(radius) - voxelRadius;
675 mVoxelDist2 *= mVoxelDist2;
676 }
677
678 const ScalarType leafNodeRadius = ScalarType(leafNodeDim * std::sqrt(3.0) * 0.5);
679 mLeafNodeDist1 = leafNodeRadius + ScalarType(radius);
680 mLeafNodeDist1 *= mLeafNodeDist1;
681
682 if (radius > leafNodeRadius) {
683 mLeafNodeDist2 = ScalarType(radius) - leafNodeRadius;
684 mLeafNodeDist2 *= mLeafNodeDist2;
685 }
686
687 mWSRadiusSqr *= mWSRadiusSqr;
688 }
689
690 template <typename LeafNodeType>
691 void filterLeafNode(const LeafNodeType& leaf)
692 {
693 {
694 const Coord& ijk = leaf.origin();
695 PosType vec;
696 vec[0] = ScalarType(ijk[0]);
697 vec[1] = ScalarType(ijk[1]);
698 vec[2] = ScalarType(ijk[2]);
699 vec += ScalarType(LeafNodeType::DIM - 1) * 0.5;
700 vec -= mCenter;
701
702 const ScalarType dist = vec.lengthSqr();
703 if (dist > mLeafNodeDist1) return;
704
705 if (mLeafNodeDist2 > 0.0 && dist < mLeafNodeDist2) {
706 const IndexT* begin = &leaf.indices().front();
707 mRanges.push_back(Range(begin, begin + leaf.indices().size()));
708 return;
709 }
710 }
711
712 typename LeafNodeType::ValueOnCIter iter;
713 const IndexT
714 *begin = static_cast<IndexT*>(nullptr),
715 *end = static_cast<IndexT*>(nullptr);
716 for (iter = leaf.cbeginValueOn(); iter; ++iter) {
717 leaf.getIndices(iter.pos(), begin, end);
718 filterVoxel(iter.getCoord(), begin, end);
719 }
720 }
721
722 void filterVoxel(const Coord& ijk, const IndexT* begin, const IndexT* end)
723 {
724 PosType vec;
725
726 {
727 vec[0] = mCenter[0] - ScalarType(ijk[0]);
728 vec[1] = mCenter[1] - ScalarType(ijk[1]);
729 vec[2] = mCenter[2] - ScalarType(ijk[2]);
730
731 const ScalarType dist = vec.lengthSqr();
732 if (dist > mVoxelDist1) return;
733
734 if (!mSubvoxelAccuracy || (mVoxelDist2 > 0.0 && dist < mVoxelDist2)) {
735 if (!mRanges.empty() && mRanges.back().second == begin) {
736 mRanges.back().second = end;
737 } else {
738 mRanges.push_back(Range(begin, end));
739 }
740 return;
741 }
742 }
743
744
745 while (begin < end) {
746 mPoints.getPos(*begin, vec);
747 vec = mWSCenter - vec;
748
749 if (vec.lengthSqr() < mWSRadiusSqr) {
750 mIndices.push_back(*begin);
751 }
752 ++begin;
753 }
754 }
755
756private:
757 RangeDeque& mRanges;
758 IndexDeque& mIndices;
759 const PosType mCenter, mWSCenter;
760 ScalarType mVoxelDist1, mVoxelDist2, mLeafNodeDist1, mLeafNodeDist2, mWSRadiusSqr;
761 const PointArray& mPoints;
762 const bool mSubvoxelAccuracy;
763}; // struct RadialRangeFilter
764
765
766////////////////////////////////////////
767
768
769template<typename RangeFilterType, typename LeafNodeType>
770inline void
771filteredPointIndexSearchVoxels(RangeFilterType& filter,
772 const LeafNodeType& leaf, const Coord& min, const Coord& max)
773{
774 using PointIndexT = typename LeafNodeType::ValueType;
775 Index xPos(0), yPos(0), pos(0);
776 Coord ijk(0);
777
778 const PointIndexT* dataPtr = &leaf.indices().front();
779 PointIndexT beginOffset, endOffset;
780
781 for (ijk[0] = min[0]; ijk[0] <= max[0]; ++ijk[0]) {
782 xPos = (ijk[0] & (LeafNodeType::DIM - 1u)) << (2 * LeafNodeType::LOG2DIM);
783 for (ijk[1] = min[1]; ijk[1] <= max[1]; ++ijk[1]) {
784 yPos = xPos + ((ijk[1] & (LeafNodeType::DIM - 1u)) << LeafNodeType::LOG2DIM);
785 for (ijk[2] = min[2]; ijk[2] <= max[2]; ++ijk[2]) {
786 pos = yPos + (ijk[2] & (LeafNodeType::DIM - 1u));
787
788 beginOffset = (pos == 0 ? PointIndexT(0) : leaf.getValue(pos - 1));
789 endOffset = leaf.getValue(pos);
790
791 if (endOffset > beginOffset) {
792 filter.filterVoxel(ijk, dataPtr + beginOffset, dataPtr + endOffset);
793 }
794 }
795 }
796 }
797}
798
799
800template<typename RangeFilterType, typename ConstAccessor>
801inline void
802filteredPointIndexSearch(RangeFilterType& filter, ConstAccessor& acc, const CoordBBox& bbox)
803{
804 using LeafNodeType = typename ConstAccessor::TreeType::LeafNodeType;
805 Coord ijk(0), ijkMax(0), ijkA(0), ijkB(0);
806 const Coord leafMin = bbox.min() & ~(LeafNodeType::DIM - 1);
807 const Coord leafMax = bbox.max() & ~(LeafNodeType::DIM - 1);
808
809 for (ijk[0] = leafMin[0]; ijk[0] <= leafMax[0]; ijk[0] += LeafNodeType::DIM) {
810 for (ijk[1] = leafMin[1]; ijk[1] <= leafMax[1]; ijk[1] += LeafNodeType::DIM) {
811 for (ijk[2] = leafMin[2]; ijk[2] <= leafMax[2]; ijk[2] += LeafNodeType::DIM) {
812
813 if (const LeafNodeType* leaf = acc.probeConstLeaf(ijk)) {
814 ijkMax = ijk;
815 ijkMax.offset(LeafNodeType::DIM - 1);
816
817 // intersect leaf bbox with search region.
818 ijkA = Coord::maxComponent(bbox.min(), ijk);
819 ijkB = Coord::minComponent(bbox.max(), ijkMax);
820
821 if (ijkA != ijk || ijkB != ijkMax) {
822 filteredPointIndexSearchVoxels(filter, *leaf, ijkA, ijkB);
823 } else { // leaf bbox is inside the search region
824 filter.filterLeafNode(*leaf);
825 }
826 }
827 }
828 }
829 }
830}
831
832
833////////////////////////////////////////
834
835
836template<typename RangeDeque, typename LeafNodeType>
837inline void
838pointIndexSearchVoxels(RangeDeque& rangeList,
839 const LeafNodeType& leaf, const Coord& min, const Coord& max)
840{
841 using PointIndexT = typename LeafNodeType::ValueType;
842 using IntT = typename PointIndexT::IntType;
843 using Range = typename RangeDeque::value_type;
844
845 Index xPos(0), pos(0), zStride = Index(max[2] - min[2]);
846 const PointIndexT* dataPtr = &leaf.indices().front();
847 PointIndexT beginOffset(0), endOffset(0),
848 previousOffset(static_cast<IntT>(leaf.indices().size() + 1u));
849 Coord ijk(0);
850
851 for (ijk[0] = min[0]; ijk[0] <= max[0]; ++ijk[0]) {
852 xPos = (ijk[0] & (LeafNodeType::DIM - 1u)) << (2 * LeafNodeType::LOG2DIM);
853
854 for (ijk[1] = min[1]; ijk[1] <= max[1]; ++ijk[1]) {
855 pos = xPos + ((ijk[1] & (LeafNodeType::DIM - 1u)) << LeafNodeType::LOG2DIM);
856 pos += (min[2] & (LeafNodeType::DIM - 1u));
857
858 beginOffset = (pos == 0 ? PointIndexT(0) : leaf.getValue(pos - 1));
859 endOffset = leaf.getValue(pos+zStride);
860
861 if (endOffset > beginOffset) {
862
863 if (beginOffset == previousOffset) {
864 rangeList.back().second = dataPtr + endOffset;
865 } else {
866 rangeList.push_back(Range(dataPtr + beginOffset, dataPtr + endOffset));
867 }
868
869 previousOffset = endOffset;
870 }
871 }
872 }
873}
874
875
876template<typename RangeDeque, typename ConstAccessor>
877inline void
878pointIndexSearch(RangeDeque& rangeList, ConstAccessor& acc, const CoordBBox& bbox)
879{
880 using LeafNodeType = typename ConstAccessor::TreeType::LeafNodeType;
881 using PointIndexT = typename LeafNodeType::ValueType;
882 using Range = typename RangeDeque::value_type;
883
884 Coord ijk(0), ijkMax(0), ijkA(0), ijkB(0);
885 const Coord leafMin = bbox.min() & ~(LeafNodeType::DIM - 1);
886 const Coord leafMax = bbox.max() & ~(LeafNodeType::DIM - 1);
887
888 for (ijk[0] = leafMin[0]; ijk[0] <= leafMax[0]; ijk[0] += LeafNodeType::DIM) {
889 for (ijk[1] = leafMin[1]; ijk[1] <= leafMax[1]; ijk[1] += LeafNodeType::DIM) {
890 for (ijk[2] = leafMin[2]; ijk[2] <= leafMax[2]; ijk[2] += LeafNodeType::DIM) {
891
892 if (const LeafNodeType* leaf = acc.probeConstLeaf(ijk)) {
893 ijkMax = ijk;
894 ijkMax.offset(LeafNodeType::DIM - 1);
895
896 // intersect leaf bbox with search region.
897 ijkA = Coord::maxComponent(bbox.min(), ijk);
898 ijkB = Coord::minComponent(bbox.max(), ijkMax);
899
900 if (ijkA != ijk || ijkB != ijkMax) {
901 pointIndexSearchVoxels(rangeList, *leaf, ijkA, ijkB);
902 } else {
903 // leaf bbox is inside the search region, add all indices.
904 const PointIndexT* begin = &leaf->indices().front();
905 rangeList.push_back(Range(begin, (begin + leaf->indices().size())));
906 }
907 }
908 }
909 }
910 }
911}
912
913
914} // namespace point_index_grid_internal
915
916/// @endcond
917
918// PointIndexIterator implementation
919
920template<typename TreeType>
921inline
923 : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
924 , mRangeList()
925 , mIter(mRangeList.begin())
926 , mIndexArray()
927 , mIndexArraySize(0)
928{
929}
930
931
932template<typename TreeType>
933inline
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
948template<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
968template<typename TreeType>
969inline
971 : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
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
985template<typename TreeType>
986inline
988 : mRange(static_cast<ValueType*>(nullptr), static_cast<ValueType*>(nullptr))
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
1003template<typename TreeType>
1004inline 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*>(nullptr);
1015 mRange.second = static_cast<ValueType*>(nullptr);
1016 }
1017}
1018
1019
1020template<typename TreeType>
1021inline 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
1037template<typename TreeType>
1038inline bool
1040{
1041 if (!this->test()) return false;
1042 this->increment();
1043 return this->test();
1044}
1045
1046
1047template<typename TreeType>
1048inline 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
1062template<typename TreeType>
1063inline void
1065{
1066 mRange.first = static_cast<ValueType*>(nullptr);
1067 mRange.second = static_cast<ValueType*>(nullptr);
1068 mRangeList.clear();
1069 mIter = mRangeList.end();
1070 mIndexArray.reset();
1071 mIndexArraySize = 0;
1072}
1073
1074
1075template<typename TreeType>
1076inline 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
1088template<typename TreeType>
1089inline 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
1102template<typename TreeType>
1103template<typename PointArray>
1104inline 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;
1132 point_index_grid_internal::BBoxFilter<PointArray, ValueType>
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
1145template<typename TreeType>
1146template<typename PointArray>
1147inline void
1148PointIndexIterator<TreeType>::searchAndUpdate(const Vec3d& center, double radius,
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
1182 using FilterT = point_index_grid_internal::RadialRangeFilter<PointArray, ValueType>;
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
1197template<typename TreeType>
1198template<typename PointArray>
1199inline 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
1208template<typename TreeType>
1209template<typename PointArray>
1210inline 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
1220////////////////////////////////////////
1221
1222// PointIndexFilter implementation
1223
1224template<typename PointArray, typename TreeType>
1225inline
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
1233template<typename PointArray, typename TreeType>
1234inline
1236 : mPoints(rhs.mPoints)
1237 , mAcc(rhs.mAcc.tree())
1238 , mXform(rhs.mXform)
1239 , mInvVoxelSize(rhs.mInvVoxelSize)
1240{
1241}
1242
1243
1244template<typename PointArray, typename TreeType>
1245template<typename FilterType>
1246inline void
1248 const PosType& center, ScalarType radius, FilterType& op)
1249{
1250 if (radius * mInvVoxelSize < ScalarType(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 ScalarType radiusSqr = radius * radius;
1260 ScalarType distSqr = 0.0;
1261 PosType 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
1274////////////////////////////////////////
1275
1276
1277template<typename GridT, typename PointArrayT>
1278inline typename GridT::Ptr
1279createPointIndexGrid(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) {
1285 point_index_grid_internal::constructPointTree(
1286 grid->tree(), grid->transform(), points);
1287 }
1288
1289 return grid;
1290}
1291
1292
1293template<typename GridT, typename PointArrayT>
1294inline typename GridT::Ptr
1295createPointIndexGrid(const PointArrayT& points, double voxelSize)
1296{
1298 return createPointIndexGrid<GridT>(points, *xform);
1299}
1300
1301
1302template<typename PointArrayT, typename GridT>
1303inline bool
1304isValidPartition(const PointArrayT& points, const GridT& grid)
1305{
1307
1308 size_t pointCount = 0;
1309 for (size_t n = 0, N = leafs.leafCount(); n < N; ++n) {
1310 pointCount += leafs.leaf(n).indices().size();
1311 }
1312
1313 if (points.size() != pointCount) {
1314 return false;
1315 }
1316
1317 std::atomic<bool> changed;
1318 changed = false;
1319
1320 point_index_grid_internal::ValidPartitioningOp<PointArrayT>
1321 op(changed, points, grid.transform());
1322
1323 leafs.foreach(op);
1324
1325 return !bool(changed);
1326}
1327
1328
1329template<typename GridT, typename PointArrayT>
1330inline typename GridT::ConstPtr
1331getValidPointIndexGrid(const PointArrayT& points, const typename GridT::ConstPtr& grid)
1332{
1333 if (isValidPartition(points, *grid)) {
1334 return grid;
1335 }
1336
1337 return createPointIndexGrid<GridT>(points, grid->transform());
1338}
1339
1340
1341template<typename GridT, typename PointArrayT>
1342inline typename GridT::Ptr
1343getValidPointIndexGrid(const PointArrayT& points, const typename GridT::Ptr& grid)
1344{
1345 if (isValidPartition(points, *grid)) {
1346 return grid;
1347 }
1348
1349 return createPointIndexGrid<GridT>(points, grid->transform());
1350}
1351
1352
1353////////////////////////////////////////
1354
1355
1356template<typename T, Index Log2Dim>
1357struct PointIndexLeafNode : public tree::LeafNode<T, Log2Dim>
1358{
1361
1362 using ValueType = T;
1363 using IndexArray = std::vector<ValueType>;
1364
1365
1366 IndexArray& indices() { return mIndices; }
1367 const IndexArray& indices() const { return mIndices; }
1368
1369 bool getIndices(const Coord& ijk, const ValueType*& begin, const ValueType*& end) const;
1370 bool getIndices(Index offset, const ValueType*& begin, const ValueType*& end) const;
1371
1372 void setOffsetOn(Index offset, const ValueType& val);
1373 void setOffsetOnly(Index offset, const ValueType& val);
1374
1375 bool isEmpty(const CoordBBox& bbox) const;
1376
1377private:
1378 IndexArray mIndices;
1379
1380 ////////////////////////////////////////
1381
1382 // The following methods had to be copied from the LeafNode class
1383 // to make the derived PointIndexLeafNode class compatible with the tree structure.
1384
1385public:
1388
1389 using BaseLeaf::LOG2DIM;
1390 using BaseLeaf::TOTAL;
1391 using BaseLeaf::DIM;
1394 using BaseLeaf::SIZE;
1395 using BaseLeaf::LEVEL;
1396
1397 /// Default constructor
1398 PointIndexLeafNode() : BaseLeaf(), mIndices() {}
1399
1400 explicit
1401 PointIndexLeafNode(const Coord& coords, const T& value = zeroVal<T>(), bool active = false)
1402 : BaseLeaf(coords, value, active)
1403 , mIndices()
1404 {
1405 }
1406
1408 const T& value = zeroVal<T>(), bool active = false)
1409 : BaseLeaf(PartialCreate(), coords, value, active)
1410 , mIndices()
1411 {
1412 }
1413
1414 /// Deep copy constructor
1415 PointIndexLeafNode(const PointIndexLeafNode& rhs) : BaseLeaf(rhs), mIndices(rhs.mIndices) {}
1416
1417 /// @brief Return @c true if the given node (which may have a different @c ValueType
1418 /// than this node) has the same active value topology as this node.
1419 template<typename OtherType, Index OtherLog2Dim>
1423
1424 /// Check for buffer, state and origin equivalence.
1425 bool operator==(const PointIndexLeafNode& other) const { return BaseLeaf::operator==(other); }
1426
1427 bool operator!=(const PointIndexLeafNode& other) const { return !(other == *this); }
1428
1429 template<MergePolicy Policy> void merge(const PointIndexLeafNode& rhs) {
1430 BaseLeaf::template merge<Policy>(rhs);
1431 }
1432 template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive) {
1433 BaseLeaf::template merge<Policy>(tileValue, tileActive);
1434 }
1435
1436 template<MergePolicy Policy>
1437 void merge(const PointIndexLeafNode& other,
1438 const ValueType& /*bg*/, const ValueType& /*otherBG*/)
1439 {
1440 BaseLeaf::template merge<Policy>(other);
1441 }
1442
1444 template<typename AccessorT>
1446
1447 //@{
1448 /// @brief Return a pointer to this node.
1449 PointIndexLeafNode* touchLeaf(const Coord&) { return this; }
1450 template<typename AccessorT>
1451 PointIndexLeafNode* touchLeafAndCache(const Coord&, AccessorT&) { return this; }
1452
1453 template<typename NodeT, typename AccessorT>
1454 NodeT* probeNodeAndCache(const Coord&, AccessorT&)
1455 {
1457 if (!(std::is_same<NodeT, PointIndexLeafNode>::value)) return nullptr;
1458 return reinterpret_cast<NodeT*>(this);
1460 }
1461 PointIndexLeafNode* probeLeaf(const Coord&) { return this; }
1462 template<typename AccessorT>
1463 PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) { return this; }
1464 //@}
1465
1466 //@{
1467 /// @brief Return a @const pointer to this node.
1468 const PointIndexLeafNode* probeConstLeaf(const Coord&) const { return this; }
1469 template<typename AccessorT>
1470 const PointIndexLeafNode* probeConstLeafAndCache(const Coord&, AccessorT&) const {return this;}
1471 template<typename AccessorT>
1472 const PointIndexLeafNode* probeLeafAndCache(const Coord&, AccessorT&) const { return this; }
1473 const PointIndexLeafNode* probeLeaf(const Coord&) const { return this; }
1474 template<typename NodeT, typename AccessorT>
1475 const NodeT* probeConstNodeAndCache(const Coord&, AccessorT&) const
1476 {
1478 if (!(std::is_same<NodeT, PointIndexLeafNode>::value)) return nullptr;
1479 return reinterpret_cast<const NodeT*>(this);
1481 }
1482 //@}
1483
1484
1485 // I/O methods
1486
1487 void readBuffers(std::istream& is, bool fromHalf = false);
1488 void readBuffers(std::istream& is, const CoordBBox&, bool fromHalf = false);
1489 void writeBuffers(std::ostream& os, bool toHalf = false) const;
1490
1491
1492 Index64 memUsage() const;
1493 Index64 memUsageIfLoaded() const;
1494
1495
1496 ////////////////////////////////////////
1497
1498 // Disable all write methods to avoid unintentional changes
1499 // to the point-array offsets.
1500
1502 assert(false && "Cannot modify voxel values in a PointIndexTree.");
1503 }
1504
1505 void setActiveState(const Coord&, bool) { assertNonmodifiable(); }
1507
1510
1513
1516
1519
1520 void setValueOn(const Coord&, const ValueType&) { assertNonmodifiable(); }
1522
1523 void setValue(const Coord&, const ValueType&) { assertNonmodifiable(); }
1524
1527
1528 template<typename ModifyOp>
1529 void modifyValue(Index, const ModifyOp&) { assertNonmodifiable(); }
1530
1531 template<typename ModifyOp>
1532 void modifyValue(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1533
1534 template<typename ModifyOp>
1535 void modifyValueAndActiveState(const Coord&, const ModifyOp&) { assertNonmodifiable(); }
1536
1537 void clip(const CoordBBox&, const ValueType&) { assertNonmodifiable(); }
1538
1539 void fill(const CoordBBox&, const ValueType&, bool) { assertNonmodifiable(); }
1540 void fill(const ValueType&) {}
1541 void fill(const ValueType&, bool) { assertNonmodifiable(); }
1542
1543 template<typename AccessorT>
1544 void setValueOnlyAndCache(const Coord&, const ValueType&, AccessorT&) {assertNonmodifiable();}
1545
1546 template<typename ModifyOp, typename AccessorT>
1547 void modifyValueAndActiveStateAndCache(const Coord&, const ModifyOp&, AccessorT&) {
1549 }
1550
1551 template<typename AccessorT>
1552 void setValueOffAndCache(const Coord&, const ValueType&, AccessorT&) { assertNonmodifiable(); }
1553
1554 template<typename AccessorT>
1555 void setActiveStateAndCache(const Coord&, bool, AccessorT&) { assertNonmodifiable(); }
1556
1558
1561
1563
1564protected:
1565 using ValueOn = typename BaseLeaf::ValueOn;
1568 using ChildOn = typename BaseLeaf::ChildOn;
1571
1575
1576 // During topology-only construction, access is needed
1577 // to protected/private members of other template instances.
1578 template<typename, Index> friend struct PointIndexLeafNode;
1579
1583
1584public:
1585 using ValueOnIter = typename BaseLeaf::template ValueIter<
1587 using ValueOnCIter = typename BaseLeaf::template ValueIter<
1589 using ValueOffIter = typename BaseLeaf::template ValueIter<
1591 using ValueOffCIter = typename BaseLeaf::template ValueIter<
1593 using ValueAllIter = typename BaseLeaf::template ValueIter<
1595 using ValueAllCIter = typename BaseLeaf::template ValueIter<
1597 using ChildOnIter = typename BaseLeaf::template ChildIter<
1599 using ChildOnCIter = typename BaseLeaf::template ChildIter<
1601 using ChildOffIter = typename BaseLeaf::template ChildIter<
1603 using ChildOffCIter = typename BaseLeaf::template ChildIter<
1605 using ChildAllIter = typename BaseLeaf::template DenseIter<
1607 using ChildAllCIter = typename BaseLeaf::template DenseIter<
1608 const PointIndexLeafNode, const ValueType, ChildAll>;
1609
1610#define VMASK_ this->getValueMask()
1611 ValueOnCIter cbeginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1612 ValueOnCIter beginValueOn() const { return ValueOnCIter(VMASK_.beginOn(), this); }
1613 ValueOnIter beginValueOn() { return ValueOnIter(VMASK_.beginOn(), this); }
1614 ValueOffCIter cbeginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1615 ValueOffCIter beginValueOff() const { return ValueOffCIter(VMASK_.beginOff(), this); }
1616 ValueOffIter beginValueOff() { return ValueOffIter(VMASK_.beginOff(), this); }
1617 ValueAllCIter cbeginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1618 ValueAllCIter beginValueAll() const { return ValueAllCIter(VMASK_.beginDense(), this); }
1619 ValueAllIter beginValueAll() { return ValueAllIter(VMASK_.beginDense(), this); }
1620
1621 ValueOnCIter cendValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1622 ValueOnCIter endValueOn() const { return ValueOnCIter(VMASK_.endOn(), this); }
1623 ValueOnIter endValueOn() { return ValueOnIter(VMASK_.endOn(), this); }
1624 ValueOffCIter cendValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1625 ValueOffCIter endValueOff() const { return ValueOffCIter(VMASK_.endOff(), this); }
1626 ValueOffIter endValueOff() { return ValueOffIter(VMASK_.endOff(), this); }
1627 ValueAllCIter cendValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1628 ValueAllCIter endValueAll() const { return ValueAllCIter(VMASK_.endDense(), this); }
1629 ValueAllIter endValueAll() { return ValueAllIter(VMASK_.endDense(), this); }
1630
1631 ChildOnCIter cbeginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1632 ChildOnCIter beginChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1633 ChildOnIter beginChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1634 ChildOffCIter cbeginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1635 ChildOffCIter beginChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1636 ChildOffIter beginChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1637 ChildAllCIter cbeginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1638 ChildAllCIter beginChildAll() const { return ChildAllCIter(VMASK_.beginDense(), this); }
1639 ChildAllIter beginChildAll() { return ChildAllIter(VMASK_.beginDense(), this); }
1640
1641 ChildOnCIter cendChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1642 ChildOnCIter endChildOn() const { return ChildOnCIter(VMASK_.endOn(), this); }
1643 ChildOnIter endChildOn() { return ChildOnIter(VMASK_.endOn(), this); }
1644 ChildOffCIter cendChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1645 ChildOffCIter endChildOff() const { return ChildOffCIter(VMASK_.endOff(), this); }
1646 ChildOffIter endChildOff() { return ChildOffIter(VMASK_.endOff(), this); }
1647 ChildAllCIter cendChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1648 ChildAllCIter endChildAll() const { return ChildAllCIter(VMASK_.endDense(), this); }
1649 ChildAllIter endChildAll() { return ChildAllIter(VMASK_.endDense(), this); }
1650#undef VMASK_
1651}; // struct PointIndexLeafNode
1652
1653
1654template<typename T, Index Log2Dim>
1655inline bool
1657 const ValueType*& begin, const ValueType*& end) const
1658{
1659 return getIndices(LeafNodeType::coordToOffset(ijk), begin, end);
1660}
1661
1662
1663template<typename T, Index Log2Dim>
1664inline bool
1666 const ValueType*& begin, const ValueType*& end) const
1667{
1668 if (this->isValueMaskOn(offset)) {
1669 const ValueType* dataPtr = &mIndices.front();
1670 begin = dataPtr + (offset == 0 ? ValueType(0) : this->buffer()[offset - 1]);
1671 end = dataPtr + this->buffer()[offset];
1672 return true;
1673 }
1674 return false;
1675}
1676
1677
1678template<typename T, Index Log2Dim>
1679inline void
1681{
1682 this->buffer().setValue(offset, val);
1683 this->setValueMaskOn(offset);
1684}
1685
1686
1687template<typename T, Index Log2Dim>
1688inline void
1690{
1691 this->buffer().setValue(offset, val);
1692}
1693
1694
1695template<typename T, Index Log2Dim>
1696inline bool
1698{
1699 Index xPos, pos, zStride = Index(bbox.max()[2] - bbox.min()[2]);
1700 Coord ijk;
1701
1702 for (ijk[0] = bbox.min()[0]; ijk[0] <= bbox.max()[0]; ++ijk[0]) {
1703 xPos = (ijk[0] & (DIM - 1u)) << (2 * LOG2DIM);
1704
1705 for (ijk[1] = bbox.min()[1]; ijk[1] <= bbox.max()[1]; ++ijk[1]) {
1706 pos = xPos + ((ijk[1] & (DIM - 1u)) << LOG2DIM);
1707 pos += (bbox.min()[2] & (DIM - 1u));
1708
1709 if (this->buffer()[pos+zStride] > (pos == 0 ? T(0) : this->buffer()[pos - 1])) {
1710 return false;
1711 }
1712 }
1713 }
1714
1715 return true;
1716}
1717
1718
1719template<typename T, Index Log2Dim>
1720inline void
1721PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
1722{
1723 BaseLeaf::readBuffers(is, fromHalf);
1724
1725 Index64 numIndices = Index64(0);
1726 is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1727
1728 mIndices.resize(size_t(numIndices));
1729 is.read(reinterpret_cast<char*>(mIndices.data()), numIndices * sizeof(T));
1730}
1731
1732
1733template<typename T, Index Log2Dim>
1734inline void
1735PointIndexLeafNode<T, Log2Dim>::readBuffers(std::istream& is, const CoordBBox& bbox, bool fromHalf)
1736{
1737 // Read and clip voxel values.
1738 BaseLeaf::readBuffers(is, bbox, fromHalf);
1739
1740 Index64 numIndices = Index64(0);
1741 is.read(reinterpret_cast<char*>(&numIndices), sizeof(Index64));
1742
1743 const Index64 numBytes = numIndices * sizeof(T);
1744
1745 if (bbox.hasOverlap(this->getNodeBoundingBox())) {
1746 mIndices.resize(size_t(numIndices));
1747 is.read(reinterpret_cast<char*>(mIndices.data()), numBytes);
1748
1749 /// @todo If any voxels were deactivated as a result of clipping in the call to
1750 /// BaseLeaf::readBuffers(), the point index list will need to be regenerated.
1751 } else {
1752 // Read and discard voxel values.
1753 std::unique_ptr<char[]> buf{new char[numBytes]};
1754 is.read(buf.get(), numBytes);
1755 }
1756
1757 // Reserved for future use
1758 Index64 auxDataBytes = Index64(0);
1759 is.read(reinterpret_cast<char*>(&auxDataBytes), sizeof(Index64));
1760 if (auxDataBytes > 0) {
1761 // For now, read and discard any auxiliary data.
1762 std::unique_ptr<char[]> auxData{new char[auxDataBytes]};
1763 is.read(auxData.get(), auxDataBytes);
1764 }
1765}
1766
1767
1768template<typename T, Index Log2Dim>
1769inline void
1770PointIndexLeafNode<T, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
1771{
1772 BaseLeaf::writeBuffers(os, toHalf);
1773
1774 Index64 numIndices = Index64(mIndices.size());
1775 os.write(reinterpret_cast<const char*>(&numIndices), sizeof(Index64));
1776 os.write(reinterpret_cast<const char*>(mIndices.data()), numIndices * sizeof(T));
1777
1778 // Reserved for future use
1779 const Index64 auxDataBytes = Index64(0);
1780 os.write(reinterpret_cast<const char*>(&auxDataBytes), sizeof(Index64));
1781}
1782
1783
1784template<typename T, Index Log2Dim>
1785inline Index64
1787{
1788 return BaseLeaf::memUsage() + Index64((sizeof(T)*mIndices.capacity()) + sizeof(mIndices));
1789}
1790
1791template<typename T, Index Log2Dim>
1792inline Index64
1794{
1795 return BaseLeaf::memUsageIfLoaded() + Index64((sizeof(T)*mIndices.capacity()) + sizeof(mIndices));
1796}
1797
1798} // namespace tools
1799
1800
1801////////////////////////////////////////
1802
1803
1804namespace tree {
1805
1806/// Helper metafunction used to implement LeafNode::SameConfiguration
1807/// (which, as an inner class, can't be independently specialized)
1808template<Index Dim1, typename T2>
1810{
1811 static const bool value = true;
1812};
1813
1814} // namespace tree
1815} // namespace OPENVDB_VERSION_NAME
1816} // namespace openvdb
1817
1818#endif // OPENVDB_TOOLS_POINT_INDEX_GRID_HAS_BEEN_INCLUDED
ValueT value
Definition GridBuilder.h:1290
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition Platform.h:118
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition Platform.h:117
#define VMASK_
Definition PointDataGrid.h:703
Spatially partitions points using a parallel radix-based sorting algorithm.
Container class that associates a tree with a transform and metadata.
Definition Grid.h:571
Tag dispatch class that distinguishes constructors during file input.
Definition Types.h:650
const Vec3T & max() const
Return a const reference to the maximum point of this bounding box.
Definition BBox.h:64
const Vec3T & min() const
Return a const reference to the minimum point of this bounding box.
Definition BBox.h:62
Axis-aligned bounding box of signed integer coordinates.
Definition Coord.h:249
void expand(ValueType padding)
Pad this bounding box with the specified padding.
Definition Coord.h:418
const Coord & min() const
Definition Coord.h:321
bool hasOverlap(const CoordBBox &b) const
Return true if the given bounding box overlaps with this bounding box.
Definition Coord.h:412
const Coord & max() const
Definition Coord.h:322
Coord dim() const
Return the dimensions of the coordinates spanned by this bounding box.
Definition Coord.h:380
Signed (x, y, z) 32-bit integer coordinates.
Definition Coord.h:25
static Coord round(const Vec3< T > &xyz)
Return xyz rounded to the closest integer coordinates (cell centered conversion).
Definition Coord.h:50
Definition Transform.h:40
Vec3d voxelSize() const
Return the size of a voxel using the linear component of the map.
Definition Transform.h:93
Ptr copy() const
Definition Transform.h:50
Vec3d worldToIndex(const Vec3d &xyz) const
Definition Transform.h:110
SharedPtr< Transform > Ptr
Definition Transform.h:42
static Transform::Ptr createLinearTransform(double voxelSize=1.0)
Create and return a shared pointer to a new transform.
Definition InternalNode.h:34
Base class for iterators over internal and leaf nodes.
Definition Iterator.h:30
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition LeafManager.h:85
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition LeafManager.h:318
void foreach(const LeafOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to each leaf node in the LeafManager.
Definition LeafManager.h:483
size_t leafCount() const
Return the number of leaf nodes.
Definition LeafManager.h:287
Templated block class to hold specific data types and a fixed number of values determined by Log2Dim....
Definition LeafNode.h:38
static const Index NUM_VOXELS
Definition LeafNode.h:52
static const Index DIM
Definition LeafNode.h:50
static const Index LEVEL
Definition LeafNode.h:54
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:1479
static const Index NUM_VALUES
Definition LeafNode.h:51
static const Index LOG2DIM
Definition LeafNode.h:48
bool operator==(const LeafNode &other) const
Check for buffer, state and origin equivalence.
Definition LeafNode.h:1431
static const Index SIZE
Definition LeafNode.h:53
bool isEmpty() const
Return true if this node has no active voxels.
Definition LeafNode.h:148
static const Index TOTAL
Definition LeafNode.h:49
Definition RootNode.h:39
Definition Tree.h:178
Definition ValueAccessor.h:191
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Definition ValueAccessor.h:400
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation.
Definition NodeMasks.h:308
DenseMaskIterator< NodeMask > DenseIterator
Definition NodeMasks.h:350
OnMaskIterator< NodeMask > OnIterator
Definition NodeMasks.h:348
OffMaskIterator< NodeMask > OffIterator
Definition NodeMasks.h:349
Selectively extract and filter point data using a custom filter operator.
Partitions points into BucketLog2Dim aligned buckets using a parallel radix-based sorting algorithm.
BBox< Coord > CoordBBox
Definition NanoVDB.h:1809
Index64 pointCount(const PointDataTreeT &tree, const FilterT &filter=NullFilter(), const bool inCoreOnly=false, const bool threaded=true)
Count the total number of points in a PointDataTree.
Definition PointCount.h:88
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition Composite.h:110
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition Composite.h:106
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:343
GridT::ConstPtr getValidPointIndexGrid(const PointArrayT &points, const typename GridT::ConstPtr &grid)
Repartition the points if needed, otherwise return the input grid.
Definition PointIndexGrid.h:1331
GridT::Ptr createPointIndexGrid(const PointArrayT &points, double voxelSize)
Partition points into a point index grid to accelerate range and nearest-neighbor searches.
Definition PointIndexGrid.h:1295
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:1304
Index32 Index
Definition Types.h:54
math::BBox< Vec3d > BBoxd
Definition Types.h:84
uint64_t Index64
Definition Types.h:53
std::shared_ptr< T > SharedPtr
Definition Types.h:114
Definition Exceptions.h:13
#define OPENVDB_THROW(exception, message)
Definition Exceptions.h:74
Definition PointIndexGrid.h:306
PointIndexFilter(const PointArray &points, const TreeType &tree, const math::Transform &xform)
Constructor.
Definition PointIndexGrid.h:1226
typename PosType::value_type ScalarType
Definition PointIndexGrid.h:308
typename PointArray::PosType PosType
Definition PointIndexGrid.h:307
void searchAndApply(const PosType &center, ScalarType radius, FilterType &op)
Perform a radial search query and apply the given filter operator to the selected points.
Definition PointIndexGrid.h:1247
Accelerated range and nearest-neighbor searches for point index grids.
Definition PointIndexGrid.h:134
void operator++()
Advance iterator to next item.
Definition PointIndexGrid.h:242
PointIndexIterator(const PointIndexIterator &rhs)
Definition PointIndexGrid.h:934
void worldSpaceSearchAndUpdate(const Vec3d &center, double radius, ConstAccessor &acc, const PointArray &points, const math::Transform &xform, bool subvoxelAccuracy=true)
Clear the iterator and update it with the result of the given world-space radial query.
Definition PointIndexGrid.h:1211
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
size_t size() const
Return the number of point indices in the iterator range.
Definition PointIndexGrid.h:1049
typename TreeType::ValueType ValueType
Definition PointIndexGrid.h:137
const ValueType & operator*() const
Return a const reference to the item to which this iterator is pointing.
Definition PointIndexGrid.h:230
PointIndexIterator(const Coord &ijk, ConstAccessor &acc)
Construct an iterator over the indices of the points contained in voxel (i, j, k).
Definition PointIndexGrid.h:970
bool test() const
Return true if this iterator is not yet exhausted.
Definition PointIndexGrid.h:234
PointIndexIterator()
Definition PointIndexGrid.h:922
PointIndexIterator(const CoordBBox &bbox, ConstAccessor &acc)
Construct an iterator over the indices of the points contained in the given bounding box.
Definition PointIndexGrid.h:987
void searchAndUpdate(const BBoxd &bbox, ConstAccessor &acc, const PointArray &points, const math::Transform &xform)
Clear the iterator and update it with the result of the given index-space bounding box query.
Definition PointIndexGrid.h:1105
PointIndexIterator & operator=(const PointIndexIterator &rhs)
Definition PointIndexGrid.h:950
void searchAndUpdate(const Vec3d &center, double radius, ConstAccessor &acc, const PointArray &points, const math::Transform &xform, bool subvoxelAccuracy=true)
Clear the iterator and update it with the result of the given index-space radial query.
Definition PointIndexGrid.h:1148
void searchAndUpdate(const CoordBBox &bbox, ConstAccessor &acc)
Clear the iterator and update it with the result of the given voxel region query.
Definition PointIndexGrid.h:1090
bool next()
Advance iterator to next item.
Definition PointIndexGrid.h:1039
typename TreeType::LeafNodeType LeafNodeType
Definition PointIndexGrid.h:136
void reset()
Reset the iterator to point to the first item.
Definition PointIndexGrid.h:1005
bool operator!=(const PointIndexIterator &p) const
Definition PointIndexGrid.h:254
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
void increment()
Advance iterator to next item.
Definition PointIndexGrid.h:1022
bool operator==(const PointIndexIterator &p) const
Return true if both iterators point to the same element.
Definition PointIndexGrid.h:253
Definition PointIndexGrid.h:1358
typename BaseLeaf::template DenseIter< PointIndexLeafNode, ValueType, ChildAll > ChildAllIter
Definition PointIndexGrid.h:1606
ChildOnCIter cbeginChildOn() const
Definition PointIndexGrid.h:1631
void setValueOff(const Coord &, const ValueType &)
Definition PointIndexGrid.h:1514
ChildOnCIter beginChildOn() const
Definition PointIndexGrid.h:1632
PointIndexLeafNode(const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition PointIndexGrid.h:1401
ChildOnIter beginChildOn()
Definition PointIndexGrid.h:1633
void merge(const PointIndexLeafNode &other, const ValueType &, const ValueType &)
Definition PointIndexGrid.h:1437
ValueOnIter endValueOn()
Definition PointIndexGrid.h:1623
void setValueOff(const Coord &)
Definition PointIndexGrid.h:1511
const PointIndexLeafNode * probeConstLeaf(const Coord &) const
Return a const pointer to this node.
Definition PointIndexGrid.h:1468
void fill(const ValueType &)
Definition PointIndexGrid.h:1540
ValueOffCIter cbeginValueOff() const
Definition PointIndexGrid.h:1614
void merge(const PointIndexLeafNode &rhs)
Definition PointIndexGrid.h:1429
void setValueOff(Index)
Definition PointIndexGrid.h:1512
ChildOnIter endChildOn()
Definition PointIndexGrid.h:1643
ValueAllIter endValueAll()
Definition PointIndexGrid.h:1629
void resetBackground(const ValueType &, const ValueType &)
Definition PointIndexGrid.h:1557
void addLeaf(PointIndexLeafNode *)
Definition PointIndexGrid.h:1443
SharedPtr< PointIndexLeafNode > Ptr
Definition PointIndexGrid.h:1360
const IndexArray & indices() const
Definition PointIndexGrid.h:1367
void modifyValue(Index, const ModifyOp &)
Definition PointIndexGrid.h:1529
void setValueOn(Index, const ValueType &)
Definition PointIndexGrid.h:1521
friend struct PointIndexLeafNode
Definition PointIndexGrid.h:1578
void setValuesOff()
Definition PointIndexGrid.h:1526
ValueAllCIter endValueAll() const
Definition PointIndexGrid.h:1628
const PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &) const
Definition PointIndexGrid.h:1472
ChildOffCIter endChildOff() const
Definition PointIndexGrid.h:1645
void merge(const ValueType &tileValue, bool tileActive)
Definition PointIndexGrid.h:1432
void setValueOff(Index, const ValueType &)
Definition PointIndexGrid.h:1515
PointIndexLeafNode(const PointIndexLeafNode &rhs)
Deep copy constructor.
Definition PointIndexGrid.h:1415
ValueAllCIter cbeginValueAll() const
Definition PointIndexGrid.h:1617
typename BaseLeaf::ChildOff ChildOff
Definition PointIndexGrid.h:1569
void setValueOnly(Index, const ValueType &)
Definition PointIndexGrid.h:1509
ValueOnCIter beginValueOn() const
Definition PointIndexGrid.h:1612
typename BaseLeaf::ChildOn ChildOn
Definition PointIndexGrid.h:1568
PointIndexLeafNode()
Default constructor.
Definition PointIndexGrid.h:1398
void signedFloodFill(const ValueType &, const ValueType &)
Definition PointIndexGrid.h:1560
void addLeafAndCache(PointIndexLeafNode *, AccessorT &)
Definition PointIndexGrid.h:1445
const PointIndexLeafNode * probeLeaf(const Coord &) const
Definition PointIndexGrid.h:1473
void setActiveState(Index, bool)
Definition PointIndexGrid.h:1506
void modifyValueAndActiveState(const Coord &, const ModifyOp &)
Definition PointIndexGrid.h:1535
typename BaseLeaf::ChildAll ChildAll
Definition PointIndexGrid.h:1570
typename BaseLeaf::template ChildIter< MaskOffIterator, const PointIndexLeafNode, ChildOff > ChildOffCIter
Definition PointIndexGrid.h:1604
void setActiveStateAndCache(const Coord &, bool, AccessorT &)
Definition PointIndexGrid.h:1555
ValueOnCIter cendValueOn() const
Definition PointIndexGrid.h:1621
void setOffsetOnly(Index offset, const ValueType &val)
Definition PointIndexGrid.h:1689
ValueOffCIter beginValueOff() const
Definition PointIndexGrid.h:1615
ChildAllCIter cbeginChildAll() const
Definition PointIndexGrid.h:1637
ChildOffIter endChildOff()
Definition PointIndexGrid.h:1646
void modifyValueAndActiveStateAndCache(const Coord &, const ModifyOp &, AccessorT &)
Definition PointIndexGrid.h:1547
void setValueOnly(const Coord &, const ValueType &)
Definition PointIndexGrid.h:1508
ChildAllIter beginChildAll()
Definition PointIndexGrid.h:1639
typename BaseLeaf::template ChildIter< MaskOnIterator, PointIndexLeafNode, ChildOn > ChildOnIter
Definition PointIndexGrid.h:1598
PointIndexLeafNode(PartialCreate, const Coord &coords, const T &value=zeroVal< T >(), bool active=false)
Definition PointIndexGrid.h:1407
ValueOnIter beginValueOn()
Definition PointIndexGrid.h:1613
NodeT * probeNodeAndCache(const Coord &, AccessorT &)
Definition PointIndexGrid.h:1454
bool operator!=(const PointIndexLeafNode &other) const
Definition PointIndexGrid.h:1427
PointIndexLeafNode * probeLeaf(const Coord &)
Definition PointIndexGrid.h:1461
PointIndexLeafNode * touchLeafAndCache(const Coord &, AccessorT &)
Definition PointIndexGrid.h:1451
ChildOffCIter cbeginChildOff() const
Definition PointIndexGrid.h:1634
ChildOffIter beginChildOff()
Definition PointIndexGrid.h:1636
typename BaseLeaf::template ValueIter< MaskOnIterator, PointIndexLeafNode, const ValueType, ValueOn > ValueOnIter
Definition PointIndexGrid.h:1586
typename BaseLeaf::template ValueIter< MaskOffIterator, PointIndexLeafNode, const ValueType, ValueOff > ValueOffIter
Definition PointIndexGrid.h:1590
ChildOffCIter beginChildOff() const
Definition PointIndexGrid.h:1635
bool operator==(const PointIndexLeafNode &other) const
Check for buffer, state and origin equivalence.
Definition PointIndexGrid.h:1425
ValueOffIter endValueOff()
Definition PointIndexGrid.h:1626
typename BaseLeaf::template ChildIter< MaskOnIterator, const PointIndexLeafNode, ChildOn > ChildOnCIter
Definition PointIndexGrid.h:1600
ChildAllCIter endChildAll() const
Definition PointIndexGrid.h:1648
PointIndexLeafNode * probeLeafAndCache(const Coord &, AccessorT &)
Definition PointIndexGrid.h:1463
const NodeT * probeConstNodeAndCache(const Coord &, AccessorT &) const
Definition PointIndexGrid.h:1475
void setOffsetOn(Index offset, const ValueType &val)
Definition PointIndexGrid.h:1680
ValueOnCIter cbeginValueOn() const
Definition PointIndexGrid.h:1611
void writeBuffers(std::ostream &os, bool toHalf=false) const
Definition PointIndexGrid.h:1770
ChildOnCIter endChildOn() const
Definition PointIndexGrid.h:1642
ChildOnCIter cendChildOn() const
Definition PointIndexGrid.h:1641
void fill(const ValueType &, bool)
Definition PointIndexGrid.h:1541
ChildAllCIter cendChildAll() const
Definition PointIndexGrid.h:1647
void assertNonmodifiable()
Definition PointIndexGrid.h:1501
Index64 memUsageIfLoaded() const
Definition PointIndexGrid.h:1793
void setValueOffAndCache(const Coord &, const ValueType &, AccessorT &)
Definition PointIndexGrid.h:1552
ChildAllIter endChildAll()
Definition PointIndexGrid.h:1649
PointIndexLeafNode * touchLeaf(const Coord &)
Return a pointer to this node.
Definition PointIndexGrid.h:1449
typename NodeMaskType::OffIterator MaskOffIterator
Definition PointIndexGrid.h:1573
void readBuffers(std::istream &is, bool fromHalf=false)
Definition PointIndexGrid.h:1721
typename BaseLeaf::template ChildIter< MaskOffIterator, PointIndexLeafNode, ChildOff > ChildOffIter
Definition PointIndexGrid.h:1602
void setValue(const Coord &, const ValueType &)
Definition PointIndexGrid.h:1523
const PointIndexLeafNode * probeConstLeafAndCache(const Coord &, AccessorT &) const
Definition PointIndexGrid.h:1470
void setValueOn(const Coord &)
Definition PointIndexGrid.h:1517
ValueAllCIter cendValueAll() const
Definition PointIndexGrid.h:1627
void setValueOn(Index)
Definition PointIndexGrid.h:1518
void negate()
Definition PointIndexGrid.h:1562
ChildAllCIter beginChildAll() const
Definition PointIndexGrid.h:1638
typename BaseLeaf::ValueAll ValueAll
Definition PointIndexGrid.h:1567
typename BaseLeaf::template ValueIter< MaskDenseIterator, PointIndexLeafNode, const ValueType, ValueAll > ValueAllIter
Definition PointIndexGrid.h:1594
void setValuesOn()
Definition PointIndexGrid.h:1525
typename BaseLeaf::template ValueIter< MaskDenseIterator, const PointIndexLeafNode, const ValueType, ValueAll > ValueAllCIter
Definition PointIndexGrid.h:1596
typename BaseLeaf::ValueOn ValueOn
Definition PointIndexGrid.h:1565
IndexArray & indices()
Definition PointIndexGrid.h:1366
ChildOffCIter cendChildOff() const
Definition PointIndexGrid.h:1644
void setValueOnlyAndCache(const Coord &, const ValueType &, AccessorT &)
Definition PointIndexGrid.h:1544
typename BaseLeaf::template DenseIter< const PointIndexLeafNode, const ValueType, ChildAll > ChildAllCIter
Definition PointIndexGrid.h:1608
typename NodeMaskType::OnIterator MaskOnIterator
Definition PointIndexGrid.h:1572
typename BaseLeaf::template ValueIter< MaskOnIterator, const PointIndexLeafNode, const ValueType, ValueOn > ValueOnCIter
Definition PointIndexGrid.h:1588
typename BaseLeaf::template ValueIter< MaskOffIterator, const PointIndexLeafNode, const ValueType, ValueOff > ValueOffCIter
Definition PointIndexGrid.h:1592
void signedFloodFill(const ValueType &)
Definition PointIndexGrid.h:1559
ValueOffIter beginValueOff()
Definition PointIndexGrid.h:1616
void clip(const CoordBBox &, const ValueType &)
Definition PointIndexGrid.h:1537
typename BaseLeaf::ValueOff ValueOff
Definition PointIndexGrid.h:1566
void modifyValue(const Coord &, const ModifyOp &)
Definition PointIndexGrid.h:1532
ValueOffCIter cendValueOff() const
Definition PointIndexGrid.h:1624
Index64 memUsage() const
Definition PointIndexGrid.h:1786
void fill(const CoordBBox &, const ValueType &, bool)
Definition PointIndexGrid.h:1539
ValueOffCIter endValueOff() const
Definition PointIndexGrid.h:1625
T ValueType
Definition PointIndexGrid.h:1362
ValueOnCIter endValueOn() const
Definition PointIndexGrid.h:1622
typename NodeMaskType::DenseIterator MaskDenseIterator
Definition PointIndexGrid.h:1574
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:1420
ValueAllCIter beginValueAll() const
Definition PointIndexGrid.h:1618
void setActiveState(const Coord &, bool)
Definition PointIndexGrid.h:1505
bool getIndices(const Coord &ijk, const ValueType *&begin, const ValueType *&end) const
Definition PointIndexGrid.h:1656
void setValueOn(const Coord &, const ValueType &)
Definition PointIndexGrid.h:1520
ValueAllIter beginValueAll()
Definition PointIndexGrid.h:1619
std::vector< ValueType > IndexArray
Definition PointIndexGrid.h:1363
Leaf nodes have no children, so their child iterators have no get/set accessors.
Definition LeafNode.h:252
Definition LeafNode.h:894
static const bool value
Definition LeafNode.h:894
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition version.h.in:212