OpenVDB  3.1.0
Morphology.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2015 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()
52 #include <openvdb/tree/TreeIterator.h>
53 #include <openvdb/tree/ValueAccessor.h>
54 #include <openvdb/tree/LeafManager.h>
55 #include <boost/scoped_array.hpp>
56 #include <boost/bind.hpp>
57 #include "Prune.h"// for pruneLevelSet
58 #include "ValueTransformer.h" // for foreach()
59 
60 namespace openvdb {
62 namespace OPENVDB_VERSION_NAME {
63 namespace tools {
64 
82 
83 
96 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
97 inline void dilateVoxels(TreeType& tree,
98  int iterations = 1,
100 
113 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
114 inline void dilateVoxels(tree::LeafManager<TreeType>& manager,
115  int iterations = 1,
117 
118 
120 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
126 inline void erodeVoxels(TreeType& tree,
127  int iterations=1,
129 
130 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
131 inline void erodeVoxels(tree::LeafManager<TreeType>& manager,
132  int iterations = 1,
135 
136 
139 template<typename GridOrTree>
140 inline void activate(
141  GridOrTree&,
142  const typename GridOrTree::ValueType& value,
143  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
144 );
145 
146 
149 template<typename GridOrTree>
150 inline void deactivate(
151  GridOrTree&,
152  const typename GridOrTree::ValueType& value,
153  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
154 );
155 
156 
158 
159 
161 template<Index Log2Dim> struct DimToWord {};
162 template<> struct DimToWord<3> { typedef uint8_t Type; };
163 template<> struct DimToWord<4> { typedef uint16_t Type; };
164 template<> struct DimToWord<5> { typedef uint32_t Type; };
165 template<> struct DimToWord<6> { typedef uint64_t Type; };
166 
167 
169 
170 
171 template<typename TreeType>
173 {
174 public:
176 
177  Morphology(TreeType& tree):
178  mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
179  Morphology(ManagerType* mgr):
180  mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
181  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
182 
184  void dilateVoxels6();
186  void dilateVoxels18();
188  void dilateVoxels26();
189  void dilateVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE);
190 
192  void erodeVoxels6() { mSteps = 1; this->doErosion(NN_FACE); }
194  void erodeVoxels18() { mSteps = 1; this->doErosion(NN_FACE_EDGE); }
196  void erodeVoxels26() { mSteps = 1; this->doErosion(NN_FACE_EDGE_VERTEX); }
197  void erodeVoxels(int iterations = 1, NearestNeighbors nn = NN_FACE)
198  {
199  mSteps = iterations;
200  this->doErosion(nn);
201  }
202 
203 protected:
204 
205  void doErosion(NearestNeighbors nn);
206 
207  typedef typename TreeType::LeafNodeType LeafType;
208  typedef typename LeafType::NodeMaskType MaskType;
210 
211  const bool mOwnsManager;
212  ManagerType* mManager;
213  AccessorType mAcc;
214  int mSteps;
215 
216  static const int LEAF_DIM = LeafType::DIM;
217  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
219 
220  struct Neighbor {
221  LeafType* leaf;//null if a tile
222  bool init;//true if initialization is required
223  bool isOn;//true if an active tile
224  Neighbor() : leaf(NULL), init(true) {}
225  inline void clear() { leaf = NULL; init = true; }
226  template<int DX, int DY, int DZ>
227  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word mask)
228  {
229  if (init) {
230  init = false;
231  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
232  leaf = acc.probeLeaf(orig);
233  if (leaf==NULL && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
234  }
235 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
236  static
237 #endif
238  const int N = (LEAF_DIM - 1)*(DY + DX*LEAF_DIM);
239  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= mask;
240  }
241 
242  template<int DX, int DY, int DZ>
243  Word gather(AccessorType& acc, const Coord &xyz, int indx)
244  {
245  if (init) {
246  init = false;
247  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
248  leaf = acc.probeLeaf(orig);
249  isOn = leaf ? false : acc.isValueOn(orig);
250  }
251 #ifndef _MSC_VER // Visual C++ doesn't guarantee thread-safe initialization of local statics
252  static
253 #endif
254  const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
255  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
256  : isOn ? ~Word(0) : Word(0);
257  }
258  };// Neighbor
259 
260  struct LeafCache
261  {
262  LeafCache(size_t n, TreeType& tree) : size(n), leafs(new LeafType*[n]), acc(tree)
263  {
264  onTile.setValuesOn();
265  this->clear();
266  }
267  ~LeafCache() { delete [] leafs; }
268  LeafType*& operator[](int offset) { return leafs[offset]; }
269  inline void clear() { for (size_t i=0; i<size; ++i) leafs[i]=NULL; }
270  inline void setOrigin(const Coord& xyz) { origin = &xyz; }
271  inline void scatter(int n, int indx)
272  {
273  assert(leafs[n]);
274  leafs[n]->getValueMask().template getWord<Word>(indx) |= mask;
275  }
276  template<int DX, int DY, int DZ>
277  inline void scatter(int n, int indx)
278  {
279  if (!leafs[n]) {
280  const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
281  leafs[n] = acc.probeLeaf(xyz);
282  if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : acc.touchLeaf(xyz);
283  }
284  this->scatter(n, indx - (LEAF_DIM - 1)*(DY + DX*LEAF_DIM));
285  }
286  inline Word gather(int n, int indx)
287  {
288  assert(leafs[n]);
289  return leafs[n]->getValueMask().template getWord<Word>(indx);
290  }
291  template<int DX, int DY, int DZ>
292  inline Word gather(int n, int indx)
293  {
294  if (!leafs[n]) {
295  const Coord xyz = origin->offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
296  leafs[n] = acc.probeLeaf(xyz);
297  if (!leafs[n]) leafs[n] = acc.isValueOn(xyz) ? &onTile : &offTile;
298  }
299  return this->gather(n, indx - (LEAF_DIM -1 )*(DY + DX*LEAF_DIM));
300  }
301  // Scatters in the xy face-directions relative to leaf i1
302  void scatterFacesXY(int x, int y, int i1, int n, int i2);
303 
304  // Scatters in the xy edge-directions relative to leaf i1
305  void scatterEdgesXY(int x, int y, int i1, int n, int i2);
306 
307  Word gatherFacesXY(int x, int y, int i1, int n, int i2);
308 
309  Word gatherEdgesXY(int x, int y, int i1, int n, int i2);
310 
311  const Coord* origin;
312  size_t size;
313  LeafType** leafs;
314  LeafType onTile, offTile;
315  AccessorType acc;
316  Word mask;
317  };// LeafCache
318 
319  struct ErodeVoxelsOp {
320  typedef tbb::blocked_range<size_t> RangeT;
321  ErodeVoxelsOp(std::vector<MaskType>& masks, ManagerType& manager)
322  : mTask(0), mSavedMasks(masks) , mManager(manager) {}
323  void runParallel(NearestNeighbors nn);
324  void operator()(const RangeT& r) const {mTask(const_cast<ErodeVoxelsOp*>(this), r);}
325  void erode6( const RangeT&) const;
326  void erode18(const RangeT&) const;
327  void erode26(const RangeT&) const;
328  private:
329  typedef typename boost::function<void (ErodeVoxelsOp*, const RangeT&)> FuncT;
330  FuncT mTask;
331  std::vector<MaskType>& mSavedMasks;
332  ManagerType& mManager;
333  };// ErodeVoxelsOp
334 
335  struct MaskManager {
336  MaskManager(std::vector<MaskType>& masks, ManagerType& manager)
337  : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
338 
339  void save() { mSaveMasks = true; tbb::parallel_for(mManager.getRange(), *this); }
340  void update() { mSaveMasks = false; tbb::parallel_for(mManager.getRange(), *this); }
341  void operator()(const tbb::blocked_range<size_t>& range) const
342  {
343  if (mSaveMasks) {
344  for (size_t i = range.begin(); i < range.end(); ++i) {
345  mMasks[i] = mManager.leaf(i).getValueMask();
346  }
347  } else {
348  for (size_t i = range.begin(); i < range.end(); ++i) {
349  mManager.leaf(i).setValueMask(mMasks[i]);
350  }
351  }
352  }
353  private:
354  std::vector<MaskType>& mMasks;
355  ManagerType& mManager;
356  bool mSaveMasks;
357  };// MaskManager
358 
359  struct UpdateMasks {
360  UpdateMasks(const std::vector<MaskType>& masks, ManagerType& manager)
361  : mMasks(masks), mManager(manager) {}
362  void update() { tbb::parallel_for(mManager.getRange(), *this); }
363  void operator()(const tbb::blocked_range<size_t>& r) const {
364  for (size_t i=r.begin(); i<r.end(); ++i) mManager.leaf(i).setValueMask(mMasks[i]);
365  }
366  const std::vector<MaskType>& mMasks;
367  ManagerType& mManager;
368  };
369  struct CopyMasks {
370  CopyMasks(std::vector<MaskType>& masks, const ManagerType& manager)
371  : mMasks(masks), mManager(manager) {}
372  void copy() { tbb::parallel_for(mManager.getRange(), *this); }
373  void operator()(const tbb::blocked_range<size_t>& r) const {
374  for (size_t i=r.begin(); i<r.end(); ++i) mMasks[i]=mManager.leaf(i).getValueMask();
375  }
376  std::vector<MaskType>& mMasks;
377  const ManagerType& mManager;
378  };
379  void copyMasks(std::vector<MaskType>& a, const ManagerType& b) {CopyMasks c(a, b); c.copy();}
380 };// Morphology
381 
382 
383 template<typename TreeType>
384 inline void
386 {
387  for (int i=0; i<iterations; ++i) {
388  switch (nn) {
389  case NN_FACE_EDGE: this->dilateVoxels18(); break;
390  case NN_FACE_EDGE_VERTEX: this->dilateVoxels26(); break;
391  default: this->dilateVoxels6();
392  }
393  }
394 }
395 
396 
397 template<typename TreeType>
398 inline void
400 {
402  const int leafCount = static_cast<int>(mManager->leafCount());
403 
404  // Save the value masks of all leaf nodes.
405  std::vector<MaskType> savedMasks(leafCount);
406  this->copyMasks(savedMasks, *mManager);
407  LeafCache cache(7, mManager->tree());
408  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
409  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
410  cache[0] = &mManager->leaf(leafIdx);
411  cache.setOrigin(cache[0]->origin());
412  for (int x = 0; x < LEAF_DIM; ++x ) {
413  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
414  // Extract the portion of the original mask that corresponds to a row in z.
415  if (const Word w = oldMask.template getWord<Word>(n)) {
416 
417  // Dilate the current leaf in the +z and -z direction
418  cache.mask = Word(w | (w>>1) | (w<<1)); cache.scatter(0, n);
419 
420  // Dilate into neighbor leaf in the -z direction
421  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
422  cache.template scatter< 0, 0,-1>(1, n);
423  }
424  // Dilate into neighbor leaf in the +z direction
425  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
426  cache.template scatter< 0, 0, 1>(2, n);
427  }
428  // Dilate in the xy-face directions relative to the center leaf
429  cache.mask = w; cache.scatterFacesXY(x, y, 0, n, 3);
430  }
431  }// loop over y
432  }//loop over x
433  cache.clear();
434  }//loop over leafs
435 
436  mManager->rebuildLeafArray();
437 }//dilateVoxels6
438 
439 
440 template<typename TreeType>
441 inline void
443 {
445  const int leafCount = static_cast<int>(mManager->leafCount());
446 
447  // Save the value masks of all leaf nodes.
448  std::vector<MaskType> savedMasks(leafCount);
449  this->copyMasks(savedMasks, *mManager);
450  LeafCache cache(19, mManager->tree());
451  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
452  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
453  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
454  cache[0] = &mManager->leaf(leafIdx);
455  orig_mz = cache[0]->origin().offsetBy(0, 0, -LEAF_DIM);
456  orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
457  for (int x = 0; x < LEAF_DIM; ++x ) {
458  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
459  if (const Word w = oldMask.template getWord<Word>(n)) {
460  {
461  cache.mask = Word(w | (w>>1) | (w<<1));
462  cache.setOrigin(cache[0]->origin());
463  cache.scatter(0, n);
464  cache.scatterFacesXY(x, y, 0, n, 3);
465  cache.mask = w;
466  cache.scatterEdgesXY(x, y, 0, n, 3);
467  }
468  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
469  cache.setOrigin(cache[0]->origin());
470  cache.template scatter< 0, 0,-1>(1, n);
471  cache.setOrigin(orig_mz);
472  cache.scatterFacesXY(x, y, 1, n, 11);
473  }
474  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
475  cache.setOrigin(cache[0]->origin());
476  cache.template scatter< 0, 0, 1>(2, n);
477  cache.setOrigin(orig_pz);
478  cache.scatterFacesXY(x, y, 2, n, 15);
479  }
480  }
481  }// loop over y
482  }//loop over x
483  cache.clear();
484  }//loop over leafs
485 
486  mManager->rebuildLeafArray();
487 }// dilateVoxels18
488 
489 
490 template<typename TreeType>
491 inline void
493 {
495  const int leafCount = static_cast<int>(mManager->leafCount());
496 
497  // Save the value masks of all leaf nodes.
498  std::vector<MaskType> savedMasks(leafCount);
499  this->copyMasks(savedMasks, *mManager);
500  LeafCache cache(27, mManager->tree());
501  Coord orig_mz, orig_pz;//origins of neighbor leaf nodes in the -z and +z directions
502  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
503  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
504  cache[0] = &mManager->leaf(leafIdx);
505  orig_mz = cache[0]->origin().offsetBy(0, 0, -LEAF_DIM);
506  orig_pz = cache[0]->origin().offsetBy(0, 0, LEAF_DIM);
507  for (int x = 0; x < LEAF_DIM; ++x ) {
508  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
509  if (const Word w = oldMask.template getWord<Word>(n)) {
510  {
511  cache.mask = Word(w | (w>>1) | (w<<1));
512  cache.setOrigin(cache[0]->origin());
513  cache.scatter(0, n);
514  cache.scatterFacesXY(x, y, 0, n, 3);
515  cache.scatterEdgesXY(x, y, 0, n, 3);
516  }
517  if ( (cache.mask = Word(w<<(LEAF_DIM-1))) ) {
518  cache.setOrigin(cache[0]->origin());
519  cache.template scatter< 0, 0,-1>(1, n);
520  cache.setOrigin(orig_mz);
521  cache.scatterFacesXY(x, y, 1, n, 11);
522  cache.scatterEdgesXY(x, y, 1, n, 11);
523  }
524  if ( (cache.mask = Word(w>>(LEAF_DIM-1))) ) {
525  cache.setOrigin(cache[0]->origin());
526  cache.template scatter< 0, 0, 1>(2, n);
527  cache.setOrigin(orig_pz);
528  cache.scatterFacesXY(x, y, 2, n, 19);
529  cache.scatterEdgesXY(x, y, 2, n, 19);
530  }
531  }
532  }// loop over y
533  }//loop over x
534  cache.clear();
535  }//loop over leafs
536 
537  mManager->rebuildLeafArray();
538 }// dilateVoxels26
539 
540 
541 template<typename TreeType>
542 inline void
543 Morphology<TreeType>::LeafCache::scatterFacesXY(int x, int y, int i1, int n, int i2)
544 {
545  // dilate current leaf or neighbor in the -x direction
546  if (x > 0) {
547  this->scatter(i1, n-LEAF_DIM);
548  } else {
549  this->template scatter<-1, 0, 0>(i2, n);
550  }
551  // dilate current leaf or neighbor in the +x direction
552  if (x < LEAF_DIM-1) {
553  this->scatter(i1, n+LEAF_DIM);
554  } else {
555  this->template scatter< 1, 0, 0>(i2+1, n);
556  }
557  // dilate current leaf or neighbor in the -y direction
558  if (y > 0) {
559  this->scatter(i1, n-1);
560  } else {
561  this->template scatter< 0,-1, 0>(i2+2, n);
562  }
563  // dilate current leaf or neighbor in the +y direction
564  if (y < LEAF_DIM-1) {
565  this->scatter(i1, n+1);
566  } else {
567  this->template scatter< 0, 1, 0>(i2+3, n);
568  }
569 }
570 
571 
572 template<typename TreeType>
573 inline void
574 Morphology<TreeType>::LeafCache::scatterEdgesXY(int x, int y, int i1, int n, int i2)
575 {
576  if (x > 0) {
577  if (y > 0) {
578  this->scatter(i1, n-LEAF_DIM-1);
579  } else {
580  this->template scatter< 0,-1, 0>(i2+2, n-LEAF_DIM);
581  }
582  if (y < LEAF_DIM-1) {
583  this->scatter(i1, n-LEAF_DIM+1);
584  } else {
585  this->template scatter< 0, 1, 0>(i2+3, n-LEAF_DIM);
586  }
587  } else {
588  if (y < LEAF_DIM-1) {
589  this->template scatter<-1, 0, 0>(i2 , n+1);
590  } else {
591  this->template scatter<-1, 1, 0>(i2+7, n );
592  }
593  if (y > 0) {
594  this->template scatter<-1, 0, 0>(i2 , n-1);
595  } else {
596  this->template scatter<-1,-1, 0>(i2+4, n );
597  }
598  }
599  if (x < LEAF_DIM-1) {
600  if (y > 0) {
601  this->scatter(i1, n+LEAF_DIM-1);
602  } else {
603  this->template scatter< 0,-1, 0>(i2+2, n+LEAF_DIM);
604  }
605  if (y < LEAF_DIM-1) {
606  this->scatter(i1, n+LEAF_DIM+1);
607  } else {
608  this->template scatter< 0, 1, 0>(i2+3, n+LEAF_DIM);
609  }
610  } else {
611  if (y > 0) {
612  this->template scatter< 1, 0, 0>(i2+1, n-1);
613  } else {
614  this->template scatter< 1,-1, 0>(i2+6, n );
615  }
616  if (y < LEAF_DIM-1) {
617  this->template scatter< 1, 0, 0>(i2+1, n+1);
618  } else {
619  this->template scatter< 1, 1, 0>(i2+5, n );
620  }
621  }
622 }
623 
624 
625 template<typename TreeType>
626 inline void
628 {
629  switch (nn) {
630  case NN_FACE_EDGE:
631  mTask = boost::bind(&ErodeVoxelsOp::erode18, _1, _2);
632  break;
633  case NN_FACE_EDGE_VERTEX:
634  mTask = boost::bind(&ErodeVoxelsOp::erode26, _1, _2);
635  break;
636  default:
637  mTask = boost::bind(&ErodeVoxelsOp::erode6, _1, _2);
638  }
639  tbb::parallel_for(mManager.getRange(), *this);
640 }
641 
642 
643 template<typename TreeType>
644 inline typename Morphology<TreeType>::Word
645 Morphology<TreeType>::LeafCache::gatherFacesXY(int x, int y, int i1, int n, int i2)
646 {
647  // erode current leaf or neighbor in negative x-direction
648  Word w = x>0 ? this->gather(i1,n-LEAF_DIM) : this->template gather<-1,0,0>(i2, n);
649 
650  // erode current leaf or neighbor in positive x-direction
651  w = Word(w & (x<LEAF_DIM-1?this->gather(i1,n+LEAF_DIM):this->template gather<1,0,0>(i2+1,n)));
652 
653  // erode current leaf or neighbor in negative y-direction
654  w = Word(w & (y>0 ? this->gather(i1, n-1) : this->template gather<0,-1,0>(i2+2, n)));
655 
656  // erode current leaf or neighbor in positive y-direction
657  w = Word(w & (y<LEAF_DIM-1 ? this->gather(i1, n+1) : this->template gather<0,1,0>(i2+3, n)));
658 
659  return w;
660 }
661 
662 
663 template<typename TreeType>
664 inline typename Morphology<TreeType>::Word
665 Morphology<TreeType>::LeafCache::gatherEdgesXY(int x, int y, int i1, int n, int i2)
666 {
667  Word w = ~Word(0);
668 
669  if (x > 0) {
670  w &= y > 0 ? this->gather(i1, n-LEAF_DIM-1) :
671  this->template gather< 0,-1, 0>(i2+2, n-LEAF_DIM);
672  w &= y < LEAF_DIM-1 ? this->gather(i1, n-LEAF_DIM+1) :
673  this->template gather< 0, 1, 0>(i2+3, n-LEAF_DIM);
674  } else {
675  w &= y < LEAF_DIM-1 ? this->template gather<-1, 0, 0>(i2 , n+1):
676  this->template gather<-1, 1, 0>(i2+7, n );
677  w &= y > 0 ? this->template gather<-1, 0, 0>(i2 , n-1):
678  this->template gather<-1,-1, 0>(i2+4, n );
679  }
680  if (x < LEAF_DIM-1) {
681  w &= y > 0 ? this->gather(i1, n+LEAF_DIM-1) :
682  this->template gather< 0,-1, 0>(i2+2, n+LEAF_DIM);
683  w &= y < LEAF_DIM-1 ? this->gather(i1, n+LEAF_DIM+1) :
684  this->template gather< 0, 1, 0>(i2+3, n+LEAF_DIM);
685  } else {
686  w &= y > 0 ? this->template gather< 1, 0, 0>(i2+1, n-1):
687  this->template gather< 1,-1, 0>(i2+6, n );
688  w &= y < LEAF_DIM-1 ? this->template gather< 1, 0, 0>(i2+1, n+1):
689  this->template gather< 1, 1, 0>(i2+5, n );
690  }
691 
692  return w;
693 }
694 
695 
696 template <typename TreeType>
697 inline void
699 {
700  LeafCache cache(7, mManager.tree());
701  for (size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
702  cache[0] = &mManager.leaf(leafIdx);
703  if (cache[0]->isEmpty()) continue;
704  cache.setOrigin(cache[0]->origin());
705  MaskType& newMask = mSavedMasks[leafIdx];//original bit-mask of current leaf node
706  for (int x = 0; x < LEAF_DIM; ++x ) {
707  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
708  // Extract the portion of the original mask that corresponds to a row in z.
709  if (Word& w = newMask.template getWord<Word>(n)) {
710 
711  // erode in two z directions (this is first since it uses the original w)
712  w = Word(w &
713  (Word(w<<1 | (cache.template gather<0,0,-1>(1, n)>>(LEAF_DIM-1))) &
714  Word(w>>1 | (cache.template gather<0,0, 1>(2, n)<<(LEAF_DIM-1)))));
715 
716  w = Word(w & cache.gatherFacesXY(x, y, 0, n, 3));
717  }
718  }// loop over y
719  }//loop over x
720  cache.clear();
721  }//loop over leafs
722 }
723 
724 
725 template <typename TreeType>
726 inline void
728 {
729  OPENVDB_THROW(NotImplementedError, "tools::erode18 is not implemented yet!");
730 }
731 
732 
733 template <typename TreeType>
734 inline void
736 {
737  OPENVDB_THROW(NotImplementedError, "tools::erode26 is not implemented yet!");
738 }
739 
740 
741 template<typename TreeType>
742 inline void
744 {
746  const size_t leafCount = mManager->leafCount();
747 
748  // Save the value masks of all leaf nodes.
749  std::vector<MaskType> savedMasks(leafCount);
750  this->copyMasks(savedMasks, *mManager);
751  UpdateMasks a(savedMasks, *mManager);
752  ErodeVoxelsOp erode(savedMasks, *mManager);
753 
754  for (int i = 0; i < mSteps; ++i) {
755  erode.runParallel(nn);
756  a.update();
757  }
758 
759  tools::pruneLevelSet(mManager->tree());
760 }
761 
762 
764 
765 
766 template<typename TreeType>
769 {
770  if (iterations > 0 ) {
771  Morphology<TreeType> m(&manager);
772  m.dilateVoxels(iterations, nn);
773  }
774 }
775 
776 template<typename TreeType>
778 dilateVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
779 {
780  if (iterations > 0 ) {
781  Morphology<TreeType> m(tree);
782  m.dilateVoxels(iterations, nn);
783  }
784 }
785 
786 template<typename TreeType>
789 {
790  if (iterations > 0 ) {
791  Morphology<TreeType> m(&manager);
792  m.erodeVoxels(iterations, nn);
793  }
794 }
795 
796 template<typename TreeType>
798 erodeVoxels(TreeType& tree, int iterations, NearestNeighbors nn)
799 {
800  if (iterations > 0 ) {
801  Morphology<TreeType> m(tree);
802  m.erodeVoxels(iterations, nn);
803  }
804 }
805 
806 
808 
809 
810 namespace activation {
811 
812 template<typename TreeType>
814 {
815 public:
816  typedef typename TreeType::ValueType ValueT;
817 
818  ActivationOp(bool state, const ValueT& val, const ValueT& tol)
819  : mActivate(state)
820  , mValue(val)
821  , mTolerance(tol)
822  {}
823 
824  void operator()(const typename TreeType::ValueOnIter& it) const
825  {
826  if (math::isApproxEqual(*it, mValue, mTolerance)) {
827  it.setValueOff();
828  }
829  }
830 
831  void operator()(const typename TreeType::ValueOffIter& it) const
832  {
833  if (math::isApproxEqual(*it, mValue, mTolerance)) {
834  it.setActiveState(/*on=*/true);
835  }
836  }
837 
838  void operator()(const typename TreeType::LeafIter& lit) const
839  {
840  typedef typename TreeType::LeafNodeType LeafT;
841  LeafT& leaf = *lit;
842  if (mActivate) {
843  for (typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
844  if (math::isApproxEqual(*it, mValue, mTolerance)) {
845  leaf.setValueOn(it.pos());
846  }
847  }
848  } else {
849  for (typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
850  if (math::isApproxEqual(*it, mValue, mTolerance)) {
851  leaf.setValueOff(it.pos());
852  }
853  }
854  }
855  }
856 
857 private:
858  bool mActivate;
859  const ValueT mValue, mTolerance;
860 }; // class ActivationOp
861 
862 } // namespace activation
863 
864 
865 template<typename GridOrTree>
866 inline void
867 activate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
868  const typename GridOrTree::ValueType& tolerance)
869 {
870  typedef TreeAdapter<GridOrTree> Adapter;
871  typedef typename Adapter::TreeType TreeType;
872 
873  TreeType& tree = Adapter::tree(gridOrTree);
874 
875  activation::ActivationOp<TreeType> op(/*activate=*/true, value, tolerance);
876 
877  // Process all leaf nodes in parallel.
878  foreach(tree.beginLeaf(), op);
879 
880  // Process all other inactive values serially (because changing active states
881  // is not thread-safe unless no two threads modify the same node).
882  typename TreeType::ValueOffIter it = tree.beginValueOff();
883  it.setMaxDepth(tree.treeDepth() - 2);
884  foreach(it, op, /*threaded=*/false);
885 }
886 
887 
888 template<typename GridOrTree>
889 inline void
890 deactivate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
891  const typename GridOrTree::ValueType& tolerance)
892 {
893  typedef TreeAdapter<GridOrTree> Adapter;
894  typedef typename Adapter::TreeType TreeType;
895 
896  TreeType& tree = Adapter::tree(gridOrTree);
897 
898  activation::ActivationOp<TreeType> op(/*activate=*/false, value, tolerance);
899 
900  // Process all leaf nodes in parallel.
901  foreach(tree.beginLeaf(), op);
902 
903  // Process all other active values serially (because changing active states
904  // is not thread-safe unless no two threads modify the same node).
905  typename TreeType::ValueOnIter it = tree.beginValueOn();
906  it.setMaxDepth(tree.treeDepth() - 2);
907  foreach(it, op, /*threaded=*/false);
908 }
909 
910 } // namespace tools
911 } // namespace OPENVDB_VERSION_NAME
912 } // namespace openvdb
913 
914 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
915 
916 // Copyright (c) 2012-2015 DreamWorks Animation LLC
917 // All rights reserved. This software is distributed under the
918 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
tree::ValueAccessor< TreeType > AccessorType
Definition: Morphology.h:209
tree::LeafManager< TreeType > ManagerType
Definition: Morphology.h:175
LeafNodeT * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z), or NULL if no such node exists...
Definition: ValueAccessor.h:424
const bool mOwnsManager
Definition: Morphology.h:211
NearestNeighbors
Voxel topology of nearest neighbors.
Definition: Morphology.h:81
void save()
Definition: Morphology.h:339
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Morphology.h:341
void erodeVoxels26()
Face-, edge- and vertex-adjacent erosion pattern.
Definition: Morphology.h:196
void clear()
Definition: Morphology.h:269
tbb::blocked_range< size_t > RangeT
Definition: Morphology.h:320
size_t size
Definition: Morphology.h:312
Definition: Morphology.h:172
void scatter(AccessorType &acc, const Coord &xyz, int indx, Word mask)
Definition: Morphology.h:227
void erodeVoxels6()
Face-adjacent erosion pattern.
Definition: Morphology.h:192
OPENVDB_STATIC_SPECIALIZATION 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:788
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:363
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:161
AccessorType acc
Definition: Morphology.h:315
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:114
AccessorType mAcc
Definition: Morphology.h:213
void operator()(const typename TreeType::ValueOnIter &it) const
Definition: Morphology.h:824
Word gather(int n, int indx)
Definition: Morphology.h:286
LeafType * leaf
Definition: Morphology.h:221
Morphology(TreeType &tree)
Definition: Morphology.h:177
LeafType *& operator[](int offset)
Definition: Morphology.h:268
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
TreeType::LeafNodeType LeafType
Definition: Morphology.h:207
int mSteps
Definition: Morphology.h:214
LeafType::NodeMaskType MaskType
Definition: Morphology.h:208
bool isOn
Definition: Morphology.h:223
LeafCache(size_t n, TreeType &tree)
Definition: Morphology.h:262
void operator()(const tbb::blocked_range< size_t > &r) const
Definition: Morphology.h:373
TreeType::ValueType ValueT
Definition: Morphology.h:816
Defined various multi-threaded utility functions for trees.
void copy()
Definition: Morphology.h:372
UpdateMasks(const std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:360
DimToWord< LEAF_LOG2DIM >::Type Word
Definition: Morphology.h:218
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:867
Definition: Morphology.h:81
void erodeVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:197
MaskManager(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:336
void operator()(const RangeT &r) const
Definition: Morphology.h:324
uint32_t Type
Definition: Morphology.h:164
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:323
LeafType ** leafs
Definition: Morphology.h:313
void setOrigin(const Coord &xyz)
Definition: Morphology.h:270
std::vector< MaskType > & mMasks
Definition: Morphology.h:376
const std::vector< MaskType > & mMasks
Definition: Morphology.h:366
void scatter(int n, int indx)
Definition: Morphology.h:277
Word gather(AccessorType &acc, const Coord &xyz, int indx)
Definition: Morphology.h:243
#define OPENVDB_VERSION_NAME
Definition: version.h:43
const ManagerType & mManager
Definition: Morphology.h:377
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:263
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:890
LeafType onTile
Definition: Morphology.h:314
ManagerType & mManager
Definition: Morphology.h:367
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:402
void update()
Definition: Morphology.h:340
void clear()
Definition: Morphology.h:225
Definition: Exceptions.h:39
Morphology(ManagerType *mgr)
Definition: Morphology.h:179
ActivationOp(bool state, const ValueT &val, const ValueT &tol)
Definition: Morphology.h:818
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:880
OPENVDB_STATIC_SPECIALIZATION 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:768
Word gather(int n, int indx)
Definition: Morphology.h:292
void runParallel(NearestNeighbors nn)
Definition: Morphology.h:627
bool init
Definition: Morphology.h:222
ManagerType * mManager
Definition: Morphology.h:212
Definition: Morphology.h:81
void operator()(const typename TreeType::ValueOffIter &it) const
Definition: Morphology.h:831
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
CopyMasks(std::vector< MaskType > &masks, const ManagerType &manager)
Definition: Morphology.h:370
void erodeVoxels18()
Face- and edge-adjacent erosion pattern.
Definition: Morphology.h:194
void update()
Definition: Morphology.h:362
ErodeVoxelsOp(std::vector< MaskType > &masks, ManagerType &manager)
Definition: Morphology.h:321
#define OPENVDB_STATIC_SPECIALIZATION
Macro for determining if there are sufficient C++0x/C++11 features.
Definition: Platform.h:91
Definition: Exceptions.h:84
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:347
Word mask
Definition: Morphology.h:316
void scatter(int n, int indx)
Definition: Morphology.h:271
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Neighbor()
Definition: Morphology.h:224
void operator()(const typename TreeType::LeafIter &lit) const
Definition: Morphology.h:838
uint64_t Type
Definition: Morphology.h:165
const Coord * origin
Definition: Morphology.h:311
virtual ~Morphology()
Definition: Morphology.h:181
void copyMasks(std::vector< MaskType > &a, const ManagerType &b)
Definition: Morphology.h:379
void dilateVoxels(int iterations=1, NearestNeighbors nn=NN_FACE)
Definition: Morphology.h:385
uint16_t Type
Definition: Morphology.h:163
uint8_t Type
Definition: Morphology.h:162
~LeafCache()
Definition: Morphology.h:267