OpenVDB  6.2.1
Morphology.h
Go to the documentation of this file.
1 //
3 // Copyright (c) DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
45 
46 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
47 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
48 
49 #include <openvdb/Types.h>
50 #include <openvdb/Grid.h>
51 #include <openvdb/math/Math.h> // for isApproxEqual()
55 #include "Prune.h"// for pruneLevelSet
56 #include "ValueTransformer.h" // for foreach()
57 #include <tbb/tbb_thread.h>
58 #include <tbb/task_scheduler_init.h>
59 #include <tbb/enumerable_thread_specific.h>
60 #include <tbb/parallel_for.h>
61 #include <functional>
62 #include <type_traits>
63 #include <vector>
64 
65 
66 namespace openvdb {
68 namespace OPENVDB_VERSION_NAME {
69 namespace tools {
70 
88 
103 
119 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
120 inline void dilateActiveValues(TreeType& tree,
121  int iterations = 1,
123  TilePolicy mode = PRESERVE_TILES);
124 
149 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
151  int iterations = 1,
153  TilePolicy mode = PRESERVE_TILES);
154 
155 
168 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
169 inline void dilateVoxels(TreeType& tree,
170  int iterations = 1,
172 
187 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
188 inline void dilateVoxels(tree::LeafManager<TreeType>& manager,
189  int iterations = 1,
191 
192 
194 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
200 inline void erodeVoxels(TreeType& tree,
201  int iterations=1,
203 
204 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
205 inline void erodeVoxels(tree::LeafManager<TreeType>& manager,
206  int iterations = 1,
209 
210 
213 template<typename GridOrTree>
214 inline void activate(
215  GridOrTree&,
216  const typename GridOrTree::ValueType& value,
217  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
218 );
219 
220 
223 template<typename GridOrTree>
224 inline void deactivate(
225  GridOrTree&,
226  const typename GridOrTree::ValueType& value,
227  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
228 );
229 
230 
232 
233 
235 template<Index Log2Dim> struct DimToWord {};
236 template<> struct DimToWord<3> { using Type = uint8_t; };
237 template<> struct DimToWord<4> { using Type = uint16_t; };
238 template<> struct DimToWord<5> { using Type = uint32_t; };
239 template<> struct DimToWord<6> { using Type = uint64_t; };
240 
241 
243 
244 
245 template<typename TreeType>
247 {
248 public:
250 
251  Morphology(TreeType& tree):
252  mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
254  mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
255  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
256 
258  void dilateVoxels6();
260  void dilateVoxels18();
262  void dilateVoxels26();
263  void dilateVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE);
264 
266  void erodeVoxels6() { mSteps = 1; this->doErosion(NN_FACE); }
268  void erodeVoxels18() { mSteps = 1; this->doErosion(NN_FACE_EDGE); }
270  void erodeVoxels26() { mSteps = 1; this->doErosion(NN_FACE_EDGE_VERTEX); }
271  void erodeVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE)
272  {
273  mSteps = iterations;
274  this->doErosion(nn);
275  }
276 
277 protected:
278 
279  void doErosion(NearestNeighbors nn);
280 
281  using LeafType = typename TreeType::LeafNodeType;
282  using MaskType = typename LeafType::NodeMaskType;
284 
285  const bool mOwnsManager;
288  int mSteps;
289 
290  static const int LEAF_DIM = LeafType::DIM;
291  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
293 
294  struct Neighbor {
295  LeafType* leaf;//null if a tile
296  bool init;//true if initialization is required
297  bool isOn;//true if an active tile
298  Neighbor() : leaf(nullptr), init(true) {}
299  inline void clear() { leaf = nullptr; init = true; }
300  template<int DX, int DY, int DZ>
301  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word mask)
302  {
303  if (init) {
304  init = false;
305  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
306  leaf = acc.probeLeaf(orig);
307  if ((leaf == nullptr) && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
308  }
309 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
310  static
311 #endif
312  const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
313  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
314  }
315 
316  template<int DX, int DY, int DZ>
317  Word gather(AccessorType& acc, const Coord &xyz, int indx)
318  {
319  if (init) {
320  init = false;
321  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
322  leaf = acc.probeLeaf(orig);
323  isOn = leaf ? false : acc.isValueOn(orig);
324  }
325 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
326  static
327 #endif
328  const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
329  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
330  : isOn ? ~Word(0) : Word(0);
331  }
332  };// Neighbor
333 
334  struct LeafCache
335  {
336  LeafCache(size_t n, TreeType& tree) : size(n), leafs(new LeafType*[n]), acc(tree)
337  {
338  onTile.setValuesOn();
339  this->clear();
340  }
341  ~LeafCache() { delete [] leafs; }
342  LeafType*& operator[](int offset) { return leafs[offset]; }
343  inline void clear() { for (size_t i = 0; i < size; ++i) leafs[i] = nullptr; }
344  inline void setOrigin(const Coord& xyz) { origin = &xyz; }
345  inline void scatter(int n, int indx)
346  {
347  assert(leafs[n]);
348  leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
349  }
350  template<int DX, int DY, int DZ>
351  inline void scatter(int n, int indx)
352  {
353  if (!leafs[n]) {
354  const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
355  leafs[n] = acc.probeLeaf(xyz);
356  if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
357  }
358  this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
359  }
360  inline Word gather(int n, int indx)
361  {
362  assert(leafs[n]);
363  return leafs[n]->getValueMask().template getWord<Word>(indx);
364  }
365  template<int DX, int DY, int DZ>
366  inline Word gather(int n, int indx)
367  {
368  if (!leafs[n]) {
369  const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
370  leafs[n] = acc.probeLeaf(xyz);
371  if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
372  }
373  return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
374  }
375  // Scatters in the xy face-directions relative to leaf i1
376  void scatterFacesXY(int x, int y, int i1, int n, int i2);
377 
378  // Scatters in the xy edge-directions relative to leaf i1
379  void scatterEdgesXY(int x, int y, int i1, int n, int i2);
380 
381  Word gatherFacesXY(int x, int y, int i1, int n, int i2);
382 
383  Word gatherEdgesXY(int x, int y, int i1, int n, int i2);
384 
385  const Coord* origin;
386  size_t size;
388  LeafType onTile, offTile;
391  };// LeafCache
392 
393  struct ErodeVoxelsOp {
394  using RangeT = tbb::blocked_range<size_t>;
395  ErodeVoxelsOp(std::vector<MaskType>& masks, ManagerType& manager)
396  : mTask(nullptr), mSavedMasks(masks) , mManager(manager) {}
397  void runParallel(NearestNeighbors nn);
398  void operator()(const RangeT& r) const {mTask(const_cast<ErodeVoxelsOp*>(this), r);}
399  void erode6( const RangeT&) const;
400  void erode18(const RangeT&) const;
401  void erode26(const RangeT&) const;
402  private:
403  using FuncT = typename std::function<void (ErodeVoxelsOp*, const RangeT&)>;
404  FuncT mTask;
405  std::vector<MaskType>& mSavedMasks;
406  ManagerType& mManager;
407  };// ErodeVoxelsOp
408 
409  struct MaskManager {
410  MaskManager(std::vector<MaskType>& masks, ManagerType& manager)
411  : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
412 
413  void save() { mSaveMasks = true; tbb::parallel_for(mManager.getRange(), *this); }
414  void update() { mSaveMasks = false; tbb::parallel_for(mManager.getRange(), *this); }
415  void operator()(const tbb::blocked_range<size_t>& range) const
416  {
417  if (mSaveMasks) {
418  for (size_t i = range.begin(); i < range.end(); ++i) {
419  mMasks[i] = mManager.leaf(i).getValueMask();
420  }
421  } else {
422  for (size_t i = range.begin(); i < range.end(); ++i) {
423  mManager.leaf(i).setValueMask(mMasks[i]);
424  }
425  }
426  }
427  private:
428  std::vector<MaskType>& mMasks;
429  ManagerType& mManager;
430  bool mSaveMasks;
431  };// MaskManager
432 
433  struct UpdateMasks {
434  UpdateMasks(const std::vector<MaskType>& masks, ManagerType& manager)
435  : mMasks(masks), mManager(manager) {}
436  void update() { tbb::parallel_for(mManager.getRange(), *this); }
437  void operator()(const tbb::blocked_range<size_t>& r) const {
438  for (size_t i=r.begin(); i<r.end(); ++i) mManager.leaf(i).setValueMask(mMasks[i]);
439  }
440  const std::vector<MaskType>& mMasks;
442  };
443  struct CopyMasks {
444  CopyMasks(std::vector<MaskType>& masks, const ManagerType& manager)
445  : mMasks(masks), mManager(manager) {}
446  void copy() { tbb::parallel_for(mManager.getRange(), *this); }
447  void operator()(const tbb::blocked_range<size_t>& r) const {
448  for (size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.leaf(i).getValueMask();
449  }
450  std::vector<MaskType>& mMasks;
452  };
453  void copyMasks(std::vector<MaskType>& a, const ManagerType& b) {CopyMasks c(a, b); c.copy();}
454 };// Morphology
455 
456 
457 template<typename TreeType>
458 inline void
460 {
461  for (int i=0; i<iterations; ++i) {
462  switch (nn) {
463  case NN_FACE_EDGE:
464  this->dilateVoxels18();
465  break;
466  case NN_FACE_EDGE_VERTEX:
467  this->dilateVoxels26();
468  break;
469  case NN_FACE:
470  default:
471  this->dilateVoxels6();
472  }
473  }
474 }
475 
476 
477 template<typename TreeType>
478 inline void
480 {
482  const int leafCount = static_cast<int>(mManager->leafCount());
483 
484  // Save the value masks of all leaf nodes.
485  std::vector<MaskType> savedMasks(leafCount);
486  this->copyMasks(savedMasks, *mManager);
487  LeafCache cache(7, mManager->tree());
488  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
489  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
490  cache[0] = &mManager->leaf(leafIdx);
491  cache.setOrigin(cache[0]->origin());
492  for (int x = 0; x < LEAF_DIM; ++x ) {
493  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
494  // Extract the portion of the original mask that corresponds to a row in z.
495  if (const Word w = oldMask.template getWord<Word>(n)) {
496 
497  // Dilate the current leaf in the +z and -z direction
498  cache.mask = Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
499 
500  // Dilate into neighbor leaf in the -z direction
501  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
502  cache.template scatter< 0, 0,-1>(1, n);
503  }
504  // Dilate into neighbor leaf in the +z direction
505  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
506  cache.template scatter< 0, 0, 1>(2, n);
507  }
508  // Dilate in the xy-face directions relative to the center leaf
509  cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
510  }
511  }// loop over y
512  }//loop over x
513  cache.clear();
514  }//loop over leafs
515 
516  mManager->rebuildLeafArray();
517 }//dilateVoxels6
518 
519 
520 template<typename TreeType>
521 inline void
523 {
525  const int leafCount = static_cast<int>(mManager->leafCount());
526 
527  // Save the value masks of all leaf nodes.
528  std::vector<MaskType> savedMasks(leafCount);
529  this->copyMasks(savedMasks, *mManager);
530  LeafCache cache(19, mManager->tree());
531  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
532  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
533  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
534  cache[0] = &mManager->leaf(leafIdx);
535  orig_mz = cache[0]->origin().offsetBy(0, 0, -LEAF_DIM);
536  orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
537  for (int x = 0; x < LEAF_DIM; ++x ) {
538  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
539  if (const Word w = oldMask.template getWord<Word>(n)) {
540  {
541  cache.mask = Word(w | (w>>1) | (w<<1));
542  cache.setOrigin(cache[0]->origin());
543  cache.scatter(0, n);
544  cache.scatterFacesXY(x, y, 0, n, 3);
545  cache.mask = w;
546  cache.scatterEdgesXY(x, y, 0, n, 3);
547  }
548  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
549  cache.setOrigin(cache[0]->origin());
550  cache.template scatter< 0, 0,-1>(1, n);
551  cache.setOrigin(orig_mz);
552  cache.scatterFacesXY(x, y, 1, n, 11);
553  }
554  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
555  cache.setOrigin(cache[0]->origin());
556  cache.template scatter< 0, 0, 1>(2, n);
557  cache.setOrigin(orig_pz);
558  cache.scatterFacesXY(x, y, 2, n, 15);
559  }
560  }
561  }// loop over y
562  }//loop over x
563  cache.clear();
564  }//loop over leafs
565 
566  mManager->rebuildLeafArray();
567 }// dilateVoxels18
568 
569 
570 template<typename TreeType>
571 inline void
573 {
574  const int leafCount = static_cast<int>(mManager->leafCount());
575 
576  // Save the value masks of all leaf nodes.
577  std::vector<MaskType> savedMasks(leafCount);
578  this->copyMasks(savedMasks, *mManager);
579  LeafCache cache(27, mManager->tree());
580  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
581  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
582  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
583  cache[0] = &mManager->leaf(leafIdx);
584  orig_mz = cache[0]->origin().offsetBy(0, 0, -LEAF_DIM);
585  orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
586  for (int x = 0; x < LEAF_DIM; ++x ) {
587  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
588  if (const Word w = oldMask.template getWord<Word>(n)) {
589  {
590  cache.mask = Word(w | (w>>1) | (w<<1));
591  cache.setOrigin(cache[0]->origin());
592  cache.scatter(0, n);
593  cache.scatterFacesXY(x, y, 0, n, 3);
594  cache.scatterEdgesXY(x, y, 0, n, 3);
595  }
596  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
597  cache.setOrigin(cache[0]->origin());
598  cache.template scatter< 0, 0,-1>(1, n);
599  cache.setOrigin(orig_mz);
600  cache.scatterFacesXY(x, y, 1, n, 11);
601  cache.scatterEdgesXY(x, y, 1, n, 11);
602  }
603  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
604  cache.setOrigin(cache[0]->origin());
605  cache.template scatter< 0, 0, 1>(2, n);
606  cache.setOrigin(orig_pz);
607  cache.scatterFacesXY(x, y, 2, n, 19);
608  cache.scatterEdgesXY(x, y, 2, n, 19);
609  }
610  }
611  }// loop over y
612  }//loop over x
613  cache.clear();
614  }//loop over leafs
615 
616  mManager->rebuildLeafArray();
617 }// dilateVoxels26
618 
619 
620 template<typename TreeType>
621 inline void
622 Morphology<TreeType>::LeafCache::scatterFacesXY(int x, int y, int i1, int n, int i2)
623 {
624  // dilate current leaf or neighbor in the -x direction
625  if (x > 0) {
626  this->scatter(i1, n-LEAF_DIM);
627  } else {
628  this->template scatter<-1, 0, 0>(i2, n);
629  }
630  // dilate current leaf or neighbor in the +x direction
631  if (x < LEAF_DIM-1) {
632  this->scatter(i1, n+LEAF_DIM);
633  } else {
634  this->template scatter< 1, 0, 0>(i2+1, n);
635  }
636  // dilate current leaf or neighbor in the -y direction
637  if (y > 0) {
638  this->scatter(i1, n-1);
639  } else {
640  this->template scatter< 0,-1, 0>(i2+2, n);
641  }
642  // dilate current leaf or neighbor in the +y direction
643  if (y < LEAF_DIM-1) {
644  this->scatter(i1, n+1);
645  } else {
646  this->template scatter< 0, 1, 0>(i2+3, n);
647  }
648 }
649 
650 
651 template<typename TreeType>
652 inline void
653 Morphology<TreeType>::LeafCache::scatterEdgesXY(int x, int y, int i1, int n, int i2)
654 {
655  if (x > 0) {
656  if (y > 0) {
657  this->scatter(i1, n-LEAF_DIM-1);
658  } else {
659  this->template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
660  }
661  if (y < LEAF_DIM-1) {
662  this->scatter(i1, n-LEAF_DIM+1);
663  } else {
664  this->template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
665  }
666  } else {
667  if (y < LEAF_DIM-1) {
668  this->template scatter<-1, 0, 0>(i2 , n+1);
669  } else {
670  this->template scatter<-1, 1, 0>(i2+7, n );
671  }
672  if (y > 0) {
673  this->template scatter<-1, 0, 0>(i2 , n-1);
674  } else {
675  this->template scatter<-1,-1, 0>(i2+4, n );
676  }
677  }
678  if (x < LEAF_DIM-1) {
679  if (y > 0) {
680  this->scatter(i1, n+LEAF_DIM-1);
681  } else {
682  this->template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
683  }
684  if (y < LEAF_DIM-1) {
685  this->scatter(i1, n+LEAF_DIM+1);
686  } else {
687  this->template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
688  }
689  } else {
690  if (y > 0) {
691  this->template scatter< 1, 0, 0>(i2+1, n-1);
692  } else {
693  this->template scatter< 1,-1, 0>(i2+6, n );
694  }
695  if (y < LEAF_DIM-1) {
696  this->template scatter< 1, 0, 0>(i2+1, n+1);
697  } else {
698  this->template scatter< 1, 1, 0>(i2+5, n );
699  }
700  }
701 }
702 
703 
704 template<typename TreeType>
705 inline void
707 {
708  namespace ph = std::placeholders;
709  switch (nn) {
710  case NN_FACE_EDGE:
711  mTask = std::bind(&ErodeVoxelsOp::erode18, ph::_1, ph::_2);
712  break;
713  case NN_FACE_EDGE_VERTEX:
714  mTask = std::bind(&ErodeVoxelsOp::erode26, ph::_1, ph::_2);
715  break;
716  case NN_FACE:
717  default:
718  mTask = std::bind(&ErodeVoxelsOp::erode6, ph::_1, ph::_2);
719  }
720  tbb::parallel_for(mManager.getRange(), *this);
721 }
722 
723 
724 template<typename TreeType>
725 inline typename Morphology<TreeType>::Word
726 Morphology<TreeType>::LeafCache::gatherFacesXY(int x, int y, int i1, int n, int i2)
727 {
728  // erode current leaf or neighbor in negative x-direction
729  Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->template gather<-1,0,0>(i2, n);
730 
731  // erode current leaf or neighbor in positive x-direction
732  w = Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->template gather<1,0,0>(i2+1,n)));
733 
734  // erode current leaf or neighbor in negative y-direction
735  w = Word(w & (y>0 ? this->gather(i1, n-1) : this->template gather<0,-1,0>(i2+2, n)));
736 
737  // erode current leaf or neighbor in positive y-direction
738  w = Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->template gather<0,1,0>(i2+3, n)));
739 
740  return w;
741 }
742 
743 
744 template<typename TreeType>
745 inline typename Morphology<TreeType>::Word
746 Morphology<TreeType>::LeafCache::gatherEdgesXY(int x, int y, int i1, int n, int i2)
747 {
748  Word w = ~Word(0);
749 
750  if (x > 0) {
751  w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
752  this->template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
753  w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
754  this->template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
755  } else {
756  w &= y < LEAF_DIM-1 ? this->template gather<-1, 0, 0>(i2 , n+1):
757  this->template gather<-1, 1, 0>(i2+7, n );
758  w &= y > 0 ? this->template gather<-1, 0, 0>(i2 , n-1):
759  this->template gather<-1,-1, 0>(i2+4, n );
760  }
761  if (x < LEAF_DIM-1) {
762  w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
763  this->template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
764  w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
765  this->template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
766  } else {
767  w &= y > 0 ? this->template gather< 1, 0, 0>(i2+1, n-1):
768  this->template gather< 1,-1, 0>(i2+6, n );
769  w &= y < LEAF_DIM-1 ? this->template gather< 1, 0, 0>(i2+1, n+1):
770  this->template gather< 1, 1, 0>(i2+5, n );
771  }
772 
773  return w;
774 }
775 
776 
777 template <typename TreeType>
778 inline void
780 {
781  LeafCache cache(7, mManager.tree());
782  for (size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
783  cache[0] = &mManager.leaf(leafIdx);
784  if (cache[0]->isEmpty()) continue;
785  cache.setOrigin(cache[0]->origin());
786  MaskType& newMask = mSavedMasks[leafIdx];//original bit-mask of current leaf node
787  for (int x = 0; x < LEAF_DIM; ++x ) {
788  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
789  // Extract the portion of the original mask that corresponds to a row in z.
790  if (Word& w = newMask.template getWord<Word>(n)) {
791 
792  // erode in two z directions (this is first since it uses the original w)
793  w = Word(w &
794  (Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
795  Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
796 
797  w = Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
798  }
799  }// loop over y
800  }//loop over x
801  cache.clear();
802  }//loop over leafs
803 }
804 
805 
806 template <typename TreeType>
807 inline void
809 {
810  OPENVDB_THROW(NotImplementedError, "tools::erode18 is not implemented yet!");
811 }
812 
813 
814 template <typename TreeType>
815 inline void
817 {
818  OPENVDB_THROW(NotImplementedError, "tools::erode26 is not implemented yet!");
819 }
820 
821 
822 template<typename TreeType>
823 inline void
825 {
827  const size_t leafCount = mManager->leafCount();
828 
829  // Save the value masks of all leaf nodes.
830  std::vector<MaskType> savedMasks(leafCount);
831  this->copyMasks(savedMasks, *mManager);
832  UpdateMasks a(savedMasks, *mManager);
833  ErodeVoxelsOp erode(savedMasks, *mManager);
834 
835  for (int i = 0; i < mSteps; ++i) {
836  erode.runParallel(nn);
837  a.update();
838  }
839 
840  tools::pruneLevelSet(mManager->tree());
841 }
842 
843 
845 
846 
847 template<typename TreeType>
850 {
851  if (iterations > 0 ) {
852  Morphology<TreeType> m(&manager);
853  m.dilateVoxels(iterations, nn);
854  }
855 }
856 
857 template<typename TreeType>
859 dilateVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
860 {
861  if (iterations > 0 ) {
862  Morphology<TreeType> m(tree);
863  m.dilateVoxels(iterations, nn);
864  }
865 }
866 
867 template<typename TreeType>
870 {
871  if (iterations > 0 ) {
872  Morphology<TreeType> m(&manager);
873  m.erodeVoxels(iterations, nn);
874  }
875 }
876 
877 template<typename TreeType>
879 erodeVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
880 {
881  if (iterations > 0 ) {
882  Morphology<TreeType> m(tree);
883  m.erodeVoxels(iterations, nn);
884  }
885 }
886 
887 
889 
890 
891 namespace activation {
892 
893 template<typename TreeType>
895 {
896 public:
897  using ValueT = typename TreeType::ValueType;
898 
899  ActivationOp(bool state, const ValueT& val, const ValueT& tol)
900  : mActivate(state)
901  , mValue(val)
902  , mTolerance(tol)
903  {}
904 
905  void operator()(const typename TreeType::ValueOnIter& it) const
906  {
907  if (math::isApproxEqual(*it, mValue, mTolerance)) {
908  it.setValueOff();
909  }
910  }
911 
912  void operator()(const typename TreeType::ValueOffIter& it) const
913  {
914  if (math::isApproxEqual(*it, mValue, mTolerance)) {
915  it.setActiveState(/*on=*/true);
916  }
917  }
918 
919  void operator()(const typename TreeType::LeafIter& lit) const
920  {
921  using LeafT = typename TreeType::LeafNodeType;
922  LeafT& leaf = *lit;
923  if (mActivate) {
924  for (typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
925  if (math::isApproxEqual(*it, mValue, mTolerance)) {
926  leaf.setValueOn(it.pos());
927  }
928  }
929  } else {
930  for (typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
931  if (math::isApproxEqual(*it, mValue, mTolerance)) {
932  leaf.setValueOff(it.pos());
933  }
934  }
935  }
936  }
937 
938 private:
939  bool mActivate;
940  const ValueT mValue, mTolerance;
941 }; // class ActivationOp
942 
943 } // namespace activation
944 
945 
946 template<typename GridOrTree>
947 inline void
948 activate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
949  const typename GridOrTree::ValueType& tolerance)
950 {
951  using Adapter = TreeAdapter<GridOrTree>;
952  using TreeType = typename Adapter::TreeType;
953 
954  TreeType& tree = Adapter::tree(gridOrTree);
955 
956  activation::ActivationOp<TreeType> op(/*activate=*/true, value, tolerance);
957 
958  // Process all leaf nodes in parallel.
959  foreach(tree.beginLeaf(), op);
960 
961  // Process all other inactive values serially (because changing active states
962  // is not thread-safe unless no two threads modify the same node).
963  typename TreeType::ValueOffIter it = tree.beginValueOff();
964  it.setMaxDepth(tree.treeDepth() - 2);
965  foreach(it, op, /*threaded=*/false);
966 }
967 
968 
969 template<typename GridOrTree>
970 inline void
971 deactivate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
972  const typename GridOrTree::ValueType& tolerance)
973 {
974  using Adapter = TreeAdapter<GridOrTree>;
975  using TreeType = typename Adapter::TreeType;
976 
977  TreeType& tree = Adapter::tree(gridOrTree);
978 
979  activation::ActivationOp<TreeType> op(/*activate=*/false, value, tolerance);
980 
981  // Process all leaf nodes in parallel.
982  foreach(tree.beginLeaf(), op);
983 
984  // Process all other active values serially (because changing active states
985  // is not thread-safe unless no two threads modify the same node).
986  typename TreeType::ValueOnIter it = tree.beginValueOn();
987  it.setMaxDepth(tree.treeDepth() - 2);
988  foreach(it, op, /*threaded=*/false);
989 }
990 
993 template<typename TreeT>
995 {
996  using MaskT = typename TreeT::template ValueConverter<ValueMask>::Type;
997  using PoolT = tbb::enumerable_thread_specific<MaskT>;
998  using LeafT = typename MaskT::LeafNodeType;
999 
1000  // Very light-weight member data
1001  const int mIter;// number of iterations
1002  const tools::NearestNeighbors mNN;//enum to specify the dilation scheme
1003  PoolT *mPool;// pointer to the thread-local pool of mask trees
1004  LeafT **mLeafs;// raw array of pointers to leaf nodes
1005 
1006 public:
1007 
1008  DilationOp(TreeT &tree, int iterations, NearestNeighbors nn, TilePolicy mode)
1009  : mIter(iterations), mNN(nn), mPool(nullptr), mLeafs(nullptr)
1010  {
1011  const size_t numLeafs = this->init( tree, mode );
1012  const size_t numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
1013  const size_t grainSize = math::Max(size_t(1), numLeafs/(2*numThreads));
1014 
1015  MaskT mask;
1016  PoolT pool(mask);// Scoped thread-local storage of mask trees
1017  mPool = &pool;
1018 
1019  tbb::parallel_for(tbb::blocked_range<LeafT**>(mLeafs, mLeafs+numLeafs, grainSize), *this);
1020 
1021  delete [] mLeafs;// no more need for the array of leaf node pointers
1022 
1023  using IterT = typename PoolT::iterator;
1024  for (IterT it=pool.begin(); it!=pool.end(); ++it) mask.merge(*it);// fast stealing
1025 
1026  if (mode == PRESERVE_TILES) tools::prune(mask);//multithreaded
1027 
1028  tree.topologyUnion(mask);//multithreaded
1029  }
1030 
1031  // This is required by tbb and should never be called directly
1032  void operator()(const tbb::blocked_range<LeafT**> &r) const
1033  {
1034  MaskT mask;// thread-local temporary mask tree
1035  for (LeafT** it=r.begin(); it!=r.end(); ++it) mask.addLeaf( *it );
1036  tree::LeafManager<MaskT> manager(mask, r.begin(), r.end());
1037  tools::dilateVoxels(manager, mIter, mNN);// serial dilation of active voxels
1038  mPool->local().merge(mask, MERGE_ACTIVE_STATES);
1039  }
1040 private:
1041 
1042  // Simple wrapper of a raw double-pointer to mimic a std container
1043  struct MyArray {
1044  using value_type = LeafT*;//required by Tree::stealNodes
1045  value_type* ptr;
1046  MyArray(value_type* array) : ptr(array) {}
1047  void push_back(value_type leaf) { *ptr++ = leaf; }//required by Tree::stealNodes
1048  };
1049 
1050  // Convert active tiles to leafs and de-construct the tree into a linear array of leafs.
1051  size_t linearize(MaskT& mask, TilePolicy mode)
1052  {
1053  if (mode != IGNORE_TILES) mask.voxelizeActiveTiles();//lightweight since this is a mask tree
1054  const size_t numLeafs = mask.leafCount();
1055  mLeafs = new LeafT*[numLeafs];// fast pre-allocation
1056  MyArray tmp(mLeafs);
1057  mask.stealNodes(tmp);// serializes the mask tree and leaves it empty
1058  return numLeafs;
1059  }
1060 
1061  template<typename T>
1062  typename std::enable_if<std::is_same<T, MaskT>::value, size_t>::type
1063  init(T& tree, TilePolicy mode)
1064  {
1065  return this->linearize(tree, mode);
1066  }
1067 
1068  template<typename T>
1069  typename std::enable_if<!std::is_same<T, MaskT>::value, size_t>::type
1070  init(const T& tree, TilePolicy mode)
1071  {
1072  MaskT mask(tree, false, true, TopologyCopy());
1073  return this->linearize(mask, mode);
1074  }
1075 
1076 };// DilationOp
1077 
1078 template<typename TreeType>
1080 dilateActiveValues(TreeType& tree, int iterations, NearestNeighbors nn, TilePolicy mode)
1081 {
1082  if (iterations > 0 ) DilationOp<TreeType> tmp(tree, iterations, nn, mode);
1083 }
1084 
1085 template<typename TreeType>
1088  int iterations,
1089  NearestNeighbors nn,
1090  TilePolicy mode)
1091 {
1092  if (iterations > 0 ) {
1093  DilationOp<TreeType> tmp(manager.tree(), iterations, nn, mode);
1094  manager.rebuildLeafArray();
1095  }
1096 }
1097 
1098 } // namespace tools
1099 } // namespace OPENVDB_VERSION_NAME
1100 } // namespace openvdb
1101 
1102 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
1103 
1104 // Copyright (c) DreamWorks Animation LLC
1105 // All rights reserved. This software is distributed under the
1106 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void scatter(int n, int indx)
Definition: Morphology.h:351
void save()
Definition: Morphology.h:413
const Type & Max(const Type &a, const Type &b)
Return the maximum of two values.
Definition: Math.h:569
void erodeVoxels18()
Face- and edge-adjacent erosion pattern.
Definition: Morphology.h:268
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:315
Neighbor()
Definition: Morphology.h:298
Morphology(ManagerType *mgr)
Definition: Morphology.h:253
Definition: Morphology.h:102
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Definition: Morphology.h:87
Word gather(int n, int indx)
Definition: Morphology.h:366
void clear()
Definition: Morphology.h:299
typename LeafType::NodeMaskType MaskType
Definition: Morphology.h:282
const ManagerType & mManager
Definition: Morphology.h:451
TilePolicy
Different policies when dilating trees with active tiles.
Definition: Morphology.h:102
Word mask
Definition: Morphology.h:390
void scatter(int n, int indx)
Definition: Morphology.h:345
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Morphology.h:415
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:361
NearestNeighbors
Voxel topology of nearest neighbors.
Definition: Morphology.h:87
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:386
UpdateMasks(const std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:434
void dilateVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:459
void setOrigin(const Coord &xyz)
Definition: Morphology.h:344
void clear()
Definition: Morphology.h:343
uint32_t Type
Definition: Morphology.h:238
void copyMasks(std::vector< MaskType > &a, const ManagerType &b)
Definition: Morphology.h:453
ManagerType * mManager
Definition: Morphology.h:286
void operator()(const RangeT &r) const
Definition: Morphology.h:398
AccessorType mAcc
Definition: Morphology.h:287
ErodeVoxelsOp(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:395
void operator()(const typename TreeType::LeafIter &lit) const
Definition: Morphology.h:919
Defined various multi-threaded utility functions for trees.
Word gather(AccessorType &acc, const Coord &xyz, int indx)
Definition: Morphology.h:317
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:437
void erodeVoxels26()
Face-, edge- and vertex-adjacent erosion pattern.
Definition: Morphology.h:270
LeafType ** leafs
Definition: Morphology.h:387
LeafType *& operator[](int offset)
Definition: Morphology.h:342
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:342
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:750
Definition: Morphology.h:294
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:235
ManagerType & mManager
Definition: Morphology.h:441
Definition: Types.h:556
void operator()(const tbb::blocked_range< LeafT ** > &r) const
Definition: Morphology.h:1032
~LeafCache()
Definition: Morphology.h:341
CopyMasks(std::vector< MaskType > &masks, const ManagerType &manager)
Definition: Morphology.h:444
typename TreeType::LeafNodeType LeafType
Definition: Morphology.h:281
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:971
void erodeVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:271
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
bool init
Definition: Morphology.h:296
Morphology(TreeType &tree)
Definition: Morphology.h:251
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:1087
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:416
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:447
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:417
ActivationOp(bool state, const ValueT &val, const ValueT &tol)
Definition: Morphology.h:899
void operator()(const typename TreeType::ValueOnIter &it) const
Definition: Morphology.h:905
uint16_t Type
Definition: Morphology.h:237
DilationOp(TreeT &tree, int iterations, NearestNeighbors nn, TilePolicy mode)
Definition: Morphology.h:1008
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:378
Definition: Exceptions.h:40
Definition: Morphology.h:102
tbb::blocked_range< size_t > RangeT
Definition: Morphology.h:394
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:358
typename TreeType::ValueType ValueT
Definition: Morphology.h:897
void scatter(AccessorType &acc, const Coord &xyz, int indx, Word mask)
Definition: Morphology.h:301
std::vector< MaskType > & mMasks
Definition: Morphology.h:450
typename DimToWord< LEAF_LOG2DIM >::Type Word
Definition: Morphology.h:292
AccessorType acc
Definition: Morphology.h:389
Class that performs multi-threaded dilation with support for active tiles.
Definition: Morphology.h:994
void runParallel(NearestNeighbors nn)
Definition: Morphology.h:706
virtual ~Morphology()
Definition: Morphology.h:255
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:849
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:264
int mSteps
Definition: Morphology.h:288
void update()
Definition: Morphology.h:436
const bool mOwnsManager
Definition: Morphology.h:285
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
void operator()(const typename TreeType::ValueOffIter &it) const
Definition: Morphology.h:912
Definition: Morphology.h:102
#define OPENVDB_STATIC_SPECIALIZATION
Macro for determining if there are sufficient C++0x/C++11 features.
Definition: Platform.h:111
void erodeVoxels6()
Face-adjacent erosion pattern.
Definition: Morphology.h:266
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:948
const std::vector< MaskType > & mMasks
Definition: Morphology.h:440
uint64_t Type
Definition: Morphology.h:239
uint8_t Type
Definition: Morphology.h:236
size_t size
Definition: Morphology.h:386
Definition: Exceptions.h:88
Definition: Morphology.h:246
LeafType * leaf
Definition: Morphology.h:295
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1076
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
bool isOn
Definition: Morphology.h:297
Word gather(int n, int indx)
Definition: Morphology.h:360
Definition: Morphology.h:87
MaskManager(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:410
void update()
Definition: Morphology.h:414
LeafType onTile
Definition: Morphology.h:388
const Coord * origin
Definition: Morphology.h:385
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:382
void copy()
Definition: Morphology.h:446
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:869
LeafCache(size_t n, TreeType &tree)
Definition: Morphology.h:336