OpenVDB  2.1.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"
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  Morphology<TreeType> m(&manager);
357  m.dilateVoxels(count);
358 }
359 
360 template<typename TreeType>
362 dilateVoxels(TreeType& tree, int count)
363 {
364  Morphology<TreeType> m(tree);
365  m.dilateVoxels(count);
366 }
367 
368 template<typename TreeType>
371 {
372  Morphology<TreeType> m(&manager);
373  m.erodeVoxels(count);
374 }
375 
376 template<typename TreeType>
378 erodeVoxels(TreeType& tree, int count)
379 {
380  Morphology<TreeType> m(tree);
381  m.erodeVoxels(count);
382 }
383 
384 
386 
387 
388 namespace activation {
389 
390 template<typename TreeType>
392 {
393 public:
394  typedef typename TreeType::ValueType ValueT;
395 
396  ActivationOp(bool state, const ValueT& val, const ValueT& tol)
397  : mActivate(state)
398  , mValue(val)
399  , mTolerance(tol)
400  {}
401 
402  void operator()(const typename TreeType::ValueOnIter& it) const
403  {
404  if (math::isApproxEqual(*it, mValue, mTolerance)) {
405  it.setValueOff();
406  }
407  }
408 
409  void operator()(const typename TreeType::ValueOffIter& it) const
410  {
411  if (math::isApproxEqual(*it, mValue, mTolerance)) {
412  it.setActiveState(/*on=*/true);
413  }
414  }
415 
416  void operator()(const typename TreeType::LeafIter& lit) const
417  {
418  typedef typename TreeType::LeafNodeType LeafT;
419  LeafT& leaf = *lit;
420  if (mActivate) {
421  for (typename LeafT::ValueOffIter it = leaf.beginValueOff(); it; ++it) {
422  if (math::isApproxEqual(*it, mValue, mTolerance)) {
423  leaf.setValueOn(it.pos());
424  }
425  }
426  } else {
427  for (typename LeafT::ValueOnIter it = leaf.beginValueOn(); it; ++it) {
428  if (math::isApproxEqual(*it, mValue, mTolerance)) {
429  leaf.setValueOff(it.pos());
430  }
431  }
432  }
433  }
434 
435 private:
436  bool mActivate;
437  const ValueT mValue, mTolerance;
438 }; // class ActivationOp
439 
440 } // namespace activation
441 
442 
443 template<typename GridOrTree>
444 inline void
445 activate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
446  const typename GridOrTree::ValueType& tolerance)
447 {
448  typedef TreeAdapter<GridOrTree> Adapter;
449  typedef typename Adapter::TreeType TreeType;
450 
451  TreeType& tree = Adapter::tree(gridOrTree);
452 
453  activation::ActivationOp<TreeType> op(/*activate=*/true, value, tolerance);
454 
455  // Process all leaf nodes in parallel.
456  foreach(tree.beginLeaf(), op);
457 
458  // Process all other inactive values serially (because changing active states
459  // is not thread-safe unless no two threads modify the same node).
460  typename TreeType::ValueOffIter it = tree.beginValueOff();
461  it.setMaxDepth(tree.treeDepth() - 2);
462  foreach(it, op, /*threaded=*/false);
463 }
464 
465 
466 template<typename GridOrTree>
467 inline void
468 deactivate(GridOrTree& gridOrTree, const typename GridOrTree::ValueType& value,
469  const typename GridOrTree::ValueType& tolerance)
470 {
471  typedef TreeAdapter<GridOrTree> Adapter;
472  typedef typename Adapter::TreeType TreeType;
473 
474  TreeType& tree = Adapter::tree(gridOrTree);
475 
476  activation::ActivationOp<TreeType> op(/*activate=*/false, value, tolerance);
477 
478  // Process all leaf nodes in parallel.
479  foreach(tree.beginLeaf(), op);
480 
481  // Process all other active values serially (because changing active states
482  // is not thread-safe unless no two threads modify the same node).
483  typename TreeType::ValueOnIter it = tree.beginValueOn();
484  it.setMaxDepth(tree.treeDepth() - 2);
485  foreach(it, op, /*threaded=*/false);
486 }
487 
488 } // namespace tools
489 } // namespace OPENVDB_VERSION_NAME
490 } // namespace openvdb
491 
492 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
493 
494 // Copyright (c) 2012-2013 DreamWorks Animation LLC
495 // All rights reserved. This software is distributed under the
496 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
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:468
void dilateVoxels()
Definition: Morphology.h:217
Morphology(ManagerType *mgr)
Definition: Morphology.h:118
void dilateVoxels(int count)
Definition: Morphology.h:122
OPENVDB_STATIC_SPECIALIZATION void erodeVoxels(TreeType &tree, int count=1)
Definition: Morphology.h:378
void operator()(const typename TreeType::ValueOnIter &it) const
Definition: Morphology.h:402
TreeType::ValueType ValueT
Definition: Morphology.h:394
virtual ~Morphology()
Definition: Morphology.h:120
AccessorT mAcc
Definition: GridOperators.h:383
uint64_t Type
Definition: Morphology.h:104
uint16_t Type
Definition: Morphology.h:102
tree::LeafManager< TreeType > ManagerType
Definition: Morphology.h:114
#define OPENVDB_VERSION_NAME
Definition: version.h:45
Definition: Morphology.h:111
uint8_t Type
Definition: Morphology.h:101
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:100
ActivationOp(bool state, const ValueT &val, const ValueT &tol)
Definition: Morphology.h:396
Morphology(TreeType &tree)
Definition: Morphology.h:116
void operator()(const typename TreeType::ValueOffIter &it) const
Definition: Morphology.h:409
void erodeVoxels(int count=1)
Definition: Morphology.h:123
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:445
OPENVDB_STATIC_SPECIALIZATION void dilateVoxels(TreeType &tree, int count=1)
Definition: Morphology.h:362
#define OPENVDB_STATIC_SPECIALIZATION
Definition: Platform.h:64
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:823
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
void operator()(const typename TreeType::LeafIter &lit) const
Definition: Morphology.h:416
uint32_t Type
Definition: Morphology.h:103