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