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> 53 #include <openvdb/Types.h> 54 #include <openvdb/Grid.h> 55 #include <openvdb/math/Math.h> 56 #include <openvdb/tree/TreeIterator.h> 57 #include <openvdb/tree/ValueAccessor.h> 58 #include <openvdb/tree/LeafManager.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 = NULL; init =
true; }
296 template<
int DX,
int DY,
int DZ>
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>
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]=NULL; }
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();
466 this->dilateVoxels6();
472 template<
typename TreeType>
477 const int leafCount =
static_cast<int>(mManager->leafCount());
480 std::vector<MaskType> savedMasks(leafCount);
481 this->copyMasks(savedMasks, *mManager);
483 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
484 const MaskType& oldMask = savedMasks[leafIdx];
485 cache[0] = &mManager->leaf(leafIdx);
487 for (
int x = 0; x < LEAF_DIM; ++x ) {
488 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
490 if (
const Word w = oldMask.template getWord<Word>(n)) {
493 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
496 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
497 cache.template scatter< 0, 0,-1>(1, n);
500 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
501 cache.template scatter< 0, 0, 1>(2, n);
504 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
511 mManager->rebuildLeafArray();
515 template<
typename TreeType>
520 const int leafCount =
static_cast<int>(mManager->leafCount());
523 std::vector<MaskType> savedMasks(leafCount);
524 this->copyMasks(savedMasks, *mManager);
526 Coord orig_mz, orig_pz;
527 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
528 const MaskType& oldMask = savedMasks[leafIdx];
529 cache[0] = &mManager->leaf(leafIdx);
530 orig_mz = cache[0]->origin().
offsetBy(0, 0, -LEAF_DIM);
531 orig_pz = cache[0]->origin().
offsetBy(0, 0, LEAF_DIM);
532 for (
int x = 0; x < LEAF_DIM; ++x ) {
533 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
534 if (
const Word w = oldMask.template getWord<Word>(n)) {
536 cache.mask =
Word(w | (w>>1) | (w<<1));
537 cache.setOrigin(cache[0]->origin());
539 cache.scatterFacesXY(x, y, 0, n, 3);
541 cache.scatterEdgesXY(x, y, 0, n, 3);
543 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
544 cache.setOrigin(cache[0]->origin());
545 cache.template scatter< 0, 0,-1>(1, n);
546 cache.setOrigin(orig_mz);
547 cache.scatterFacesXY(x, y, 1, n, 11);
549 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
550 cache.setOrigin(cache[0]->origin());
551 cache.template scatter< 0, 0, 1>(2, n);
552 cache.setOrigin(orig_pz);
553 cache.scatterFacesXY(x, y, 2, n, 15);
561 mManager->rebuildLeafArray();
565 template<
typename TreeType>
569 const int leafCount =
static_cast<int>(mManager->leafCount());
572 std::vector<MaskType> savedMasks(leafCount);
573 this->copyMasks(savedMasks, *mManager);
575 Coord orig_mz, orig_pz;
576 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
577 const MaskType& oldMask = savedMasks[leafIdx];
578 cache[0] = &mManager->leaf(leafIdx);
579 orig_mz = cache[0]->origin().
offsetBy(0, 0, -LEAF_DIM);
580 orig_pz = cache[0]->origin().
offsetBy(0, 0, LEAF_DIM);
581 for (
int x = 0; x < LEAF_DIM; ++x ) {
582 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
583 if (
const Word w = oldMask.template getWord<Word>(n)) {
585 cache.mask =
Word(w | (w>>1) | (w<<1));
586 cache.setOrigin(cache[0]->origin());
588 cache.scatterFacesXY(x, y, 0, n, 3);
589 cache.scatterEdgesXY(x, y, 0, n, 3);
591 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
592 cache.setOrigin(cache[0]->origin());
593 cache.template scatter< 0, 0,-1>(1, n);
594 cache.setOrigin(orig_mz);
595 cache.scatterFacesXY(x, y, 1, n, 11);
596 cache.scatterEdgesXY(x, y, 1, n, 11);
598 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
599 cache.setOrigin(cache[0]->origin());
600 cache.template scatter< 0, 0, 1>(2, n);
601 cache.setOrigin(orig_pz);
602 cache.scatterFacesXY(x, y, 2, n, 19);
603 cache.scatterEdgesXY(x, y, 2, n, 19);
611 mManager->rebuildLeafArray();
615 template<
typename TreeType>
621 this->scatter(i1, n-LEAF_DIM);
623 this->
template scatter<-1, 0, 0>(i2, n);
626 if (x < LEAF_DIM-1) {
627 this->scatter(i1, n+LEAF_DIM);
629 this->
template scatter< 1, 0, 0>(i2+1, n);
633 this->scatter(i1, n-1);
635 this->
template scatter< 0,-1, 0>(i2+2, n);
638 if (y < LEAF_DIM-1) {
639 this->scatter(i1, n+1);
641 this->
template scatter< 0, 1, 0>(i2+3, n);
646 template<
typename TreeType>
652 this->scatter(i1, n-LEAF_DIM-1);
654 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
656 if (y < LEAF_DIM-1) {
657 this->scatter(i1, n-LEAF_DIM+1);
659 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
662 if (y < LEAF_DIM-1) {
663 this->
template scatter<-1, 0, 0>(i2 , n+1);
665 this->
template scatter<-1, 1, 0>(i2+7, n );
668 this->
template scatter<-1, 0, 0>(i2 , n-1);
670 this->
template scatter<-1,-1, 0>(i2+4, n );
673 if (x < LEAF_DIM-1) {
675 this->scatter(i1, n+LEAF_DIM-1);
677 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
679 if (y < LEAF_DIM-1) {
680 this->scatter(i1, n+LEAF_DIM+1);
682 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
686 this->
template scatter< 1, 0, 0>(i2+1, n-1);
688 this->
template scatter< 1,-1, 0>(i2+6, n );
690 if (y < LEAF_DIM-1) {
691 this->
template scatter< 1, 0, 0>(i2+1, n+1);
693 this->
template scatter< 1, 1, 0>(i2+5, n );
699 template<
typename TreeType>
705 mTask = boost::bind(&ErodeVoxelsOp::erode18, _1, _2);
708 mTask = boost::bind(&ErodeVoxelsOp::erode26, _1, _2);
711 mTask = boost::bind(&ErodeVoxelsOp::erode6, _1, _2);
713 tbb::parallel_for(mManager.getRange(), *
this);
717 template<
typename TreeType>
722 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
725 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
728 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
731 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
737 template<
typename TreeType>
744 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
745 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
746 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
747 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
749 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
750 this->
template gather<-1, 1, 0>(i2+7, n );
751 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
752 this->
template gather<-1,-1, 0>(i2+4, n );
754 if (x < LEAF_DIM-1) {
755 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
756 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
757 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
758 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
760 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
761 this->
template gather< 1,-1, 0>(i2+6, n );
762 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
763 this->
template gather< 1, 1, 0>(i2+5, n );
770 template <
typename TreeType>
775 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
776 cache[0] = &mManager.leaf(leafIdx);
777 if (cache[0]->isEmpty())
continue;
779 MaskType& newMask = mSavedMasks[leafIdx];
780 for (
int x = 0; x < LEAF_DIM; ++x ) {
781 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
783 if (
Word& w = newMask.template getWord<Word>(n)) {
787 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
788 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
790 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
799 template <
typename TreeType>
807 template <
typename TreeType>
815 template<
typename TreeType>
820 const size_t leafCount = mManager->leafCount();
823 std::vector<MaskType> savedMasks(leafCount);
824 this->copyMasks(savedMasks, *mManager);
828 for (
int i = 0; i < mSteps; ++i) {
840 template<
typename TreeType>
844 if (iterations > 0 ) {
850 template<
typename TreeType>
854 if (iterations > 0 ) {
860 template<
typename TreeType>
864 if (iterations > 0 ) {
870 template<
typename TreeType>
874 if (iterations > 0 ) {
884 namespace activation {
886 template<
typename TreeType>
890 typedef typename TreeType::ValueType
ValueT;
898 void operator()(
const typename TreeType::ValueOnIter& it)
const 905 void operator()(
const typename TreeType::ValueOffIter& it)
const 908 it.setActiveState(
true);
912 void operator()(
const typename TreeType::LeafIter& lit)
const 914 typedef typename TreeType::LeafNodeType LeafT;
917 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
919 leaf.setValueOn(it.pos());
923 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
925 leaf.setValueOff(it.pos());
933 const ValueT mValue, mTolerance;
939 template<
typename Gr
idOrTree>
941 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
942 const typename GridOrTree::ValueType& tolerance)
945 typedef typename Adapter::TreeType TreeType;
947 TreeType& tree = Adapter::tree(gridOrTree);
952 foreach(tree.beginLeaf(), op);
956 typename TreeType::ValueOffIter it = tree.beginValueOff();
957 it.setMaxDepth(tree.treeDepth() - 2);
958 foreach(it, op,
false);
962 template<
typename Gr
idOrTree>
964 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
965 const typename GridOrTree::ValueType& tolerance)
968 typedef typename Adapter::TreeType TreeType;
970 TreeType& tree = Adapter::tree(gridOrTree);
975 foreach(tree.beginLeaf(), op);
979 typename TreeType::ValueOnIter it = tree.beginValueOn();
980 it.setMaxDepth(tree.treeDepth() - 2);
981 foreach(it, op,
false);
986 template<
typename TreeT>
989 typedef typename TreeT::template ValueConverter<ValueMask>::Type MaskT;
990 typedef tbb::enumerable_thread_specific<MaskT> PoolT;
991 typedef typename MaskT::LeafNodeType LeafT;
1002 : mIter(iterations), mNN(nn), mPool(NULL), mLeafs(NULL)
1004 const size_t numLeafs = this->init( tree, mode );
1005 const size_t numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
1006 const size_t grainSize =
math::Max(
size_t(1), numLeafs/(2*numThreads));
1012 tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *
this);
1016 typedef typename PoolT::iterator IterT;
1017 for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);
1021 tree.topologyUnion(mask);
1028 for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1037 typedef LeafT* value_type;
1039 MyArray(value_type* array) : ptr(array) {}
1040 void push_back(value_type leaf) { *ptr++ = leaf; }
1044 size_t linearize(MaskT& mask,
TilePolicy mode)
1047 const size_t numLeafs = mask.leafCount();
1048 mLeafs =
new LeafT*[numLeafs];
1049 MyArray tmp(mLeafs);
1050 mask.stealNodes(tmp);
1054 template <
typename T>
1055 typename boost::enable_if<boost::is_same<T,MaskT>,
size_t>::type init(T& tree,
TilePolicy mode)
1057 return this->linearize(tree, mode);
1060 template <
typename T>
1061 typename boost::disable_if<boost::is_same<T,MaskT>,
size_t>::type init(
const T& tree,
TilePolicy mode)
1064 return this->linearize(mask, mode);
1069 template<
typename TreeType>
1076 template<
typename TreeType>
1083 if (iterations > 0 ) {
1093 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or NULL if no such node exists...
Definition: ValueAccessor.h:424
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:378
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:323
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:115
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:47
Defined various multi-threaded utility functions for trees.
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
#define OPENVDB_VERSION_NAME
Definition: version.h:43
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:898
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition: Coord.h:111
Definition: Exceptions.h:39
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:263
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
Definition: Exceptions.h:84
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:354
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:561
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:338