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