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