HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Prune.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2017 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @file Prune.h
32 ///
33 /// @brief Defined various multi-threaded utility functions for trees
34 ///
35 /// @author Ken Museth
36 
37 #ifndef OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
38 #define OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
39 
40 #include <algorithm> // for std::nth_element
41 
42 #include <hboost/utility/enable_if.hpp>
43 #include <hboost/static_assert.hpp>
44 #include <hboost/type_traits/is_floating_point.hpp>
45 
46 #include <openvdb/math/Math.h> // for isNegative and negative
47 #include <openvdb/Types.h> // for Index typedef
48 #include <openvdb/Types.h>
50 
51 namespace openvdb {
53 namespace OPENVDB_VERSION_NAME {
54 namespace tools {
55 
56 /// @brief Reduce the memory footprint of a @a tree by replacing with tiles
57 /// any nodes whose values are all the same (optionally to within a tolerance)
58 /// and have the same active state.
59 ///
60 /// @note For trees with non-boolean values a child node with (approximately)
61 /// constant values are replaced with a tile value corresponding to the median
62 /// of the values in said child node.
63 ///
64 /// @param tree the tree to be pruned
65 /// @param tolerance tolerance within which values are considered to be equal
66 /// @param threaded enable or disable threading (threading is enabled by default)
67 /// @param grainSize used to control the threading granularity (default is 1)
68 template<typename TreeT>
69 inline void
70 prune(TreeT& tree,
71  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
72  bool threaded = true,
73  size_t grainSize = 1);
74 
75 
76 /// @brief Reduce the memory footprint of a @a tree by replacing with tiles
77 /// any non-leaf nodes whose values are all the same (optionally to within a tolerance)
78 /// and have the same active state.
79 ///
80 /// @param tree the tree to be pruned
81 /// @param tolerance tolerance within which values are considered to be equal
82 /// @param threaded enable or disable threading (threading is enabled by default)
83 /// @param grainSize used to control the threading granularity (default is 1)
84 template<typename TreeT>
85 inline void
86 pruneTiles(TreeT& tree,
87  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
88  bool threaded = true,
89  size_t grainSize = 1);
90 
91 
92 /// @brief Reduce the memory footprint of a @a tree by replacing with
93 /// background tiles any nodes whose values are all inactive.
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 template<typename TreeT>
99 inline void
100 pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1);
101 
102 
103 /// @brief Reduce the memory footprint of a @a tree by replacing any nodes
104 /// whose values are all inactive with tiles of the given @a value.
105 ///
106 /// @param tree the tree to be pruned
107 /// @param value value assigned to inactive tiles created during pruning
108 /// @param threaded enable or disable threading (threading is enabled by default)
109 /// @param grainSize used to control the threading granularity (default is 1)
110 template<typename TreeT>
111 inline void
113  TreeT& tree,
114  const typename TreeT::ValueType& value,
115  bool threaded = true,
116  size_t grainSize = 1);
117 
118 
119 /// @brief Reduce the memory footprint of a @a tree by replacing nodes
120 /// whose values are all inactive with inactive tiles having a value equal to
121 /// the first value encountered in the (inactive) child.
122 /// @details This method is faster than tolerance-based prune and
123 /// useful for narrow-band level set applications where inactive
124 /// values are limited to either an inside or an outside value.
125 ///
126 /// @param tree the tree to be pruned
127 /// @param threaded enable or disable threading (threading is enabled by default)
128 /// @param grainSize used to control the threading granularity (default is 1)
129 ///
130 /// @throw ValueError if the background of the @a tree is negative (as defined by math::isNegative)
131 template<typename TreeT>
132 inline void
133 pruneLevelSet(TreeT& tree,
134  bool threaded = true,
135  size_t grainSize = 1);
136 
137 
138 /// @brief Reduce the memory footprint of a @a tree by replacing nodes whose voxel values
139 /// are all inactive with inactive tiles having the value -| @a insideWidth |
140 /// if the voxel values are negative and | @a outsideWidth | otherwise.
141 ///
142 /// @details This method is faster than tolerance-based prune and
143 /// useful for narrow-band level set applications where inactive
144 /// values are limited to either an inside or an outside value.
145 ///
146 /// @param tree the tree to be pruned
147 /// @param outsideWidth the width of the outside of the narrow band
148 /// @param insideWidth the width of the inside of the narrow band
149 /// @param threaded enable or disable threading (threading is enabled by default)
150 /// @param grainSize used to control the threading granularity (default is 1)
151 ///
152 /// @throw ValueError if @a outsideWidth is negative or @a insideWidth is
153 /// not negative (as defined by math::isNegative).
154 template<typename TreeT>
155 inline void
156 pruneLevelSet(TreeT& tree,
157  const typename TreeT::ValueType& outsideWidth,
158  const typename TreeT::ValueType& insideWidth,
159  bool threaded = true,
160  size_t grainSize = 1);
161 
162 
163 ////////////////////////////////////////////////
164 
165 
166 template<typename TreeT, Index TerminationLevel = 0>
168 {
169 public:
170  typedef typename TreeT::ValueType ValueT;
171  typedef typename TreeT::RootNodeType RootT;
172  typedef typename TreeT::LeafNodeType LeafT;
173  HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
174 
175  InactivePruneOp(TreeT& tree) : mValue(tree.background())
176  {
177  tree.clearAllAccessors();//clear cache of nodes that could be pruned
178  }
179 
180  InactivePruneOp(TreeT& tree, const ValueT& v) : mValue(v)
181  {
182  tree.clearAllAccessors();//clear cache of nodes that could be pruned
183  }
184 
185  // Nothing to do at the leaf node level
186  void operator()(LeafT&) const {}
187  // Prune the child nodes of the internal nodes
188  template<typename NodeT>
189  void operator()(NodeT& node) const
190  {
191  if (NodeT::LEVEL > TerminationLevel) {
192  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
193  if (it->isInactive()) node.addTile(it.pos(), mValue, false);
194  }
195  }
196  }
197  // Prune the child nodes of the root node
198  void operator()(RootT& root) const
199  {
200  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
201  if (it->isInactive()) root.addTile(it.getCoord(), mValue, false);
202  }
203  root.eraseBackgroundTiles();
204  }
205 private:
206 
207  const ValueT mValue;
208 };// InactivePruneOp
209 
210 
211 template<typename TreeT, Index TerminationLevel = 0>
213 {
214 public:
215  typedef typename TreeT::ValueType ValueT;
216  typedef typename TreeT::RootNodeType RootT;
217  typedef typename TreeT::LeafNodeType LeafT;
218  HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
219 
220  TolerancePruneOp(TreeT& tree, const ValueT& t) : mTolerance(t)
221  {
222  tree.clearAllAccessors();//clear cache of nodes that could be pruned
223  }
224 
225  // Prune the child nodes of the root node
226  inline void operator()(RootT& root) const
227  {
228  ValueT value;
229  bool state;
230  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
231  if (this->isConstant(*it, value, state)) root.addTile(it.getCoord(), value, state);
232  }
233  root.eraseBackgroundTiles();
234  }
235 
236  // Prune the child nodes of the internal nodes
237  template<typename NodeT>
238  inline void operator()(NodeT& node) const
239  {
240  if (NodeT::LEVEL > TerminationLevel) {
241  ValueT value;
242  bool state;
243  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
244  if (this->isConstant(*it, value, state)) node.addTile(it.pos(), value, state);
245  }
246  }
247  }
248 
249  // Nothing to do at the leaf node level
250  inline void operator()(LeafT&) const {}
251 
252 private:
253 
254  template<typename NodeT>
255  struct CompareOp {
256  CompareOp() {}
257  typedef typename NodeT::UnionType T;
258  inline bool operator()(const T& a, const T& b) const {return a.getValue() < b.getValue();}
259  };// CompareOp
260 
261  // Private method specialized for leaf nodes
262  inline ValueT median(LeafT& leaf) const
263  {
264  ValueT* data = leaf.buffer().data();
265  static const size_t midpoint = (LeafT::NUM_VALUES - 1) >> 1;
266  std::nth_element(data, data + midpoint, data + LeafT::NUM_VALUES);
267  return data[midpoint];
268  }
269 
270  // Private method for internal nodes
271  template<typename NodeT>
272  inline typename NodeT::ValueType median(NodeT& node) const
273  {
274  typedef typename NodeT::UnionType UnionT;
275  UnionT* data = const_cast<UnionT*>(node.getTable());//never do this at home kids :)
276  static const size_t midpoint = (NodeT::NUM_VALUES - 1) >> 1;
277  CompareOp<NodeT> op;
278  std::nth_element(data, data + midpoint, data + NodeT::NUM_VALUES, op);
279  return data[midpoint].getValue();
280  }
281 
282  // Specialization to nodes templated on booleans values
283  template<typename NodeT>
284  inline
285  typename hboost::enable_if<hboost::is_same<bool, typename NodeT::ValueType>, bool>::type
286  isConstant(NodeT& node, bool& value, bool& state) const
287  {
288  return node.isConstant(value, state, mTolerance);
289  }
290 
291  // Nodes templated on non-boolean values
292  template<typename NodeT>
293  inline
294  typename hboost::disable_if<hboost::is_same<bool, typename NodeT::ValueType>, bool>::type
295  isConstant(NodeT& node, ValueT& value, bool& state) const
296  {
297  ValueT tmp;
298  const bool test = node.isConstant(value, tmp, state, mTolerance);
299  if (test) value = this->median(node);
300  return test;
301  }
302 
303  const ValueT mTolerance;
304 };// TolerancePruneOp
305 
306 
307 template<typename TreeT, Index TerminationLevel = 0>
309 {
310 public:
311  typedef typename TreeT::ValueType ValueT;
312  typedef typename TreeT::RootNodeType RootT;
313  typedef typename TreeT::LeafNodeType LeafT;
314  HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
315 
316  LevelSetPruneOp(TreeT& tree)
317  : mOutside(tree.background())
318  , mInside(math::negative(mOutside))
319  {
320  if (math::isNegative(mOutside)) {
321  OPENVDB_THROW(ValueError,
322  "LevelSetPruneOp: the background value cannot be negative!");
323  }
324  tree.clearAllAccessors();//clear cache of nodes that could be pruned
325  }
326  LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside)
327  : mOutside(outside)
328  , mInside(inside)
329  {
330  if (math::isNegative(mOutside)) {
331  OPENVDB_THROW(ValueError,
332  "LevelSetPruneOp: the outside value cannot be negative!");
333  }
334  if (!math::isNegative(mInside)) {
335  OPENVDB_THROW(ValueError,
336  "LevelSetPruneOp: the inside value must be negative!");
337  }
338  tree.clearAllAccessors();//clear cache of nodes that could be pruned
339  }
340  // Nothing to do at the leaf node level
341  void operator()(LeafT&) const {}
342  // Prune the child nodes of the internal nodes
343  template<typename NodeT>
344  void operator()(NodeT& node) const
345  {
346  if (NodeT::LEVEL > TerminationLevel) {
347  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
348  if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false);
349  }
350  }
351  }
352  // Prune the child nodes of the root node
353  void operator()(RootT& root) const
354  {
355  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
356  if (it->isInactive()) root.addTile(it.getCoord(), this->getTileValue(it), false);
357  }
358  root.eraseBackgroundTiles();
359  }
360 
361 private:
362  template <typename IterT>
363  inline ValueT getTileValue(const IterT& iter) const
364  {
365  return math::isNegative(iter->getFirstValue()) ? mInside : mOutside;
366  }
367 
368  const ValueT mOutside, mInside;
369 };// LevelSetPruneOp
370 
371 
372 template<typename TreeT>
373 inline void
374 prune(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
375 {
376  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
377  TolerancePruneOp<TreeT> op(tree, tol);
378  nodes.foreachBottomUp(op, threaded, grainSize);
379 }
380 
381 
382 template<typename TreeT>
383 inline void
384 pruneTiles(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
385 {
386  tree::NodeManager<TreeT, TreeT::DEPTH-3> nodes(tree);
387  TolerancePruneOp<TreeT> op(tree, tol);
388  nodes.foreachBottomUp(op, threaded, grainSize);
389 }
390 
391 
392 template<typename TreeT>
393 inline void
394 pruneInactive(TreeT& tree, bool threaded, size_t grainSize)
395 {
396  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
397  InactivePruneOp<TreeT> op(tree);
398  nodes.foreachBottomUp(op, threaded, grainSize);
399 }
400 
401 
402 template<typename TreeT>
403 inline void
404 pruneInactiveWithValue(TreeT& tree, const typename TreeT::ValueType& v,
405  bool threaded, size_t grainSize)
406 {
407  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
408  InactivePruneOp<TreeT> op(tree, v);
409  nodes.foreachBottomUp(op, threaded, grainSize);
410 }
411 
412 
413 template<typename TreeT>
414 inline void
415 pruneLevelSet(TreeT& tree,
416  const typename TreeT::ValueType& outside,
417  const typename TreeT::ValueType& inside,
418  bool threaded,
419  size_t grainSize)
420 {
421  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
422  LevelSetPruneOp<TreeT> op(tree, outside, inside);
423  nodes.foreachBottomUp(op, threaded, grainSize);
424 }
425 
426 
427 template<typename TreeT>
428 inline void
429 pruneLevelSet(TreeT& tree, bool threaded, size_t grainSize)
430 {
431  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
432  LevelSetPruneOp<TreeT> op(tree);
433  nodes.foreachBottomUp(op, threaded, grainSize);
434 }
435 
436 } // namespace tools
437 } // namespace OPENVDB_VERSION_NAME
438 } // namespace openvdb
439 
440 #endif // OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
441 
442 // Copyright (c) 2012-2017 DreamWorks Animation LLC
443 // All rights reserved. This software is distributed under the
444 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
TolerancePruneOp(TreeT &tree, const ValueT &t)
Definition: Prune.h:220
HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel)
InactivePruneOp(TreeT &tree, const ValueT &v)
Definition: Prune.h:180
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:384
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:116
const GLdouble * v
Definition: glcorearb.h:836
png_infop png_color_16p * background
Definition: png.h:2326
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
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:404
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:354
LevelSetPruneOp(TreeT &tree, const ValueT &outside, const ValueT &inside)
Definition: Prune.h:326
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:57
#define OPENVDB_VERSION_NAME
Definition: version.h:43
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
GLboolean * data
Definition: glcorearb.h:130
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel)
GLsizei const GLfloat * value
Definition: glcorearb.h:823
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
HBOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel)
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
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:374
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:429
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:394
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101