OpenVDB  0.104.0
Morphology.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012 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 
31 #ifndef OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
32 #define OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
33 
34 #include <openvdb/Types.h>
35 #include <openvdb/tree/TreeIterator.h>
36 #include <openvdb/tree/ValueAccessor.h>
37 #include <openvdb/tree/LeafManager.h>
38 
39 
40 namespace openvdb {
42 namespace OPENVDB_VERSION_NAME {
43 namespace tools {
44 
50 template<typename TreeType> OPENVDB_STATIC_SPECIALIZATION
51 inline void dilateVoxels(TreeType& tree);
52 
58 
59 
61 
62 
64 template<Index Log2Dim> struct DimToWord { typedef uint8_t Type[0]; };
65 template<> struct DimToWord<3> { typedef uint8_t Type; };
66 template<> struct DimToWord<4> { typedef uint16_t Type; };
67 template<> struct DimToWord<5> { typedef uint32_t Type; };
68 template<> struct DimToWord<6> { typedef uint64_t Type; };
69 
70 
72 
73 
74 #undef OPENVDB_TOOLS_MORPHOLOGY_USE_WORKAROUND_FOR_BROKEN_ICC12_COMPILER
75 #ifdef __ICC
76 #if __ICC >= 1210 && __ICC < 1300
77 // ICC 12.1 generates incorrect optimized code for the following dilateVoxels() implementation.
78 // A less-efficient alternate implementation is provided instead for use with that compiler.
79 #define OPENVDB_TOOLS_MORPHOLOGY_USE_WORKAROUND_FOR_BROKEN_ICC12_COMPILER
80 #endif
81 #endif
82 
83 
84 #ifndef OPENVDB_TOOLS_MORPHOLOGY_USE_WORKAROUND_FOR_BROKEN_ICC12_COMPILER
85 
86 template<typename TreeType>
89 {
90  typedef typename TreeType::LeafNodeType LeafType;
91  typedef typename LeafType::NodeMaskType MaskType;
92  typedef tree::ValueAccessor<TreeType> Accessor;
93 
94  static const Index LEAF_DIM = LeafType::DIM;
95  static const Index LEAF_LOG2DIM = LeafType::LOG2DIM;
96 
97  typedef typename DimToWord<LEAF_LOG2DIM>::Type Word;
98 
99  Accessor acc(manager.tree());
100 
101  const Index leafCount = manager.leafCount();
102 
103  // Save the value masks of all leaf nodes.
104  std::vector<MaskType> savedMasks;
105  savedMasks.resize(leafCount);
106  for (Index i = 0; i < leafCount; ++i) {
107  savedMasks[i] = manager.leaf(i).getValueMask();
108  }
109 
110  struct Neighbor {
111  LeafType* leaf;//null if a tile
112  bool isOn;//true if active tile
113  Coord orig;
114  Neighbor(Accessor& acc, const Coord& xyz):
115  leaf(acc.probeLeaf(xyz)), isOn(false), orig(xyz)
116  {
117  if (leaf == NULL) isOn = acc.isValueOn(xyz);
118  }
119  void createLeaf(Accessor& acc) { if (leaf == NULL) leaf = acc.touchLeaf(orig); }
120  };
121 
122  Coord origin;
123  for (Index i = 0; i < leafCount; ++i) {
124 
125  const MaskType& oldMask = savedMasks[i];
126  LeafType& leaf = manager.leaf(i);//current leaf node
127  leaf.getOrigin(origin);
128 
129  // Cache the six neighbor nodes of the current leaf node. Note
130  // they can be a leaf node or an active or inactive tile node.
131  Neighbor MX(acc, origin.offsetBy(-LEAF_DIM, 0, 0));
132  Neighbor PX(acc, origin.offsetBy( LEAF_DIM, 0, 0));
133  Neighbor MY(acc, origin.offsetBy( 0, -LEAF_DIM, 0));
134  Neighbor PY(acc, origin.offsetBy( 0, LEAF_DIM, 0));
135  Neighbor MZ(acc, origin.offsetBy( 0, 0,-LEAF_DIM));
136  Neighbor PZ(acc, origin.offsetBy( 0, 0, LEAF_DIM));
137 
138  for (Index x = 0; x < LEAF_DIM; ++x) {
139  for (Index y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
140  // Extract the portion of the original mask that corresponds to a row in z.
141  const Word oldWord = oldMask.template getWord<Word>(n);
142  if (oldWord == 0) continue; // no active voxels
143 
144  // Dilate the current leaf node in the z direction by ORing its mask
145  // with itself shifted first left and then right by one bit.
146  leaf.getValueMask().template getWord<Word>(n) |= (oldWord >> 1) | (oldWord << 1);
147 
148  if (!MZ.isOn && Word(oldWord<<(LEAF_DIM-1))) {
149  MZ.createLeaf(acc);
150  MZ.leaf->getValueMask().template getWord<Word>(n)
151  |= Word(oldWord<<(LEAF_DIM-1));
152  }
153  if (!PZ.isOn && Word(oldWord>>(LEAF_DIM-1))) {
154  PZ.createLeaf(acc);
155  PZ.leaf->getValueMask().template getWord<Word>(n)
156  |= Word(oldWord>>(LEAF_DIM-1));
157  }
158 
159  if (x > 0) {
160  // Dilate row (x-1, y, z) of the current leaf node by ORing its mask
161  // with that of the original row (x, y, z).
162  leaf.getValueMask().template getWord<Word>(n-LEAF_DIM) |= oldWord;
163  } else if (!MX.isOn) {
164  // If the neighbor in the -x direction is an active tile, there's no need
165  // to propagate set bits. Otherwise, dilate into the neighbor's first row.
166  MX.createLeaf(acc);
167  // Dilate into the neighbor's first row by ORing its mask with that of
168  // the current leaf node's original row (0, y, z).
169  MX.leaf->getValueMask().template getWord<Word>(n+LEAF_DIM*(LEAF_DIM-1))
170  |= oldWord;
171  }
172 
173  if (x < LEAF_DIM - 1) {
174  // Dilate row (x+1, y, z) of the current leaf node by ORing its mask
175  // with that of the original row (x, y, z).
176  leaf.getValueMask().template getWord<Word>(n+LEAF_DIM) |= oldWord;
177  } else if (!PX.isOn) {
178  // Dilate into the first row of the neighbor in the +x direction.
179  PX.createLeaf(acc);
180  PX.leaf->getValueMask().template getWord<Word>(n-LEAF_DIM*(LEAF_DIM-1))
181  |= oldWord;
182  }
183 
184  if (y > 0) {
185  // Dilate row (x, y-1, z) of the current leaf node by ORing its mask
186  // with that of the original row (x, y, z).
187  leaf.getValueMask().template getWord<Word>(n-1) |= oldWord;
188  } else if (!MY.isOn) {
189  // Dilate into the first row of the neighbor in the -y direction.
190  MY.createLeaf(acc);
191  MY.leaf->getValueMask().template getWord<Word>(n+LEAF_DIM-1) |= oldWord;
192  }
193 
194  if (y < LEAF_DIM - 1) {
195  // Dilate row (x, y+1, z) of the current leaf node by ORing its mask
196  // with that of the original row (x, y, z).
197  leaf.getValueMask().template getWord<Word>(n+1) |= oldWord;
198  } else if (!PY.isOn) {
199  // Dilate into the first row of the neighbor in the +y direction.
200  PY.createLeaf(acc);
201  PY.leaf->getValueMask().template getWord<Word>(n-LEAF_DIM+1) |= oldWord;
202  }
203  }
204  }
205  }
206 }
207 
208 #else // ifdef OPENVDB_TOOLS_MORPHOLOGY_USE_WORKAROUND_FOR_BROKEN_ICC12_COMPILER
209 
210 //#warning using alternate tools::dilateVoxels() implementation due to broken ICC 12.1 compiler
211 
212 // ICC 12.1 generates incorrect optimized code for the above implementation.
213 // This less-efficient implementation is used instead with that compiler.
214 
216 template<typename TreeType>
217 struct LeafLookup
218 {
219  typedef typename TreeType::LeafNodeType LeafType;
220 
222  // These dummy leaf nodes can be inserted into the cache, where they
223  // represent neighbors that are either active or inactive tiles.
224  const boost::shared_ptr<LeafType> onTile, offTile;
225 
226  LeafLookup(TreeType& tree):
227  cache(tree), onTile(new LeafType), offTile(new LeafType) {}
228 
229  bool isActiveTile(const LeafType* leaf) const { return leaf == onTile.get(); }
230  bool isInactiveTile(const LeafType* leaf) const { return leaf == offTile.get(); }
231 
232  // Return the leaf node that contains voxel (x, y, z), or, if the voxel lies
233  // inside a tile, return either the onTile or offTile dummy leaf node.
234  LeafType* operator()(const Coord& xyz)
235  {
236  // Remove any existing leaf node from the cache.
237  cache.template eraseNode<LeafType>();
238  // Trigger a cache update, which may or may not replace the preloaded node.
239  bool on = cache.isValueOn(xyz);
240  LeafType* leaf = cache.template getNode<LeafType>();
241  // If the "active tile" node is still in the cache, but voxel (x, y, z)
242  // is actually inactive, then it must lie inside an inactive tile.
243  return leaf != NULL ? leaf : (on ? onTile.get() : offTile.get());
244  }
245 
246  // Create and return the leaf node that contains voxel (x, y, z).
247  LeafType* createLeaf(const Coord& xyz)
248  {
249  cache.template eraseNode<LeafType>();
250  // Mark the voxel as active to force creation of the node.
251  cache.setValueOn(xyz);
252  LeafType* leaf = cache.template getNode<LeafType>();
253  // Mark all voxels as inactive.
254  leaf->setValuesOff();
255  return leaf;
256  }
257 }; // struct LeafLookup
258 
259 
260 template<typename TreeType>
261 inline void
262 dilateVoxels(tree::LeafManager<TreeType>& manager)
263 {
264  typedef typename TreeType::LeafNodeType LeafType;
265  typedef typename LeafType::NodeMaskType MaskType;
266 
267  static const Index LEAF_DIM = LeafType::DIM;
268  static const Index LEAF_LOG2DIM = LeafType::LOG2DIM;
269 
270  typedef typename DimToWord<LEAF_LOG2DIM>::Type Word;
271 
273  const Index leafCount = manager.leafCount();
274 
275  // Save the value masks of all leaf nodes.
276  std::vector<MaskType> savedMasks;
277  savedMasks.resize(leafCount);
278  for (Index i = 0; i < leafCount; ++i) {
279  savedMasks[i] = manager.leaf(i).getValueMask();
280  }
281 
282  LeafLookup<TreeType> leafLookup(manager.tree());
283 
284  Coord origin;
285  for (Index i = 0; i < leafCount; ++i) {
286  const MaskType& oldMask = savedMasks[i];
287 
288  // Get the origin of the current leaf node.
289  manager.leaf(i).getOrigin(origin);
290 
291  // This array caches pointers to the current leaf node (nbhd[0]) and four of its
292  // neighbors, some of which might not yet exist and might need to be created
293  LeafType* nbhd[5] = {
294  &manager.leaf(i),
295  leafLookup(origin.offsetBy(-LEAF_DIM, 0, 0)),
296  leafLookup(origin.offsetBy( LEAF_DIM, 0, 0)),
297  leafLookup(origin.offsetBy( 0, -LEAF_DIM, 0)),
298  leafLookup(origin.offsetBy( 0, LEAF_DIM, 0))
299  };
300 
301  for (Index x = 0; x < LEAF_DIM; ++x) {
302  for (Index y = 0, n = (x << LEAF_LOG2DIM); y < LEAF_DIM; ++y, ++n) {
303  // Extract the portion of the original mask that corresponds to a row in z.
304  const Word oldWord = oldMask.template getWord<Word>(n);
305  if (oldWord == 0) continue; // no active voxels
306 
307  // Dilate the current leaf node in the z direction by ORing its mask
308  // with itself shifted first left and then right by one bit.
309  nbhd[0]->getValueMask().template getWord<Word>(n) |=
310  (oldWord >> 1) | (oldWord << 1);
311 
312  if (oldWord & 1) {
313  // If the low bit of the original mask was set, it needs to propagate
314  // into the mask of the neighboring leaf node in the -z direction.
315  leafLookup.cache.setValueOn(origin.offsetBy(x, y, -1));
316  }
317  if (Word(oldWord >> (LEAF_DIM - 1))) {
318  // If the high bit of the original mask was set, it needs to propagate
319  // into the mask of the neighboring leaf node in the +z direction.
320  leafLookup.cache.setValueOn(origin.offsetBy(x, y, LEAF_DIM));
321  }
322 
323  if (x > 0) {
324  // Dilate row (x-1, y, z) of the current leaf node by ORing its mask
325  // with that of the original row (x, y, z).
326  nbhd[0]->getValueMask().template getWord<Word>(n - LEAF_DIM) |= oldWord;
327  } else if (!leafLookup.isActiveTile(nbhd[1])) {
328  // If the neighbor in the -x direction is an active tile, there's no need
329  // to propagate set bits. Otherwise, dilate into the neighbor's first row.
330  if (leafLookup.isInactiveTile(nbhd[1])) {
331  // If the neighbor is an inactive tile, create a neighbor leaf node.
332  nbhd[1] = leafLookup.createLeaf(origin.offsetBy(-LEAF_DIM, 0, 0));
333  }
334  // Dilate into the neighbor's first row by ORing its mask with that of
335  // the current leaf node's original row (0, y, z).
336  nbhd[1]->getValueMask().template getWord<Word>(
337  n + LEAF_DIM * (LEAF_DIM - 1)) |= oldWord;
338  }
339 
340  if (x < LEAF_DIM - 1) {
341  // Dilate row (x+1, y, z) of the current leaf node by ORing its mask
342  // with that of the original row (x, y, z).
343  nbhd[0]->getValueMask().template getWord<Word>(n + LEAF_DIM) |= oldWord;
344  } else if (!leafLookup.isActiveTile(nbhd[2])) {
345  // Dilate into the first row of the neighbor in the +x direction.
346  if (leafLookup.isInactiveTile(nbhd[2])) {
347  // If the neighbor is an inactive tile, create a neighbor leaf node.
348  nbhd[2] = leafLookup.createLeaf(origin.offsetBy(LEAF_DIM, 0, 0));
349  }
350  nbhd[2]->getValueMask().template getWord<Word>(
351  n - LEAF_DIM * (LEAF_DIM - 1)) |= oldWord;
352  }
353 
354  if (y > 0) {
355  // Dilate row (x, y-1, z) of the current leaf node by ORing its mask
356  // with that of the original row (x, y, z).
357  nbhd[0]->getValueMask().template getWord<Word>(n - 1) |= oldWord;
358  } else if (!leafLookup.isActiveTile(nbhd[3])) {
359  // Dilate into the first row of the neighbor in the -y direction.
360  if (leafLookup.isInactiveTile(nbhd[3])) {
361  // If the neighbor is an inactive tile, create a neighbor leaf node.
362  nbhd[3] = leafLookup.createLeaf(origin.offsetBy(0, -LEAF_DIM, 0));
363  }
364  nbhd[3]->getValueMask().template getWord<Word>(n+LEAF_DIM-1) |= oldWord;
365  }
366 
367  if (y < LEAF_DIM - 1) {
368  // Dilate row (x, y+1, z) of the current leaf node by ORing its mask
369  // with that of the original row (x, y, z).
370  nbhd[0]->getValueMask().template getWord<Word>(n + 1) |= oldWord;
371  } else if (!leafLookup.isActiveTile(nbhd[4])) {
372  // Dilate into the first row of the neighbor in the +y direction.
373  if (leafLookup.isInactiveTile(nbhd[4])) {
374  // If the neighbor is an inactive tile, create a neighbor leaf node.
375  nbhd[4] = leafLookup.createLeaf(origin.offsetBy(0, LEAF_DIM, 0));
376  }
377  nbhd[4]->getValueMask().template getWord<Word>(n-LEAF_DIM+1) |= oldWord;
378  }
379  }
380  }
381  }
382 }
383 
384 #endif // defined(OPENVDB_TOOLS_MORPHOLOGY_USE_WORKAROUND_FOR_BROKEN_ICC12_COMPILER)
385 
386 
387 template<typename TreeType>
389 dilateVoxels(TreeType& tree)
390 {
391  tree::LeafManager<TreeType> manager(tree);
392  dilateVoxels<TreeType>(manager);
393 }
394 
395 } // namespace tools
396 } // namespace OPENVDB_VERSION_NAME
397 } // namespace openvdb
398 
399 #endif // OPENVDB_TOOLS_MORPHOLOGY_HAS_BEEN_INCLUDED
400 
401 // Copyright (c) 2012 DreamWorks Animation LLC
402 // All rights reserved. This software is distributed under the
403 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )