OpenVDB  1.1.0
Morphology.h
Go to the documentation of this file.
1 
2 //
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 
42 namespace openvdb {
44 namespace OPENVDB_VERSION_NAME {
45 namespace tools {
46 
48 
49 
50 
51 
52 
53 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
54 inline void dilateVoxels(TreeType& tree, int count=1);
55 
56 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
57 inline void dilateVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
59 
61 
62 
63 
64 
65 
66 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
67 inline void erodeVoxels(TreeType& tree, int count=1);
68 
69 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
70 inline void erodeVoxels(tree::LeafManager<TreeType>& manager, int count = 1);
72 
74 
76 template<Index Log2Dim> struct DimToWord { typedef uint8_t Type[0]; };
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; };
82 
83 template<typename TreeType>
85 {
86  public:
87 
89 
90  Morphology(TreeType& tree) : mOwnsManager(true), mManager(new ManagerType(tree)), mAcc(tree) {}
91  Morphology(ManagerType* mgr) : mOwnsManager(false), mManager(mgr), mAcc(mgr->tree()) {}
92  virtual ~Morphology() { if (mOwnsManager) delete mManager; }
93  void dilateVoxels();
94  void dilateVoxels(int count) { for (int i=0; i<count; ++i) this->dilateVoxels(); }
95  void erodeVoxels();
96  void erodeVoxels(int count) { for (int i=0; i<count; ++i) this->erodeVoxels(); }
97  private:
98 
99  typedef typename TreeType::LeafNodeType LeafType;
100  typedef typename LeafType::NodeMaskType MaskType;
101  typedef tree::ValueAccessor<TreeType> AccessorType;
102 
103  const bool mOwnsManager;
104  ManagerType* mManager;
105  AccessorType mAcc;
106 
107  static const int LEAF_DIM = LeafType::DIM;
108  static const int LEAF_LOG2DIM = LeafType::LOG2DIM;
109  typedef typename DimToWord<LEAF_LOG2DIM>::Type Word;
110 
111  struct Neighbor {
112  LeafType* leaf;//null if a tile
113  bool init;//true if initialization is required
114  bool isOn;//true if an active tile
115  static const Word OFF = Word(0), ON = ~OFF;
116  Neighbor() : leaf(NULL), init(true) {}
117  inline void clear() { init = true; }
118  template<int DX, int DY, int DZ>
119  void scatter(AccessorType& acc, const Coord &xyz, int indx, Word oldWord)
120  {
121  if (init) {
122  init = false;
123  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
124  leaf = acc.probeLeaf(orig);
125  if (leaf==NULL && !acc.isValueOn(orig)) leaf = acc.touchLeaf(orig);
126  }
127  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
128  if (leaf) leaf->getValueMask().template getWord<Word>(indx-N) |= oldWord;
129  }
130  template<int DX, int DY, int DZ>
131  Word gather(AccessorType& acc, const Coord &xyz, int indx)
132  {
133  if (init) {
134  init = false;
135  Coord orig = xyz.offsetBy(DX*LEAF_DIM, DY*LEAF_DIM, DZ*LEAF_DIM);
136  leaf = acc.probeLeaf(orig);
137  isOn = leaf ? false : acc.isValueOn(orig);
138  }
139  static const int N = (LEAF_DIM -1 )*(DY + DX*LEAF_DIM);
140  return leaf ? leaf->getValueMask().template getWord<Word>(indx-N) : isOn ? ON : OFF;
141  }
142  };// Neighbor
143 };
144 
145 template <typename TreeType>
147 {
149  const int leafCount = mManager->leafCount();
150 
151  // Save the value masks of all leaf nodes.
152  std::vector<MaskType> savedMasks;
153  savedMasks.resize(leafCount);
154  for (int i = 0; i < leafCount; ++i) savedMasks[i] = mManager->leaf(i).getValueMask();
155 
156  Neighbor NN[6];
157  Coord origin;
158  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
159  const MaskType& oldMask = savedMasks[leafIdx];//original bit-mask of current leaf node
160  LeafType& leaf = mManager->leaf(leafIdx);//current leaf node
161  leaf.getOrigin(origin);// origin of the current leaf node.
162  for (int x = 0; x < LEAF_DIM; ++x ) {
163  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
164  // Extract the portion of the original mask that corresponds to a row in z.
165  const Word oldWord = oldMask.template getWord<Word>(n);
166  if (oldWord == 0) continue; // no active voxels
167 
168  // dilate current leaf or neighbor in negative x-direction
169  if (x > 0) {
170  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM) |= oldWord;
171  } else {
172  NN[0].template scatter<-1, 0, 0>(mAcc, origin, n, oldWord);
173  }
174  // dilate current leaf or neighbor in positive x-direction
175  if (x < LEAF_DIM - 1) {
176  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM) |= oldWord;
177  } else {
178  NN[1].template scatter< 1, 0, 0>(mAcc, origin, n, oldWord);
179  }
180  // dilate current leaf or neighbor in negative y-direction
181  if (y > 0) {
182  leaf.getValueMask().template getWord<Word>(n-1) |= oldWord;
183  } else {
184  NN[2].template scatter< 0,-1, 0>(mAcc, origin, n, oldWord);
185  }
186  // dilate current leaf or neighbor in positive y-direction
187  if (y < LEAF_DIM - 1) {
188  leaf.getValueMask().template getWord<Word>(n+1) |= oldWord;
189  } else {
190  NN[3].template scatter< 0, 1, 0>(mAcc, origin, n, oldWord);
191  }
192  // Dilate the current leaf node in the z direction by ORing its mask
193  // with itself shifted first left and then right by one bit.
194  leaf.getValueMask().template getWord<Word>(n) |= (oldWord >> 1) | (oldWord << 1);
195  // dilate neighbor in negative z-direction
196  if (Word w = oldWord<<(LEAF_DIM-1)) {
197  NN[4].template scatter< 0, 0,-1>(mAcc, origin, n, w);
198  }
199  // dilate neighbot in positive z-direction
200  if (Word w = oldWord>>(LEAF_DIM-1)) {
201  NN[5].template scatter< 0, 0, 1>(mAcc, origin, n, w);
202  }
203  }// loop over y
204  }//loop over x
205  for (int i=0; i<6; ++i) NN[i].clear();
206  }//loop over leafs
207 
208  mManager->rebuildLeafArray();
209 }
210 
211 template <typename TreeType>
213 {
215  const int leafCount = mManager->leafCount();
216 
217  // Save the value masks of all leaf nodes.
218  std::vector<MaskType> savedMasks;
219  savedMasks.resize(leafCount);
220  for (int i = 0; i < leafCount; ++i) savedMasks[i] = mManager->leaf(i).getValueMask();
221 
222  Neighbor NN[6];
223  Coord origin;
224  for (int leafIdx = 0; leafIdx < leafCount; ++leafIdx) {
225  MaskType& newMask = savedMasks[leafIdx];//original bit-mask of current leaf node
226  LeafType& leaf = mManager->leaf(leafIdx);//current leaf node
227  leaf.getOrigin(origin);// origin of the current leaf node.
228  for (int x = 0; x < LEAF_DIM; ++x ) {
229  for (int y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
230  // Extract the portion of the original mask that corresponds to a row in z.
231  Word& w = newMask.template getWord<Word>(n);
232  if (w == 0) continue; // no active voxels
233 
234  // Erode in two z directions (this is first since it uses the original w)
235  w &= (w<<1 | (NN[4].template gather<0,0,-1>(mAcc, origin, n)>>(LEAF_DIM-1))) &
236  (w>>1 | (NN[5].template gather<0,0, 1>(mAcc, origin, n)<<(LEAF_DIM-1)));
237 
238  // dilate current leaf or neighbor in negative x-direction
239  w &= (x == 0) ? NN[0].template gather<-1, 0, 0>(mAcc, origin, n) :
240  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM);
241 
242  // dilate current leaf or neighbor in positive x-direction
243  w &= (x == LEAF_DIM-1) ? NN[1].template gather< 1, 0, 0>(mAcc, origin, n) :
244  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM);
245 
246  // dilate current leaf or neighbor in negative y-direction
247  w &= (y == 0) ? NN[2].template gather< 0,-1, 0>(mAcc, origin, n) :
248  leaf.getValueMask().template getWord<Word>(n-1);
249 
250  // dilate current leaf or neighbor in positive y-direction
251  w &= (y == LEAF_DIM-1) ? NN[3].template gather< 0, 1, 0>(mAcc, origin, n) :
252  leaf.getValueMask().template getWord<Word>(n+1);
253  }// loop over y
254  }//loop over x
255  for (int i=0; i<6; ++i) NN[i].clear();
256  }//loop over leafs
257 
258  for (int i = 0; i < leafCount; ++i) mManager->leaf(i).setValueMask(savedMasks[i]);
259 
260  mManager->tree().pruneLevelSet();
261 
262  mManager->rebuildLeafArray();
263 }
264 
265 
267 
268 
269 template<typename TreeType>
272 {
273  Morphology<TreeType> m(&manager);
274  m.dilateVoxels(count);
275 }
276 
277 template<typename TreeType>
279 dilateVoxels(TreeType& tree, int count)
280 {
281  Morphology<TreeType> m(tree);
282  m.dilateVoxels(count);
283 }
284 
285 template<typename TreeType>
288 {
289  Morphology<TreeType> m(&manager);
290  m.erodeVoxels(count);
291 }
292 
293 template<typename TreeType>
295 erodeVoxels(TreeType& tree, int count)
296 {
297  Morphology<TreeType> m(tree);
298  m.erodeVoxels(count);
299 }
300 
301 } // namespace tools
302 } // namespace OPENVDB_VERSION_NAME
303 } // namespace openvdb
304 
305 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
306 
307 // Copyright (c) 2012-2013 DreamWorks Animation LLC
308 // All rights reserved. This software is distributed under the
309 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )