46 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
47 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
49 #include <openvdb/Types.h>
50 #include <openvdb/Grid.h>
51 #include <openvdb/math/Math.h>
52 #include <openvdb/tree/TreeIterator.h>
53 #include <openvdb/tree/ValueAccessor.h>
54 #include <openvdb/tree/LeafManager.h>
55 #include <boost/scoped_array.hpp>
56 #include <boost/bind.hpp>
139 template<
typename Gr
idOrTree>
142 const typename GridOrTree::ValueType& value,
143 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
149 template<
typename Gr
idOrTree>
152 const typename GridOrTree::ValueType& value,
153 const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
171 template<
typename TreeType>
178 mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
180 mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
184 void dilateVoxels6();
186 void dilateVoxels18();
188 void dilateVoxels26();
216 static const int LEAF_DIM = LeafType::DIM;
217 static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
225 inline void clear() { leaf = NULL; init =
true; }
226 template<
int DX,
int DY,
int DZ>
227 void scatter(AccessorType& acc,
const Coord &xyz,
int indx, Word mask)
231 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
235 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
238 const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
239 if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
242 template<
int DX,
int DY,
int DZ>
243 Word
gather(AccessorType& acc,
const Coord &xyz,
int indx)
247 Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
249 isOn = leaf ?
false : acc.
isValueOn(orig);
251 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
254 const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
255 return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
256 : isOn ? ~Word(0) : Word(0);
262 LeafCache(
size_t n, TreeType& tree) : size(n), leafs(new LeafType*[n]), acc(tree)
264 onTile.setValuesOn();
269 inline void clear() {
for (
size_t i=0; i<size; ++i) leafs[i]=NULL; }
270 inline void setOrigin(
const Coord& xyz) { origin = &xyz; }
274 leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
276 template<
int DX,
int DY,
int DZ>
280 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
281 leafs[n] = acc.probeLeaf(xyz);
282 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
284 this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
289 return leafs[n]->getValueMask().template getWord<Word>(indx);
291 template<
int DX,
int DY,
int DZ>
295 const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
296 leafs[n] = acc.probeLeaf(xyz);
297 if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
299 return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
302 void scatterFacesXY(
int x,
int y,
int i1,
int n,
int i2);
305 void scatterEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
307 Word gatherFacesXY(
int x,
int y,
int i1,
int n,
int i2);
309 Word gatherEdgesXY(
int x,
int y,
int i1,
int n,
int i2);
320 typedef tbb::blocked_range<size_t>
RangeT;
322 : mTask(0), mSavedMasks(masks) , mManager(manager) {}
324 void operator()(
const RangeT& r)
const {mTask(const_cast<ErodeVoxelsOp*>(
this), r);}
325 void erode6(
const RangeT&)
const;
326 void erode18(
const RangeT&)
const;
327 void erode26(
const RangeT&)
const;
329 typedef typename boost::function<void (ErodeVoxelsOp*, const RangeT&)> FuncT;
331 std::vector<MaskType>& mSavedMasks;
332 ManagerType& mManager;
337 : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
339 void save() { mSaveMasks =
true; tbb::parallel_for(mManager.
getRange(), *
this); }
340 void update() { mSaveMasks =
false; tbb::parallel_for(mManager.
getRange(), *
this); }
341 void operator()(
const tbb::blocked_range<size_t>& range)
const
344 for (
size_t i = range.begin(); i < range.end(); ++i) {
345 mMasks[i] = mManager.
leaf(i).getValueMask();
348 for (
size_t i = range.begin(); i < range.end(); ++i) {
349 mManager.
leaf(i).setValueMask(mMasks[i]);
354 std::vector<MaskType>& mMasks;
355 ManagerType& mManager;
360 UpdateMasks(
const std::vector<MaskType>& masks, ManagerType& manager)
361 : mMasks(masks), mManager(manager) {}
364 for (
size_t i=r.begin(); i<r.end(); ++i) mManager.
leaf(i).setValueMask(mMasks[i]);
370 CopyMasks(std::vector<MaskType>& masks,
const ManagerType& manager)
371 : mMasks(masks), mManager(manager) {}
374 for (
size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.
leaf(i).getValueMask();
382 template<
typename TreeType>
386 for (
int i=0; i<iterations; ++i) {
390 default: this->dilateVoxels6();
395 template<
typename TreeType>
400 const int leafCount =
static_cast<int>(mManager->leafCount());
403 std::vector<MaskType> savedMasks(leafCount);
404 this->copyMasks(savedMasks, *mManager);
406 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
407 const MaskType& oldMask = savedMasks[leafIdx];
408 cache[0] = &mManager->leaf(leafIdx);
410 for (
int x = 0; x < LEAF_DIM; ++x ) {
411 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
413 if (
const Word w = oldMask.template getWord<Word>(n)) {
416 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
419 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
420 cache.template scatter< 0, 0,-1>(1, n);
423 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
424 cache.template scatter< 0, 0, 1>(2, n);
427 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
434 mManager->rebuildLeafArray();
437 template<
typename TreeType>
442 const int leafCount =
static_cast<int>(mManager->leafCount());
445 std::vector<MaskType> savedMasks(leafCount);
446 this->copyMasks(savedMasks, *mManager);
448 Coord orig_mz, orig_pz;
449 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
450 const MaskType& oldMask = savedMasks[leafIdx];
451 cache[0] = &mManager->leaf(leafIdx);
452 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
453 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
454 for (
int x = 0; x < LEAF_DIM; ++x ) {
455 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
456 if (
const Word w = oldMask.template getWord<Word>(n)) {
458 cache.mask =
Word(w | (w>>1) | (w<<1));
459 cache.setOrigin(cache[0]->origin());
461 cache.scatterFacesXY(x, y, 0, n, 3);
463 cache.scatterEdgesXY(x, y, 0, n, 3);
465 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
466 cache.setOrigin(cache[0]->origin());
467 cache.template scatter< 0, 0,-1>(1, n);
468 cache.setOrigin(orig_mz);
469 cache.scatterFacesXY(x, y, 1, n, 11);
471 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
472 cache.setOrigin(cache[0]->origin());
473 cache.template scatter< 0, 0, 1>(2, n);
474 cache.setOrigin(orig_pz);
475 cache.scatterFacesXY(x, y, 2, n, 15);
483 mManager->rebuildLeafArray();
486 template<
typename TreeType>
491 const int leafCount =
static_cast<int>(mManager->leafCount());
494 std::vector<MaskType> savedMasks(leafCount);
495 this->copyMasks(savedMasks, *mManager);
497 Coord orig_mz, orig_pz;
498 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
499 const MaskType& oldMask = savedMasks[leafIdx];
500 cache[0] = &mManager->leaf(leafIdx);
501 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
502 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
503 for (
int x = 0; x < LEAF_DIM; ++x ) {
504 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
505 if (
const Word w = oldMask.template getWord<Word>(n)) {
507 cache.mask =
Word(w | (w>>1) | (w<<1));
508 cache.setOrigin(cache[0]->origin());
510 cache.scatterFacesXY(x, y, 0, n, 3);
511 cache.scatterEdgesXY(x, y, 0, n, 3);
513 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
514 cache.setOrigin(cache[0]->origin());
515 cache.template scatter< 0, 0,-1>(1, n);
516 cache.setOrigin(orig_mz);
517 cache.scatterFacesXY(x, y, 1, n, 11);
518 cache.scatterEdgesXY(x, y, 1, n, 11);
520 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
521 cache.setOrigin(cache[0]->origin());
522 cache.template scatter< 0, 0, 1>(2, n);
523 cache.setOrigin(orig_pz);
524 cache.scatterFacesXY(x, y, 2, n, 19);
525 cache.scatterEdgesXY(x, y, 2, n, 19);
533 mManager->rebuildLeafArray();
536 template<
typename TreeType>
542 this->scatter(i1, n-LEAF_DIM);
544 this->
template scatter<-1, 0, 0>(i2, n);
547 if (x < LEAF_DIM-1) {
548 this->scatter(i1, n+LEAF_DIM);
550 this->
template scatter< 1, 0, 0>(i2+1, n);
554 this->scatter(i1, n-1);
556 this->
template scatter< 0,-1, 0>(i2+2, n);
559 if (y < LEAF_DIM-1) {
560 this->scatter(i1, n+1);
562 this->
template scatter< 0, 1, 0>(i2+3, n);
566 template<
typename TreeType>
573 this->scatter(i1, n-LEAF_DIM-1);
575 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
577 if (y < LEAF_DIM-1) {
578 this->scatter(i1, n-LEAF_DIM+1);
580 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
583 if (y < LEAF_DIM-1) {
584 this->
template scatter<-1, 0, 0>(i2 , n+1);
586 this->
template scatter<-1, 1, 0>(i2+7, n );
589 this->
template scatter<-1, 0, 0>(i2 , n-1);
591 this->
template scatter<-1,-1, 0>(i2+4, n );
594 if (x < LEAF_DIM-1) {
596 this->scatter(i1, n+LEAF_DIM-1);
598 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
600 if (y < LEAF_DIM-1) {
601 this->scatter(i1, n+LEAF_DIM+1);
603 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
607 this->
template scatter< 1, 0, 0>(i2+1, n-1);
609 this->
template scatter< 1,-1, 0>(i2+6, n );
611 if (y < LEAF_DIM-1) {
612 this->
template scatter< 1, 0, 0>(i2+1, n+1);
614 this->
template scatter< 1, 1, 0>(i2+5, n );
619 template<
typename TreeType>
626 mTask = boost::bind(&ErodeVoxelsOp::erode18, _1, _2);
629 mTask = boost::bind(&ErodeVoxelsOp::erode26, _1, _2);
632 mTask = boost::bind(&ErodeVoxelsOp::erode6, _1, _2);
634 tbb::parallel_for(mManager.getRange(), *
this);
637 template<
typename TreeType>
643 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
646 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
649 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
652 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
657 template<
typename TreeType>
666 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
667 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
668 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
669 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
671 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
672 this->
template gather<-1, 1, 0>(i2+7, n );
673 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
674 this->
template gather<-1,-1, 0>(i2+4, n );
676 if (x < LEAF_DIM-1) {
677 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
678 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
679 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
680 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
682 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
683 this->
template gather< 1,-1, 0>(i2+6, n );
684 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
685 this->
template gather< 1, 1, 0>(i2+5, n );
691 template <
typename TreeType>
697 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
698 cache[0] = &mManager.leaf(leafIdx);
699 if (cache[0]->isEmpty())
continue;
701 MaskType& newMask = mSavedMasks[leafIdx];
702 for (
int x = 0; x < LEAF_DIM; ++x ) {
703 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
705 if (
Word& w = newMask.template getWord<Word>(n)) {
709 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
710 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
712 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
720 template <
typename TreeType>
728 template <
typename TreeType>
737 template<
typename TreeType>
742 const size_t leafCount = mManager->leafCount();
745 std::vector<MaskType> savedMasks(leafCount);
746 this->copyMasks(savedMasks, *mManager);
750 for (
int i = 0; i < mSteps; ++i) {
762 template<
typename TreeType>
766 if (iterations > 0 ) {
772 template<
typename TreeType>
776 if (iterations > 0 ) {
782 template<
typename TreeType>
786 if (iterations > 0 ) {
792 template<
typename TreeType>
796 if (iterations > 0 ) {
806 namespace activation {
808 template<
typename TreeType>
812 typedef typename TreeType::ValueType
ValueT;
820 void operator()(
const typename TreeType::ValueOnIter& it)
const
827 void operator()(
const typename TreeType::ValueOffIter& it)
const
830 it.setActiveState(
true);
834 void operator()(
const typename TreeType::LeafIter& lit)
const
836 typedef typename TreeType::LeafNodeType LeafT;
839 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
841 leaf.setValueOn(it.pos());
845 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
847 leaf.setValueOff(it.pos());
855 const ValueT mValue, mTolerance;
861 template<
typename Gr
idOrTree>
863 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
864 const typename GridOrTree::ValueType& tolerance)
867 typedef typename Adapter::TreeType TreeType;
869 TreeType& tree = Adapter::tree(gridOrTree);
874 foreach(tree.beginLeaf(), op);
878 typename TreeType::ValueOffIter it = tree.beginValueOff();
879 it.setMaxDepth(tree.treeDepth() - 2);
880 foreach(it, op,
false);
884 template<
typename Gr
idOrTree>
886 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
887 const typename GridOrTree::ValueType& tolerance)
890 typedef typename Adapter::TreeType TreeType;
892 TreeType& tree = Adapter::tree(gridOrTree);
897 foreach(tree.beginLeaf(), op);
901 typename TreeType::ValueOnIter it = tree.beginValueOn();
902 it.setMaxDepth(tree.treeDepth() - 2);
903 foreach(it, op,
false);
910 #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:378
#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:109
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:342
Defined various multi-threaded utility functions for trees.
Definition: Exceptions.h:86
#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:217
Definition: Exceptions.h:39
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
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:347
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:858
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318