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