46 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 47 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 49 #include <tbb/tbb_thread.h> 50 #include <tbb/task_scheduler_init.h> 51 #include <tbb/enumerable_thread_specific.h> 52 #include <tbb/parallel_for.h> 59 #include <boost/scoped_array.hpp> 60 #include <boost/bind.hpp> 61 #include <boost/utility/enable_if.hpp> 62 #include <boost/type_traits/is_same.hpp> 209 template<
typename Gr
idOrTree>
212 const typename GridOrTree::ValueType& value,
213 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
219 template<
typename Gr
idOrTree>
222 const typename GridOrTree::ValueType& value,
223 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
241 template<
typename TreeType>
248 mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
250 mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
254 void dilateVoxels6();
256 void dilateVoxels18();
258 void dilateVoxels26();
286 static const int LEAF_DIM = LeafType::DIM;
287 static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
295 inline void clear() { leaf =
nullptr; init =
true; }
296 template<
int DX,
int DY,
int DZ>
297 void scatter(AccessorType& acc,
const Coord &xyz,
int indx, Word mask)
301 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
305 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics 308 const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
309 if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
312 template<
int DX,
int DY,
int DZ>
313 Word
gather(AccessorType& acc,
const Coord &xyz,
int indx)
317 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
319 isOn = leaf ?
false : acc.
isValueOn(orig);
321 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics 324 const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
325 return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
326 : isOn ? ~Word(0) : Word(0);
332 LeafCache(
size_t n, TreeType& tree) : size(n), leafs(new LeafType*[n]), acc(tree)
334 onTile.setValuesOn();
339 inline void clear() {
for (
size_t i = 0; i < size; ++i) leafs[i] =
nullptr; }
340 inline void setOrigin(
const Coord& xyz) { origin = &xyz; }
344 leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
346 template<
int DX,
int DY,
int DZ>
350 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
351 leafs[n] = acc.probeLeaf(xyz);
352 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
354 this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
359 return leafs[n]->getValueMask().template getWord<Word>(indx);
361 template<
int DX,
int DY,
int DZ>
365 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
366 leafs[n] = acc.probeLeaf(xyz);
367 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
369 return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
372 void scatterFacesXY(
int x,
int y,
int i1,
int n,
int i2);
375 void scatterEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
377 Word gatherFacesXY(
int x,
int y,
int i1,
int n,
int i2);
379 Word gatherEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
390 typedef tbb::blocked_range<size_t>
RangeT;
392 : mTask(0), mSavedMasks(masks) , mManager(manager) {}
394 void operator()(
const RangeT& r)
const {mTask(const_cast<ErodeVoxelsOp*>(
this), r);}
395 void erode6(
const RangeT&)
const;
396 void erode18(
const RangeT&)
const;
397 void erode26(
const RangeT&)
const;
399 typedef typename boost::function<void (ErodeVoxelsOp*, const RangeT&)> FuncT;
401 std::vector<MaskType>& mSavedMasks;
402 ManagerType& mManager;
407 : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
409 void save() { mSaveMasks =
true; tbb::parallel_for(mManager.
getRange(), *
this); }
410 void update() { mSaveMasks =
false; tbb::parallel_for(mManager.
getRange(), *
this); }
411 void operator()(
const tbb::blocked_range<size_t>& range)
const 414 for (
size_t i = range.begin(); i < range.end(); ++i) {
415 mMasks[i] = mManager.
leaf(i).getValueMask();
418 for (
size_t i = range.begin(); i < range.end(); ++i) {
419 mManager.
leaf(i).setValueMask(mMasks[i]);
424 std::vector<MaskType>& mMasks;
425 ManagerType& mManager;
430 UpdateMasks(
const std::vector<MaskType>& masks, ManagerType& manager)
431 : mMasks(masks), mManager(manager) {}
434 for (
size_t i=r.begin(); i<r.end(); ++i) mManager.
leaf(i).setValueMask(mMasks[i]);
440 CopyMasks(std::vector<MaskType>& masks,
const ManagerType& manager)
441 : mMasks(masks), mManager(manager) {}
444 for (
size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.
leaf(i).getValueMask();
453 template<
typename TreeType>
457 for (
int i=0; i<iterations; ++i) {
460 this->dilateVoxels18();
463 this->dilateVoxels26();
467 this->dilateVoxels6();
473 template<
typename TreeType>
478 const int leafCount =
static_cast<int>(mManager->leafCount());
481 std::vector<MaskType> savedMasks(leafCount);
482 this->copyMasks(savedMasks, *mManager);
484 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
485 const MaskType& oldMask = savedMasks[leafIdx];
486 cache[0] = &mManager->leaf(leafIdx);
488 for (
int x = 0; x < LEAF_DIM; ++x ) {
489 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
491 if (
const Word w = oldMask.template getWord<Word>(n)) {
494 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
497 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
498 cache.template scatter< 0, 0,-1>(1, n);
501 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
502 cache.template scatter< 0, 0, 1>(2, n);
505 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
512 mManager->rebuildLeafArray();
516 template<
typename TreeType>
521 const int leafCount =
static_cast<int>(mManager->leafCount());
524 std::vector<MaskType> savedMasks(leafCount);
525 this->copyMasks(savedMasks, *mManager);
527 Coord orig_mz, orig_pz;
528 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
529 const MaskType& oldMask = savedMasks[leafIdx];
530 cache[0] = &mManager->leaf(leafIdx);
531 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
532 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
533 for (
int x = 0; x < LEAF_DIM; ++x ) {
534 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
535 if (
const Word w = oldMask.template getWord<Word>(n)) {
537 cache.mask =
Word(w | (w>>1) | (w<<1));
538 cache.setOrigin(cache[0]->origin());
540 cache.scatterFacesXY(x, y, 0, n, 3);
542 cache.scatterEdgesXY(x, y, 0, n, 3);
544 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
545 cache.setOrigin(cache[0]->origin());
546 cache.template scatter< 0, 0,-1>(1, n);
547 cache.setOrigin(orig_mz);
548 cache.scatterFacesXY(x, y, 1, n, 11);
550 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
551 cache.setOrigin(cache[0]->origin());
552 cache.template scatter< 0, 0, 1>(2, n);
553 cache.setOrigin(orig_pz);
554 cache.scatterFacesXY(x, y, 2, n, 15);
562 mManager->rebuildLeafArray();
566 template<
typename TreeType>
570 const int leafCount =
static_cast<int>(mManager->leafCount());
573 std::vector<MaskType> savedMasks(leafCount);
574 this->copyMasks(savedMasks, *mManager);
576 Coord orig_mz, orig_pz;
577 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
578 const MaskType& oldMask = savedMasks[leafIdx];
579 cache[0] = &mManager->leaf(leafIdx);
580 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
581 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
582 for (
int x = 0; x < LEAF_DIM; ++x ) {
583 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
584 if (
const Word w = oldMask.template getWord<Word>(n)) {
586 cache.mask =
Word(w | (w>>1) | (w<<1));
587 cache.setOrigin(cache[0]->origin());
589 cache.scatterFacesXY(x, y, 0, n, 3);
590 cache.scatterEdgesXY(x, y, 0, n, 3);
592 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
593 cache.setOrigin(cache[0]->origin());
594 cache.template scatter< 0, 0,-1>(1, n);
595 cache.setOrigin(orig_mz);
596 cache.scatterFacesXY(x, y, 1, n, 11);
597 cache.scatterEdgesXY(x, y, 1, n, 11);
599 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
600 cache.setOrigin(cache[0]->origin());
601 cache.template scatter< 0, 0, 1>(2, n);
602 cache.setOrigin(orig_pz);
603 cache.scatterFacesXY(x, y, 2, n, 19);
604 cache.scatterEdgesXY(x, y, 2, n, 19);
612 mManager->rebuildLeafArray();
616 template<
typename TreeType>
622 this->scatter(i1, n-LEAF_DIM);
624 this->
template scatter<-1, 0, 0>(i2, n);
627 if (x < LEAF_DIM-1) {
628 this->scatter(i1, n+LEAF_DIM);
630 this->
template scatter< 1, 0, 0>(i2+1, n);
634 this->scatter(i1, n-1);
636 this->
template scatter< 0,-1, 0>(i2+2, n);
639 if (y < LEAF_DIM-1) {
640 this->scatter(i1, n+1);
642 this->
template scatter< 0, 1, 0>(i2+3, n);
647 template<
typename TreeType>
653 this->scatter(i1, n-LEAF_DIM-1);
655 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
657 if (y < LEAF_DIM-1) {
658 this->scatter(i1, n-LEAF_DIM+1);
660 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
663 if (y < LEAF_DIM-1) {
664 this->
template scatter<-1, 0, 0>(i2 , n+1);
666 this->
template scatter<-1, 1, 0>(i2+7, n );
669 this->
template scatter<-1, 0, 0>(i2 , n-1);
671 this->
template scatter<-1,-1, 0>(i2+4, n );
674 if (x < LEAF_DIM-1) {
676 this->scatter(i1, n+LEAF_DIM-1);
678 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
680 if (y < LEAF_DIM-1) {
681 this->scatter(i1, n+LEAF_DIM+1);
683 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
687 this->
template scatter< 1, 0, 0>(i2+1, n-1);
689 this->
template scatter< 1,-1, 0>(i2+6, n );
691 if (y < LEAF_DIM-1) {
692 this->
template scatter< 1, 0, 0>(i2+1, n+1);
694 this->
template scatter< 1, 1, 0>(i2+5, n );
700 template<
typename TreeType>
706 mTask = boost::bind(&ErodeVoxelsOp::erode18, _1, _2);
709 mTask = boost::bind(&ErodeVoxelsOp::erode26, _1, _2);
713 mTask = boost::bind(&ErodeVoxelsOp::erode6, _1, _2);
715 tbb::parallel_for(mManager.getRange(), *
this);
719 template<
typename TreeType>
724 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
727 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
730 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
733 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
739 template<
typename TreeType>
746 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
747 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
748 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
749 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
751 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
752 this->
template gather<-1, 1, 0>(i2+7, n );
753 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
754 this->
template gather<-1,-1, 0>(i2+4, n );
756 if (x < LEAF_DIM-1) {
757 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
758 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
759 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
760 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
762 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
763 this->
template gather< 1,-1, 0>(i2+6, n );
764 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
765 this->
template gather< 1, 1, 0>(i2+5, n );
772 template <
typename TreeType>
777 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
778 cache[0] = &mManager.leaf(leafIdx);
779 if (cache[0]->isEmpty())
continue;
781 MaskType& newMask = mSavedMasks[leafIdx];
782 for (
int x = 0; x < LEAF_DIM; ++x ) {
783 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
785 if (
Word& w = newMask.template getWord<Word>(n)) {
789 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
790 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
792 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
801 template <
typename TreeType>
809 template <
typename TreeType>
817 template<
typename TreeType>
822 const size_t leafCount = mManager->leafCount();
825 std::vector<MaskType> savedMasks(leafCount);
826 this->copyMasks(savedMasks, *mManager);
830 for (
int i = 0; i < mSteps; ++i) {
842 template<
typename TreeType>
846 if (iterations > 0 ) {
852 template<
typename TreeType>
856 if (iterations > 0 ) {
862 template<
typename TreeType>
866 if (iterations > 0 ) {
872 template<
typename TreeType>
876 if (iterations > 0 ) {
886 namespace activation {
888 template<
typename TreeType>
892 typedef typename TreeType::ValueType
ValueT;
900 void operator()(
const typename TreeType::ValueOnIter& it)
const 907 void operator()(
const typename TreeType::ValueOffIter& it)
const 910 it.setActiveState(
true);
914 void operator()(
const typename TreeType::LeafIter& lit)
const 916 typedef typename TreeType::LeafNodeType LeafT;
919 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
921 leaf.setValueOn(it.pos());
925 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
927 leaf.setValueOff(it.pos());
935 const ValueT mValue, mTolerance;
941 template<
typename Gr
idOrTree>
943 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
944 const typename GridOrTree::ValueType& tolerance)
947 typedef typename Adapter::TreeType TreeType;
949 TreeType& tree = Adapter::tree(gridOrTree);
954 foreach(tree.beginLeaf(), op);
958 typename TreeType::ValueOffIter it = tree.beginValueOff();
959 it.setMaxDepth(tree.treeDepth() - 2);
960 foreach(it, op,
false);
964 template<
typename Gr
idOrTree>
966 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
967 const typename GridOrTree::ValueType& tolerance)
970 typedef typename Adapter::TreeType TreeType;
972 TreeType& tree = Adapter::tree(gridOrTree);
977 foreach(tree.beginLeaf(), op);
981 typename TreeType::ValueOnIter it = tree.beginValueOn();
982 it.setMaxDepth(tree.treeDepth() - 2);
983 foreach(it, op,
false);
988 template<
typename TreeT>
991 typedef typename TreeT::template ValueConverter<ValueMask>::Type MaskT;
992 typedef tbb::enumerable_thread_specific<MaskT> PoolT;
993 typedef typename MaskT::LeafNodeType LeafT;
1004 : mIter(iterations), mNN(nn), mPool(nullptr), mLeafs(nullptr)
1006 const size_t numLeafs = this->init( tree, mode );
1007 const size_t numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
1008 const size_t grainSize =
math::Max(
size_t(1), numLeafs/(2*numThreads));
1014 tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *
this);
1018 typedef typename PoolT::iterator IterT;
1019 for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);
1023 tree.topologyUnion(mask);
1030 for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1039 typedef LeafT* value_type;
1041 MyArray(value_type* array) : ptr(array) {}
1042 void push_back(value_type leaf) { *ptr++ = leaf; }
1046 size_t linearize(MaskT& mask,
TilePolicy mode)
1049 const size_t numLeafs = mask.leafCount();
1050 mLeafs =
new LeafT*[numLeafs];
1051 MyArray tmp(mLeafs);
1052 mask.stealNodes(tmp);
1056 template <
typename T>
1057 typename boost::enable_if<boost::is_same<T,MaskT>,
size_t>::type init(T& tree,
TilePolicy mode)
1059 return this->linearize(tree, mode);
1062 template <
typename T>
1063 typename boost::disable_if<boost::is_same<T,MaskT>,
size_t>::type init(
const T& tree,
TilePolicy mode)
1066 return this->linearize(mask, mode);
1071 template<
typename TreeType>
1078 template<
typename TreeType>
1085 if (iterations > 0 ) {
1095 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:503
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:370
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:424
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:115
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:388
Defined various multi-threaded utility functions for trees.
#define OPENVDB_VERSION_NAME
Definition: version.h:43
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:263
Definition: Exceptions.h:39
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:393
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:321
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:561
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:935
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:348
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:364