HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SignedFloodFill.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2017 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 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @file SignedFloodFill.h
32 ///
33 /// @brief Propagates the sign of distance values from the active
34 /// voxels in the narrow band to the inactive values outside the
35 /// narrow band.
36 ///
37 /// @author Ken Museth
38 
39 #ifndef OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
40 #define OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
41 
42 #include <hboost/utility/enable_if.hpp>
43 #include <openvdb/math/Math.h> // for math::negative
44 #include <openvdb/Types.h> // for Index typedef
45 #include <hboost/static_assert.hpp>
46 #include <hboost/type_traits/is_floating_point.hpp>
47 #include <hboost/type_traits/is_signed.hpp>
48 
50 
51 
52 namespace openvdb {
54 namespace OPENVDB_VERSION_NAME {
55 namespace tools {
56 
57 /// @brief Set the values of all inactive voxels and tiles of a narrow-band
58 /// level set from the signs of the active voxels, setting outside values to
59 /// +background and inside values to -background.
60 ///
61 /// @warning This method should only be used on closed, symmetric narrow-band level sets.
62 ///
63 /// @note If a LeafManager is used the cached leaf nodes are reused,
64 /// resulting in slightly better overall performance.
65 ///
66 /// @param tree Tree or LeafManager that will be flood filled.
67 /// @param threaded enable or disable threading (threading is enabled by default)
68 /// @param grainSize used to control the threading granularity (default is 1)
69 /// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
70 ///
71 /// @throw TypeError if the ValueType of @a tree is not floating-point.
72 template<typename TreeOrLeafManagerT>
73 inline void
74 signedFloodFill(TreeOrLeafManagerT& tree, bool threaded = true,
75  size_t grainSize = 1, Index minLevel = 0);
76 
77 
78 /// @brief Set the values of all inactive voxels and tiles of a narrow-band
79 /// level set from the signs of the active voxels, setting exterior values to
80 /// @a outsideWidth and interior values to @a insideWidth. Set the background value
81 /// of this tree to @a outsideWidth.
82 ///
83 /// @warning This method should only be used on closed, narrow-band level sets.
84 ///
85 /// @note If a LeafManager is used the cached leaf nodes are reused
86 /// resulting in slightly better overall performance.
87 ///
88 /// @param tree Tree or LeafManager that will be flood filled
89 /// @param outsideWidth the width of the outside of the narrow band
90 /// @param insideWidth the width of the inside of the narrow band
91 /// @param threaded enable or disable threading (threading is enabled by default)
92 /// @param grainSize used to control the threading granularity (default is 1)
93 /// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
94 ///
95 /// @throw TypeError if the ValueType of @a tree is not floating-point.
96 template<typename TreeOrLeafManagerT>
97 inline void
99  TreeOrLeafManagerT& tree,
100  const typename TreeOrLeafManagerT::ValueType& outsideWidth,
101  const typename TreeOrLeafManagerT::ValueType& insideWidth,
102  bool threaded = true,
103  size_t grainSize = 1,
104  Index minLevel = 0);
105 
106 
107 ////////////////////////// Implementation of SignedFloodFill ////////////////////////////
108 
109 
110 template<typename TreeOrLeafManagerT>
112 {
113 public:
114  typedef typename TreeOrLeafManagerT::ValueType ValueT;
115  typedef typename TreeOrLeafManagerT::RootNodeType RootT;
116  typedef typename TreeOrLeafManagerT::LeafNodeType LeafT;
118 
119  SignedFloodFillOp(const TreeOrLeafManagerT& tree, Index minLevel = 0)
120  : mOutside(ValueT(math::Abs(tree.background())))
121  , mInside(ValueT(math::negative(mOutside)))
122  , mMinLevel(minLevel)
123  {
124  }
125 
126  SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel = 0)
127  : mOutside(ValueT(math::Abs(outsideValue)))
128  , mInside(ValueT(math::negative(math::Abs(insideValue))))
129  , mMinLevel(minLevel)
130  {
131  }
132 
133  // Nothing to do at the leaf node level
134  void operator()(LeafT& leaf) const
135  {
136  if (LeafT::LEVEL < mMinLevel) return;
137 
138 #ifndef OPENVDB_2_ABI_COMPATIBLE
139  if (!leaf.allocate()) return;//this assures that the buffer is allocated and in-memory
140 #endif
141  const typename LeafT::NodeMaskType& valueMask = leaf.getValueMask();
142  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
143  typename LeafT::ValueType* buffer =
144  const_cast<typename LeafT::ValueType*>(&(leaf.getFirstValue()));
145 
146  const Index first = valueMask.findFirstOn();
147  if (first < LeafT::SIZE) {
148  bool xInside = buffer[first]<0, yInside = xInside, zInside = xInside;
149  for (Index x = 0; x != (1 << LeafT::LOG2DIM); ++x) {
150  const Index x00 = x << (2 * LeafT::LOG2DIM);
151  if (valueMask.isOn(x00)) xInside = buffer[x00] < 0; // element(x, 0, 0)
152  yInside = xInside;
153  for (Index y = 0; y != (1 << LeafT::LOG2DIM); ++y) {
154  const Index xy0 = x00 + (y << LeafT::LOG2DIM);
155  if (valueMask.isOn(xy0)) yInside = buffer[xy0] < 0; // element(x, y, 0)
156  zInside = yInside;
157  for (Index z = 0; z != (1 << LeafT::LOG2DIM); ++z) {
158  const Index xyz = xy0 + z; // element(x, y, z)
159  if (valueMask.isOn(xyz)) {
160  zInside = buffer[xyz] < 0;
161  } else {
162  buffer[xyz] = zInside ? mInside : mOutside;
163  }
164  }
165  }
166  }
167  } else {// if no active voxels exist simply use the sign of the first value
168  leaf.fill(buffer[0] < 0 ? mInside : mOutside);
169  }
170  }
171 
172  // Prune the child nodes of the internal nodes
173  template<typename NodeT>
174  void operator()(NodeT& node) const
175  {
176  if (NodeT::LEVEL < mMinLevel) return;
177  // We assume the child nodes have already been flood filled!
178  const typename NodeT::NodeMaskType& childMask = node.getChildMask();
179  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
180  typename NodeT::UnionType* table = const_cast<typename NodeT::UnionType*>(node.getTable());
181 
182  const Index first = childMask.findFirstOn();
183  if (first < NodeT::NUM_VALUES) {
184  bool xInside = table[first].getChild()->getFirstValue()<0;
185  bool yInside = xInside, zInside = xInside;
186  for (Index x = 0; x != (1 << NodeT::LOG2DIM); ++x) {
187  const int x00 = x << (2 * NodeT::LOG2DIM); // offset for block(x, 0, 0)
188  if (childMask.isOn(x00)) xInside = table[x00].getChild()->getLastValue()<0;
189  yInside = xInside;
190  for (Index y = 0; y != (1 << NodeT::LOG2DIM); ++y) {
191  const Index xy0 = x00 + (y << NodeT::LOG2DIM); // offset for block(x, y, 0)
192  if (childMask.isOn(xy0)) yInside = table[xy0].getChild()->getLastValue()<0;
193  zInside = yInside;
194  for (Index z = 0; z != (1 << NodeT::LOG2DIM); ++z) {
195  const Index xyz = xy0 + z; // offset for block(x, y, z)
196  if (childMask.isOn(xyz)) {
197  zInside = table[xyz].getChild()->getLastValue()<0;
198  } else {
199  table[xyz].setValue(zInside ? mInside : mOutside);
200  }
201  }
202  }
203  }
204  } else {//no child nodes exist simply use the sign of the first tile value.
205  const ValueT v = table[0].getValue()<0 ? mInside : mOutside;
206  for (Index i = 0; i < NodeT::NUM_VALUES; ++i) table[i].setValue(v);
207  }
208  }
209 
210  // Prune the child nodes of the root node
211  void operator()(RootT& root) const
212  {
213  if (RootT::LEVEL < mMinLevel) return;
214  typedef typename RootT::ChildNodeType ChildT;
215  // Insert the child nodes into a map sorted according to their origin
216  std::map<Coord, ChildT*> nodeKeys;
217  typename RootT::ChildOnIter it = root.beginChildOn();
218  for (; it; ++it) nodeKeys.insert(std::pair<Coord, ChildT*>(it.getCoord(), &(*it)));
219  static const Index DIM = RootT::ChildNodeType::DIM;
220 
221  // We employ a simple z-scanline algorithm that inserts inactive tiles with
222  // the inside value if they are sandwiched between inside child nodes only!
223  typename std::map<Coord, ChildT*>::const_iterator b = nodeKeys.begin(), e = nodeKeys.end();
224  if ( b == e ) return;
225  for (typename std::map<Coord, ChildT*>::const_iterator a = b++; b != e; ++a, ++b) {
226  Coord d = b->first - a->first; // delta of neighboring coordinates
227  if (d[0]!=0 || d[1]!=0 || d[2]==Int32(DIM)) continue;// not same z-scanline or neighbors
228  const ValueT fill[] = { a->second->getLastValue(), b->second->getFirstValue() };
229  if (!(fill[0] < 0) || !(fill[1] < 0)) continue; // scanline isn't inside
230  Coord c = a->first + Coord(0u, 0u, DIM);
231  for (; c[2] != b->first[2]; c[2] += DIM) root.addTile(c, mInside, false);
232  }
233  root.setBackground(mOutside, /*updateChildNodes=*/false);
234  }
235 
236 private:
237  const ValueT mOutside, mInside;
238  const Index mMinLevel;
239 };// SignedFloodFillOp
240 
241 
242 template<typename TreeOrLeafManagerT>
243 inline
244 typename hboost::enable_if_c<
247 doSignedFloodFill(TreeOrLeafManagerT& tree,
248  typename TreeOrLeafManagerT::ValueType outsideValue,
249  typename TreeOrLeafManagerT::ValueType insideValue,
250  bool threaded,
251  size_t grainSize,
252  Index minLevel)
253 {
255  SignedFloodFillOp<TreeOrLeafManagerT> op(outsideValue, insideValue, minLevel);
256  nodes.foreachBottomUp(op, threaded, grainSize);
257 }
258 
259 // Dummy (no-op) implementation for non-float types
260 template <typename TreeOrLeafManagerT>
261 inline
262 typename hboost::disable_if_c<
265 doSignedFloodFill(TreeOrLeafManagerT&,
266  const typename TreeOrLeafManagerT::ValueType&,
267  const typename TreeOrLeafManagerT::ValueType&,
268  bool,
269  size_t,
270  Index)
271 {
272  OPENVDB_THROW(TypeError,
273  "signedFloodFill is supported only for signed value grids");
274 }
275 
276 
277 // If the narrow-band is symmetric and unchanged
278 template <typename TreeOrLeafManagerT>
279 inline void
281  TreeOrLeafManagerT& tree,
282  const typename TreeOrLeafManagerT::ValueType& outsideValue,
283  const typename TreeOrLeafManagerT::ValueType& insideValue,
284  bool threaded,
285  size_t grainSize,
286  Index minLevel)
287 {
288  doSignedFloodFill(tree, outsideValue, insideValue, threaded, grainSize, minLevel);
289 }
290 
291 
292 template <typename TreeOrLeafManagerT>
293 inline void
294 signedFloodFill(TreeOrLeafManagerT& tree,
295  bool threaded,
296  size_t grainSize,
297  Index minLevel)
298 {
299  const typename TreeOrLeafManagerT::ValueType v = tree.root().background();
300  doSignedFloodFill(tree, v, math::negative(v), threaded, grainSize, minLevel);
301 }
302 
303 } // namespace tools
304 } // namespace OPENVDB_VERSION_NAME
305 } // namespace openvdb
306 
307 #endif // OPENVDB_TOOLS_RESETBACKGROUND_HAS_BEEN_INCLUDED
308 
309 // Copyright (c) 2012-2017 DreamWorks Animation LLC
310 // All rights reserved. This software is distributed under the
311 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
GLint first
Definition: glcorearb.h:404
MeshToVoxelEdgeData::EdgeData Abs(const MeshToVoxelEdgeData::EdgeData &x)
HBOOST_STATIC_ASSERT(hboost::is_floating_point< ValueT >::value||hboost::is_signed< ValueT >::value)
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:116
const GLdouble * v
Definition: glcorearb.h:836
png_infop png_color_16p * background
Definition: png.h:2326
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:847
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
GLint y
Definition: glcorearb.h:102
GLuint buffer
Definition: glcorearb.h:659
png_uint_32 i
Definition: png.h:2877
void signedFloodFillWithValues(TreeOrLeafManagerT &tree, const typename TreeOrLeafManagerT::ValueType &outsideWidth, const typename TreeOrLeafManagerT::ValueType &insideWidth, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays, one for each level of the tree.
Definition: NodeManager.h:57
void foreachBottomUp(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:492
#define OPENVDB_VERSION_NAME
Definition: version.h:43
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
hboost::enable_if_c< hboost::is_floating_point< typename TreeOrLeafManagerT::ValueType >::value||hboost::is_signed< typename TreeOrLeafManagerT::ValueType >::value, void >::type doSignedFloodFill(TreeOrLeafManagerT &tree, typename TreeOrLeafManagerT::ValueType outsideValue, typename TreeOrLeafManagerT::ValueType insideValue, bool threaded, size_t grainSize, Index minLevel)
GLsizei const GLfloat * value
Definition: glcorearb.h:823
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
GLint GLenum GLint x
Definition: glcorearb.h:408
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
#define SIZE
Definition: simple.C:40
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
SignedFloodFillOp(const TreeOrLeafManagerT &tree, Index minLevel=0)
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel=0)
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101