19 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 20 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED 30 #include <tbb/tbb_thread.h> 31 #include <tbb/task_scheduler_init.h> 32 #include <tbb/enumerable_thread_specific.h> 33 #include <tbb/parallel_for.h> 35 #include <type_traits> 92 template<
typename TreeType>
122 template<
typename TreeType>
141 template<
typename TreeType>
160 template<
typename TreeType>
167 template<
typename TreeType>
177 template<
typename TreeType>
186 template<
typename Gr
idOrTree>
189 const typename GridOrTree::ValueType& value,
190 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
196 template<
typename Gr
idOrTree>
199 const typename GridOrTree::ValueType& value,
200 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
218 template<
typename TreeType>
225 mOwnsManager(true), mManager(new
ManagerType(tree)), mAcc(tree), mSteps(1) {}
227 mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
231 void dilateVoxels6();
233 void dilateVoxels18();
235 void dilateVoxels26();
263 static const int LEAF_DIM = LeafType::DIM;
264 static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
272 inline void clear() { leaf =
nullptr; init =
true; }
273 template<
int DX,
int DY,
int DZ>
278 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
282 static const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
283 if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
286 template<
int DX,
int DY,
int DZ>
291 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
293 isOn = leaf ?
false : acc.
isValueOn(orig);
295 static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
296 return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
305 onTile.setValuesOn();
310 inline void clear() {
for (
size_t i = 0; i < size; ++i) leafs[i] =
nullptr; }
311 inline void setOrigin(
const Coord& xyz) { origin = &xyz; }
315 leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
317 template<
int DX,
int DY,
int DZ>
321 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
322 leafs[n] = acc.probeLeaf(xyz);
323 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
325 this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
330 return leafs[n]->getValueMask().template getWord<Word>(indx);
332 template<
int DX,
int DY,
int DZ>
336 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
337 leafs[n] = acc.probeLeaf(xyz);
338 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
340 return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
343 void scatterFacesXY(
int x,
int y,
int i1,
int n,
int i2);
346 void scatterEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
348 Word gatherFacesXY(
int x,
int y,
int i1,
int n,
int i2);
350 Word gatherEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
361 using RangeT = tbb::blocked_range<size_t>;
363 : mTask(nullptr), mSavedMasks(masks) , mManager(manager) {}
366 void erode6(
const RangeT&)
const;
367 void erode18(
const RangeT&)
const;
368 void erode26(
const RangeT&)
const;
370 using FuncT =
typename std::function<void (ErodeVoxelsOp*, const RangeT&)>;
372 std::vector<MaskType>& mSavedMasks;
378 : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
380 void save() { mSaveMasks =
true; tbb::parallel_for(mManager.
getRange(), *
this); }
381 void update() { mSaveMasks =
false; tbb::parallel_for(mManager.
getRange(), *
this); }
382 void operator()(
const tbb::blocked_range<size_t>& range)
const 385 for (
size_t i = range.begin(); i < range.end(); ++i) {
386 mMasks[i] = mManager.
leaf(i).getValueMask();
389 for (
size_t i = range.begin(); i < range.end(); ++i) {
390 mManager.
leaf(i).setValueMask(mMasks[i]);
395 std::vector<MaskType>& mMasks;
402 : mMasks(masks), mManager(manager) {}
405 for (
size_t i=r.begin(); i<r.end(); ++i) mManager.
leaf(i).setValueMask(mMasks[i]);
412 : mMasks(masks), mManager(manager) {}
415 for (
size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.
leaf(i).getValueMask();
424 template<
typename TreeType>
428 for (
int i=0; i<iterations; ++i) {
431 this->dilateVoxels18();
434 this->dilateVoxels26();
438 this->dilateVoxels6();
444 template<
typename TreeType>
449 const int leafCount =
static_cast<int>(mManager->leafCount());
452 std::vector<MaskType> savedMasks(leafCount);
453 this->copyMasks(savedMasks, *mManager);
455 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
456 const MaskType& oldMask = savedMasks[leafIdx];
457 cache[0] = &mManager->leaf(leafIdx);
459 for (
int x = 0; x < LEAF_DIM; ++x ) {
460 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
462 if (
const Word w = oldMask.template getWord<Word>(n)) {
465 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
468 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
469 cache.template scatter< 0, 0,-1>(1, n);
472 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
473 cache.template scatter< 0, 0, 1>(2, n);
476 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
483 mManager->rebuildLeafArray();
487 template<
typename TreeType>
492 const int leafCount =
static_cast<int>(mManager->leafCount());
495 std::vector<MaskType> savedMasks(leafCount);
496 this->copyMasks(savedMasks, *mManager);
498 Coord orig_mz, orig_pz;
499 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
500 const MaskType& oldMask = savedMasks[leafIdx];
501 cache[0] = &mManager->leaf(leafIdx);
502 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
503 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
504 for (
int x = 0; x < LEAF_DIM; ++x ) {
505 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
506 if (
const Word w = oldMask.template getWord<Word>(n)) {
508 cache.mask =
Word(w | (w>>1) | (w<<1));
509 cache.setOrigin(cache[0]->origin());
511 cache.scatterFacesXY(x, y, 0, n, 3);
513 cache.scatterEdgesXY(x, y, 0, n, 3);
515 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
516 cache.setOrigin(cache[0]->origin());
517 cache.template scatter< 0, 0,-1>(1, n);
518 cache.setOrigin(orig_mz);
519 cache.scatterFacesXY(x, y, 1, n, 11);
521 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
522 cache.setOrigin(cache[0]->origin());
523 cache.template scatter< 0, 0, 1>(2, n);
524 cache.setOrigin(orig_pz);
525 cache.scatterFacesXY(x, y, 2, n, 15);
533 mManager->rebuildLeafArray();
537 template<
typename TreeType>
541 const int leafCount =
static_cast<int>(mManager->leafCount());
544 std::vector<MaskType> savedMasks(leafCount);
545 this->copyMasks(savedMasks, *mManager);
547 Coord orig_mz, orig_pz;
548 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
549 const MaskType& oldMask = savedMasks[leafIdx];
550 cache[0] = &mManager->leaf(leafIdx);
551 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
552 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
553 for (
int x = 0; x < LEAF_DIM; ++x ) {
554 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
555 if (
const Word w = oldMask.template getWord<Word>(n)) {
557 cache.mask =
Word(w | (w>>1) | (w<<1));
558 cache.setOrigin(cache[0]->origin());
560 cache.scatterFacesXY(x, y, 0, n, 3);
561 cache.scatterEdgesXY(x, y, 0, n, 3);
563 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
564 cache.setOrigin(cache[0]->origin());
565 cache.template scatter< 0, 0,-1>(1, n);
566 cache.setOrigin(orig_mz);
567 cache.scatterFacesXY(x, y, 1, n, 11);
568 cache.scatterEdgesXY(x, y, 1, n, 11);
570 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
571 cache.setOrigin(cache[0]->origin());
572 cache.template scatter< 0, 0, 1>(2, n);
573 cache.setOrigin(orig_pz);
574 cache.scatterFacesXY(x, y, 2, n, 19);
575 cache.scatterEdgesXY(x, y, 2, n, 19);
583 mManager->rebuildLeafArray();
587 template<
typename TreeType>
593 this->scatter(i1, n-LEAF_DIM);
595 this->
template scatter<-1, 0, 0>(i2, n);
598 if (x < LEAF_DIM-1) {
599 this->scatter(i1, n+LEAF_DIM);
601 this->
template scatter< 1, 0, 0>(i2+1, n);
605 this->scatter(i1, n-1);
607 this->
template scatter< 0,-1, 0>(i2+2, n);
610 if (y < LEAF_DIM-1) {
611 this->scatter(i1, n+1);
613 this->
template scatter< 0, 1, 0>(i2+3, n);
618 template<
typename TreeType>
624 this->scatter(i1, n-LEAF_DIM-1);
626 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
628 if (y < LEAF_DIM-1) {
629 this->scatter(i1, n-LEAF_DIM+1);
631 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
634 if (y < LEAF_DIM-1) {
635 this->
template scatter<-1, 0, 0>(i2 , n+1);
637 this->
template scatter<-1, 1, 0>(i2+7, n );
640 this->
template scatter<-1, 0, 0>(i2 , n-1);
642 this->
template scatter<-1,-1, 0>(i2+4, n );
645 if (x < LEAF_DIM-1) {
647 this->scatter(i1, n+LEAF_DIM-1);
649 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
651 if (y < LEAF_DIM-1) {
652 this->scatter(i1, n+LEAF_DIM+1);
654 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
658 this->
template scatter< 1, 0, 0>(i2+1, n-1);
660 this->
template scatter< 1,-1, 0>(i2+6, n );
662 if (y < LEAF_DIM-1) {
663 this->
template scatter< 1, 0, 0>(i2+1, n+1);
665 this->
template scatter< 1, 1, 0>(i2+5, n );
671 template<
typename TreeType>
675 namespace ph = std::placeholders;
678 mTask = std::bind(&ErodeVoxelsOp::erode18, ph::_1, ph::_2);
681 mTask = std::bind(&ErodeVoxelsOp::erode26, ph::_1, ph::_2);
685 mTask = std::bind(&ErodeVoxelsOp::erode6, ph::_1, ph::_2);
687 tbb::parallel_for(mManager.getRange(), *
this);
691 template<
typename TreeType>
696 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
699 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
702 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
705 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
711 template<
typename TreeType>
718 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
719 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
720 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
721 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
723 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
724 this->
template gather<-1, 1, 0>(i2+7, n );
725 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
726 this->
template gather<-1,-1, 0>(i2+4, n );
728 if (x < LEAF_DIM-1) {
729 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
730 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
731 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
732 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
734 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
735 this->
template gather< 1,-1, 0>(i2+6, n );
736 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
737 this->
template gather< 1, 1, 0>(i2+5, n );
744 template <
typename TreeType>
749 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
750 cache[0] = &mManager.leaf(leafIdx);
751 if (cache[0]->isEmpty())
continue;
753 MaskType& newMask = mSavedMasks[leafIdx];
754 for (
int x = 0; x < LEAF_DIM; ++x ) {
755 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
757 if (
Word& w = newMask.template getWord<Word>(n)) {
761 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
762 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
764 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
773 template <
typename TreeType>
781 template <
typename TreeType>
789 template<
typename TreeType>
794 const size_t leafCount = mManager->leafCount();
797 std::vector<MaskType> savedMasks(leafCount);
798 this->copyMasks(savedMasks, *mManager);
802 for (
int i = 0; i < mSteps; ++i) {
814 template<
typename TreeType>
818 if (iterations > 0 ) {
824 template<
typename TreeType>
828 if (iterations > 0 ) {
834 template<
typename TreeType>
838 if (iterations > 0 ) {
844 template<
typename TreeType>
848 if (iterations > 0 ) {
858 namespace activation {
860 template<
typename TreeType>
864 using ValueT =
typename TreeType::ValueType;
872 void operator()(
const typename TreeType::ValueOnIter& it)
const 879 void operator()(
const typename TreeType::ValueOffIter& it)
const 882 it.setActiveState(
true);
886 void operator()(
const typename TreeType::LeafIter& lit)
const 888 using LeafT =
typename TreeType::LeafNodeType;
891 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
893 leaf.setValueOn(it.pos());
897 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
899 leaf.setValueOff(it.pos());
907 const ValueT mValue, mTolerance;
913 template<
typename Gr
idOrTree>
915 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
916 const typename GridOrTree::ValueType& tolerance)
919 using TreeType =
typename Adapter::TreeType;
921 TreeType& tree = Adapter::tree(gridOrTree);
926 foreach(tree.beginLeaf(), op);
930 typename TreeType::ValueOffIter it = tree.beginValueOff();
931 it.setMaxDepth(tree.treeDepth() - 2);
932 foreach(it, op,
false);
936 template<
typename Gr
idOrTree>
938 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
939 const typename GridOrTree::ValueType& tolerance)
942 using TreeType =
typename Adapter::TreeType;
944 TreeType& tree = Adapter::tree(gridOrTree);
949 foreach(tree.beginLeaf(), op);
953 typename TreeType::ValueOnIter it = tree.beginValueOn();
954 it.setMaxDepth(tree.treeDepth() - 2);
955 foreach(it, op,
false);
960 template<
typename TreeT>
963 using MaskT =
typename TreeT::template ValueConverter<ValueMask>::Type;
964 using PoolT = tbb::enumerable_thread_specific<MaskT>;
965 using LeafT =
typename MaskT::LeafNodeType;
976 : mIter(iterations), mNN(nn), mPool(nullptr), mLeafs(nullptr)
978 const size_t numLeafs = this->init( tree, mode );
979 const size_t numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
980 const size_t grainSize =
math::Max(
size_t(1), numLeafs/(2*numThreads));
986 tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *
this);
990 using IterT =
typename PoolT::iterator;
991 for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);
995 tree.topologyUnion(mask);
1002 for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1011 using value_type = LeafT*;
1013 MyArray(value_type* array) : ptr(array) {}
1014 void push_back(value_type leaf) { *ptr++ = leaf; }
1021 const size_t numLeafs = mask.leafCount();
1022 mLeafs =
new LeafT*[numLeafs];
1023 MyArray tmp(mLeafs);
1024 mask.stealNodes(tmp);
1028 template<
typename T>
1029 typename std::enable_if<std::is_same<T, MaskT>::value,
size_t>::type
1035 template<
typename T>
1036 typename std::enable_if<!std::is_same<T, MaskT>::value,
size_t>::type
1045 template<
typename TreeType>
1052 template<
typename TreeType>
1059 if (iterations > 0 ) {
1069 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1077
#define OPENVDB_THROW(exception, message)
Definition: openvdb/Exceptions.h:74
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
bool isApproxEqual(const Type &a, const Type &b, const Type &tolerance)
Return true if a is equal to b to within the given tolerance.
Definition: Math.h:407
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:348
Definition: openvdb/Types.h:367
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: openvdb/Types.h:542
Defined various multi-threaded utility functions for trees.
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:302
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:101
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:379
Definition: openvdb/Exceptions.h:13
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:598
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:226
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
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:84
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
void rebuildLeafArray(bool serial=false)
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:275
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:153
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
void linearize(const ast::Node &node, std::vector< const ast::Node * > &list)
Flatten the provided AST branch into a linear list using post order traversal.
Definition: openvdb/Exceptions.h:61