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)) {
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);
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);
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));
548 if ( (cache.
mask =
Word(w<<(LEAF_DIM-1))) ) {
550 cache.template scatter< 0, 0,-1>(1, n);
554 if ( (cache.
mask =
Word(w>>(LEAF_DIM-1))) ) {
556 cache.template scatter< 0, 0, 1>(2, n);
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);
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));
596 if ( (cache.
mask =
Word(w<<(LEAF_DIM-1))) ) {
598 cache.template scatter< 0, 0,-1>(1, n);
603 if ( (cache.
mask =
Word(w>>(LEAF_DIM-1))) ) {
605 cache.template scatter< 0, 0, 1>(2, n);
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)))));
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
1072 MaskT mask(tree,
false,
true, TopologyCopy());
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