OpenVDB  3.1.0
Prune.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2015 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 //
30 //
36 
37 #ifndef OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
38 #define OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
39 
40 #include <boost/utility/enable_if.hpp>
41 #include <boost/static_assert.hpp>
42 #include <boost/type_traits/is_floating_point.hpp>
43 
44 #include <openvdb/math/Math.h> // for isNegative and negative
45 #include <openvdb/Types.h> // for Index typedef
46 #include <openvdb/Types.h>
47 #include <openvdb/tree/NodeManager.h>
48 
49 namespace openvdb {
51 namespace OPENVDB_VERSION_NAME {
52 namespace tools {
53 
67 template<typename TreeT>
68 inline void
69 prune(TreeT& tree,
70  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
71  bool threaded = true,
72  size_t grainSize = 1);
73 
74 
83 template<typename TreeT>
84 inline void
85 pruneTiles(TreeT& tree,
86  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
87  bool threaded = true,
88  size_t grainSize = 1);
89 
90 
97 template<typename TreeT>
98 inline void
99 pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1);
100 
101 
109 template<typename TreeT>
110 inline void
112  TreeT& tree,
113  const typename TreeT::ValueType& value,
114  bool threaded = true,
115  size_t grainSize = 1);
116 
117 
130 template<typename TreeT>
131 inline void
132 pruneLevelSet(TreeT& tree,
133  bool threaded = true,
134  size_t grainSize = 1);
135 
136 
153 template<typename TreeT>
154 inline void
155 pruneLevelSet(TreeT& tree,
156  const typename TreeT::ValueType& outsideWidth,
157  const typename TreeT::ValueType& insideWidth,
158  bool threaded = true,
159  size_t grainSize = 1);
160 
161 
163 
164 
165 template<typename TreeT, Index TerminationLevel = 0>
167 {
168 public:
169  typedef typename TreeT::ValueType ValueT;
170  typedef typename TreeT::RootNodeType RootT;
171  typedef typename TreeT::LeafNodeType LeafT;
172  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
173 
174  InactivePruneOp(TreeT& tree) : mValue(tree.background())
175  {
176  tree.clearAllAccessors();//clear cache of nodes that could be pruned
177  }
178 
179  InactivePruneOp(TreeT& tree, const ValueT& v) : mValue(v)
180  {
181  tree.clearAllAccessors();//clear cache of nodes that could be pruned
182  }
183 
184  // Nothing to do at the leaf node level
185  void operator()(LeafT&) const {}
186  // Prune the child nodes of the internal nodes
187  template<typename NodeT>
188  void operator()(NodeT& node) const
189  {
190  if (NodeT::LEVEL > TerminationLevel) {
191  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
192  if (it->isInactive()) node.addTile(it.pos(), mValue, false);
193  }
194  }
195  }
196  // Prune the child nodes of the root node
197  void operator()(RootT& root) const
198  {
199  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
200  if (it->isInactive()) root.addTile(it.getCoord(), mValue, false);
201  }
202  root.eraseBackgroundTiles();
203  }
204 private:
205 
206  const ValueT mValue;
207 };// InactivePruneOp
208 
209 
210 template<typename TreeT, Index TerminationLevel = 0>
212 {
213 public:
214  typedef typename TreeT::ValueType ValueT;
215  typedef typename TreeT::RootNodeType RootT;
216  typedef typename TreeT::LeafNodeType LeafT;
217  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
218 
219  TolerancePruneOp(TreeT& tree, const ValueT& t) : mTolerance(t)
220  {
221  tree.clearAllAccessors();//clear cache of nodes that could be pruned
222  }
223 
224  // Prune the child nodes of the root node
225  inline void operator()(RootT& root) const
226  {
227  ValueT value;
228  bool state;
229  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
230  if (this->isConstant(*it, value, state)) root.addTile(it.getCoord(), value, state);
231  }
232  root.eraseBackgroundTiles();
233  }
234 
235  // Prune the child nodes of the internal nodes
236  template<typename NodeT>
237  inline void operator()(NodeT& node) const
238  {
239  if (NodeT::LEVEL > TerminationLevel) {
240  ValueT value;
241  bool state;
242  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
243  if (this->isConstant(*it, value, state)) node.addTile(it.pos(), value, state);
244  }
245  }
246  }
247 
248  // Nothing to do at the leaf node level
249  inline void operator()(LeafT&) const {}
250 
251 private:
252 
253  // For floating-point value types set tile values to
254  // the mean of the extrema values of the constant node
255  template<typename NodeT>
256  inline
257  typename boost::enable_if<boost::is_floating_point<typename NodeT::ValueType>, bool>::type
258  isConstant(const NodeT& node, ValueT& value, bool& state) const
259  {
260  ValueT tmp;
261  const bool test = node.isConstant(value, tmp, state, mTolerance);
262  if (test) value = ValueT(0.5f)*(value + tmp);
263  return test;
264  }
265 
266  // For non-floating-point value types set tile values to
267  // the first value encountered in the constant node
268  template<typename NodeT>
269  inline
270  typename boost::disable_if<boost::is_floating_point<typename NodeT::ValueType>, bool>::type
271  isConstant(const NodeT& node, ValueT& value, bool& state) const
272  {
273  return node.isConstant(value, state, mTolerance);
274  }
275 
276  const ValueT mTolerance;
277 };// TolerancePruneOp
278 
279 
280 template<typename TreeT, Index TerminationLevel = 0>
282 {
283 public:
284  typedef typename TreeT::ValueType ValueT;
285  typedef typename TreeT::RootNodeType RootT;
286  typedef typename TreeT::LeafNodeType LeafT;
287  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
288 
289  LevelSetPruneOp(TreeT& tree)
290  : mOutside(tree.background())
291  , mInside(math::negative(mOutside))
292  {
293  if (math::isNegative(mOutside)) {
295  "LevelSetPruneOp: the background value cannot be negative!");
296  }
297  tree.clearAllAccessors();//clear cache of nodes that could be pruned
298  }
299  LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside)
300  : mOutside(outside)
301  , mInside(inside)
302  {
303  if (math::isNegative(mOutside)) {
305  "LevelSetPruneOp: the outside value cannot be negative!");
306  }
307  if (!math::isNegative(mInside)) {
309  "LevelSetPruneOp: the inside value must be negative!");
310  }
311  tree.clearAllAccessors();//clear cache of nodes that could be pruned
312  }
313  // Nothing to do at the leaf node level
314  void operator()(LeafT&) const {}
315  // Prune the child nodes of the internal nodes
316  template<typename NodeT>
317  void operator()(NodeT& node) const
318  {
319  if (NodeT::LEVEL > TerminationLevel) {
320  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
321  if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false);
322  }
323  }
324  }
325  // Prune the child nodes of the root node
326  void operator()(RootT& root) const
327  {
328  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
329  if (it->isInactive()) root.addTile(it.getCoord(), this->getTileValue(it), false);
330  }
331  root.eraseBackgroundTiles();
332  }
333 
334 private:
335  template <typename IterT>
336  inline ValueT getTileValue(const IterT& iter) const
337  {
338  return math::isNegative(iter->getFirstValue()) ? mInside : mOutside;
339  }
340 
341  const ValueT mOutside, mInside;
342 };// LevelSetPruneOp
343 
344 
345 template<typename TreeT>
346 inline void
347 prune(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
348 {
349  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
350  TolerancePruneOp<TreeT> op(tree, tol);
351  nodes.processBottomUp(op, threaded, grainSize);
352 }
353 
354 
355 template<typename TreeT>
356 inline void
357 pruneTiles(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
358 {
359  tree::NodeManager<TreeT, TreeT::DEPTH-3> nodes(tree);
360  TolerancePruneOp<TreeT> op(tree, tol);
361  nodes.processBottomUp(op, threaded, grainSize);
362 }
363 
364 
365 template<typename TreeT>
366 inline void
367 pruneInactive(TreeT& tree, bool threaded, size_t grainSize)
368 {
369  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
370  InactivePruneOp<TreeT> op(tree);
371  nodes.processBottomUp(op, threaded, grainSize);
372 }
373 
374 
375 template<typename TreeT>
376 inline void
377 pruneInactiveWithValue(TreeT& tree, const typename TreeT::ValueType& v,
378  bool threaded, size_t grainSize)
379 {
380  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
381  InactivePruneOp<TreeT> op(tree, v);
382  nodes.processBottomUp(op, threaded, grainSize);
383 }
384 
385 
386 template<typename TreeT>
387 inline void
388 pruneLevelSet(TreeT& tree,
389  const typename TreeT::ValueType& outside,
390  const typename TreeT::ValueType& inside,
391  bool threaded,
392  size_t grainSize)
393 {
394  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
395  LevelSetPruneOp<TreeT> op(tree, outside, inside);
396  nodes.processBottomUp(op, threaded, grainSize);
397 }
398 
399 
400 template<typename TreeT>
401 inline void
402 pruneLevelSet(TreeT& tree, bool threaded, size_t grainSize)
403 {
404  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
405  LevelSetPruneOp<TreeT> op(tree);
406  nodes.processBottomUp(op, threaded, grainSize);
407 }
408 
409 } // namespace tools
410 } // namespace OPENVDB_VERSION_NAME
411 } // namespace openvdb
412 
413 #endif // OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
414 
415 // Copyright (c) 2012-2015 DreamWorks Animation LLC
416 // All rights reserved. This software is distributed under the
417 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
LevelSetPruneOp(TreeT &tree)
Definition: Prune.h:289
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:116
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:388
TreeT::RootNodeType RootT
Definition: Prune.h:285
void operator()(LeafT &) const
Definition: Prune.h:249
TreeT::ValueType ValueT
Definition: Prune.h:214
Definition: Exceptions.h:88
InactivePruneOp(TreeT &tree, const ValueT &v)
Definition: Prune.h:179
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
TolerancePruneOp(TreeT &tree, const ValueT &t)
Definition: Prune.h:219
TreeT::LeafNodeType LeafT
Definition: Prune.h:216
void operator()(RootT &root) const
Definition: Prune.h:197
#define OPENVDB_VERSION_NAME
Definition: version.h:43
InactivePruneOp(TreeT &tree)
Definition: Prune.h:174
void operator()(NodeT &node) const
Definition: Prune.h:188
TreeT::ValueType ValueT
Definition: Prune.h:169
void operator()(RootT &root) const
Definition: Prune.h:326
void operator()(RootT &root) const
Definition: Prune.h:225
Definition: Exceptions.h:39
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:354
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:347
TreeT::LeafNodeType LeafT
Definition: Prune.h:171
void operator()(NodeT &node) const
Definition: Prune.h:237
TreeT::RootNodeType RootT
Definition: Prune.h:215
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:377
TreeT::ValueType ValueT
Definition: Prune.h:284
void operator()(LeafT &) const
Definition: Prune.h:314
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:367
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:56
LevelSetPruneOp(TreeT &tree, const ValueT &outside, const ValueT &inside)
Definition: Prune.h:299
TreeT::LeafNodeType LeafT
Definition: Prune.h:286
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
TreeT::RootNodeType RootT
Definition: Prune.h:170
void operator()(NodeT &node) const
Definition: Prune.h:317
void operator()(LeafT &) const
Definition: Prune.h:185
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:357