OpenVDB  3.0.0
LevelSetUtil.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 //
35 
36 #ifndef OPENVDB_TOOLS_LEVELSETUTIL_HAS_BEEN_INCLUDED
37 #define OPENVDB_TOOLS_LEVELSETUTIL_HAS_BEEN_INCLUDED
38 
39 #include <openvdb/Grid.h>
40 #include <openvdb/tree/LeafManager.h>
41 #include <openvdb/tools/Prune.h>
42 #include <tbb/blocked_range.h>
43 #include <tbb/parallel_reduce.h>
44 #include <limits>
45 
46 
47 namespace openvdb {
49 namespace OPENVDB_VERSION_NAME {
50 namespace tools {
51 
52 // MS Visual C++ requires this extra level of indirection in order to compile
53 // THIS MUST EXIST IN AN UNNAMED NAMESPACE IN ORDER TO COMPILE ON WINDOWS
54 namespace {
55 
56 template<typename GridType>
57 inline typename GridType::ValueType lsutilGridMax()
58 {
60 }
61 
62 template<typename GridType>
63 inline typename GridType::ValueType lsutilGridZero()
64 {
65  return zeroVal<typename GridType::ValueType>();
66 }
67 
68 } // unnamed namespace
69 
70 
72 
73 
88 template<class GridType>
89 inline void
91  GridType& grid,
92  typename GridType::ValueType cutoffDistance = lsutilGridMax<GridType>());
93 
94 
96 
97 
107 template<class GridType>
108 inline typename Grid<typename GridType::TreeType::template ValueConverter<bool>::Type>::Ptr
110  const GridType& grid,
111  typename GridType::ValueType iso = lsutilGridZero<GridType>());
112 
113 
115 
116 
121 template<class TreeType>
123 {
124 public:
126  typedef typename TreeType::ValueType ValueType;
127 
128  // LeafArray = openvdb::tree::LeafManager<TreeType> leafs(myTree)
129  MinMaxVoxel(LeafArray&);
130 
131  void runParallel();
132  void runSerial();
133 
134  const ValueType& minVoxel() const { return mMin; }
135  const ValueType& maxVoxel() const { return mMax; }
136 
137  inline MinMaxVoxel(const MinMaxVoxel<TreeType>&, tbb::split);
138  inline void operator()(const tbb::blocked_range<size_t>&);
139  inline void join(const MinMaxVoxel<TreeType>&);
140 
141 private:
142  LeafArray& mLeafArray;
143  ValueType mMin, mMax;
144 };
145 
146 
148 
149 
150 // Internal utility objects and implementation details
151 namespace internal {
152 
153 template<typename ValueType>
155 {
156 public:
157  FogVolumeOp(ValueType cutoffDistance)
158  : mWeight(ValueType(1.0) / cutoffDistance)
159  {
160  }
161 
162  // cutoff has to be < 0.0
163  template <typename LeafNodeType>
164  void operator()(LeafNodeType &leaf, size_t/*leafIndex*/) const
165  {
166  const ValueType zero = zeroVal<ValueType>();
167 
168  for (typename LeafNodeType::ValueAllIter iter = leaf.beginValueAll(); iter; ++iter) {
169  ValueType& value = const_cast<ValueType&>(iter.getValue());
170  if (value > zero) {
171  value = zero;
172  iter.setValueOff();
173  } else {
174  value = std::min(ValueType(1.0), value * mWeight);
175  iter.setValueOn(value > zero);
176  }
177  }
178  }
179 
180 private:
181  ValueType mWeight;
182 }; // class FogVolumeOp
183 
184 
185 template<typename TreeType>
187 {
188 public:
189  InteriorMaskOp(const TreeType& tree, typename TreeType::ValueType iso)
190  : mTree(tree)
191  , mIso(iso)
192  {
193  }
194 
195  template <typename LeafNodeType>
196  void operator()(LeafNodeType &leaf, size_t/*leafIndex*/) const
197  {
198  const Coord origin = leaf.origin();
199  const typename TreeType::LeafNodeType* refLeafPt = mTree.probeConstLeaf(origin);
200 
201  if (refLeafPt != NULL) {
202 
203  const typename TreeType::LeafNodeType& refLeaf = *refLeafPt;
204  typename LeafNodeType::ValueAllIter iter = leaf.beginValueAll();
205 
206  for (; iter; ++iter) {
207  if (refLeaf.getValue(iter.pos()) < mIso) {
208  iter.setValueOn();
209  } else {
210  iter.setValueOff();
211  }
212  }
213  }
214  }
215 
216 private:
217  const TreeType& mTree;
218  typename TreeType::ValueType mIso;
219 }; // class InteriorMaskOp
220 
221 } // namespace internal
222 
223 
225 
226 
227 template <class TreeType>
229  : mLeafArray(leafs)
230  , mMin(std::numeric_limits<ValueType>::max())
231  , mMax(-mMin)
232 {
233 }
234 
235 
236 template <class TreeType>
237 inline
239  : mLeafArray(rhs.mLeafArray)
240  , mMin(rhs.mMin)
241  , mMax(rhs.mMax)
242 {
243 }
244 
245 
246 template <class TreeType>
247 void
249 {
250  tbb::parallel_reduce(mLeafArray.getRange(), *this);
251 }
252 
253 
254 template <class TreeType>
255 void
257 {
258  (*this)(mLeafArray.getRange());
259 }
260 
261 
262 template <class TreeType>
263 inline void
264 MinMaxVoxel<TreeType>::operator()(const tbb::blocked_range<size_t>& range)
265 {
266  typename TreeType::LeafNodeType::ValueOnCIter iter;
267 
268  for (size_t n = range.begin(); n < range.end(); ++n) {
269  iter = mLeafArray.leaf(n).cbeginValueOn();
270  for (; iter; ++iter) {
271  const ValueType value = iter.getValue();
272  mMin = std::min(mMin, value);
273  mMax = std::max(mMax, value);
274  }
275  }
276 }
277 
278 
279 template <class TreeType>
280 inline void
282 {
283  mMin = std::min(mMin, rhs.mMin);
284  mMax = std::max(mMax, rhs.mMax);
285 }
286 
287 
288 
290 
291 
292 template <class GridType>
293 inline void
294 sdfToFogVolume(GridType& grid, typename GridType::ValueType cutoffDistance)
295 {
296  typedef typename GridType::TreeType TreeType;
297  typedef typename GridType::ValueType ValueType;
298 
299  cutoffDistance = -std::abs(cutoffDistance);
300 
301  TreeType& tree = const_cast<TreeType&>(grid.tree());
302 
303  { // Transform all voxels (parallel, over leaf nodes)
304  tree::LeafManager<TreeType> leafs(tree);
305 
306  MinMaxVoxel<TreeType> minmax(leafs);
307  minmax.runParallel();
308 
309  // Clamp to the interior band width.
310  if (minmax.minVoxel() > cutoffDistance) {
311  cutoffDistance = minmax.minVoxel();
312  }
313 
314  leafs.foreach(internal::FogVolumeOp<ValueType>(cutoffDistance));
315  }
316 
317  // Transform all tile values (serial, but the iteration
318  // is constrained from descending into leaf nodes)
319  const ValueType zero = zeroVal<ValueType>();
320  typename TreeType::ValueAllIter iter(tree);
321  iter.setMaxDepth(TreeType::ValueAllIter::LEAF_DEPTH - 1);
322 
323  for ( ; iter; ++iter) {
324  ValueType& value = const_cast<ValueType&>(iter.getValue());
325 
326  if (value > zero) {
327  value = zero;
328  iter.setValueOff();
329  } else {
330  value = ValueType(1.0);
331  iter.setActiveState(true);
332  }
333  }
334 
335  // Update the tree background value.
336 
337  typename TreeType::Ptr newTree(new TreeType(/*background=*/zero));
338  newTree->merge(tree);
339  // This is faster than calling Tree::setBackground, since we only need
340  // to update the value that is returned for coordinates that don't fall
341  // inside an allocated node. All inactive tiles and voxels have already
342  // been updated in the previous step so the Tree::setBackground method
343  // will in this case do a redundant traversal of the tree to update the
344  // inactive values once more.
345 
346  //newTree->pruneInactive();
347  grid.setTree(newTree);
348 
349  grid.setGridClass(GRID_FOG_VOLUME);
350 }
351 
352 
354 
355 
356 template <class GridType>
358 sdfInteriorMask(const GridType& grid, typename GridType::ValueType iso)
359 {
360  typedef typename GridType::TreeType::template ValueConverter<bool>::Type BoolTreeType;
361  typedef Grid<BoolTreeType> BoolGridType;
362 
363  typename BoolGridType::Ptr maskGrid(BoolGridType::create(false));
364  maskGrid->setTransform(grid.transform().copy());
365  BoolTreeType& maskTree = maskGrid->tree();
366 
367  maskTree.topologyUnion(grid.tree());
368 
369  { // Evaluate voxels (parallel, over leaf nodes)
370 
371  tree::LeafManager<BoolTreeType> leafs(maskTree);
372 
374  }
375 
376  // Evaluate tile values (serial, but the iteration
377  // is constrained from descending into leaf nodes)
378 
380  typename BoolTreeType::ValueAllIter iter(maskTree);
381  iter.setMaxDepth(BoolTreeType::ValueAllIter::LEAF_DEPTH - 1);
382 
383  for ( ; iter; ++iter) {
384  iter.setActiveState(acc.getValue(iter.getCoord()) < iso);
385  }
386 
387  tools::pruneInactive(maskTree);
388 
389  return maskGrid;
390 }
391 
392 } // namespace tools
393 } // namespace OPENVDB_VERSION_NAME
394 } // namespace openvdb
395 
396 #endif // OPENVDB_TOOLS_LEVELSETUTIL_HAS_BEEN_INCLUDED
397 
398 // Copyright (c) 2012-2014 DreamWorks Animation LLC
399 // All rights reserved. This software is distributed under the
400 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
MinMaxVoxel(LeafArray &)
Definition: LevelSetUtil.h:228
TreeType::ValueType ValueType
Definition: LevelSetUtil.h:126
void join(const MinMaxVoxel< TreeType > &)
Definition: LevelSetUtil.h:281
Grid< typename GridType::TreeType::template ValueConverter< bool >::Type >::Ptr sdfInteriorMask(const GridType &grid, typename GridType::ValueType iso=lsutilGridZero< GridType >())
Threaded method to extract an interior region mask from a level set/SDF grid.
Definition: LevelSetUtil.h:358
Definition: ValueAccessor.h:173
void operator()(const tbb::blocked_range< size_t > &)
Definition: LevelSetUtil.h:264
void runParallel()
Definition: LevelSetUtil.h:248
Threaded operator that finds the minimum and maximum values among the active leaf-level voxels of a g...
Definition: LevelSetUtil.h:122
FogVolumeOp(ValueType cutoffDistance)
Definition: LevelSetUtil.h:157
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
InteriorMaskOp(const TreeType &tree, typename TreeType::ValueType iso)
Definition: LevelSetUtil.h:189
void runSerial()
Definition: LevelSetUtil.h:256
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
tree::LeafManager< TreeType > LeafArray
Definition: LevelSetUtil.h:125
void foreach(const LeafOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to each leaf node in the LeafManager.
Definition: LeafManager.h:476
const ValueType & minVoxel() const
Definition: LevelSetUtil.h:134
void operator()(LeafNodeType &leaf, size_t) const
Definition: LevelSetUtil.h:196
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Definition: Types.h:211
void sdfToFogVolume(GridType &grid, typename GridType::ValueType cutoffDistance=lsutilGridMax< GridType >())
Threaded method to convert a sparse level set/SDF into a sparse fog volume.
Definition: LevelSetUtil.h:294
Definition: Exceptions.h:39
void operator()(LeafNodeType &leaf, size_t) const
Definition: LevelSetUtil.h:164
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
const ValueType & maxVoxel() const
Definition: LevelSetUtil.h:135
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
void setActiveState(const Coord &xyz, bool on=true)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: ValueAccessor.h:291
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Definition: LevelSetUtil.h:154