GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/SignedFloodFill.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 57 61 93.4%
Functions: 24 61 39.3%
Branches: 63 98 64.3%
Line Branch Exec Source
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
17 #include <openvdb/tree/NodeManager.h>
18 #include <openvdb/openvdb.h>
19 #include <map>
20 #include <type_traits>
21
22
23 namespace openvdb {
24 OPENVDB_USE_VERSION_NAMESPACE
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
69 signedFloodFillWithValues(
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>
82 class SignedFloodFillOp
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
3/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 125 times.
✗ Branch 11 not taken.
 130 SignedFloodFillOp(ValueT outsideValue, ValueT insideValue, Index minLevel = 0)
99 : mOutside(ValueT(math::Abs(outsideValue)))
100 , mInside(ValueT(math::negative(math::Abs(insideValue))))
101
3/8
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 125 times.
✗ Branch 11 not taken.
 131 , mMinLevel(minLevel)
102 {
103 }
104
105 // Nothing to do at the leaf node level
106 653390 void operator()(LeafT& leaf) const
107 {
108
2/2
✓ Branch 0 taken 327179 times.
✓ Branch 1 taken 292 times.
 653390 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 652106 const Index first = valueMask.findFirstOn();
118
2/2
✓ Branch 0 taken 327175 times.
✓ Branch 1 taken 4 times.
 652806 if (first < LeafT::SIZE) {
119 652802 bool xInside = buffer[first]<0, yInside = xInside, zInside = xInside;
120
2/2
✓ Branch 0 taken 2614600 times.
✓ Branch 1 taken 327175 times.
 5872418 for (Index x = 0; x != (1 << LeafT::LOG2DIM); ++x) {
121 5219616 const Index x00 = x << (2 * LeafT::LOG2DIM);
122
2/2
✓ Branch 1 taken 877838 times.
✓ Branch 2 taken 1736762 times.
 5219616 if (valueMask.isOn(x00)) xInside = buffer[x00] < 0; // element(x, 0, 0)
123 yInside = xInside;
124
2/2
✓ Branch 0 taken 20905600 times.
✓ Branch 1 taken 2614600 times.
 46965344 for (Index y = 0; y != (1 << LeafT::LOG2DIM); ++y) {
125 41745728 const Index xy0 = x00 + (y << LeafT::LOG2DIM);
126
2/2
✓ Branch 1 taken 7081849 times.
✓ Branch 2 taken 13823751 times.
 41745728 if (valueMask.isOn(xy0)) yInside = buffer[xy0] < 0; // element(x, y, 0)
127 zInside = yInside;
128
2/2
✓ Branch 0 taken 167200000 times.
✓ Branch 1 taken 20905600 times.
 375666752 for (Index z = 0; z != (1 << LeafT::LOG2DIM); ++z) {
129 333921024 const Index xyz = xy0 + z; // element(x, y, z)
130
2/2
✓ Branch 1 taken 57074009 times.
✓ Branch 2 taken 110125991 times.
 333921024 if (valueMask.isOn(xyz)) {
131 113841881 zInside = buffer[xyz] < 0;
132 } else {
133
2/2
✓ Branch 0 taken 50562414 times.
✓ Branch 1 taken 59563577 times.
 220079143 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
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 leaf.fill(buffer[0] < 0 ? mInside : mOutside);
140 }
141 }
142
143 // Prune the child nodes of the internal nodes
144 template<typename NodeT>
145 4418 void operator()(NodeT& node) const
146 {
147
1/2
✓ Branch 0 taken 2222 times.
✗ Branch 1 not taken.
 4418 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 4392 const Index first = childMask.findFirstOn();
154
1/2
✓ Branch 0 taken 2222 times.
✗ Branch 1 not taken.
 4418 if (first < NodeT::NUM_VALUES) {
155 4418 bool xInside = table[first].getChild()->getFirstValue()<0;
156 bool yInside = xInside, zInside = xInside;
157
2/2
✓ Branch 0 taken 46392 times.
✓ Branch 1 taken 2222 times.
 97098 for (Index x = 0; x != (1 << NodeT::LOG2DIM); ++x) {
158 92680 const int x00 = x << (2 * NodeT::LOG2DIM); // offset for block(x, 0, 0)
159
2/2
✓ Branch 1 taken 1498 times.
✓ Branch 2 taken 44894 times.
 92680 if (childMask.isOn(x00)) xInside = table[x00].getChild()->getLastValue()<0;
160 yInside = xInside;
161
2/2
✓ Branch 0 taken 1097888 times.
✓ Branch 1 taken 46392 times.
 2288040 for (Index y = 0; y != (1 << NodeT::LOG2DIM); ++y) {
162 2195360 const Index xy0 = x00 + (y << NodeT::LOG2DIM); // offset for block(x, y, 0)
163
2/2
✓ Branch 1 taken 20575 times.
✓ Branch 2 taken 1077313 times.
 2195360 if (childMask.isOn(xy0)) yInside = table[xy0].getChild()->getLastValue()<0;
164 zInside = yInside;
165
2/2
✓ Branch 0 taken 28980864 times.
✓ Branch 1 taken 1097888 times.
 60155424 for (Index z = 0; z != (1 << NodeT::LOG2DIM); ++z) {
166 57960064 const Index xyz = xy0 + z; // offset for block(x, y, z)
167
2/2
✓ Branch 1 taken 328969 times.
✓ Branch 2 taken 28651895 times.
 57960064 if (childMask.isOn(xyz)) {
168 657239 zInside = table[xyz].getChild()->getLastValue()<0;
169 } else {
170
2/2
✓ Branch 0 taken 1188280 times.
✓ Branch 1 taken 27463615 times.
 57302825 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 257 void operator()(RootT& root) const
183 {
184
1/2
✓ Branch 0 taken 130 times.
✗ Branch 1 not taken.
 257 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 257 typename RootT::ChildOnIter it = root.beginChildOn();
189
3/4
✓ Branch 0 taken 723 times.
✓ Branch 1 taken 130 times.
✓ Branch 3 taken 723 times.
✗ Branch 4 not taken.
 1661 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
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 130 times.
 257 if ( b == e ) return;
196
2/2
✓ Branch 0 taken 593 times.
✓ Branch 1 taken 130 times.
 1404 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
6/6
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 81 times.
✓ Branch 2 taken 337 times.
✓ Branch 3 taken 175 times.
✓ Branch 4 taken 336 times.
✓ Branch 5 taken 1 times.
 1147 if (d[0]!=0 || d[1]!=0 || d[2]==Int32(DIM)) continue;// not same z-scanline or neighbors
199
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 const ValueT fill[] = { a->second->getLastValue(), b->second->getFirstValue() };
200
2/4
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
 1 if (!(fill[0] < 0) || !(fill[1] < 0)) continue; // scanline isn't inside
201 1 Coord c = a->first + Coord(0u, 0u, DIM);
202
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 2 for (; c[2] != b->first[2]; c[2] += DIM) root.addTile(c, mInside, false);
203 }
204
1/2
✓ Branch 1 taken 130 times.
✗ Branch 2 not taken.
 257 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
218 typename std::enable_if<std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
219 257 doSignedFloodFill(TreeOrLeafManagerT& tree,
220 typename TreeOrLeafManagerT::ValueType outsideValue,
221 typename TreeOrLeafManagerT::ValueType insideValue,
222 bool threaded,
223 size_t grainSize,
224 Index minLevel)
225 {
226 514 tree::NodeManager<TreeOrLeafManagerT> nodes(tree);
227 SignedFloodFillOp<TreeOrLeafManagerT> op(outsideValue, insideValue, minLevel);
228
1/2
✓ Branch 1 taken 130 times.
✗ Branch 2 not taken.
 257 nodes.foreachBottomUp(op, threaded, grainSize);
229 257 }
230
231 // Dummy (no-op) implementation for unsigned types
232 template <typename TreeOrLeafManagerT>
233 inline
234 typename std::enable_if<!std::is_signed<typename TreeOrLeafManagerT::ValueType>::value, void>::type
235 ✗ doSignedFloodFill(TreeOrLeafManagerT&,
236 const typename TreeOrLeafManagerT::ValueType&,
237 const typename TreeOrLeafManagerT::ValueType&,
238 bool,
239 size_t,
240 Index)
241 {
242 ✗ OPENVDB_THROW(TypeError,
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
253 72 signedFloodFillWithValues(
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 72 doSignedFloodFill(tree, outsideValue, insideValue, threaded, grainSize, minLevel);
262 }
263
264
265 template <typename TreeOrLeafManagerT>
266 void
267 185 signedFloodFill(TreeOrLeafManagerT& tree,
268 bool threaded,
269 size_t grainSize,
270 Index minLevel)
271 {
272 185 const typename TreeOrLeafManagerT::ValueType v = tree.root().background();
273 185 doSignedFloodFill(tree, v, math::negative(v), threaded, grainSize, minLevel);
274 185 }
275
276
277 ////////////////////////////////////////
278
279
280 // Explicit Template Instantiation
281
282 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
283
284 #ifdef OPENVDB_INSTANTIATE_SIGNEDFLOODFILL
285 #include <openvdb/util/ExplicitInstantiation.h>
286 #endif
287
288 #define _FUNCTION(TreeT) \
289 void signedFloodFill(TreeT&, bool, size_t, Index)
290 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
291 #undef _FUNCTION
292
293 #define _FUNCTION(TreeT) \
294 void signedFloodFill(tree::LeafManager<TreeT>&, bool, size_t, Index)
295 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
296 #undef _FUNCTION
297
298 #define _FUNCTION(TreeT) \
299 void signedFloodFillWithValues(TreeT&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
300 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
301 #undef _FUNCTION
302
303 #define _FUNCTION(TreeT) \
304 void signedFloodFillWithValues(tree::LeafManager<TreeT>&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t, Index)
305 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
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
316