OpenVDB  9.0.1
SignedFloodFill.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file SignedFloodFill.h
5 ///
6 /// @brief Propagate the signs of distance values from the active voxels
7 /// in the narrow band to the inactive values outside the narrow band.
8 ///
9 /// @author Ken Museth
10 
11 #ifndef OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
12 #define OPENVDB_TOOLS_SIGNEDFLOODFILL_HAS_BEEN_INCLUDED
13 
14 #include <openvdb/version.h>
15 #include <openvdb/Types.h> // for Index typedef
16 #include <openvdb/math/Math.h> // for math::negative
18 #include <openvdb/openvdb.h>
19 #include <map>
20 #include <type_traits>
21 
22 
23 namespace openvdb {
25 namespace OPENVDB_VERSION_NAME {
26 namespace tools {
27 
28 /// @brief Set the values of all inactive voxels and tiles of a narrow-band
29 /// level set from the signs of the active voxels, setting outside values to
30 /// +background and inside values to -background.
31 ///
32 /// @warning This method should only be used on closed, symmetric narrow-band level sets.
33 ///
34 /// @note If a LeafManager is used the cached leaf nodes are reused,
35 /// resulting in slightly better overall performance.
36 ///
37 /// @param tree Tree or LeafManager that will be flood filled.
38 /// @param threaded enable or disable threading (threading is enabled by default)
39 /// @param grainSize used to control the threading granularity (default is 1)
40 /// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
41 ///
42 /// @throw TypeError if the ValueType of @a tree is not floating-point.
43 template<typename TreeOrLeafManagerT>
44 void
45 signedFloodFill(TreeOrLeafManagerT& tree, bool threaded = true,
46  size_t grainSize = 1, Index minLevel = 0);
47 
48 
49 /// @brief Set the values of all inactive voxels and tiles of a narrow-band
50 /// level set from the signs of the active voxels, setting exterior values to
51 /// @a outsideWidth and interior values to @a insideWidth. Set the background value
52 /// of this tree to @a outsideWidth.
53 ///
54 /// @warning This method should only be used on closed, narrow-band level sets.
55 ///
56 /// @note If a LeafManager is used the cached leaf nodes are reused
57 /// resulting in slightly better overall performance.
58 ///
59 /// @param tree Tree or LeafManager that will be flood filled
60 /// @param outsideWidth the width of the outside of the narrow band
61 /// @param insideWidth the width of the inside of the narrow band
62 /// @param threaded enable or disable threading (threading is enabled by default)
63 /// @param grainSize used to control the threading granularity (default is 1)
64 /// @param minLevel Specify the lowest tree level to process (leafnode level = 0)
65 ///
66 /// @throw TypeError if the ValueType of @a tree is not floating-point.
67 template<typename TreeOrLeafManagerT>
68 void
70  TreeOrLeafManagerT& tree,
71  const typename TreeOrLeafManagerT::ValueType& outsideWidth,
72  const typename TreeOrLeafManagerT::ValueType& insideWidth,
73  bool threaded = true,
74  size_t grainSize = 1,
75  Index minLevel = 0);
76 
77 
78 ////////////////////////// Implementation of SignedFloodFill ////////////////////////////
79 
80 
81 template<typename TreeOrLeafManagerT>
83 {
84 public:
85  using ValueT = typename TreeOrLeafManagerT::ValueType;
86  using RootT = typename TreeOrLeafManagerT::RootNodeType;
87  using LeafT = typename TreeOrLeafManagerT::LeafNodeType;
88  static_assert(std::is_signed<ValueT>::value,
89  "signed flood fill is supported only for signed value grids");
90 
91  SignedFloodFillOp(const TreeOrLeafManagerT& tree, Index minLevel = 0)
92  : mOutside(ValueT(math::Abs(tree.background())))
93  , mInside(ValueT(math::negative(mOutside)))
94  , mMinLevel(minLevel)
95  {
96  }
97 
98  SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel = 0)
99  : mOutside(ValueT(math::Abs(outsideValue)))
100  , mInside(ValueT(math::negative(math::Abs(insideValue))))
101  , mMinLevel(minLevel)
102  {
103  }
104 
105  // Nothing to do at the leaf node level
106  void operator()(LeafT& leaf) const
107  {
108  if (LeafT::LEVEL < mMinLevel) return;
109 
110  if (!leaf.allocate()) return; // this assures that the buffer is allocated and in-memory
111 
112  const typename LeafT::NodeMaskType& valueMask = leaf.getValueMask();
113  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
114  typename LeafT::ValueType* buffer =
115  const_cast<typename LeafT::ValueType*>(&(leaf.getFirstValue()));
116 
117  const Index first = valueMask.findFirstOn();
118  if (first < LeafT::SIZE) {
119  bool xInside = buffer[first]<0, yInside = xInside, zInside = xInside;
120  for (Index x = 0; x != (1 << LeafT::LOG2DIM); ++x) {
121  const Index x00 = x << (2 * LeafT::LOG2DIM);
122  if (valueMask.isOn(x00)) xInside = buffer[x00] < 0; // element(x, 0, 0)
123  yInside = xInside;
124  for (Index y = 0; y != (1 << LeafT::LOG2DIM); ++y) {
125  const Index xy0 = x00 + (y << LeafT::LOG2DIM);
126  if (valueMask.isOn(xy0)) yInside = buffer[xy0] < 0; // element(x, y, 0)
127  zInside = yInside;
128  for (Index z = 0; z != (1 << LeafT::LOG2DIM); ++z) {
129  const Index xyz = xy0 + z; // element(x, y, z)
130  if (valueMask.isOn(xyz)) {
131  zInside = buffer[xyz] < 0;
132  } else {
133  buffer[xyz] = zInside ? mInside : mOutside;
134  }
135  }
136  }
137  }
138  } else {// if no active voxels exist simply use the sign of the first value
139  leaf.fill(buffer[0] < 0 ? mInside : mOutside);
140  }
141  }
142 
143  // Prune the child nodes of the internal nodes
144  template<typename NodeT>
145  void operator()(NodeT& node) const
146  {
147  if (NodeT::LEVEL < mMinLevel) return;
148  // We assume the child nodes have already been flood filled!
149  const typename NodeT::NodeMaskType& childMask = node.getChildMask();
150  // WARNING: "Never do what you're about to see at home, we're what you call experts!"
151  typename NodeT::UnionType* table = const_cast<typename NodeT::UnionType*>(node.getTable());
152 
153  const Index first = childMask.findFirstOn();
154  if (first < NodeT::NUM_VALUES) {
155  bool xInside = table[first].getChild()->getFirstValue()<0;
156  bool yInside = xInside, zInside = xInside;
157  for (Index x = 0; x != (1 << NodeT::LOG2DIM); ++x) {
158  const int x00 = x << (2 * NodeT::LOG2DIM); // offset for block(x, 0, 0)
159  if (childMask.isOn(x00)) xInside = table[x00].getChild()->getLastValue()<0;
160  yInside = xInside;
161  for (Index y = 0; y != (1 << NodeT::LOG2DIM); ++y) {
162  const Index xy0 = x00 + (y << NodeT::LOG2DIM); // offset for block(x, y, 0)
163  if (childMask.isOn(xy0)) yInside = table[xy0].getChild()->getLastValue()<0;
164  zInside = yInside;
165  for (Index z = 0; z != (1 << NodeT::LOG2DIM); ++z) {
166  const Index xyz = xy0 + z; // offset for block(x, y, z)
167  if (childMask.isOn(xyz)) {
168  zInside = table[xyz].getChild()->getLastValue()<0;
169  } else {
170  table[xyz].setValue(zInside ? mInside : mOutside);
171  }
172  }
173  }
174  }
175  } else {//no child nodes exist simply use the sign of the first tile value.
176  const ValueT v = table[0].getValue()<0 ? mInside : mOutside;
177  for (Index i = 0; i < NodeT::NUM_VALUES; ++i) table[i].setValue(v);
178  }
179  }
180 
181  // Prune the child nodes of the root node
182  void operator()(RootT& root) const
183  {
184  if (RootT::LEVEL < mMinLevel) return;
185  using ChildT = typename RootT::ChildNodeType;
186  // Insert the child nodes into a map sorted according to their origin
187  std::map<Coord, ChildT*> nodeKeys;
188  typename RootT::ChildOnIter it = root.beginChildOn();
189  for (; it; ++it) nodeKeys.insert(std::pair<Coord, ChildT*>(it.getCoord(), &(*it)));
190  static const Index DIM = RootT::ChildNodeType::DIM;
191 
192  // We employ a simple z-scanline algorithm that inserts inactive tiles with
193  // the inside value if they are sandwiched between inside child nodes only!
194  typename std::map<Coord, ChildT*>::const_iterator b = nodeKeys.begin(), e = nodeKeys.end();
195  if ( b == e ) return;
196  for (typename std::map<Coord, ChildT*>::const_iterator a = b++; b != e; ++a, ++b) {
197  Coord d = b->first - a->first; // delta of neighboring coordinates
198  if (d[0]!=0 || d[1]!=0 || d[2]==Int32(DIM)) continue;// not same z-scanline or neighbors
199  const ValueT fill[] = { a->second->getLastValue(), b->second->getFirstValue() };
200  if (!(fill[0] < 0) || !(fill[1] < 0)) continue; // scanline isn't inside
201  Coord c = a->first + Coord(0u, 0u, DIM);
202  for (; c[2] != b->first[2]; c[2] += DIM) root.addTile(c, mInside, false);
203  }
204  root.setBackground(mOutside, /*updateChildNodes=*/false);
205  }
206 
207 private:
208  const ValueT mOutside, mInside;
209  const Index mMinLevel;
210 };// SignedFloodFillOp
211 
212 
213 //{
214 /// @cond OPENVDB_DOCS_INTERNAL
215 
216 template<typename TreeOrLeafManagerT>
217 inline
219 doSignedFloodFill(TreeOrLeafManagerT& tree,
220  typename TreeOrLeafManagerT::ValueType outsideValue,
221  typename TreeOrLeafManagerT::ValueType insideValue,
222  bool threaded,
223  size_t grainSize,
224  Index minLevel)
225 {
227  SignedFloodFillOp<TreeOrLeafManagerT> op(outsideValue, insideValue, minLevel);
228  nodes.foreachBottomUp(op, threaded, grainSize);
229 }
230 
231 // Dummy (no-op) implementation for unsigned types
232 template <typename TreeOrLeafManagerT>
233 inline
235 doSignedFloodFill(TreeOrLeafManagerT&,
236  const typename TreeOrLeafManagerT::ValueType&,
237  const typename TreeOrLeafManagerT::ValueType&,
238  bool,
239  size_t,
240  Index)
241 {
243  "signedFloodFill is supported only for signed value grids");
244 }
245 
246 /// @endcond
247 //}
248 
249 
250 // If the narrow-band is symmetric and unchanged
251 template <typename TreeOrLeafManagerT>
252 void
254  TreeOrLeafManagerT& tree,
255  const typename TreeOrLeafManagerT::ValueType& outsideValue,
256  const typename TreeOrLeafManagerT::ValueType& insideValue,
257  bool threaded,
258  size_t grainSize,
259  Index minLevel)
260 {
261  doSignedFloodFill(tree, outsideValue, insideValue, threaded, grainSize, minLevel);
262 }
263 
264 
265 template <typename TreeOrLeafManagerT>
266 void
267 signedFloodFill(TreeOrLeafManagerT& tree,
268  bool threaded,
269  size_t grainSize,
270  Index minLevel)
271 {
272  const typename TreeOrLeafManagerT::ValueType v = tree.root().background();
273  doSignedFloodFill(tree, v, math::negative(v), threaded, grainSize, minLevel);
274 }
275 
276 
277 ////////////////////////////////////////
278 
279 
280 // Explicit Template Instantiation
281 
282 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
283 
284 #ifdef OPENVDB_INSTANTIATE_SIGNEDFLOODFILL
286 #endif
287 
288 #define _FUNCTION(TreeT) \
289  void signedFloodFill(TreeT&, bool, size_t, Index)
291 #undef _FUNCTION
292 
293 #define _FUNCTION(TreeT) \
294  void signedFloodFill(tree::LeafManager<TreeT>&, bool, size_t, Index)
296 #undef _FUNCTION
297 
298 #define _FUNCTION(TreeT) \
299  void signedFloodFillWithValues(TreeT&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
301 #undef _FUNCTION
302 
303 #define _FUNCTION(TreeT) \
304  void signedFloodFillWithValues(tree::LeafManager<TreeT>&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
306 #undef _FUNCTION
307 
308 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
309 
310 
311 } // namespace tools
312 } // namespace OPENVDB_VERSION_NAME
313 } // namespace openvdb
314 
315 #endif // OPENVDB_TOOLS_RESETBACKGROUND_HAS_BEEN_INCLUDED
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
typename TreeOrLeafManagerT::RootNodeType RootT
Definition: SignedFloodFill.h:86
Definition: SignedFloodFill.h:82
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...
Definition: SignedFloodFill.h:253
void operator()(RootT &root) const
Definition: SignedFloodFill.h:182
typename TreeOrLeafManagerT::ValueType ValueT
Definition: SignedFloodFill.h:85
SignedFloodFillOp(const TreeOrLeafManagerT &tree, Index minLevel=0)
Definition: SignedFloodFill.h:91
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:30
void operator()(NodeT &node) const
Definition: SignedFloodFill.h:145
Definition: Exceptions.h:13
ValueT value
Definition: GridBuilder.h:1287
typename TreeOrLeafManagerT::LeafNodeType LeafT
Definition: SignedFloodFill.h:87
Index32 Index
Definition: Types.h:54
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
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...
Definition: SignedFloodFill.h:267
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:624
void operator()(LeafT &leaf) const
Definition: SignedFloodFill.h:106
int32_t Int32
Definition: Types.h:56
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel=0)
Definition: SignedFloodFill.h:98
Definition: Exceptions.h:64
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
Definition: version.h.in:147
Coord Abs(const Coord &xyz)
Definition: Coord.h:514
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202