OpenVDB  9.0.1
Prune.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 Prune.h
5 ///
6 /// @brief Defined various multi-threaded utility functions for trees
7 ///
8 /// @author Ken Museth
9 
10 #ifndef OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
12 
13 #include <openvdb/math/Math.h> // for isNegative and negative
14 #include <openvdb/Types.h>
16 #include <openvdb/openvdb.h>
17 #include <algorithm> // for std::nth_element()
18 #include <type_traits>
19 
20 namespace openvdb {
22 namespace OPENVDB_VERSION_NAME {
23 namespace tools {
24 
25 /// @brief Reduce the memory footprint of a @a tree by replacing with tiles
26 /// any nodes whose values are all the same (optionally to within a tolerance)
27 /// and have the same active state.
28 ///
29 /// @note For trees with non-boolean values a child node with (approximately)
30 /// constant values are replaced with a tile value corresponding to the median
31 /// of the values in said child node.
32 ///
33 /// @param tree the tree to be pruned
34 /// @param tolerance tolerance within which values are considered to be equal
35 /// @param threaded enable or disable threading (threading is enabled by default)
36 /// @param grainSize used to control the threading granularity (default is 1)
37 template<typename TreeT>
38 void
39 prune(TreeT& tree,
40  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
41  bool threaded = true,
42  size_t grainSize = 1);
43 
44 
45 /// @brief Reduce the memory footprint of a @a tree by replacing with tiles
46 /// any non-leaf nodes whose values are all the same (optionally to within a tolerance)
47 /// and have the same active state.
48 ///
49 /// @param tree the tree to be pruned
50 /// @param tolerance tolerance within which values are considered to be equal
51 /// @param threaded enable or disable threading (threading is enabled by default)
52 /// @param grainSize used to control the threading granularity (default is 1)
53 template<typename TreeT>
54 void
55 pruneTiles(TreeT& tree,
56  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
57  bool threaded = true,
58  size_t grainSize = 1);
59 
60 
61 /// @brief Reduce the memory footprint of a @a tree by replacing with
62 /// background tiles any nodes whose values are all inactive.
63 ///
64 /// @param tree the tree to be pruned
65 /// @param threaded enable or disable threading (threading is enabled by default)
66 /// @param grainSize used to control the threading granularity (default is 1)
67 template<typename TreeT>
68 void
69 pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1);
70 
71 
72 /// @brief Reduce the memory footprint of a @a tree by replacing any nodes
73 /// whose values are all inactive with tiles of the given @a value.
74 ///
75 /// @param tree the tree to be pruned
76 /// @param value value assigned to inactive tiles created during pruning
77 /// @param threaded enable or disable threading (threading is enabled by default)
78 /// @param grainSize used to control the threading granularity (default is 1)
79 template<typename TreeT>
80 void
82  TreeT& tree,
83  const typename TreeT::ValueType& value,
84  bool threaded = true,
85  size_t grainSize = 1);
86 
87 
88 /// @brief Reduce the memory footprint of a @a tree by replacing nodes
89 /// whose values are all inactive with inactive tiles having a value equal to
90 /// the first value encountered in the (inactive) child.
91 /// @details This method is faster than tolerance-based prune and
92 /// useful for narrow-band level set applications where inactive
93 /// values are limited to either an inside or an outside value.
94 ///
95 /// @param tree the tree to be pruned
96 /// @param threaded enable or disable threading (threading is enabled by default)
97 /// @param grainSize used to control the threading granularity (default is 1)
98 ///
99 /// @throw ValueError if the background of the @a tree is negative (as defined by math::isNegative)
100 template<typename TreeT>
101 void
102 pruneLevelSet(TreeT& tree,
103  bool threaded = true,
104  size_t grainSize = 1);
105 
106 
107 /// @brief Reduce the memory footprint of a @a tree by replacing nodes whose voxel values
108 /// are all inactive with inactive tiles having the value -| @a insideWidth |
109 /// if the voxel values are negative and | @a outsideWidth | otherwise.
110 ///
111 /// @details This method is faster than tolerance-based prune and
112 /// useful for narrow-band level set applications where inactive
113 /// values are limited to either an inside or an outside value.
114 ///
115 /// @param tree the tree to be pruned
116 /// @param outsideWidth the width of the outside of the narrow band
117 /// @param insideWidth the width of the inside of the narrow band
118 /// @param threaded enable or disable threading (threading is enabled by default)
119 /// @param grainSize used to control the threading granularity (default is 1)
120 ///
121 /// @throw ValueError if @a outsideWidth is negative or @a insideWidth is
122 /// not negative (as defined by math::isNegative).
123 template<typename TreeT>
124 void
125 pruneLevelSet(TreeT& tree,
126  const typename TreeT::ValueType& outsideWidth,
127  const typename TreeT::ValueType& insideWidth,
128  bool threaded = true,
129  size_t grainSize = 1);
130 
131 
132 ////////////////////////////////////////////////
133 
134 
135 template<typename TreeT, Index TerminationLevel = 0>
137 {
138 public:
139  using ValueT = typename TreeT::ValueType;
140  using RootT = typename TreeT::RootNodeType;
141  using LeafT = typename TreeT::LeafNodeType;
142  static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range");
143 
144  InactivePruneOp(TreeT& tree) : mValue(tree.background())
145  {
146  tree.clearAllAccessors();//clear cache of nodes that could be pruned
147  }
148 
149  InactivePruneOp(TreeT& tree, const ValueT& v) : mValue(v)
150  {
151  tree.clearAllAccessors();//clear cache of nodes that could be pruned
152  }
153 
154  // Nothing to do at the leaf node level
155  void operator()(LeafT&) const {}
156 
157  // Prune the child nodes of the internal nodes
158  template<typename NodeT>
159  void operator()(NodeT& node) const
160  {
161  if (NodeT::LEVEL > TerminationLevel) {
162  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
163  if (it->isInactive()) node.addTile(it.pos(), mValue, false);
164  }
165  }
166  }
167 
168  // Prune the child nodes of the root node
169  void operator()(RootT& root) const
170  {
171  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
172  if (it->isInactive()) root.addTile(it.getCoord(), mValue, false);
173  }
174  root.eraseBackgroundTiles();
175  }
176 
177 private:
178  const ValueT mValue;
179 };// InactivePruneOp
180 
181 
182 template<typename TreeT, Index TerminationLevel = 0>
184 {
185 public:
186  using ValueT = typename TreeT::ValueType;
187  using RootT = typename TreeT::RootNodeType;
188  using LeafT = typename TreeT::LeafNodeType;
189  static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range");
190 
191  TolerancePruneOp(TreeT& tree, const ValueT& tol) : mTolerance(tol)
192  {
193  tree.clearAllAccessors();//clear cache of nodes that could be pruned
194  }
195 
196  // Prune the child nodes of the root node
197  inline void operator()(RootT& root) const
198  {
199  ValueT value;
200  bool state;
201  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
202  if (this->isConstant(*it, value, state)) root.addTile(it.getCoord(), value, state);
203  }
204  root.eraseBackgroundTiles();
205  }
206 
207  // Prune the child nodes of the internal nodes
208  template<typename NodeT>
209  inline void operator()(NodeT& node) const
210  {
211  if (NodeT::LEVEL > TerminationLevel) {
212  ValueT value;
213  bool state;
214  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
215  if (this->isConstant(*it, value, state)) node.addTile(it.pos(), value, state);
216  }
217  }
218  }
219 
220  // Nothing to do at the leaf node level
221  inline void operator()(LeafT&) const {}
222 
223 private:
224  // Private method specialized for leaf nodes
225  inline ValueT median(LeafT& leaf) const {return leaf.medianAll(leaf.buffer().data());}
226 
227  // Private method for internal nodes
228  template<typename NodeT>
229  inline typename NodeT::ValueType median(NodeT& node) const
230  {
231  using UnionT = typename NodeT::UnionType;
232  UnionT* data = const_cast<UnionT*>(node.getTable());//never do this at home kids :)
233  static const size_t midpoint = (NodeT::NUM_VALUES - 1) >> 1;
234  auto op = [](const UnionT& a, const UnionT& b){return a.getValue() < b.getValue();};
235  std::nth_element(data, data + midpoint, data + NodeT::NUM_VALUES, op);
236  return data[midpoint].getValue();
237  }
238 
239  // Specialization to nodes templated on booleans values
240  template<typename NodeT>
241  inline
243  isConstant(NodeT& node, bool& value, bool& state) const
244  {
245  return node.isConstant(value, state, mTolerance);
246  }
247 
248  // Nodes templated on non-boolean values
249  template<typename NodeT>
250  inline
252  isConstant(NodeT& node, ValueT& value, bool& state) const
253  {
254  ValueT tmp;
255  const bool test = node.isConstant(value, tmp, state, mTolerance);
256  if (test) value = this->median(node);
257  return test;
258  }
259 
260  const ValueT mTolerance;
261 };// TolerancePruneOp
262 
263 
264 template<typename TreeT, Index TerminationLevel = 0>
266 {
267 public:
268  using ValueT = typename TreeT::ValueType;
269  using RootT = typename TreeT::RootNodeType;
270  using LeafT = typename TreeT::LeafNodeType;
271  static_assert(RootT::LEVEL > TerminationLevel, "TerminationLevel out of range");
272 
273  LevelSetPruneOp(TreeT& tree)
274  : mOutside(tree.background())
275  , mInside(math::negative(mOutside))
276  {
277  if (math::isNegative(mOutside)) {
279  "LevelSetPruneOp: the background value cannot be negative!");
280  }
281  tree.clearAllAccessors();//clear cache of nodes that could be pruned
282  }
283 
284  LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside)
285  : mOutside(outside)
286  , mInside(inside)
287  {
288  if (math::isNegative(mOutside)) {
290  "LevelSetPruneOp: the outside value cannot be negative!");
291  }
292  if (!math::isNegative(mInside)) {
294  "LevelSetPruneOp: the inside value must be negative!");
295  }
296  tree.clearAllAccessors();//clear cache of nodes that could be pruned
297  }
298 
299  // Nothing to do at the leaf node level
300  void operator()(LeafT&) const {}
301 
302  // Prune the child nodes of the internal nodes
303  template<typename NodeT>
304  void operator()(NodeT& node) const
305  {
306  if (NodeT::LEVEL > TerminationLevel) {
307  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
308  if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false);
309  }
310  }
311  }
312 
313  // Prune the child nodes of the root node
314  void operator()(RootT& root) const
315  {
316  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
317  if (it->isInactive()) root.addTile(it.getCoord(), this->getTileValue(it), false);
318  }
319  root.eraseBackgroundTiles();
320  }
321 
322 private:
323  template <typename IterT>
324  inline ValueT getTileValue(const IterT& iter) const
325  {
326  return math::isNegative(iter->getFirstValue()) ? mInside : mOutside;
327  }
328 
329  const ValueT mOutside, mInside;
330 };// LevelSetPruneOp
331 
332 
333 template<typename TreeT>
334 void
335 prune(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
336 {
337  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
338  TolerancePruneOp<TreeT> op(tree, tol);
339  nodes.foreachBottomUp(op, threaded, grainSize);
340 }
341 
342 
343 template<typename TreeT>
344 void
345 pruneTiles(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
346 {
347  tree::NodeManager<TreeT, TreeT::DEPTH-3> nodes(tree);
348  TolerancePruneOp<TreeT> op(tree, tol);
349  nodes.foreachBottomUp(op, threaded, grainSize);
350 }
351 
352 
353 template<typename TreeT>
354 void
355 pruneInactive(TreeT& tree, bool threaded, size_t grainSize)
356 {
357  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
358  InactivePruneOp<TreeT> op(tree);
359  nodes.foreachBottomUp(op, threaded, grainSize);
360 }
361 
362 
363 template<typename TreeT>
364 void
365 pruneInactiveWithValue(TreeT& tree, const typename TreeT::ValueType& v,
366  bool threaded, size_t grainSize)
367 {
368  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
369  InactivePruneOp<TreeT> op(tree, v);
370  nodes.foreachBottomUp(op, threaded, grainSize);
371 }
372 
373 
374 template<typename TreeT>
375 void
376 pruneLevelSet(TreeT& tree,
377  const typename TreeT::ValueType& outside,
378  const typename TreeT::ValueType& inside,
379  bool threaded,
380  size_t grainSize)
381 {
382  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
383  LevelSetPruneOp<TreeT> op(tree, outside, inside);
384  nodes.foreachBottomUp(op, threaded, grainSize);
385 }
386 
387 
388 template<typename TreeT>
389 void
390 pruneLevelSet(TreeT& tree, bool threaded, size_t grainSize)
391 {
392  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
393  LevelSetPruneOp<TreeT> op(tree);
394  nodes.foreachBottomUp(op, threaded, grainSize);
395 }
396 
397 
398 ////////////////////////////////////////
399 
400 
401 // Explicit Template Instantiation
402 
403 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
404 
405 #ifdef OPENVDB_INSTANTIATE_PRUNE
407 #endif
408 
409 #define _FUNCTION(TreeT) \
410  void prune(TreeT&, TreeT::ValueType, bool, size_t)
412 #undef _FUNCTION
413 
414 #define _FUNCTION(TreeT) \
415  void pruneTiles(TreeT&, TreeT::ValueType, bool, size_t)
417 #undef _FUNCTION
418 
419 #define _FUNCTION(TreeT) \
420  void pruneInactive(TreeT&, bool, size_t)
422 #undef _FUNCTION
423 
424 #define _FUNCTION(TreeT) \
425  void pruneInactiveWithValue(TreeT&, const TreeT::ValueType&, bool, size_t)
427 #undef _FUNCTION
428 
429 #define _FUNCTION(TreeT) \
430  void pruneLevelSet(TreeT&, bool, size_t)
432 #undef _FUNCTION
433 
434 #define _FUNCTION(TreeT) \
435  void pruneLevelSet(TreeT&, const TreeT::ValueType&, const TreeT::ValueType&, bool, size_t)
437 #undef _FUNCTION
438 
439 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
440 
441 
442 } // namespace tools
443 } // namespace OPENVDB_VERSION_NAME
444 } // namespace openvdb
445 
446 #endif // OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
void pruneTiles(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any non-leaf nodes whose values are all...
Definition: Prune.h:345
void operator()(NodeT &node) const
Definition: Prune.h:209
typename TreeT::LeafNodeType LeafT
Definition: Prune.h:188
typename TreeT::ValueType ValueT
Definition: Prune.h:268
#define OPENVDB_VOLUME_TREE_INSTANTIATE(Function)
Definition: version.h.in:150
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
LevelSetPruneOp(TreeT &tree)
Definition: Prune.h:273
void operator()(RootT &root) const
Definition: Prune.h:197
void operator()(NodeT &node) const
Definition: Prune.h:159
void operator()(LeafT &) const
Definition: Prune.h:300
void operator()(RootT &root) const
Definition: Prune.h:169
void operator()(LeafT &) const
Definition: Prune.h:155
Definition: Exceptions.h:65
void pruneInactiveWithValue(TreeT &tree, const typename TreeT::ValueType &value, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing any nodes whose values are all inactive with tiles...
Definition: Prune.h:365
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:335
void operator()(NodeT &node) const
Definition: Prune.h:304
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:368
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
typename TreeT::LeafNodeType LeafT
Definition: Prune.h:141
Definition: Exceptions.h:13
ValueT value
Definition: GridBuilder.h:1287
void pruneLevelSet(TreeT &tree, const typename TreeT::ValueType &outsideWidth, const typename TreeT::ValueType &insideWidth, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing nodes whose voxel values are all inactive with ina...
Definition: Prune.h:376
void pruneInactive(TreeT &tree, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with background tiles any nodes whose values are a...
Definition: Prune.h:355
LevelSetPruneOp(TreeT &tree, const ValueT &outside, const ValueT &inside)
Definition: Prune.h:284
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
void operator()(LeafT &) const
Definition: Prune.h:221
typename TreeT::ValueType ValueT
Definition: Prune.h:139
void operator()(RootT &root) const
Definition: Prune.h:314
typename TreeT::RootNodeType RootT
Definition: Prune.h:140
typename TreeT::LeafNodeType LeafT
Definition: Prune.h:270
typename TreeT::RootNodeType RootT
Definition: Prune.h:269
InactivePruneOp(TreeT &tree, const ValueT &v)
Definition: Prune.h:149
#define OPENVDB_REAL_TREE_INSTANTIATE(Function)
Definition: version.h.in:147
typename TreeT::RootNodeType RootT
Definition: Prune.h:187
typename TreeT::ValueType ValueT
Definition: Prune.h:186
InactivePruneOp(TreeT &tree)
Definition: Prune.h:144
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
TolerancePruneOp(TreeT &tree, const ValueT &tol)
Definition: Prune.h:191
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202