46 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
47 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
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();
383 template<
typename TreeType>
387 for (
int i=0; i<iterations; ++i) {
391 default: this->dilateVoxels6();
397 template<
typename TreeType>
402 const int leafCount =
static_cast<int>(mManager->leafCount());
405 std::vector<MaskType> savedMasks(leafCount);
406 this->copyMasks(savedMasks, *mManager);
408 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
409 const MaskType& oldMask = savedMasks[leafIdx];
410 cache[0] = &mManager->leaf(leafIdx);
412 for (
int x = 0; x < LEAF_DIM; ++x ) {
413 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
415 if (
const Word w = oldMask.template getWord<Word>(n)) {
418 cache.mask =
Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
421 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
422 cache.template scatter< 0, 0,-1>(1, n);
425 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
426 cache.template scatter< 0, 0, 1>(2, n);
429 cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
436 mManager->rebuildLeafArray();
440 template<
typename TreeType>
445 const int leafCount =
static_cast<int>(mManager->leafCount());
448 std::vector<MaskType> savedMasks(leafCount);
449 this->copyMasks(savedMasks, *mManager);
451 Coord orig_mz, orig_pz;
452 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
453 const MaskType& oldMask = savedMasks[leafIdx];
454 cache[0] = &mManager->leaf(leafIdx);
455 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
456 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
457 for (
int x = 0; x < LEAF_DIM; ++x ) {
458 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
459 if (
const Word w = oldMask.template getWord<Word>(n)) {
461 cache.mask =
Word(w | (w>>1) | (w<<1));
462 cache.setOrigin(cache[0]->origin());
464 cache.scatterFacesXY(x, y, 0, n, 3);
466 cache.scatterEdgesXY(x, y, 0, n, 3);
468 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
469 cache.setOrigin(cache[0]->origin());
470 cache.template scatter< 0, 0,-1>(1, n);
471 cache.setOrigin(orig_mz);
472 cache.scatterFacesXY(x, y, 1, n, 11);
474 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
475 cache.setOrigin(cache[0]->origin());
476 cache.template scatter< 0, 0, 1>(2, n);
477 cache.setOrigin(orig_pz);
478 cache.scatterFacesXY(x, y, 2, n, 15);
486 mManager->rebuildLeafArray();
490 template<
typename TreeType>
495 const int leafCount =
static_cast<int>(mManager->leafCount());
498 std::vector<MaskType> savedMasks(leafCount);
499 this->copyMasks(savedMasks, *mManager);
501 Coord orig_mz, orig_pz;
502 for (
int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
503 const MaskType& oldMask = savedMasks[leafIdx];
504 cache[0] = &mManager->leaf(leafIdx);
505 orig_mz = cache[0]->
origin().offsetBy(0, 0, -LEAF_DIM);
506 orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
507 for (
int x = 0; x < LEAF_DIM; ++x ) {
508 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
509 if (
const Word w = oldMask.template getWord<Word>(n)) {
511 cache.mask =
Word(w | (w>>1) | (w<<1));
512 cache.setOrigin(cache[0]->origin());
514 cache.scatterFacesXY(x, y, 0, n, 3);
515 cache.scatterEdgesXY(x, y, 0, n, 3);
517 if ( (cache.mask =
Word(w<<(LEAF_DIM-1))) ) {
518 cache.setOrigin(cache[0]->origin());
519 cache.template scatter< 0, 0,-1>(1, n);
520 cache.setOrigin(orig_mz);
521 cache.scatterFacesXY(x, y, 1, n, 11);
522 cache.scatterEdgesXY(x, y, 1, n, 11);
524 if ( (cache.mask =
Word(w>>(LEAF_DIM-1))) ) {
525 cache.setOrigin(cache[0]->origin());
526 cache.template scatter< 0, 0, 1>(2, n);
527 cache.setOrigin(orig_pz);
528 cache.scatterFacesXY(x, y, 2, n, 19);
529 cache.scatterEdgesXY(x, y, 2, n, 19);
537 mManager->rebuildLeafArray();
541 template<
typename TreeType>
547 this->scatter(i1, n-LEAF_DIM);
549 this->
template scatter<-1, 0, 0>(i2, n);
552 if (x < LEAF_DIM-1) {
553 this->scatter(i1, n+LEAF_DIM);
555 this->
template scatter< 1, 0, 0>(i2+1, n);
559 this->scatter(i1, n-1);
561 this->
template scatter< 0,-1, 0>(i2+2, n);
564 if (y < LEAF_DIM-1) {
565 this->scatter(i1, n+1);
567 this->
template scatter< 0, 1, 0>(i2+3, n);
572 template<
typename TreeType>
578 this->scatter(i1, n-LEAF_DIM-1);
580 this->
template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
582 if (y < LEAF_DIM-1) {
583 this->scatter(i1, n-LEAF_DIM+1);
585 this->
template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
588 if (y < LEAF_DIM-1) {
589 this->
template scatter<-1, 0, 0>(i2 , n+1);
591 this->
template scatter<-1, 1, 0>(i2+7, n );
594 this->
template scatter<-1, 0, 0>(i2 , n-1);
596 this->
template scatter<-1,-1, 0>(i2+4, n );
599 if (x < LEAF_DIM-1) {
601 this->scatter(i1, n+LEAF_DIM-1);
603 this->
template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
605 if (y < LEAF_DIM-1) {
606 this->scatter(i1, n+LEAF_DIM+1);
608 this->
template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
612 this->
template scatter< 1, 0, 0>(i2+1, n-1);
614 this->
template scatter< 1,-1, 0>(i2+6, n );
616 if (y < LEAF_DIM-1) {
617 this->
template scatter< 1, 0, 0>(i2+1, n+1);
619 this->
template scatter< 1, 1, 0>(i2+5, n );
625 template<
typename TreeType>
631 mTask = boost::bind(&ErodeVoxelsOp::erode18, _1, _2);
634 mTask = boost::bind(&ErodeVoxelsOp::erode26, _1, _2);
637 mTask = boost::bind(&ErodeVoxelsOp::erode6, _1, _2);
639 tbb::parallel_for(mManager.getRange(), *
this);
643 template<
typename TreeType>
648 Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->
template gather<-1,0,0>(i2, n);
651 w =
Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->
template gather<1,0,0>(i2+1,n)));
654 w =
Word(w & (y>0 ? this->gather(i1, n-1) : this->
template gather<0,-1,0>(i2+2, n)));
657 w =
Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->
template gather<0,1,0>(i2+3, n)));
663 template<
typename TreeType>
670 w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
671 this->
template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
672 w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
673 this->
template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
675 w &= y < LEAF_DIM-1 ? this->
template gather<-1, 0, 0>(i2 , n+1):
676 this->
template gather<-1, 1, 0>(i2+7, n );
677 w &= y > 0 ? this->
template gather<-1, 0, 0>(i2 , n-1):
678 this->
template gather<-1,-1, 0>(i2+4, n );
680 if (x < LEAF_DIM-1) {
681 w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
682 this->
template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
683 w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
684 this->
template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
686 w &= y > 0 ? this->
template gather< 1, 0, 0>(i2+1, n-1):
687 this->
template gather< 1,-1, 0>(i2+6, n );
688 w &= y < LEAF_DIM-1 ? this->
template gather< 1, 0, 0>(i2+1, n+1):
689 this->
template gather< 1, 1, 0>(i2+5, n );
696 template <
typename TreeType>
701 for (
size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
702 cache[0] = &mManager.leaf(leafIdx);
703 if (cache[0]->isEmpty())
continue;
705 MaskType& newMask = mSavedMasks[leafIdx];
706 for (
int x = 0; x < LEAF_DIM; ++x ) {
707 for (
int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
709 if (
Word& w = newMask.template getWord<Word>(n)) {
713 (
Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
714 Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
716 w =
Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
725 template <
typename TreeType>
733 template <
typename TreeType>
741 template<
typename TreeType>
746 const size_t leafCount = mManager->leafCount();
749 std::vector<MaskType> savedMasks(leafCount);
750 this->copyMasks(savedMasks, *mManager);
754 for (
int i = 0; i < mSteps; ++i) {
766 template<
typename TreeType>
770 if (iterations > 0 ) {
776 template<
typename TreeType>
780 if (iterations > 0 ) {
786 template<
typename TreeType>
790 if (iterations > 0 ) {
796 template<
typename TreeType>
800 if (iterations > 0 ) {
810 namespace activation {
812 template<
typename TreeType>
816 typedef typename TreeType::ValueType
ValueT;
824 void operator()(
const typename TreeType::ValueOnIter& it)
const
831 void operator()(
const typename TreeType::ValueOffIter& it)
const
834 it.setActiveState(
true);
838 void operator()(
const typename TreeType::LeafIter& lit)
const
840 typedef typename TreeType::LeafNodeType LeafT;
843 for (
typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
845 leaf.setValueOn(it.pos());
849 for (
typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
851 leaf.setValueOff(it.pos());
859 const ValueT mValue, mTolerance;
865 template<
typename Gr
idOrTree>
867 activate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
868 const typename GridOrTree::ValueType& tolerance)
871 typedef typename Adapter::TreeType TreeType;
873 TreeType& tree = Adapter::tree(gridOrTree);
878 foreach(tree.beginLeaf(), op);
882 typename TreeType::ValueOffIter it = tree.beginValueOff();
883 it.setMaxDepth(tree.treeDepth() - 2);
884 foreach(it, op,
false);
888 template<
typename Gr
idOrTree>
890 deactivate(GridOrTree& gridOrTree,
const typename GridOrTree::ValueType& value,
891 const typename GridOrTree::ValueType& tolerance)
894 typedef typename Adapter::TreeType TreeType;
896 TreeType& tree = Adapter::tree(gridOrTree);
901 foreach(tree.beginLeaf(), op);
905 typename TreeType::ValueOnIter it = tree.beginValueOn();
906 it.setMaxDepth(tree.treeDepth() - 2);
907 foreach(it, op,
false);
914 #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
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
#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:114
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
Defined various multi-threaded utility functions for trees.
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:323
#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
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:880
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
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:347
#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...