OpenVDB  5.0.0
Prune.h
Go to the documentation of this file.
1 //
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 //
30 //
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 <boost/utility/enable_if.hpp>
43 #include <boost/static_assert.hpp>
44 #include <boost/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>
49 #include <openvdb/tree/NodeManager.h>
50 
51 namespace openvdb {
53 namespace OPENVDB_VERSION_NAME {
54 namespace tools {
55 
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 
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 
98 template<typename TreeT>
99 inline void
100 pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1);
101 
102 
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 
131 template<typename TreeT>
132 inline void
133 pruneLevelSet(TreeT& tree,
134  bool threaded = true,
135  size_t grainSize = 1);
136 
137 
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 
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  BOOST_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  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
219 
220  TolerancePruneOp(TreeT& tree, const ValueT& tol) : mTolerance(tol)
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  // Private method specialized for leaf nodes
255  inline ValueT median(LeafT& leaf) const {return leaf.medianAll(leaf.buffer().data());}
256 
257  // Private method for internal nodes
258  template<typename NodeT>
259  inline typename NodeT::ValueType median(NodeT& node) const
260  {
261  using UnionT = typename NodeT::UnionType;
262  UnionT* data = const_cast<UnionT*>(node.getTable());//never do this at home kids :)
263  static const size_t midpoint = (NodeT::NUM_VALUES - 1) >> 1;
264  auto op = [](const UnionT& a, const UnionT& b){return a.getValue() < b.getValue();};
265  std::nth_element(data, data + midpoint, data + NodeT::NUM_VALUES, op);
266  return data[midpoint].getValue();
267  }
268 
269  // Specialization to nodes templated on booleans values
270  template<typename NodeT>
271  inline
272  typename boost::enable_if<boost::is_same<bool, typename NodeT::ValueType>, bool>::type
273  isConstant(NodeT& node, bool& value, bool& state) const
274  {
275  return node.isConstant(value, state, mTolerance);
276  }
277 
278  // Nodes templated on non-boolean values
279  template<typename NodeT>
280  inline
281  typename boost::disable_if<boost::is_same<bool, typename NodeT::ValueType>, bool>::type
282  isConstant(NodeT& node, ValueT& value, bool& state) const
283  {
284  ValueT tmp;
285  const bool test = node.isConstant(value, tmp, state, mTolerance);
286  if (test) value = this->median(node);
287  return test;
288  }
289 
290  const ValueT mTolerance;
291 };// TolerancePruneOp
292 
293 
294 template<typename TreeT, Index TerminationLevel = 0>
296 {
297 public:
298  typedef typename TreeT::ValueType ValueT;
299  typedef typename TreeT::RootNodeType RootT;
300  typedef typename TreeT::LeafNodeType LeafT;
301  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
302 
303  LevelSetPruneOp(TreeT& tree)
304  : mOutside(tree.background())
305  , mInside(math::negative(mOutside))
306  {
307  if (math::isNegative(mOutside)) {
309  "LevelSetPruneOp: the background value cannot be negative!");
310  }
311  tree.clearAllAccessors();//clear cache of nodes that could be pruned
312  }
313  LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside)
314  : mOutside(outside)
315  , mInside(inside)
316  {
317  if (math::isNegative(mOutside)) {
319  "LevelSetPruneOp: the outside value cannot be negative!");
320  }
321  if (!math::isNegative(mInside)) {
323  "LevelSetPruneOp: the inside value must be negative!");
324  }
325  tree.clearAllAccessors();//clear cache of nodes that could be pruned
326  }
327  // Nothing to do at the leaf node level
328  void operator()(LeafT&) const {}
329  // Prune the child nodes of the internal nodes
330  template<typename NodeT>
331  void operator()(NodeT& node) const
332  {
333  if (NodeT::LEVEL > TerminationLevel) {
334  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
335  if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false);
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-2017 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/ )
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
TreeT::LeafNodeType LeafT
Definition: Prune.h:172
TreeT::ValueType ValueT
Definition: Prune.h:170
TreeT::LeafNodeType LeafT
Definition: Prune.h:300
InactivePruneOp(TreeT &tree)
Definition: Prune.h:175
LevelSetPruneOp(TreeT &tree)
Definition: Prune.h:303
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:338
void operator()(LeafT &) const
Definition: Prune.h:250
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:108
void operator()(NodeT &node) const
Definition: Prune.h:189
TreeT::RootNodeType RootT
Definition: Prune.h:299
void operator()(NodeT &node) const
Definition: Prune.h:238
void operator()(RootT &root) const
Definition: Prune.h:340
InactivePruneOp(TreeT &tree, const ValueT &v)
Definition: Prune.h:180
void operator()(RootT &root) const
Definition: Prune.h:198
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
TreeT::LeafNodeType LeafT
Definition: Prune.h:217
Definition: Exceptions.h:91
TolerancePruneOp(TreeT &tree, const ValueT &tol)
Definition: Prune.h:220
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
TreeT::ValueType ValueT
Definition: Prune.h:215
Definition: Exceptions.h:39
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:402
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:108
void operator()(NodeT &node) const
Definition: Prune.h:331
void operator()(RootT &root) const
Definition: Prune.h:226
TreeT::RootNodeType RootT
Definition: Prune.h:216
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
void operator()(LeafT &) const
Definition: Prune.h:186
LevelSetPruneOp(TreeT &tree, const ValueT &outside, const ValueT &inside)
Definition: Prune.h:313
TreeT::RootNodeType RootT
Definition: Prune.h:171
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
TreeT::ValueType ValueT
Definition: Prune.h:298
void operator()(LeafT &) const
Definition: Prune.h:328
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
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