46 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 47 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 57 #include <tbb/tbb_thread.h> 58 #include <tbb/task_scheduler_init.h> 59 #include <tbb/enumerable_thread_specific.h> 60 #include <tbb/parallel_for.h> 62 #include <type_traits> 213 template<
typename Gr
idOrTree>
216 const typename GridOrTree::ValueType& value,
217 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
223 template<
typename Gr
idOrTree>
226 const typename GridOrTree::ValueType& value,
227 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
245 template<
typename TreeType>
252 mOwnsManager(true), mManager(new
ManagerType(tree)), mAcc(tree), mSteps(1) {}
254 mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
258 void dilateVoxels6();
260 void dilateVoxels18();
262 void dilateVoxels26();
290 static const int LEAF_DIM = LeafType::DIM;
291 static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
299 inline void clear() { leaf =
nullptr; init =
true; }
300 template<
int DX,
int DY,
int DZ>
305 Coord orig = xyz.
offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
309 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics 312 const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
313 if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
316 template<
int DX,
int DY,
int DZ>
321 Coord orig = xyz.
offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
323 isOn = leaf ? false : acc.
isValueOn(orig);
325 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics 328 const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
329 return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
338 onTile.setValuesOn();
343 inline void clear() {
for (
size_t i = 0; i < size; ++i) leafs[i] =
nullptr; }
348 leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
350 template<
int DX,
int DY,
int DZ>
354 const Coord xyz = origin->
offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
355 leafs[n] = acc.probeLeaf(xyz);
356 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
358 this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
363 return leafs[n]->getValueMask().template getWord<Word>(indx);
365 template<
int DX,
int DY,
int DZ>
369 const Coord xyz = origin->
offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
370 leafs[n] = acc.probeLeaf(xyz);
371 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
373 return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
376 void scatterFacesXY(
int x,
int y,
int i1,
int n,
int i2);
379 void scatterEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
381 Word gatherFacesXY(
int x,
int y,
int i1,
int n,
int i2);
383 Word gatherEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
394 using RangeT = tbb::blocked_range<size_t>;
396 : mTask(nullptr), mSavedMasks(masks) , mManager(manager) {}
399 void erode6(
const RangeT&)
const;
400 void erode18(
const RangeT&)
const;
401 void erode26(
const RangeT&)
const;
403 using FuncT =
typename std::function<void (ErodeVoxelsOp*, const RangeT&)>;
405 std::vector<MaskType>& mSavedMasks;
411 : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
413 void save() { mSaveMasks =
true; tbb::parallel_for(mManager.
getRange(), *
this); }
414 void update() { mSaveMasks =
false; tbb::parallel_for(mManager.
getRange(), *
this); }
415 void operator()(
const tbb::blocked_range<size_t>& range)
const 418 for (
size_t i = range.begin(); i < range.end(); ++i) {
419 mMasks[i] = mManager.
leaf(i).getValueMask();
422 for (
size_t i = range.begin(); i < range.end(); ++i) {
423 mManager.
leaf(i).setValueMask(mMasks[i]);
428 std::vector<MaskType>& mMasks;
435 : mMasks(masks), mManager(manager) {}
438 for (
size_t i=r.begin(); i<r.end(); ++i) mManager.
leaf(i).setValueMask(mMasks[i]);
445 : mMasks(masks), mManager(manager) {}
448 for (
size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.
leaf(i).getValueMask();
457 template<
typename TreeType>
461 for (
int i=0; i<iterations; ++i) {
464 this->dilateVoxels18();
467 this->dilateVoxels26();
471 this->dilateVoxels6();
477 template<
typename TreeType>
482 const int leafCount =
static_cast<int>(mManager->leafCount());
485 std::vector<MaskType> savedMasks(leafCount);
486 this->copyMasks(savedMasks, *mManager);
488 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
489 const MaskType& oldMask = savedMasks[leafIdx];
490 cache[0] = &mManager->leaf(leafIdx);
492 for (
int x = 0; x < LEAF_DIM; ++x ) {
493 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
495 if (
const Word w = oldMask.template getWord<Word>(n)) {
498 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
501 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
502 cache.template scatter< 0, 0,-1>(1, n);
505 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
506 cache.template scatter< 0, 0, 1>(2, n);
509 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
516 mManager->rebuildLeafArray();
520 template<
typename TreeType>
525 const int leafCount =
static_cast<int>(mManager->leafCount());
528 std::vector<MaskType> savedMasks(leafCount);
529 this->copyMasks(savedMasks, *mManager);
531 Coord orig_mz, orig_pz;
532 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
533 const MaskType& oldMask = savedMasks[leafIdx];
534 cache[0] = &mManager->leaf(leafIdx);
535 orig_mz = cache[0]->origin().
offsetBy(0, 0, -LEAF_DIM);
536 orig_pz = cache[0]->origin().
offsetBy(0, 0, LEAF_DIM);
537 for (
int x = 0; x < LEAF_DIM; ++x ) {
538 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
539 if (
const Word w = oldMask.template getWord<Word>(n)) {
541 cache.mask =
Word(w | (w>>1) | (w<<1));
542 cache.setOrigin(cache[0]->origin());
544 cache.scatterFacesXY(x, y, 0, n, 3);
546 cache.scatterEdgesXY(x, y, 0, n, 3);
548 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
549 cache.setOrigin(cache[0]->origin());
550 cache.template scatter< 0, 0,-1>(1, n);
551 cache.setOrigin(orig_mz);
552 cache.scatterFacesXY(x, y, 1, n, 11);
554 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
555 cache.setOrigin(cache[0]->origin());
556 cache.template scatter< 0, 0, 1>(2, n);
557 cache.setOrigin(orig_pz);
558 cache.scatterFacesXY(x, y, 2, n, 15);
566 mManager->rebuildLeafArray();
570 template<
typename TreeType>
574 const int leafCount =
static_cast<int>(mManager->leafCount());
577 std::vector<MaskType> savedMasks(leafCount);
578 this->copyMasks(savedMasks, *mManager);
580 Coord orig_mz, orig_pz;
581 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
582 const MaskType& oldMask = savedMasks[leafIdx];
583 cache[0] = &mManager->leaf(leafIdx);
584 orig_mz = cache[0]->origin().
offsetBy(0, 0, -LEAF_DIM);
585 orig_pz = cache[0]->origin().
offsetBy(0, 0, LEAF_DIM);
586 for (
int x = 0; x < LEAF_DIM; ++x ) {
587 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
588 if (
const Word w = oldMask.template getWord<Word>(n)) {
590 cache.mask =
Word(w | (w>>1) | (w<<1));
591 cache.setOrigin(cache[0]->origin());
593 cache.scatterFacesXY(x, y, 0, n, 3);
594 cache.scatterEdgesXY(x, y, 0, n, 3);
596 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
597 cache.setOrigin(cache[0]->origin());
598 cache.template scatter< 0, 0,-1>(1, n);
599 cache.setOrigin(orig_mz);
600 cache.scatterFacesXY(x, y, 1, n, 11);
601 cache.scatterEdgesXY(x, y, 1, n, 11);
603 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
604 cache.setOrigin(cache[0]->origin());
605 cache.template scatter< 0, 0, 1>(2, n);
606 cache.setOrigin(orig_pz);
607 cache.scatterFacesXY(x, y, 2, n, 19);
608 cache.scatterEdgesXY(x, y, 2, n, 19);
616 mManager->rebuildLeafArray();
620 template<
typename TreeType>
626 this->scatter(i1, n-LEAF_DIM);
628 this->
template scatter<-1, 0, 0>(i2, n);
631 if (x < LEAF_DIM-1) {
632 this->scatter(i1, n+LEAF_DIM);
634 this->
template scatter< 1, 0, 0>(i2+1, n);
638 this->scatter(i1, n-1);
640 this->
template scatter< 0,-1, 0>(i2+2, n);
643 if (y < LEAF_DIM-1) {
644 this->scatter(i1, n+1);
646 this->
template scatter< 0, 1, 0>(i2+3, n);
651 template<
typename TreeType>
657 this->scatter(i1, n-LEAF_DIM-1);
659 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
661 if (y < LEAF_DIM-1) {
662 this->scatter(i1, n-LEAF_DIM+1);
664 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
667 if (y < LEAF_DIM-1) {
668 this->
template scatter<-1, 0, 0>(i2 , n+1);
670 this->
template scatter<-1, 1, 0>(i2+7, n );
673 this->
template scatter<-1, 0, 0>(i2 , n-1);
675 this->
template scatter<-1,-1, 0>(i2+4, n );
678 if (x < LEAF_DIM-1) {
680 this->scatter(i1, n+LEAF_DIM-1);
682 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
684 if (y < LEAF_DIM-1) {
685 this->scatter(i1, n+LEAF_DIM+1);
687 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
691 this->
template scatter< 1, 0, 0>(i2+1, n-1);
693 this->
template scatter< 1,-1, 0>(i2+6, n );
695 if (y < LEAF_DIM-1) {
696 this->
template scatter< 1, 0, 0>(i2+1, n+1);
698 this->
template scatter< 1, 1, 0>(i2+5, n );
704 template<
typename TreeType>
708 namespace ph = std::placeholders;
711 mTask = std::bind(&ErodeVoxelsOp::erode18, ph::_1, ph::_2);
714 mTask = std::bind(&ErodeVoxelsOp::erode26, ph::_1, ph::_2);
718 mTask = std::bind(&ErodeVoxelsOp::erode6, ph::_1, ph::_2);
720 tbb::parallel_for(mManager.getRange(), *
this);
724 template<
typename TreeType>
729 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
732 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
735 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
738 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
744 template<
typename TreeType>
751 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
752 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
753 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
754 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
756 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
757 this->
template gather<-1, 1, 0>(i2+7, n );
758 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
759 this->
template gather<-1,-1, 0>(i2+4, n );
761 if (x < LEAF_DIM-1) {
762 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
763 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
764 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
765 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
767 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
768 this->
template gather< 1,-1, 0>(i2+6, n );
769 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
770 this->
template gather< 1, 1, 0>(i2+5, n );
777 template <
typename TreeType>
782 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
783 cache[0] = &mManager.leaf(leafIdx);
784 if (cache[0]->isEmpty())
continue;
786 MaskType& newMask = mSavedMasks[leafIdx];
787 for (
int x = 0; x < LEAF_DIM; ++x ) {
788 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
790 if (
Word& w = newMask.template getWord<Word>(n)) {
794 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
795 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
797 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
806 template <
typename TreeType>
814 template <
typename TreeType>
822 template<
typename TreeType>
827 const size_t leafCount = mManager->leafCount();
830 std::vector<MaskType> savedMasks(leafCount);
831 this->copyMasks(savedMasks, *mManager);
835 for (
int i = 0; i < mSteps; ++i) {
847 template<
typename TreeType>
851 if (iterations > 0 ) {
857 template<
typename TreeType>
861 if (iterations > 0 ) {
867 template<
typename TreeType>
871 if (iterations > 0 ) {
877 template<
typename TreeType>
881 if (iterations > 0 ) {
891 namespace activation {
893 template<
typename TreeType>
897 using ValueT =
typename TreeType::ValueType;
905 void operator()(
const typename TreeType::ValueOnIter& it)
const 912 void operator()(
const typename TreeType::ValueOffIter& it)
const 915 it.setActiveState(
true);
919 void operator()(
const typename TreeType::LeafIter& lit)
const 921 using LeafT =
typename TreeType::LeafNodeType;
924 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
926 leaf.setValueOn(it.pos());
930 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
932 leaf.setValueOff(it.pos());
940 const ValueT mValue, mTolerance;
946 template<
typename Gr
idOrTree>
948 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
949 const typename GridOrTree::ValueType& tolerance)
952 using TreeType =
typename Adapter::TreeType;
954 TreeType& tree = Adapter::tree(gridOrTree);
959 foreach(tree.beginLeaf(), op);
963 typename TreeType::ValueOffIter it = tree.beginValueOff();
964 it.setMaxDepth(tree.treeDepth() - 2);
965 foreach(it, op,
false);
969 template<
typename Gr
idOrTree>
971 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
972 const typename GridOrTree::ValueType& tolerance)
975 using TreeType =
typename Adapter::TreeType;
977 TreeType& tree = Adapter::tree(gridOrTree);
982 foreach(tree.beginLeaf(), op);
986 typename TreeType::ValueOnIter it = tree.beginValueOn();
987 it.setMaxDepth(tree.treeDepth() - 2);
988 foreach(it, op,
false);
993 template<
typename TreeT>
996 using MaskT =
typename TreeT::template ValueConverter<ValueMask>::Type;
997 using PoolT = tbb::enumerable_thread_specific<MaskT>;
998 using LeafT =
typename MaskT::LeafNodeType;
1009 : mIter(iterations), mNN(nn), mPool(nullptr), mLeafs(nullptr)
1011 const size_t numLeafs = this->init( tree, mode );
1012 const size_t numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
1013 const size_t grainSize =
math::Max(
size_t(1), numLeafs/(2*numThreads));
1019 tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *
this);
1023 using IterT =
typename PoolT::iterator;
1024 for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);
1028 tree.topologyUnion(mask);
1035 for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1044 using value_type = LeafT*;
1046 MyArray(value_type* array) : ptr(array) {}
1047 void push_back(value_type leaf) { *ptr++ = leaf; }
1051 size_t linearize(MaskT& mask,
TilePolicy mode)
1054 const size_t numLeafs = mask.leafCount();
1055 mLeafs =
new LeafT*[numLeafs];
1056 MyArray tmp(mLeafs);
1057 mask.stealNodes(tmp);
1061 template<
typename T>
1062 typename std::enable_if<std::is_same<T, MaskT>::value,
size_t>::type
1065 return this->linearize(tree, mode);
1068 template<
typename T>
1069 typename std::enable_if<!std::is_same<T, MaskT>::value,
size_t>::type
1073 return this->linearize(mask, mode);
1078 template<
typename TreeType>
1085 template<
typename TreeType>
1092 if (iterations > 0 ) {
1102 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:569
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:315
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:52
LeafNodeT * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one, but preserve the values and active states of all voxels.
Definition: ValueAccessor.h:386
Defined various multi-threaded utility functions for trees.
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:750
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:264
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
Definition: ValueAccessor.h:417
bool isApproxEqual(const Type &a, const Type &b)
Return true if a is equal to b to within the default floating-point comparison tolerance.
Definition: Math.h:378
Definition: Exceptions.h:40
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:358
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:342
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:382
Definition: Exceptions.h:88
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1076
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition: Coord.h:119