OpenVDB  3.0.0
SignedFloodFill.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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 //
38 
39 #ifndef OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
40 #define OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
41 
42 #include <boost/utility/enable_if.hpp>
43 #include <openvdb/math/Math.h> // for math::negative
44 #include <openvdb/Types.h> // for Index typedef
45 #include <boost/static_assert.hpp>
46 #include <boost/type_traits/is_floating_point.hpp>
47 #include <openvdb/tree/NodeManager.h>
48 
49 
50 namespace openvdb {
52 namespace OPENVDB_VERSION_NAME {
53 namespace tools {
54 
69 template<typename TreeOrLeafManagerT>
70 inline void
71 signedFloodFill(TreeOrLeafManagerT& tree, bool threaded = true, size_t grainSize = 1);
72 
73 
91 template<typename TreeOrLeafManagerT>
92 inline void
94  TreeOrLeafManagerT& tree,
95  const typename TreeOrLeafManagerT::ValueType& outsideWidth,
96  const typename TreeOrLeafManagerT::ValueType& insideWidth,
97  bool threaded = true,
98  size_t grainSize = 1);
99 
100 
102 
103 
104 template<typename TreeOrLeafManagerT>
106 {
107 public:
108  typedef typename TreeOrLeafManagerT::ValueType ValueT;
109  typedef typename TreeOrLeafManagerT::RootNodeType RootT;
110  typedef typename TreeOrLeafManagerT::LeafNodeType LeafT;
111  BOOST_STATIC_ASSERT(boost::is_floating_point<ValueT>::value);
112 
113  SignedFloodFillOp(const TreeOrLeafManagerT& tree)
114  : mOutside(math::Abs(tree.background()))
115  , mInside(math::negative(mOutside))
116  {
117  }
118 
119  SignedFloodFillOp(const TreeOrLeafManagerT& tree, const ValueT& background)
120  : mOutside(math::Abs(background))
121  , mInside(math::negative(mOutside))
122  {
123  }
124 
125  SignedFloodFillOp(ValueT outsideValue, ValueT insideValue)
126  : mOutside(math::Abs(outsideValue))
127  , mInside(math::negative(math::Abs(insideValue)))
128  {
129  }
130 
131  // Nothing to do at the leaf node level
132  void operator()(LeafT& leaf) const
133  {
134 #ifndef OPENVDB_2_ABI_COMPATIBLE
135  if (!leaf.allocate()) return;//this assures that the buffer is allocated and in-memory
136 #endif
137  const typename LeafT::NodeMaskType& valueMask = leaf.getValueMask();
138  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
139  typename LeafT::ValueType* buffer =
140  const_cast<typename LeafT::ValueType*>(&(leaf.getFirstValue()));
141 
142  const Index first = valueMask.findFirstOn();
143  if (first < LeafT::SIZE) {
144  bool xInside = buffer[first]<0, yInside = xInside, zInside = xInside;
145  for (Index x = 0; x != (1 << LeafT::LOG2DIM); ++x) {
146  const Index x00 = x << (2 * LeafT::LOG2DIM);
147  if (valueMask.isOn(x00)) xInside = buffer[x00] < 0; // element(x, 0, 0)
148  yInside = xInside;
149  for (Index y = 0; y != (1 << LeafT::LOG2DIM); ++y) {
150  const Index xy0 = x00 + (y << LeafT::LOG2DIM);
151  if (valueMask.isOn(xy0)) yInside = buffer[xy0] < 0; // element(x, y, 0)
152  zInside = yInside;
153  for (Index z = 0; z != (1 << LeafT::LOG2DIM); ++z) {
154  const Index xyz = xy0 + z; // element(x, y, z)
155  if (valueMask.isOn(xyz)) {
156  zInside = buffer[xyz] < 0;
157  } else {
158  buffer[xyz] = zInside ? mInside : mOutside;
159  }
160  }
161  }
162  }
163  } else {// if no active voxels exist simply use the sign of the first value
164  leaf.fill(buffer[0] < 0 ? mInside : mOutside);
165  }
166  }
167 
168  // Prune the child nodes of the internal nodes
169  template<typename NodeT>
170  void operator()(NodeT& node) const
171  {
172  // We assume the child nodes have already been flood filled!
173  const typename NodeT::NodeMaskType& childMask = node.getChildMask();
174  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
175  typename NodeT::UnionType* table = const_cast<typename NodeT::UnionType*>(node.getTable());
176 
177  const Index first = childMask.findFirstOn();
178  if (first < NodeT::NUM_VALUES) {
179  bool xInside = table[first].getChild()->getFirstValue()<0;
180  bool yInside = xInside, zInside = xInside;
181  for (Index x = 0; x != (1 << NodeT::LOG2DIM); ++x) {
182  const int x00 = x << (2 * NodeT::LOG2DIM); // offset for block(x, 0, 0)
183  if (childMask.isOn(x00)) xInside = table[x00].getChild()->getLastValue()<0;
184  yInside = xInside;
185  for (Index y = 0; y != (1 << NodeT::LOG2DIM); ++y) {
186  const Index xy0 = x00 + (y << NodeT::LOG2DIM); // offset for block(x, y, 0)
187  if (childMask.isOn(xy0)) yInside = table[xy0].getChild()->getLastValue()<0;
188  zInside = yInside;
189  for (Index z = 0; z != (1 << NodeT::LOG2DIM); ++z) {
190  const Index xyz = xy0 + z; // offset for block(x, y, z)
191  if (childMask.isOn(xyz)) {
192  zInside = table[xyz].getChild()->getLastValue()<0;
193  } else {
194  table[xyz].setValue(zInside ? mInside : mOutside);
195  }
196  }
197  }
198  }
199  } else {//no child nodes exist simply use the sign of the first tile value.
200  const ValueT v = table[0].getValue()<0 ? mInside : mOutside;
201  for (Index i = 0; i < NodeT::NUM_VALUES; ++i) table[i].setValue(v);
202  }
203  }
204 
205  // Prune the child nodes of the root node
206  void operator()(RootT& root) const
207  {
208  typedef typename RootT::ChildNodeType ChildT;
209  // Insert the child nodes into a map sorted according to their origin
210  std::map<Coord, ChildT*> nodeKeys;
211  typename RootT::ChildOnIter it = root.beginChildOn();
212  for (; it; ++it) nodeKeys.insert(std::pair<Coord, ChildT*>(it.getCoord(), &(*it)));
213  static const Index DIM = RootT::ChildNodeType::DIM;
214 
215  // We employ a simple z-scanline algorithm that inserts inactive tiles with
216  // the inside value if they are sandwiched between inside child nodes only!
217  typename std::map<Coord, ChildT*>::const_iterator b = nodeKeys.begin(), e = nodeKeys.end();
218  if ( b == e ) return;
219  for (typename std::map<Coord, ChildT*>::const_iterator a = b++; b != e; ++a, ++b) {
220  Coord d = b->first - a->first; // delta of neighboring coordinates
221  if (d[0]!=0 || d[1]!=0 || d[2]==Int32(DIM)) continue;// not same z-scanline or neighbors
222  const ValueT fill[] = { a->second->getLastValue(), b->second->getFirstValue() };
223  if (!(fill[0] < 0) || !(fill[1] < 0)) continue; // scanline isn't inside
224  Coord c = a->first + Coord(0u, 0u, DIM);
225  for (; c[2] != b->first[2]; c[2] += DIM) root.addTile(c, mInside, false);
226  }
227  root.setBackground(mOutside, /*updateChildNodes=*/false);
228  }
229 
230 private:
231  const ValueT mOutside, mInside;
232 };// SignedFloodFillOp
233 
234 
235 template<typename TreeOrLeafManagerT>
236 inline
237 typename boost::enable_if<typename boost::is_floating_point<
238  typename TreeOrLeafManagerT::ValueType>::type>::type
239 doSignedFloodFill(TreeOrLeafManagerT& tree,
240  typename TreeOrLeafManagerT::ValueType outsideValue,
241  typename TreeOrLeafManagerT::ValueType insideValue,
242  bool threaded,
243  size_t grainSize)
244 {
246  SignedFloodFillOp<TreeOrLeafManagerT> op(outsideValue, insideValue);
247  nodes.processBottomUp(op, threaded, grainSize);
248 }
249 
250 // Dummy (no-op) implementation for non-float types
251 template <typename TreeOrLeafManagerT>
252 inline
253 typename boost::disable_if<typename boost::is_floating_point<
254  typename TreeOrLeafManagerT::ValueType>::type>::type
255 doSignedFloodFill(TreeOrLeafManagerT&,
256  const typename TreeOrLeafManagerT::ValueType&,
257  const typename TreeOrLeafManagerT::ValueType&,
258  bool,
259  size_t)
260 {
262  "signedFloodFill is supported only for scalar, floating-point grids");
263 }
264 
265 
266 // If the narrow-band is symmetric and unchanged
267 template <typename TreeOrLeafManagerT>
268 inline void
270  TreeOrLeafManagerT& tree,
271  const typename TreeOrLeafManagerT::ValueType& outsideValue,
272  const typename TreeOrLeafManagerT::ValueType& insideValue,
273  bool threaded,
274  size_t grainSize)
275 {
276  doSignedFloodFill(tree, outsideValue, insideValue, threaded, grainSize);
277 }
278 
279 
280 template <typename TreeOrLeafManagerT>
281 inline void
282 signedFloodFill(TreeOrLeafManagerT& tree,
283  bool threaded,
284  size_t grainSize)
285 {
286  const typename TreeOrLeafManagerT::ValueType v = tree.root().background();
287  doSignedFloodFill(tree, v, math::negative(v), threaded, grainSize);
288 }
289 
290 } // namespace tools
291 } // namespace OPENVDB_VERSION_NAME
292 } // namespace openvdb
293 
294 #endif // OPENVDB_TOOLS_RESETBACKGROUND_HAS_BEEN_INCLUDED
295 
296 // Copyright (c) 2012-2014 DreamWorks Animation LLC
297 // All rights reserved. This software is distributed under the
298 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
TreeOrLeafManagerT::LeafNodeType LeafT
Definition: SignedFloodFill.h:110
int32_t Abs(int32_t i)
Return the absolute value of the given quantity.
Definition: Math.h:284
void signedFloodFillWithValues(TreeOrLeafManagerT &tree, const typename TreeOrLeafManagerT::ValueType &outsideWidth, const typename TreeOrLeafManagerT::ValueType &insideWidth, bool threaded=true, size_t grainSize=1)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:269
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
void processBottomUp(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:401
int32_t Int32
Definition: Types.h:61
TreeOrLeafManagerT::ValueType ValueT
Definition: SignedFloodFill.h:108
#define OPENVDB_VERSION_NAME
Definition: version.h:43
SignedFloodFillOp(const TreeOrLeafManagerT &tree, const ValueT &background)
Definition: SignedFloodFill.h:119
Index32 Index
Definition: Types.h:59
Definition: Exceptions.h:87
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue)
Definition: SignedFloodFill.h:125
Definition: Exceptions.h:39
void operator()(LeafT &leaf) const
Definition: SignedFloodFill.h:132
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
TreeOrLeafManagerT::RootNodeType RootT
Definition: SignedFloodFill.h:109
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:56
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Definition: SignedFloodFill.h:105
boost::disable_if< typename boost::is_floating_point< typename TreeOrLeafManagerT::ValueType >::type >::type doSignedFloodFill(TreeOrLeafManagerT &, const typename TreeOrLeafManagerT::ValueType &, const typename TreeOrLeafManagerT::ValueType &, bool, size_t)
Definition: SignedFloodFill.h:255
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:282
SignedFloodFillOp(const TreeOrLeafManagerT &tree)
Definition: SignedFloodFill.h:113
void operator()(NodeT &node) const
Definition: SignedFloodFill.h:170
void operator()(RootT &root) const
Definition: SignedFloodFill.h:206