OpenVDB  2.3.0
Morphology.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2013 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 //
32 
33 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
34 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
35 
36 #include <openvdb/Types.h>
37 #include <openvdb/Grid.h>
38 #include <openvdb/math/Math.h> // for isApproxEqual()
39 #include <openvdb/tree/TreeIterator.h>
40 #include <openvdb/tree/ValueAccessor.h>
41 #include <openvdb/tree/LeafManager.h>
42 #include "ValueTransformer.h" // for foreach()
43 
44 namespace openvdb {
46 namespace OPENVDB_VERSION_NAME {
47 namespace tools {
48 
50 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
56 inline void dilateVoxels(TreeType& tree, int count=1);
57 
58 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
59 inline void dilateVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
61 
63 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
69 inline void erodeVoxels(TreeType& tree, int count=1);
70 
71 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
72 inline void erodeVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
74 
75 
78 template<typename GridOrTree>
79 inline void activate(
80  GridOrTree&,
81  const typename GridOrTree::ValueType& value,
82  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
83 );
84 
85 
88 template<typename GridOrTree>
89 inline void deactivate(
90  GridOrTree&,
91  const typename GridOrTree::ValueType& value,
92  const typename GridOrTree::ValueType& tolerance = zeroVal<typename GridOrTree::ValueType>()
93 );
94 
95 
97 
98 
100 template<Index Log2Dim> struct DimToWord {};
101 template<> struct DimToWord<3> { typedef uint8_t Type; };
102 template<> struct DimToWord<4> { typedef uint16_t Type; };
103 template<> struct DimToWord<5> { typedef uint32_t Type; };
104 template<> struct DimToWord<6> { typedef uint64_t Type; };
105 
106 
108 
109 
110 template<typename TreeType>
112 {
113 public:
115 
116  Morphology(TreeType& tree):
117  mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
119  mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
120  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
121  void dilateVoxels();
122  void dilateVoxels(int count) { for (int i=0; i<count; ++i) this->dilateVoxels(); }
123  void erodeVoxels(int count = 1) { mSteps = count; this->doErosion(); }
124 
125 private:
126  void doErosion();
127 
128  typedef typename TreeType::LeafNodeType LeafType;
129  typedef typename LeafType::NodeMaskType MaskType;
130  typedef tree::ValueAccessor<TreeType> AccessorType;
131 
132  const bool mOwnsManager;
133  ManagerType* mManager;
134  AccessorType mAcc;
135  int mSteps;
136 
137  static const int LEAF_DIM = LeafType::DIM;
138  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
139  typedef typename DimToWord<LEAF_LOG2DIM>::Type Word;
140 
141  struct Neighbor {
142  LeafType* leaf;//null if a tile
143  bool init;//true if initialization is required
144  bool isOn;//true if an active tile
145  Neighbor() : leaf(NULL), init(true) {}
146  inline void clear() { init = true; }
147  template<int DX, int DY, int DZ>
148  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word oldWord)
149  {
150  if (init) {
151  init = false;
152  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
153  leaf = acc.probeLeaf(orig);
154  if (leaf==NULL && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
155  }
156  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
157  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= oldWord;
158  }
159  template<int DX, int DY, int DZ>
160  Word gather(AccessorType& acc, const Coord &xyz, int indx)
161  {
162  if (init) {
163  init = false;
164  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
165  leaf = acc.probeLeaf(orig);
166  isOn = leaf ? false : acc.isValueOn(orig);
167  }
168  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
169  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
170  : isOn ? ~Word(0) : Word(0);
171  }
172  };// Neighbor
173 
174 
175  struct ErodeVoxelsOp {
176  ErodeVoxelsOp(std::vector<MaskType>& masks, ManagerType& manager)
177  : mSavedMasks(masks) , mManager(manager) {}
178 
179  void runParallel() { tbb::parallel_for(mManager.getRange(), *this); }
180  void operator()(const tbb::blocked_range<size_t>& range) const;
181 
182  private:
183  std::vector<MaskType>& mSavedMasks;
184  ManagerType& mManager;
185  };// ErodeVoxelsOp
186 
187 
188  struct MaskManager {
189  MaskManager(std::vector<MaskType>& masks, ManagerType& manager)
190  : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
191 
192  void save() { mSaveMasks = true; tbb::parallel_for(mManager.getRange(), *this); }
193  void update() { mSaveMasks = false; tbb::parallel_for(mManager.getRange(), *this); }
194  void operator()(const tbb::blocked_range<size_t>& range) const
195  {
196  if (mSaveMasks) {
197  for (size_t i = range.begin(); i < range.end(); ++i) {
198  mMasks[i] = mManager.leaf(i).getValueMask();
199  }
200  } else {
201  for (size_t i = range.begin(); i < range.end(); ++i) {
202  mManager.leaf(i).setValueMask(mMasks[i]);
203  }
204  }
205  }
206 
207  private:
208  std::vector<MaskType>& mMasks;
209  ManagerType& mManager;
210  bool mSaveMasks;
211  };// MaskManager
212 };
213 
214 
215 template<typename TreeType>
216 void
218 {
220  const int leafCount = mManager->leafCount();
221 
222  // Save the value masks of all leaf nodes.
223  std::vector<MaskType> savedMasks(leafCount);
224  MaskManager masks(savedMasks, *mManager);
225  masks.save();
226 
227  Neighbor NN[6];
228  Coord origin;
229  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
230  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
231  LeafType& leaf = mManager->leaf(leafIdx);//current leaf node
232  leaf.getOrigin(origin);// origin of the current leaf node.
233  for (int x = 0; x < LEAF_DIM; ++x ) {
234  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
235  // Extract the portion of the original mask that corresponds to a row in z.
236  const Word oldWord = oldMask.template getWord<Word>(n);
237  if (oldWord == 0) continue; // no active voxels
238 
239  // dilate current leaf or neighbor in negative x-direction
240  if (x > 0) {
241  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM) |= oldWord;
242  } else {
243  NN[0].template scatter<-1, 0, 0>(mAcc, origin, n, oldWord);
244  }
245  // dilate current leaf or neighbor in positive x-direction
246  if (x < LEAF_DIM - 1) {
247  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM) |= oldWord;
248  } else {
249  NN[1].template scatter< 1, 0, 0>(mAcc, origin, n, oldWord);
250  }
251  // dilate current leaf or neighbor in negative y-direction
252  if (y > 0) {
253  leaf.getValueMask().template getWord<Word>(n-1) |= oldWord;
254  } else {
255  NN[2].template scatter< 0,-1, 0>(mAcc, origin, n, oldWord);
256  }
257  // dilate current leaf or neighbor in positive y-direction
258  if (y < LEAF_DIM - 1) {
259  leaf.getValueMask().template getWord<Word>(n+1) |= oldWord;
260  } else {
261  NN[3].template scatter< 0, 1, 0>(mAcc, origin, n, oldWord);
262  }
263  // Dilate the current leaf node in the z direction by ORing its mask
264  // with itself shifted first left and then right by one bit.
265  leaf.getValueMask().template getWord<Word>(n) |= (oldWord >> 1) | (oldWord << 1);
266  // dilate neighbor in negative z-direction
267  if (Word w = oldWord<<(LEAF_DIM-1)) {
268  NN[4].template scatter< 0, 0,-1>(mAcc, origin, n, w);
269  }
270  // dilate neighbot in positive z-direction
271  if (Word w = oldWord>>(LEAF_DIM-1)) {
272  NN[5].template scatter< 0, 0, 1>(mAcc, origin, n, w);
273  }
274  }// loop over y
275  }//loop over x
276  for (int i=0; i<6; ++i) NN[i].clear();
277  }//loop over leafs
278 
279  mManager->rebuildLeafArray();
280 }
281 
282 
283 template <typename TreeType>
284 void
285 Morphology<TreeType>::ErodeVoxelsOp::operator()(const tbb::blocked_range<size_t>& range) const
286 {
287  AccessorType acc(mManager.tree());
288  Neighbor NN[6];
289  Coord origin;
290  for (size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
291  LeafType& leaf = mManager.leaf(leafIdx);//current leaf node
292  if (leaf.isEmpty()) continue;
293  MaskType& newMask = mSavedMasks[leafIdx];//original bit-mask of current leaf node
294  leaf.getOrigin(origin);// origin of the current leaf node.
295  for (int x = 0; x < LEAF_DIM; ++x ) {
296  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
297  // Extract the portion of the original mask that corresponds to a row in z.
298  Word& w = newMask.template getWord<Word>(n);
299  if (w == 0) continue; // no active voxels
300 
301  // Erode in two z directions (this is first since it uses the original w)
302  w &= (w<<1 | (NN[4].template gather<0,0,-1>(acc, origin, n)>>(LEAF_DIM-1))) &
303  (w>>1 | (NN[5].template gather<0,0, 1>(acc, origin, n)<<(LEAF_DIM-1)));
304 
305  // dilate current leaf or neighbor in negative x-direction
306  w &= (x == 0) ? NN[0].template gather<-1, 0, 0>(acc, origin, n) :
307  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM);
308 
309  // dilate current leaf or neighbor in positive x-direction
310  w &= (x == LEAF_DIM-1) ? NN[1].template gather< 1, 0, 0>(acc, origin, n) :
311  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM);
312 
313  // dilate current leaf or neighbor in negative y-direction
314  w &= (y == 0) ? NN[2].template gather< 0,-1, 0>(acc, origin, n) :
315  leaf.getValueMask().template getWord<Word>(n-1);
316 
317  // dilate current leaf or neighbor in positive y-direction
318  w &= (y == LEAF_DIM-1) ? NN[3].template gather< 0, 1, 0>(acc, origin, n) :
319  leaf.getValueMask().template getWord<Word>(n+1);
320  }// loop over y
321  }//loop over x
322  for (int i=0; i<6; ++i) NN[i].clear();
323  }//loop over leafs
324 }
325 
326 
327 template<typename TreeType>
328 void
329 Morphology<TreeType>::doErosion()
330 {
332  const int leafCount = mManager->leafCount();
333 
334  // Save the value masks of all leaf nodes.
335  std::vector<MaskType> savedMasks(leafCount);
336  MaskManager masks(savedMasks, *mManager);
337  masks.save();
338 
339  ErodeVoxelsOp erode(savedMasks, *mManager);
340  for (int i = 0; i < mSteps; ++i) {
341  erode.runParallel();
342  masks.update();
343  }
344 
345  mManager->tree().pruneLevelSet();
346 }
347 
348 
350 
351 
352 template<typename TreeType>
355 {
356  if (count > 0 ) {
357  Morphology<TreeType> m(&manager);
358  m.dilateVoxels(count);
359  }
360 }
361 
362 template<typename TreeType>
364 dilateVoxels(TreeType& tree, int count)
365 {
366  if (count > 0 ) {
367  Morphology<TreeType> m(tree);
368  m.dilateVoxels(count);
369  }
370 }
371 
372 template<typename TreeType>
375 {
376  if (count > 0 ) {
377  Morphology<TreeType> m(&manager);
378  m.erodeVoxels(count);
379  }
380 }
381 
382 template<typename TreeType>
384 erodeVoxels(TreeType& tree, int count)
385 {
386  if (count > 0 ) {
387  Morphology<TreeType> m(tree);
388  m.erodeVoxels(count);
389  }
390 }
391 
392 
394 
395 
396 namespace activation {
397 
398 template<typename TreeType>
400 {
401 public:
402  typedef typename TreeType::ValueType ValueT;
403 
404  ActivationOp(bool state, const ValueT& val, const ValueT& tol)
405  : mActivate(state)
406  , mValue(val)
407  , mTolerance(tol)
408  {}
409 
410  void operator()(const typename TreeType::ValueOnIter& it) const
411  {
412  if (math::isApproxEqual(*it, mValue, mTolerance)) {
413  it.setValueOff();
414  }
415  }
416 
417  void operator()(const typename TreeType::ValueOffIter& it) const
418  {
419  if (math::isApproxEqual(*it, mValue, mTolerance)) {
420  it.setActiveState(/*on=*/true);
421  }
422  }
423 
424  void operator()(const typename TreeType::LeafIter& lit) const
425  {
426  typedef typename TreeType::LeafNodeType LeafT;
427  LeafT& leaf = *lit;
428  if (mActivate) {
429  for (typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
430  if (math::isApproxEqual(*it, mValue, mTolerance)) {
431  leaf.setValueOn(it.pos());
432  }
433  }
434  } else {
435  for (typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
436  if (math::isApproxEqual(*it, mValue, mTolerance)) {
437  leaf.setValueOff(it.pos());
438  }
439  }
440  }
441  }
442 
443 private:
444  bool mActivate;
445  const ValueT mValue, mTolerance;
446 }; // class ActivationOp
447 
448 } // namespace activation
449 
450 
451 template<typename GridOrTree>
452 inline void
453 activate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
454  const typename GridOrTree::ValueType& tolerance)
455 {
456  typedef TreeAdapter<GridOrTree> Adapter;
457  typedef typename Adapter::TreeType TreeType;
458 
459  TreeType& tree = Adapter::tree(gridOrTree);
460 
461  activation::ActivationOp<TreeType> op(/*activate=*/true, value, tolerance);
462 
463  // Process all leaf nodes in parallel.
464  foreach(tree.beginLeaf(), op);
465 
466  // Process all other inactive values serially (because changing active states
467  // is not thread-safe unless no two threads modify the same node).
468  typename TreeType::ValueOffIter it = tree.beginValueOff();
469  it.setMaxDepth(tree.treeDepth() - 2);
470  foreach(it, op, /*threaded=*/false);
471 }
472 
473 
474 template<typename GridOrTree>
475 inline void
476 deactivate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
477  const typename GridOrTree::ValueType& tolerance)
478 {
479  typedef TreeAdapter<GridOrTree> Adapter;
480  typedef typename Adapter::TreeType TreeType;
481 
482  TreeType& tree = Adapter::tree(gridOrTree);
483 
484  activation::ActivationOp<TreeType> op(/*activate=*/false, value, tolerance);
485 
486  // Process all leaf nodes in parallel.
487  foreach(tree.beginLeaf(), op);
488 
489  // Process all other active values serially (because changing active states
490  // is not thread-safe unless no two threads modify the same node).
491  typename TreeType::ValueOnIter it = tree.beginValueOn();
492  it.setMaxDepth(tree.treeDepth() - 2);
493  foreach(it, op, /*threaded=*/false);
494 }
495 
496 } // namespace tools
497 } // namespace OPENVDB_VERSION_NAME
498 } // namespace openvdb
499 
500 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
501 
502 // Copyright (c) 2012-2013 DreamWorks Animation LLC
503 // All rights reserved. This software is distributed under the
504 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
tree::LeafManager< TreeType > ManagerType
Definition: Morphology.h:114
void operator()(const typename TreeType::ValueOnIter &it) const
Definition: Morphology.h:410
virtual ~Morphology()
Definition: Morphology.h:120
void operator()(const typename TreeType::ValueOffIter &it) const
Definition: Morphology.h:417
TreeType::ValueType ValueT
Definition: Morphology.h:402
void operator()(const typename TreeType::LeafIter &lit) const
Definition: Morphology.h:424
OPENVDB_STATIC_SPECIALIZATION void dilateVoxels(tree::LeafManager< TreeType > &manager, int count=1)
Definition: Morphology.h:354
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:837
Morphology(ManagerType *mgr)
Definition: Morphology.h:118
uint64_t Type
Definition: Morphology.h:104
void erodeVoxels(int count=1)
Definition: Morphology.h:123
#define OPENVDB_VERSION_NAME
Definition: version.h:45
Definition: Morphology.h:111
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:453
uint32_t Type
Definition: Morphology.h:103
ActivationOp(bool state, const ValueT &val, const ValueT &tol)
Definition: Morphology.h:404
uint8_t Type
Definition: Morphology.h:101
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:100
void dilateVoxels(int count)
Definition: Morphology.h:122
#define OPENVDB_STATIC_SPECIALIZATION
Macro for determining if there are sufficient C++0x/C++11 features.
Definition: Platform.h:89
void dilateVoxels()
Definition: Morphology.h:217
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
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:476
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
uint16_t Type
Definition: Morphology.h:102
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
OPENVDB_STATIC_SPECIALIZATION void erodeVoxels(tree::LeafManager< TreeType > &manager, int count=1)
Definition: Morphology.h:374
Morphology(TreeType &tree)
Definition: Morphology.h:116