OpenVDB  2.0.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/tree/TreeIterator.h>
38 #include <openvdb/tree/ValueAccessor.h>
39 #include <openvdb/tree/LeafManager.h>
40 
41 namespace openvdb {
43 namespace OPENVDB_VERSION_NAME {
44 namespace tools {
45 
47 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
53 inline void dilateVoxels(TreeType& tree, int count=1);
54 
55 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
56 inline void dilateVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
58 
60 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
66 inline void erodeVoxels(TreeType& tree, int count=1);
67 
68 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
69 inline void erodeVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
71 
73 
74 
76 template<Index Log2Dim> struct DimToWord {};
77 template<> struct DimToWord<3> { typedef uint8_t Type; };
78 template<> struct DimToWord<4> { typedef uint16_t Type; };
79 template<> struct DimToWord<5> { typedef uint32_t Type; };
80 template<> struct DimToWord<6> { typedef uint64_t Type; };
81 
82 
84 
85 
86 template<typename TreeType>
88 {
89 public:
91 
92  Morphology(TreeType& tree):
93  mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree), mSteps(1) {}
95  mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()), mSteps(1) {}
96  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
97  void dilateVoxels();
98  void dilateVoxels(int count) { for (int i=0; i<count; ++i) this->dilateVoxels(); }
99  void erodeVoxels(int count = 1) { mSteps = count; this->doErosion(); }
100 
101 private:
102  void doErosion();
103 
104  typedef typename TreeType::LeafNodeType LeafType;
105  typedef typename LeafType::NodeMaskType MaskType;
106  typedef tree::ValueAccessor<TreeType> AccessorType;
107 
108  const bool mOwnsManager;
109  ManagerType* mManager;
110  AccessorType mAcc;
111  int mSteps;
112 
113  static const int LEAF_DIM = LeafType::DIM;
114  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
115  typedef typename DimToWord<LEAF_LOG2DIM>::Type Word;
116 
117  struct Neighbor {
118  LeafType* leaf;//null if a tile
119  bool init;//true if initialization is required
120  bool isOn;//true if an active tile
121  Neighbor() : leaf(NULL), init(true) {}
122  inline void clear() { init = true; }
123  template<int DX, int DY, int DZ>
124  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word oldWord)
125  {
126  if (init) {
127  init = false;
128  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
129  leaf = acc.probeLeaf(orig);
130  if (leaf==NULL && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
131  }
132  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
133  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= oldWord;
134  }
135  template<int DX, int DY, int DZ>
136  Word gather(AccessorType& acc, const Coord &xyz, int indx)
137  {
138  if (init) {
139  init = false;
140  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
141  leaf = acc.probeLeaf(orig);
142  isOn = leaf ? false : acc.isValueOn(orig);
143  }
144  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
145  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N)
146  : isOn ? ~Word(0) : Word(0);
147  }
148  };// Neighbor
149 
150 
151  struct ErodeVoxelsOp {
152  ErodeVoxelsOp(std::vector<MaskType>& masks, ManagerType& manager)
153  : mSavedMasks(masks) , mManager(manager) {}
154 
155  void runParallel() { tbb::parallel_for(mManager.getRange(), *this); }
156  void operator()(const tbb::blocked_range<size_t>& range) const;
157 
158  private:
159  std::vector<MaskType>& mSavedMasks;
160  ManagerType& mManager;
161  };// ErodeVoxelsOp
162 
163 
164  struct MaskManager {
165  MaskManager(std::vector<MaskType>& masks, ManagerType& manager)
166  : mMasks(masks) , mManager(manager), mSaveMasks(true) {}
167 
168  void save() { mSaveMasks = true; tbb::parallel_for(mManager.getRange(), *this); }
169  void update() { mSaveMasks = false; tbb::parallel_for(mManager.getRange(), *this); }
170  void operator()(const tbb::blocked_range<size_t>& range) const
171  {
172  if (mSaveMasks) {
173  for (size_t i = range.begin(); i < range.end(); ++i) {
174  mMasks[i] = mManager.leaf(i).getValueMask();
175  }
176  } else {
177  for (size_t i = range.begin(); i < range.end(); ++i) {
178  mManager.leaf(i).setValueMask(mMasks[i]);
179  }
180  }
181  }
182 
183  private:
184  std::vector<MaskType>& mMasks;
185  ManagerType& mManager;
186  bool mSaveMasks;
187  };// MaskManager
188 };
189 
190 
191 template<typename TreeType>
192 void
194 {
196  const int leafCount = mManager->leafCount();
197 
198  // Save the value masks of all leaf nodes.
199  std::vector<MaskType> savedMasks(leafCount);
200  MaskManager masks(savedMasks, *mManager);
201  masks.save();
202 
203  Neighbor NN[6];
204  Coord origin;
205  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
206  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
207  LeafType& leaf = mManager->leaf(leafIdx);//current leaf node
208  leaf.getOrigin(origin);// origin of the current leaf node.
209  for (int x = 0; x < LEAF_DIM; ++x ) {
210  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
211  // Extract the portion of the original mask that corresponds to a row in z.
212  const Word oldWord = oldMask.template getWord<Word>(n);
213  if (oldWord == 0) continue; // no active voxels
214 
215  // dilate current leaf or neighbor in negative x-direction
216  if (x > 0) {
217  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM) |= oldWord;
218  } else {
219  NN[0].template scatter<-1, 0, 0>(mAcc, origin, n, oldWord);
220  }
221  // dilate current leaf or neighbor in positive x-direction
222  if (x < LEAF_DIM - 1) {
223  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM) |= oldWord;
224  } else {
225  NN[1].template scatter< 1, 0, 0>(mAcc, origin, n, oldWord);
226  }
227  // dilate current leaf or neighbor in negative y-direction
228  if (y > 0) {
229  leaf.getValueMask().template getWord<Word>(n-1) |= oldWord;
230  } else {
231  NN[2].template scatter< 0,-1, 0>(mAcc, origin, n, oldWord);
232  }
233  // dilate current leaf or neighbor in positive y-direction
234  if (y < LEAF_DIM - 1) {
235  leaf.getValueMask().template getWord<Word>(n+1) |= oldWord;
236  } else {
237  NN[3].template scatter< 0, 1, 0>(mAcc, origin, n, oldWord);
238  }
239  // Dilate the current leaf node in the z direction by ORing its mask
240  // with itself shifted first left and then right by one bit.
241  leaf.getValueMask().template getWord<Word>(n) |= (oldWord >> 1) | (oldWord << 1);
242  // dilate neighbor in negative z-direction
243  if (Word w = oldWord<<(LEAF_DIM-1)) {
244  NN[4].template scatter< 0, 0,-1>(mAcc, origin, n, w);
245  }
246  // dilate neighbot in positive z-direction
247  if (Word w = oldWord>>(LEAF_DIM-1)) {
248  NN[5].template scatter< 0, 0, 1>(mAcc, origin, n, w);
249  }
250  }// loop over y
251  }//loop over x
252  for (int i=0; i<6; ++i) NN[i].clear();
253  }//loop over leafs
254 
255  mManager->rebuildLeafArray();
256 }
257 
258 
259 template <typename TreeType>
260 void
261 Morphology<TreeType>::ErodeVoxelsOp::operator()(const tbb::blocked_range<size_t>& range) const
262 {
263  AccessorType acc(mManager.tree());
264  Neighbor NN[6];
265  Coord origin;
266  for (size_t leafIdx = range.begin(); leafIdx < range.end(); ++leafIdx) {
267  LeafType& leaf = mManager.leaf(leafIdx);//current leaf node
268  if (leaf.isEmpty()) continue;
269  MaskType& newMask = mSavedMasks[leafIdx];//original bit-mask of current leaf node
270  leaf.getOrigin(origin);// origin of the current leaf node.
271  for (int x = 0; x < LEAF_DIM; ++x ) {
272  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
273  // Extract the portion of the original mask that corresponds to a row in z.
274  Word& w = newMask.template getWord<Word>(n);
275  if (w == 0) continue; // no active voxels
276 
277  // Erode in two z directions (this is first since it uses the original w)
278  w &= (w<<1 | (NN[4].template gather<0,0,-1>(acc, origin, n)>>(LEAF_DIM-1))) &
279  (w>>1 | (NN[5].template gather<0,0, 1>(acc, origin, n)<<(LEAF_DIM-1)));
280 
281  // dilate current leaf or neighbor in negative x-direction
282  w &= (x == 0) ? NN[0].template gather<-1, 0, 0>(acc, origin, n) :
283  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM);
284 
285  // dilate current leaf or neighbor in positive x-direction
286  w &= (x == LEAF_DIM-1) ? NN[1].template gather< 1, 0, 0>(acc, origin, n) :
287  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM);
288 
289  // dilate current leaf or neighbor in negative y-direction
290  w &= (y == 0) ? NN[2].template gather< 0,-1, 0>(acc, origin, n) :
291  leaf.getValueMask().template getWord<Word>(n-1);
292 
293  // dilate current leaf or neighbor in positive y-direction
294  w &= (y == LEAF_DIM-1) ? NN[3].template gather< 0, 1, 0>(acc, origin, n) :
295  leaf.getValueMask().template getWord<Word>(n+1);
296  }// loop over y
297  }//loop over x
298  for (int i=0; i<6; ++i) NN[i].clear();
299  }//loop over leafs
300 }
301 
302 
303 template<typename TreeType>
304 void
305 Morphology<TreeType>::doErosion()
306 {
308  const int leafCount = mManager->leafCount();
309 
310  // Save the value masks of all leaf nodes.
311  std::vector<MaskType> savedMasks(leafCount);
312  MaskManager masks(savedMasks, *mManager);
313  masks.save();
314 
315  ErodeVoxelsOp erode(savedMasks, *mManager);
316  for (int i = 0; i < mSteps; ++i) {
317  erode.runParallel();
318  masks.update();
319  }
320 
321  mManager->tree().pruneLevelSet();
322 }
323 
324 
326 
327 
328 template<typename TreeType>
331 {
332  Morphology<TreeType> m(&manager);
333  m.dilateVoxels(count);
334 }
335 
336 template<typename TreeType>
338 dilateVoxels(TreeType& tree, int count)
339 {
340  Morphology<TreeType> m(tree);
341  m.dilateVoxels(count);
342 }
343 
344 template<typename TreeType>
347 {
348  Morphology<TreeType> m(&manager);
349  m.erodeVoxels(count);
350 }
351 
352 template<typename TreeType>
354 erodeVoxels(TreeType& tree, int count)
355 {
356  Morphology<TreeType> m(tree);
357  m.erodeVoxels(count);
358 }
359 
360 } // namespace tools
361 } // namespace OPENVDB_VERSION_NAME
362 } // namespace openvdb
363 
364 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
365 
366 // Copyright (c) 2012-2013 DreamWorks Animation LLC
367 // All rights reserved. This software is distributed under the
368 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
Mapping from a Log2Dim to a data type of size 2^Log2Dim bits.
Definition: Morphology.h:76
uint16_t Type
Definition: Morphology.h:78
void dilateVoxels()
Definition: Morphology.h:193
uint64_t Type
Definition: Morphology.h:80
AccessorT mAcc
Definition: GridOperators.h:259
OPENVDB_STATIC_SPECIALIZATION void dilateVoxels(TreeType &tree, int count=1)
Definition: Morphology.h:338
OPENVDB_STATIC_SPECIALIZATION void erodeVoxels(TreeType &tree, int count=1)
Definition: Morphology.h:354
Morphology(TreeType &tree)
Definition: Morphology.h:92
#define OPENVDB_VERSION_NAME
Definition: version.h:45
Definition: Morphology.h:87
void erodeVoxels(int count=1)
Definition: Morphology.h:99
virtual ~Morphology()
Definition: Morphology.h:96
tree::LeafManager< TreeType > ManagerType
Definition: Morphology.h:90
uint8_t Type
Definition: Morphology.h:77
uint32_t Type
Definition: Morphology.h:79
#define OPENVDB_STATIC_SPECIALIZATION
Definition: Platform.h:64
Morphology(ManagerType *mgr)
Definition: Morphology.h:94
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:56
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 dilateVoxels(int count)
Definition: Morphology.h:98