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