OpenVDB  3.0.0
Prune.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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 <openvdb/math/Math.h> // for isNegative and negative
42 #include <openvdb/Types.h> // for Index typedef
43 #include <boost/static_assert.hpp>
44 #include <openvdb/Types.h>
45 #include <openvdb/tree/NodeManager.h>
46 
47 namespace openvdb {
49 namespace OPENVDB_VERSION_NAME {
50 namespace tools {
51 
60 template<typename TreeT>
61 inline void
62 prune(TreeT& tree,
63  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
64  bool threaded = true,
65  size_t grainSize = 1);
66 
67 
76 template<typename TreeT>
77 inline void
78 pruneTiles(TreeT& tree,
79  typename TreeT::ValueType tolerance = zeroVal<typename TreeT::ValueType>(),
80  bool threaded = true,
81  size_t grainSize = 1);
82 
83 
90 template<typename TreeT>
91 inline void
92 pruneInactive(TreeT& tree, bool threaded = true, size_t grainSize = 1);
93 
94 
102 template<typename TreeT>
103 inline void
105  TreeT& tree,
106  const typename TreeT::ValueType& value,
107  bool threaded = true,
108  size_t grainSize = 1);
109 
110 
123 template<typename TreeT>
124 inline void
125 pruneLevelSet(TreeT& tree,
126  bool threaded = true,
127  size_t grainSize = 1);
128 
129 
146 template<typename TreeT>
147 inline void
148 pruneLevelSet(TreeT& tree,
149  const typename TreeT::ValueType& outsideWidth,
150  const typename TreeT::ValueType& insideWidth,
151  bool threaded = true,
152  size_t grainSize = 1);
153 
154 
156 
157 
158 template<typename TreeT, Index TerminationLevel = 0>
160 {
161 public:
162  typedef typename TreeT::ValueType ValueT;
163  typedef typename TreeT::RootNodeType RootT;
164  typedef typename TreeT::LeafNodeType LeafT;
165  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
166 
167  InactivePruneOp(TreeT& tree) : mValue(tree.background())
168  {
169  tree.clearAllAccessors();//clear cache of nodes that could be pruned
170  }
171 
172  InactivePruneOp(TreeT& tree, const ValueT& v) : mValue(v)
173  {
174  tree.clearAllAccessors();//clear cache of nodes that could be pruned
175  }
176 
177  // Nothing to do at the leaf node level
178  void operator()(LeafT& node) const {;}
179  // Prune the child nodes of the internal nodes
180  template<typename NodeT>
181  void operator()(NodeT& node) const
182  {
183  if (NodeT::LEVEL > TerminationLevel) {
184  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
185  if (it->isInactive()) node.addTile(it.pos(), mValue, false);
186  }
187  }
188  }
189  // Prune the child nodes of the root node
190  void operator()(RootT& root) const
191  {
192  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
193  if (it->isInactive()) root.addTile(it.getCoord(), mValue, false);
194  }
195  root.eraseBackgroundTiles();
196  }
197 private:
198 
199  const ValueT mValue;
200 };// InactivePruneOp
201 
202 
203 template<typename TreeT, Index TerminationLevel = 0>
205 {
206 public:
207  typedef typename TreeT::ValueType ValueT;
208  typedef typename TreeT::RootNodeType RootT;
209  typedef typename TreeT::LeafNodeType LeafT;
210  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
211 
212  TolerancePruneOp(TreeT& tree, const ValueT& t) : mTolerance(t)
213  {
214  tree.clearAllAccessors();//clear cache of nodes that could be pruned
215  }
216 
217  // Nothing to do at the leaf node level
218  void operator()(LeafT& node) const {;}
219  // Prune the child nodes of the internal nodes
220  template<typename NodeT>
221  void operator()(NodeT& node) const
222  {
223  if (NodeT::LEVEL > TerminationLevel) {
224  ValueT value;
225  bool state;
226  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
227  if (it->isConstant(value, state, mTolerance)) node.addTile(it.pos(), value, state);
228  }
229  }
230  }
231  // Prune the child nodes of the root node
232  void operator()(RootT& root) const
233  {
234  ValueT value;
235  bool state;
236  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
237  if (it->isConstant(value, state, mTolerance)) root.addTile(it.getCoord(), value, state);
238  }
239  root.eraseBackgroundTiles();
240  }
241 private:
242 
243  const ValueT mTolerance;
244 };// TolerancePruneOp
245 
246 
247 template<typename TreeT, Index TerminationLevel = 0>
249 {
250 public:
251  typedef typename TreeT::ValueType ValueT;
252  typedef typename TreeT::RootNodeType RootT;
253  typedef typename TreeT::LeafNodeType LeafT;
254  BOOST_STATIC_ASSERT(RootT::LEVEL > TerminationLevel);
255 
256  LevelSetPruneOp(TreeT& tree)
257  : mOutside(tree.background())
258  , mInside(math::negative(mOutside))
259  {
260  if (math::isNegative(mOutside)) {
262  "LevelSetPruneOp: the background value cannot be negative!");
263  }
264  tree.clearAllAccessors();//clear cache of nodes that could be pruned
265  }
266  LevelSetPruneOp(TreeT& tree, const ValueT& outside, const ValueT& inside)
267  : mOutside(outside)
268  , mInside(inside)
269  {
270  if (math::isNegative(mOutside)) {
272  "LevelSetPruneOp: the outside value cannot be negative!");
273  }
274  if (!math::isNegative(mInside)) {
276  "LevelSetPruneOp: the inside value must be negative!");
277  }
278  tree.clearAllAccessors();//clear cache of nodes that could be pruned
279  }
280  // Nothing to do at the leaf node level
281  void operator()(LeafT& node) const {;}
282  // Prune the child nodes of the internal nodes
283  template<typename NodeT>
284  void operator()(NodeT& node) const
285  {
286  if (NodeT::LEVEL > TerminationLevel) {
287  for (typename NodeT::ChildOnIter it=node.beginChildOn(); it; ++it) {
288  if (it->isInactive()) node.addTile(it.pos(), this->getTileValue(it), false);
289  }
290  }
291  }
292  // Prune the child nodes of the root node
293  void operator()(RootT& root) const
294  {
295  for (typename RootT::ChildOnIter it = root.beginChildOn(); it; ++it) {
296  if (it->isInactive()) root.addTile(it.getCoord(), this->getTileValue(it), false);
297  }
298  root.eraseBackgroundTiles();
299  }
300 
301 private:
302  template <typename IterT>
303  inline ValueT getTileValue(const IterT& iter) const
304  {
305  return math::isNegative(iter->getFirstValue()) ? mInside : mOutside;
306  }
307 
308  const ValueT mOutside, mInside;
309 };// LevelSetPruneOp
310 
311 
312 template<typename TreeT>
313 inline void
314 prune(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
315 {
316  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
317  TolerancePruneOp<TreeT> op(tree, tol);
318  nodes.processBottomUp(op, threaded, grainSize);
319 }
320 
321 
322 template<typename TreeT>
323 inline void
324 pruneTiles(TreeT& tree, typename TreeT::ValueType tol, bool threaded, size_t grainSize)
325 {
326  tree::NodeManager<TreeT, TreeT::DEPTH-3> nodes(tree);
327  TolerancePruneOp<TreeT> op(tree, tol);
328  nodes.processBottomUp(op, threaded, grainSize);
329 }
330 
331 
332 template<typename TreeT>
333 inline void
334 pruneInactive(TreeT& tree, bool threaded, size_t grainSize)
335 {
336  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
337  InactivePruneOp<TreeT> op(tree);
338  nodes.processBottomUp(op, threaded, grainSize);
339 }
340 
341 
342 template<typename TreeT>
343 inline void
344 pruneInactiveWithValue(TreeT& tree, const typename TreeT::ValueType& v,
345  bool threaded, size_t grainSize)
346 {
347  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
348  InactivePruneOp<TreeT> op(tree, v);
349  nodes.processBottomUp(op, threaded, grainSize);
350 }
351 
352 
353 template<typename TreeT>
354 inline void
355 pruneLevelSet(TreeT& tree,
356  const typename TreeT::ValueType& outside,
357  const typename TreeT::ValueType& inside,
358  bool threaded,
359  size_t grainSize)
360 {
361  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
362  LevelSetPruneOp<TreeT> op(tree, outside, inside);
363  nodes.processBottomUp(op, threaded, grainSize);
364 }
365 
366 
367 template<typename TreeT>
368 inline void
369 pruneLevelSet(TreeT& tree, bool threaded, size_t grainSize)
370 {
371  tree::NodeManager<TreeT, TreeT::DEPTH-2> nodes(tree);
372  LevelSetPruneOp<TreeT> op(tree);
373  nodes.processBottomUp(op, threaded, grainSize);
374 }
375 
376 } // namespace tools
377 } // namespace OPENVDB_VERSION_NAME
378 } // namespace openvdb
379 
380 #endif // OPENVDB_TOOLS_PRUNE_HAS_BEEN_INCLUDED
381 
382 // Copyright (c) 2012-2014 DreamWorks Animation LLC
383 // All rights reserved. This software is distributed under the
384 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:344
void operator()(LeafT &node) const
Definition: Prune.h:218
TreeT::RootNodeType RootT
Definition: Prune.h:208
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:344
TreeT::ValueType ValueT
Definition: Prune.h:162
LevelSetPruneOp(TreeT &tree)
Definition: Prune.h:256
TreeT::RootNodeType RootT
Definition: Prune.h:163
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
TreeT::LeafNodeType LeafT
Definition: Prune.h:209
TreeT::RootNodeType RootT
Definition: Prune.h:252
LevelSetPruneOp(TreeT &tree, const ValueT &outside, const ValueT &inside)
Definition: Prune.h:266
TreeT::LeafNodeType LeafT
Definition: Prune.h:164
TreeT::ValueType ValueT
Definition: Prune.h:251
void operator()(NodeT &node) const
Definition: Prune.h:284
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:334
void operator()(RootT &root) const
Definition: Prune.h:232
#define OPENVDB_VERSION_NAME
Definition: version.h:43
TolerancePruneOp(TreeT &tree, const ValueT &t)
Definition: Prune.h:212
Definition: Exceptions.h:39
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:324
void operator()(LeafT &node) const
Definition: Prune.h:178
TreeT::LeafNodeType LeafT
Definition: Prune.h:253
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
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:355
void operator()(RootT &root) const
Definition: Prune.h:190
Definition: Exceptions.h:88
InactivePruneOp(TreeT &tree)
Definition: Prune.h:167
void operator()(LeafT &node) const
Definition: Prune.h:281
void operator()(NodeT &node) const
Definition: Prune.h:221
void operator()(NodeT &node) const
Definition: Prune.h:181
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
TreeT::ValueType ValueT
Definition: Prune.h:207
void operator()(RootT &root) const
Definition: Prune.h:293
InactivePruneOp(TreeT &tree, const ValueT &v)
Definition: Prune.h:172
#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:314