OpenVDB 10.0.1
Loading...
Searching...
No Matches
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
23namespace openvdb {
25namespace OPENVDB_VERSION_NAME {
26namespace 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.
43template<typename TreeOrLeafManagerT>
44void
45signedFloodFill(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.
67template<typename TreeOrLeafManagerT>
68void
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
81template<typename TreeOrLeafManagerT>
83{
84public:
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
207private:
208 const ValueT mOutside, mInside;
209 const Index mMinLevel;
210};// SignedFloodFillOp
211
212
213//{
214/// @cond OPENVDB_DOCS_INTERNAL
215
216template<typename TreeOrLeafManagerT>
217inline
218typename std::enable_if<std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
219doSignedFloodFill(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
232template <typename TreeOrLeafManagerT>
233inline
234typename std::enable_if<!std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
235doSignedFloodFill(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
251template <typename TreeOrLeafManagerT>
252void
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
265template <typename TreeOrLeafManagerT>
266void
267signedFloodFill(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
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Definition Exceptions.h:64
Signed (x, y, z) 32-bit integer coordinates.
Definition Coord.h:25
Definition SignedFloodFill.h:83
SignedFloodFillOp(const TreeOrLeafManagerT &tree, Index minLevel=0)
Definition SignedFloodFill.h:91
void operator()(LeafT &leaf) const
Definition SignedFloodFill.h:106
void operator()(NodeT &node) const
Definition SignedFloodFill.h:145
void operator()(RootT &root) const
Definition SignedFloodFill.h:182
typename TreeOrLeafManagerT::ValueType ValueT
Definition SignedFloodFill.h:85
SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel=0)
Definition SignedFloodFill.h:98
typename TreeOrLeafManagerT::LeafNodeType LeafT
Definition SignedFloodFill.h:87
typename TreeOrLeafManagerT::RootNodeType RootT
Definition SignedFloodFill.h:86
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays,...
Definition NodeManager.h:531
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 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
Index32 Index
Definition Types.h:54
int32_t Int32
Definition Types.h:56
Definition Exceptions.h:13
#define OPENVDB_THROW(exception, message)
Definition Exceptions.h:74
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:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition version.h.in:212
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
Definition version.h.in:157