OpenVDB  7.0.0
Morphology.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
18 
19 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
20 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
21 
22 #include <openvdb/Types.h>
23 #include <openvdb/Grid.h>
24 #include <openvdb/math/Math.h> // for isApproxEqual()
28 #include "Prune.h"// for pruneLevelSet
29 #include "ValueTransformer.h" // for foreach()
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>
34 #include <functional>
35 #include <type_traits>
36 #include <vector>
37 
38 
39 namespace openvdb {
41 namespace OPENVDB_VERSION_NAME {
42 namespace tools {
43 
61 
76 
92 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
93 inline void dilateActiveValues(TreeType& tree,
94  int iterations = 1,
96  TilePolicy mode = PRESERVE_TILES);
97 
122 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
124  int iterations = 1,
126  TilePolicy mode = PRESERVE_TILES);
127 
128 
141 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
142 inline void dilateVoxels(TreeType& tree,
143  int iterations = 1,
145 
160 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
161 inline void dilateVoxels(tree::LeafManager<TreeType>& manager,
162  int iterations = 1,
164 
165 
167 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
173 inline void erodeVoxels(TreeType& tree,
174  int iterations=1,
176 
177 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
178 inline void erodeVoxels(tree::LeafManager<TreeType>& manager,
179  int iterations = 1,
182 
183 
186 template<typename GridOrTree>
187 inline void activate(
188  GridOrTree&,
189  const typename GridOrTree::ValueType& value,
190  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
191 );
192 
193 
196 template<typename GridOrTree>
197 inline void deactivate(
198  GridOrTree&,
199  const typename GridOrTree::ValueType& value,
200  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
201 );
202 
203 
205 
206 
208 template<Index Log2Dim> struct DimToWord {};
209 template<> struct DimToWord<3> { using Type = uint8_t; };
210 template<> struct DimToWord<4> { using Type = uint16_t; };
211 template<> struct DimToWord<5> { using Type = uint32_t; };
212 template<> struct DimToWord<6> { using Type = uint64_t; };
213 
214 
216 
217 
218 template<typename TreeType>
220 {
221 public:
223 
224  Morphology(TreeType& tree):
225  mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
227  mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
228  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
229 
231  void dilateVoxels6();
233  void dilateVoxels18();
235  void dilateVoxels26();
236  void dilateVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE);
237 
239  void erodeVoxels6() { mSteps = 1; this->doErosion(NN_FACE); }
241  void erodeVoxels18() { mSteps = 1; this->doErosion(NN_FACE_EDGE); }
243  void erodeVoxels26() { mSteps = 1; this->doErosion(NN_FACE_EDGE_VERTEX); }
244  void erodeVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE)
245  {
246  mSteps = iterations;
247  this->doErosion(nn);
248  }
249 
250 protected:
251 
252  void doErosion(NearestNeighbors nn);
253 
254  using LeafType = typename TreeType::LeafNodeType;
255  using MaskType = typename LeafType::NodeMaskType;
257 
258  const bool mOwnsManager;
261  int mSteps;
262 
263  static const int LEAF_DIM = LeafType::DIM;
264  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
266 
267  struct Neighbor {
268  LeafType* leaf;//null if a tile
269  bool init;//true if initialization is required
270  bool isOn;//true if an active tile
271  Neighbor() : leaf(nullptr), init(true) {}
272  inline void clear() { leaf = nullptr; init = true; }
273  template<int DX, int DY, int DZ>
274  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word mask)
275  {
276  if (init) {
277  init = false;
278  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
279  leaf = acc.probeLeaf(orig);
280  if ((leaf == nullptr) && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
281  }
282  static const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
283  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
284  }
285 
286  template<int DX, int DY, int DZ>
287  Word gather(AccessorType& acc, const Coord &xyz, int indx)
288  {
289  if (init) {
290  init = false;
291  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
292  leaf = acc.probeLeaf(orig);
293  isOn = leaf ? false : acc.isValueOn(orig);
294  }
295  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
296  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
297  : isOn ? ~Word(0) : Word(0);
298  }
299  };// Neighbor
300 
301  struct LeafCache
302  {
303  LeafCache(size_t n, TreeType& tree) : size(n), leafs(new LeafType*[n]), acc(tree)
304  {
305  onTile.setValuesOn();
306  this->clear();
307  }
308  ~LeafCache() { delete [] leafs; }
309  LeafType*& operator[](int offset) { return leafs[offset]; }
310  inline void clear() { for (size_t i = 0; i < size; ++i) leafs[i] = nullptr; }
311  inline void setOrigin(const Coord& xyz) { origin = &xyz; }
312  inline void scatter(int n, int indx)
313  {
314  assert(leafs[n]);
315  leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
316  }
317  template<int DX, int DY, int DZ>
318  inline void scatter(int n, int indx)
319  {
320  if (!leafs[n]) {
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);
324  }
325  this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
326  }
327  inline Word gather(int n, int indx)
328  {
329  assert(leafs[n]);
330  return leafs[n]->getValueMask().template getWord<Word>(indx);
331  }
332  template<int DX, int DY, int DZ>
333  inline Word gather(int n, int indx)
334  {
335  if (!leafs[n]) {
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;
339  }
340  return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
341  }
342  // Scatters in the xy face-directions relative to leaf i1
343  void scatterFacesXY(int x, int y, int i1, int n, int i2);
344 
345  // Scatters in the xy edge-directions relative to leaf i1
346  void scatterEdgesXY(int x, int y, int i1, int n, int i2);
347 
348  Word gatherFacesXY(int x, int y, int i1, int n, int i2);
349 
350  Word gatherEdgesXY(int x, int y, int i1, int n, int i2);
351 
352  const Coord* origin;
353  size_t size;
355  LeafType onTile, offTile;
358  };// LeafCache
359 
360  struct ErodeVoxelsOp {
361  using RangeT = tbb::blocked_range<size_t>;
362  ErodeVoxelsOp(std::vector<MaskType>& masks, ManagerType& manager)
363  : mTask(nullptr), mSavedMasks(masks) , mManager(manager) {}
364  void runParallel(NearestNeighbors nn);
365  void operator()(const RangeT& r) const {mTask(const_cast<ErodeVoxelsOp*>(this), r);}
366  void erode6( const RangeT&) const;
367  void erode18(const RangeT&) const;
368  void erode26(const RangeT&) const;
369  private:
370  using FuncT = typename std::function<void (ErodeVoxelsOp*, const RangeT&)>;
371  FuncT mTask;
372  std::vector<MaskType>& mSavedMasks;
373  ManagerType& mManager;
374  };// ErodeVoxelsOp
375 
376  struct MaskManager {
377  MaskManager(std::vector<MaskType>& masks, ManagerType& manager)
378  : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
379 
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
383  {
384  if (mSaveMasks) {
385  for (size_t i = range.begin(); i < range.end(); ++i) {
386  mMasks[i] = mManager.leaf(i).getValueMask();
387  }
388  } else {
389  for (size_t i = range.begin(); i < range.end(); ++i) {
390  mManager.leaf(i).setValueMask(mMasks[i]);
391  }
392  }
393  }
394  private:
395  std::vector<MaskType>& mMasks;
396  ManagerType& mManager;
397  bool mSaveMasks;
398  };// MaskManager
399 
400  struct UpdateMasks {
401  UpdateMasks(const std::vector<MaskType>& masks, ManagerType& manager)
402  : mMasks(masks), mManager(manager) {}
403  void update() { tbb::parallel_for(mManager.getRange(), *this); }
404  void operator()(const tbb::blocked_range<size_t>& r) const {
405  for (size_t i=r.begin(); i<r.end(); ++i) mManager.leaf(i).setValueMask(mMasks[i]);
406  }
407  const std::vector<MaskType>& mMasks;
409  };
410  struct CopyMasks {
411  CopyMasks(std::vector<MaskType>& masks, const ManagerType& manager)
412  : mMasks(masks), mManager(manager) {}
413  void copy() { tbb::parallel_for(mManager.getRange(), *this); }
414  void operator()(const tbb::blocked_range<size_t>& r) const {
415  for (size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.leaf(i).getValueMask();
416  }
417  std::vector<MaskType>& mMasks;
419  };
420  void copyMasks(std::vector<MaskType>& a, const ManagerType& b) {CopyMasks c(a, b); c.copy();}
421 };// Morphology
422 
423 
424 template<typename TreeType>
425 inline void
427 {
428  for (int i=0; i<iterations; ++i) {
429  switch (nn) {
430  case NN_FACE_EDGE:
431  this->dilateVoxels18();
432  break;
433  case NN_FACE_EDGE_VERTEX:
434  this->dilateVoxels26();
435  break;
436  case NN_FACE:
437  default:
438  this->dilateVoxels6();
439  }
440  }
441 }
442 
443 
444 template<typename TreeType>
445 inline void
447 {
449  const int leafCount = static_cast<int>(mManager->leafCount());
450 
451  // Save the value masks of all leaf nodes.
452  std::vector<MaskType> savedMasks(leafCount);
453  this->copyMasks(savedMasks, *mManager);
454  LeafCache cache(7, mManager->tree());
455  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
456  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
457  cache[0] = &mManager->leaf(leafIdx);
458  cache.setOrigin(cache[0]->origin());
459  for (int x = 0; x < LEAF_DIM; ++x ) {
460  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
461  // Extract the portion of the original mask that corresponds to a row in z.
462  if (const Word w = oldMask.template getWord<Word>(n)) {
463 
464  // Dilate the current leaf in the +z and -z direction
465  cache.mask = Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
466 
467  // Dilate into neighbor leaf in the -z direction
468  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
469  cache.template scatter< 0, 0,-1>(1, n);
470  }
471  // Dilate into neighbor leaf in the +z direction
472  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
473  cache.template scatter< 0, 0, 1>(2, n);
474  }
475  // Dilate in the xy-face directions relative to the center leaf
476  cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
477  }
478  }// loop over y
479  }//loop over x
480  cache.clear();
481  }//loop over leafs
482 
483  mManager->rebuildLeafArray();
484 }//dilateVoxels6
485 
486 
487 template<typename TreeType>
488 inline void
490 {
492  const int leafCount = static_cast<int>(mManager->leafCount());
493 
494  // Save the value masks of all leaf nodes.
495  std::vector<MaskType> savedMasks(leafCount);
496  this->copyMasks(savedMasks, *mManager);
497  LeafCache cache(19, mManager->tree());
498  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
499  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
500  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
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)) {
507  {
508  cache.mask = Word(w | (w>>1) | (w<<1));
509  cache.setOrigin(cache[0]->origin());
510  cache.scatter(0, n);
511  cache.scatterFacesXY(x, y, 0, n, 3);
512  cache.mask = w;
513  cache.scatterEdgesXY(x, y, 0, n, 3);
514  }
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);
520  }
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);
526  }
527  }
528  }// loop over y
529  }//loop over x
530  cache.clear();
531  }//loop over leafs
532 
533  mManager->rebuildLeafArray();
534 }// dilateVoxels18
535 
536 
537 template<typename TreeType>
538 inline void
540 {
541  const int leafCount = static_cast<int>(mManager->leafCount());
542 
543  // Save the value masks of all leaf nodes.
544  std::vector<MaskType> savedMasks(leafCount);
545  this->copyMasks(savedMasks, *mManager);
546  LeafCache cache(27, mManager->tree());
547  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
548  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
549  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
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)) {
556  {
557  cache.mask = Word(w | (w>>1) | (w<<1));
558  cache.setOrigin(cache[0]->origin());
559  cache.scatter(0, n);
560  cache.scatterFacesXY(x, y, 0, n, 3);
561  cache.scatterEdgesXY(x, y, 0, n, 3);
562  }
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);
569  }
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);
576  }
577  }
578  }// loop over y
579  }//loop over x
580  cache.clear();
581  }//loop over leafs
582 
583  mManager->rebuildLeafArray();
584 }// dilateVoxels26
585 
586 
587 template<typename TreeType>
588 inline void
589 Morphology<TreeType>::LeafCache::scatterFacesXY(int x, int y, int i1, int n, int i2)
590 {
591  // dilate current leaf or neighbor in the -x direction
592  if (x > 0) {
593  this->scatter(i1, n-LEAF_DIM);
594  } else {
595  this->template scatter<-1, 0, 0>(i2, n);
596  }
597  // dilate current leaf or neighbor in the +x direction
598  if (x < LEAF_DIM-1) {
599  this->scatter(i1, n+LEAF_DIM);
600  } else {
601  this->template scatter< 1, 0, 0>(i2+1, n);
602  }
603  // dilate current leaf or neighbor in the -y direction
604  if (y > 0) {
605  this->scatter(i1, n-1);
606  } else {
607  this->template scatter< 0,-1, 0>(i2+2, n);
608  }
609  // dilate current leaf or neighbor in the +y direction
610  if (y < LEAF_DIM-1) {
611  this->scatter(i1, n+1);
612  } else {
613  this->template scatter< 0, 1, 0>(i2+3, n);
614  }
615 }
616 
617 
618 template<typename TreeType>
619 inline void
620 Morphology<TreeType>::LeafCache::scatterEdgesXY(int x, int y, int i1, int n, int i2)
621 {
622  if (x > 0) {
623  if (y > 0) {
624  this->scatter(i1, n-LEAF_DIM-1);
625  } else {
626  this->template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
627  }
628  if (y < LEAF_DIM-1) {
629  this->scatter(i1, n-LEAF_DIM+1);
630  } else {
631  this->template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
632  }
633  } else {
634  if (y < LEAF_DIM-1) {
635  this->template scatter<-1, 0, 0>(i2 , n+1);
636  } else {
637  this->template scatter<-1, 1, 0>(i2+7, n );
638  }
639  if (y > 0) {
640  this->template scatter<-1, 0, 0>(i2 , n-1);
641  } else {
642  this->template scatter<-1,-1, 0>(i2+4, n );
643  }
644  }
645  if (x < LEAF_DIM-1) {
646  if (y > 0) {
647  this->scatter(i1, n+LEAF_DIM-1);
648  } else {
649  this->template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
650  }
651  if (y < LEAF_DIM-1) {
652  this->scatter(i1, n+LEAF_DIM+1);
653  } else {
654  this->template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
655  }
656  } else {
657  if (y > 0) {
658  this->template scatter< 1, 0, 0>(i2+1, n-1);
659  } else {
660  this->template scatter< 1,-1, 0>(i2+6, n );
661  }
662  if (y < LEAF_DIM-1) {
663  this->template scatter< 1, 0, 0>(i2+1, n+1);
664  } else {
665  this->template scatter< 1, 1, 0>(i2+5, n );
666  }
667  }
668 }
669 
670 
671 template<typename TreeType>
672 inline void
674 {
675  namespace ph = std::placeholders;
676  switch (nn) {
677  case NN_FACE_EDGE:
678  mTask = std::bind(&ErodeVoxelsOp::erode18, ph::_1, ph::_2);
679  break;
680  case NN_FACE_EDGE_VERTEX:
681  mTask = std::bind(&ErodeVoxelsOp::erode26, ph::_1, ph::_2);
682  break;
683  case NN_FACE:
684  default:
685  mTask = std::bind(&ErodeVoxelsOp::erode6, ph::_1, ph::_2);
686  }
687  tbb::parallel_for(mManager.getRange(), *this);
688 }
689 
690 
691 template<typename TreeType>
692 inline typename Morphology<TreeType>::Word
693 Morphology<TreeType>::LeafCache::gatherFacesXY(int x, int y, int i1, int n, int i2)
694 {
695  // erode current leaf or neighbor in negative x-direction
696  Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->template gather<-1,0,0>(i2, n);
697 
698  // erode current leaf or neighbor in positive x-direction
699  w = Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->template gather<1,0,0>(i2+1,n)));
700 
701  // erode current leaf or neighbor in negative y-direction
702  w = Word(w & (y>0 ? this->gather(i1, n-1) : this->template gather<0,-1,0>(i2+2, n)));
703 
704  // erode current leaf or neighbor in positive y-direction
705  w = Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->template gather<0,1,0>(i2+3, n)));
706 
707  return w;
708 }
709 
710 
711 template<typename TreeType>
712 inline typename Morphology<TreeType>::Word
713 Morphology<TreeType>::LeafCache::gatherEdgesXY(int x, int y, int i1, int n, int i2)
714 {
715  Word w = ~Word(0);
716 
717  if (x > 0) {
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);
722  } else {
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 );
727  }
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);
733  } else {
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 );
738  }
739 
740  return w;
741 }
742 
743 
744 template <typename TreeType>
745 inline void
747 {
748  LeafCache cache(7, mManager.tree());
749  for (size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
750  cache[0] = &mManager.leaf(leafIdx);
751  if (cache[0]->isEmpty()) continue;
752  cache.setOrigin(cache[0]->origin());
753  MaskType& newMask = mSavedMasks[leafIdx];//original bit-mask of current leaf node
754  for (int x = 0; x < LEAF_DIM; ++x ) {
755  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
756  // Extract the portion of the original mask that corresponds to a row in z.
757  if (Word& w = newMask.template getWord<Word>(n)) {
758 
759  // erode in two z directions (this is first since it uses the original w)
760  w = Word(w &
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)))));
763 
764  w = Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
765  }
766  }// loop over y
767  }//loop over x
768  cache.clear();
769  }//loop over leafs
770 }
771 
772 
773 template <typename TreeType>
774 inline void
776 {
777  OPENVDB_THROW(NotImplementedError, "tools::erode18 is not implemented yet!");
778 }
779 
780 
781 template <typename TreeType>
782 inline void
784 {
785  OPENVDB_THROW(NotImplementedError, "tools::erode26 is not implemented yet!");
786 }
787 
788 
789 template<typename TreeType>
790 inline void
792 {
794  const size_t leafCount = mManager->leafCount();
795 
796  // Save the value masks of all leaf nodes.
797  std::vector<MaskType> savedMasks(leafCount);
798  this->copyMasks(savedMasks, *mManager);
799  UpdateMasks a(savedMasks, *mManager);
800  ErodeVoxelsOp erode(savedMasks, *mManager);
801 
802  for (int i = 0; i < mSteps; ++i) {
803  erode.runParallel(nn);
804  a.update();
805  }
806 
807  tools::pruneLevelSet(mManager->tree());
808 }
809 
810 
812 
813 
814 template<typename TreeType>
817 {
818  if (iterations > 0 ) {
819  Morphology<TreeType> m(&manager);
820  m.dilateVoxels(iterations, nn);
821  }
822 }
823 
824 template<typename TreeType>
826 dilateVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
827 {
828  if (iterations > 0 ) {
829  Morphology<TreeType> m(tree);
830  m.dilateVoxels(iterations, nn);
831  }
832 }
833 
834 template<typename TreeType>
837 {
838  if (iterations > 0 ) {
839  Morphology<TreeType> m(&manager);
840  m.erodeVoxels(iterations, nn);
841  }
842 }
843 
844 template<typename TreeType>
846 erodeVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
847 {
848  if (iterations > 0 ) {
849  Morphology<TreeType> m(tree);
850  m.erodeVoxels(iterations, nn);
851  }
852 }
853 
854 
856 
857 
858 namespace activation {
859 
860 template<typename TreeType>
862 {
863 public:
864  using ValueT = typename TreeType::ValueType;
865 
866  ActivationOp(bool state, const ValueT& val, const ValueT& tol)
867  : mActivate(state)
868  , mValue(val)
869  , mTolerance(tol)
870  {}
871 
872  void operator()(const typename TreeType::ValueOnIter& it) const
873  {
874  if (math::isApproxEqual(*it, mValue, mTolerance)) {
875  it.setValueOff();
876  }
877  }
878 
879  void operator()(const typename TreeType::ValueOffIter& it) const
880  {
881  if (math::isApproxEqual(*it, mValue, mTolerance)) {
882  it.setActiveState(/*on=*/true);
883  }
884  }
885 
886  void operator()(const typename TreeType::LeafIter& lit) const
887  {
888  using LeafT = typename TreeType::LeafNodeType;
889  LeafT& leaf = *lit;
890  if (mActivate) {
891  for (typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
892  if (math::isApproxEqual(*it, mValue, mTolerance)) {
893  leaf.setValueOn(it.pos());
894  }
895  }
896  } else {
897  for (typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
898  if (math::isApproxEqual(*it, mValue, mTolerance)) {
899  leaf.setValueOff(it.pos());
900  }
901  }
902  }
903  }
904 
905 private:
906  bool mActivate;
907  const ValueT mValue, mTolerance;
908 }; // class ActivationOp
909 
910 } // namespace activation
911 
912 
913 template<typename GridOrTree>
914 inline void
915 activate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
916  const typename GridOrTree::ValueType& tolerance)
917 {
918  using Adapter = TreeAdapter<GridOrTree>;
919  using TreeType = typename Adapter::TreeType;
920 
921  TreeType& tree = Adapter::tree(gridOrTree);
922 
923  activation::ActivationOp<TreeType> op(/*activate=*/true, value, tolerance);
924 
925  // Process all leaf nodes in parallel.
926  foreach(tree.beginLeaf(), op);
927 
928  // Process all other inactive values serially (because changing active states
929  // is not thread-safe unless no two threads modify the same node).
930  typename TreeType::ValueOffIter it = tree.beginValueOff();
931  it.setMaxDepth(tree.treeDepth() - 2);
932  foreach(it, op, /*threaded=*/false);
933 }
934 
935 
936 template<typename GridOrTree>
937 inline void
938 deactivate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
939  const typename GridOrTree::ValueType& tolerance)
940 {
941  using Adapter = TreeAdapter<GridOrTree>;
942  using TreeType = typename Adapter::TreeType;
943 
944  TreeType& tree = Adapter::tree(gridOrTree);
945 
946  activation::ActivationOp<TreeType> op(/*activate=*/false, value, tolerance);
947 
948  // Process all leaf nodes in parallel.
949  foreach(tree.beginLeaf(), op);
950 
951  // Process all other active values serially (because changing active states
952  // is not thread-safe unless no two threads modify the same node).
953  typename TreeType::ValueOnIter it = tree.beginValueOn();
954  it.setMaxDepth(tree.treeDepth() - 2);
955  foreach(it, op, /*threaded=*/false);
956 }
957 
960 template<typename TreeT>
962 {
963  using MaskT = typename TreeT::template ValueConverter<ValueMask>::Type;
964  using PoolT = tbb::enumerable_thread_specific<MaskT>;
965  using LeafT = typename MaskT::LeafNodeType;
966 
967  // Very light-weight member data
968  const int mIter;// number of iterations
969  const tools::NearestNeighbors mNN;//enum to specify the dilation scheme
970  PoolT *mPool;// pointer to the thread-local pool of mask trees
971  LeafT **mLeafs;// raw array of pointers to leaf nodes
972 
973 public:
974 
975  DilationOp(TreeT &tree, int iterations, NearestNeighbors nn, TilePolicy mode)
976  : mIter(iterations), mNN(nn), mPool(nullptr), mLeafs(nullptr)
977  {
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));
981 
982  MaskT mask;
983  PoolT pool(mask);// Scoped thread-local storage of mask trees
984  mPool = &pool;
985 
986  tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *this);
987 
988  delete [] mLeafs;// no more need for the array of leaf node pointers
989 
990  using IterT = typename PoolT::iterator;
991  for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);// fast stealing
992 
993  if (mode == PRESERVE_TILES) tools::prune(mask);//multithreaded
994 
995  tree.topologyUnion(mask);//multithreaded
996  }
997 
998  // This is required by tbb and should never be called directly
999  void operator()(const tbb::blocked_range<LeafT**> &r) const
1000  {
1001  MaskT mask;// thread-local temporary mask tree
1002  for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1003  tree::LeafManager<MaskT> manager(mask, r.begin(), r.end());
1004  tools::dilateVoxels(manager, mIter, mNN);// serial dilation of active voxels
1005  mPool->local().merge(mask, MERGE_ACTIVE_STATES);
1006  }
1007 private:
1008 
1009  // Simple wrapper of a raw double-pointer to mimic a std container
1010  struct MyArray {
1011  using value_type = LeafT*;//required by Tree::stealNodes
1012  value_type* ptr;
1013  MyArray(value_type* array) : ptr(array) {}
1014  void push_back(value_type leaf) { *ptr++ = leaf; }//required by Tree::stealNodes
1015  };
1016 
1017  // Convert active tiles to leafs and de-construct the tree into a linear array of leafs.
1018  size_t linearize(MaskT& mask, TilePolicy mode)
1019  {
1020  if (mode != IGNORE_TILES) mask.voxelizeActiveTiles();//lightweight since this is a mask tree
1021  const size_t numLeafs = mask.leafCount();
1022  mLeafs = new LeafT*[numLeafs];// fast pre-allocation
1023  MyArray tmp(mLeafs);
1024  mask.stealNodes(tmp);// serializes the mask tree and leaves it empty
1025  return numLeafs;
1026  }
1027 
1028  template<typename T>
1029  typename std::enable_if<std::is_same<T, MaskT>::value, size_t>::type
1030  init(T& tree, TilePolicy mode)
1031  {
1032  return this->linearize(tree, mode);
1033  }
1034 
1035  template<typename T>
1036  typename std::enable_if<!std::is_same<T, MaskT>::value, size_t>::type
1037  init(const T& tree, TilePolicy mode)
1038  {
1039  MaskT mask(tree, false, true, TopologyCopy());
1040  return this->linearize(mask, mode);
1041  }
1042 
1043 };// DilationOp
1044 
1045 template<typename TreeType>
1047 dilateActiveValues(TreeType& tree, int iterations, NearestNeighbors nn, TilePolicy mode)
1048 {
1049  if (iterations > 0 ) DilationOp<TreeType> tmp(tree, iterations, nn, mode);
1050 }
1051 
1052 template<typename TreeType>
1055  int iterations,
1056  NearestNeighbors nn,
1057  TilePolicy mode)
1058 {
1059  if (iterations > 0 ) {
1060  DilationOp<TreeType> tmp(manager.tree(), iterations, nn, mode);
1061  manager.rebuildLeafArray();
1062  }
1063 }
1064 
1065 } // namespace tools
1066 } // namespace OPENVDB_VERSION_NAME
1067 } // namespace openvdb
1068 
1069 #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 nullptr if no such node exists...
Definition: ValueAccessor.h:390
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:237
Definition: Morphology.h:60
Definition: Exceptions.h:61
virtual ~Morphology()
Definition: Morphology.h:228
void copy()
Definition: Morphology.h:413
const ManagerType & mManager
Definition: Morphology.h:418
void update()
Definition: Morphology.h:381
size_t size
Definition: Morphology.h:353
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:351
void deactivate(GridOrTree &, const typename GridOrTree::ValueType &value, const typename GridOrTree::ValueType &tolerance=zeroVal< typename GridOrTree::ValueType >())
Mark as inactive any active tiles or voxels in the given grid or tree whose values are equal to value...
Definition: Morphology.h:938
Definition: Types.h:506
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
uint8_t Type
Definition: Morphology.h:209
void clear()
Definition: Morphology.h:272
uint32_t Type
Definition: Morphology.h:211
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
Definition: Morphology.h:219
bool isOn
Definition: Morphology.h:270
void operator()(const typename TreeType::LeafIter &lit) const
Definition: Morphology.h:886
void erodeVoxels26()
Face-, edge- and vertex-adjacent erosion pattern.
Definition: Morphology.h:243
void clear()
Definition: Morphology.h:310
AccessorType acc
Definition: Morphology.h:356
int mSteps
Definition: Morphology.h:261
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:355
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:288
Word gather(int n, int indx)
Definition: Morphology.h:327
void erodeVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:244
void save()
Definition: Morphology.h:380
Definition: Morphology.h:267
typename TreeType::ValueType ValueT
Definition: Morphology.h:864
uint64_t Type
Definition: Morphology.h:212
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:542
CopyMasks(std::vector< MaskType > &masks, const ManagerType &manager)
Definition: Morphology.h:411
Defined various multi-threaded utility functions for trees.
tbb::blocked_range< size_t > RangeT
Definition: Morphology.h:361
LeafCache(size_t n, TreeType &tree)
Definition: Morphology.h:303
typename LeafType::NodeMaskType MaskType
Definition: Morphology.h:255
void scatter(AccessorType &acc, const Coord &xyz, int indx, Word mask)
Definition: Morphology.h:274
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:414
const bool mOwnsManager
Definition: Morphology.h:258
uint16_t Type
Definition: Morphology.h:210
void scatter(int n, int indx)
Definition: Morphology.h:318
void pruneLevelSet(TreeT &tree, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing nodes whose values are all inactive with inactive ...
Definition: Prune.h:389
void operator()(const RangeT &r) const
Definition: Morphology.h:365
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:331
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:404
void copyMasks(std::vector< MaskType > &a, const ManagerType &b)
Definition: Morphology.h:420
typename DimToWord< LEAF_LOG2DIM >::Type Word
Definition: Morphology.h:265
MaskManager(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:377
const Coord * origin
Definition: Morphology.h:352
void operator()(const typename TreeType::ValueOffIter &it) const
Definition: Morphology.h:879
Morphology(TreeType &tree)
Definition: Morphology.h:224
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1065
void setOrigin(const Coord &xyz)
Definition: Morphology.h:311
~LeafCache()
Definition: Morphology.h:308
void erodeVoxels(tree::LeafManager< TreeType > &manager, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically erode all leaf-level active voxels in the given tree.
Definition: Morphology.h:836
void scatter(int n, int indx)
Definition: Morphology.h:312
Definition: Exceptions.h:13
ManagerType & mManager
Definition: Morphology.h:408
Definition: Morphology.h:75
AccessorType mAcc
Definition: Morphology.h:260
Class that performs multi-threaded dilation with support for active tiles.
Definition: Morphology.h:961
Definition: Morphology.h:75
void erodeVoxels18()
Face- and edge-adjacent erosion pattern.
Definition: Morphology.h:241
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:82
void dilateActiveValues(tree::LeafManager< TreeType > &manager, int iterations=1, NearestNeighbors nn=NN_FACE, TilePolicy mode=PRESERVE_TILES)
Topologically dilate all active values (i.e. both voxels and tiles) in a tree using one of three near...
Definition: Morphology.h:1054
Morphology(ManagerType *mgr)
Definition: Morphology.h:226
NearestNeighbors
Voxel topology of nearest neighbors.
Definition: Morphology.h:60
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:681
void operator()(const typename TreeType::ValueOnIter &it) const
Definition: Morphology.h:872
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:315
void update()
Definition: Morphology.h:403
ActivationOp(bool state, const ValueT &val, const ValueT &tol)
Definition: Morphology.h:866
Neighbor()
Definition: Morphology.h:271
Word gather(AccessorType &acc, const Coord &xyz, int indx)
Definition: Morphology.h:287
void erodeVoxels6()
Face-adjacent erosion pattern.
Definition: Morphology.h:239
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:359
Word gather(int n, int indx)
Definition: Morphology.h:333
void activate(GridOrTree &, const typename GridOrTree::ValueType &value, const typename GridOrTree::ValueType &tolerance=zeroVal< typename GridOrTree::ValueType >())
Mark as active any inactive tiles or voxels in the given grid or tree whose values are equal to value...
Definition: Morphology.h:915
LeafType * leaf
Definition: Morphology.h:268
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Morphology.h:382
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:208
#define OPENVDB_STATIC_SPECIALIZATION
Definition: Platform.h:62
ErodeVoxelsOp(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:362
Definition: Morphology.h:75
std::vector< MaskType > & mMasks
Definition: Morphology.h:417
bool init
Definition: Morphology.h:269
LeafType *& operator[](int offset)
Definition: Morphology.h:309
DilationOp(TreeT &tree, int iterations, NearestNeighbors nn, TilePolicy mode)
Definition: Morphology.h:975
void operator()(const tbb::blocked_range< LeafT ** > &r) const
Definition: Morphology.h:999
UpdateMasks(const std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:401
Word mask
Definition: Morphology.h:357
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:334
const std::vector< MaskType > & mMasks
Definition: Morphology.h:407
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
TilePolicy
Different policies when dilating trees with active tiles.
Definition: Morphology.h:75
void runParallel(NearestNeighbors nn)
Definition: Morphology.h:673
LeafType onTile
Definition: Morphology.h:355
Definition: Morphology.h:60
ManagerType * mManager
Definition: Morphology.h:259
LeafType ** leafs
Definition: Morphology.h:354
void dilateVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:426
typename TreeType::LeafNodeType LeafType
Definition: Morphology.h:254
void dilateVoxels(tree::LeafManager< TreeType > &manager, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically dilate all leaf-level active voxels in a tree using one of three nearest neighbor conne...
Definition: Morphology.h:816