HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Clip.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
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 //
29 ///////////////////////////////////////////////////////////////////////////
30 
31 /// @file Clip.h
32 ///
33 /// @brief Functions to clip a grid against a bounding box or against
34 /// another grid's active voxel topology
35 
36 #ifndef OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED
37 #define OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED
38 
39 #include <openvdb/Grid.h>
40 #include <openvdb/math/Math.h> // for math::isNegative()
42 #include "GridTransformer.h" // for tools::resampleToMatch()
43 #include "Prune.h"
44 #include <tbb/blocked_range.h>
45 #include <tbb/parallel_reduce.h>
46 #include <type_traits> // for std::enable_if, std::is_same
47 
48 
49 namespace openvdb {
51 namespace OPENVDB_VERSION_NAME {
52 namespace tools {
53 
54 /// @brief Clip the given grid against a world-space bounding box
55 /// and return a new grid containing the result.
56 /// @param grid the grid to be clipped
57 /// @param bbox a world-space bounding box
58 /// @param keepInterior if true, discard voxels that lie outside the bounding box;
59 /// if false, discard voxels that lie inside the bounding box
60 /// @warning Clipping a level set will likely produce a grid that is
61 /// no longer a valid level set.
62 template<typename GridType> OPENVDB_STATIC_SPECIALIZATION
63 inline typename GridType::Ptr
64 clip(const GridType& grid, const BBoxd& bbox, bool keepInterior = true);
65 
66 /// @brief Clip a grid against the active voxels of another grid
67 /// and return a new grid containing the result.
68 /// @param grid the grid to be clipped
69 /// @param mask a grid whose active voxels form a boolean clipping mask
70 /// @param keepInterior if true, discard voxels that do not intersect the mask;
71 /// if false, discard voxels that intersect the mask
72 /// @details The mask grid need not have the same transform as the source grid.
73 /// Also, if the mask grid is a level set, consider using tools::sdfInteriorMask
74 /// to construct a new mask comprising the interior (rather than the narrow band)
75 /// of the level set.
76 /// @warning Clipping a level set will likely produce a grid that is
77 /// no longer a valid level set.
78 template<typename GridType, typename MaskTreeType> OPENVDB_STATIC_SPECIALIZATION
79 inline typename GridType::Ptr
80 clip(const GridType& grid, const Grid<MaskTreeType>& mask, bool keepInterior = true);
81 
82 
83 ////////////////////////////////////////
84 
85 
86 namespace clip_internal {
87 
88 // Use either MaskGrids or BoolGrids internally.
89 // (MaskGrids have a somewhat lower memory footprint.)
91 //using MaskValueType = bool;
92 
93 
94 template<typename TreeT>
96 {
97 public:
98  using ValueT = typename TreeT::ValueType;
99  using LeafNodeT = typename TreeT::LeafNodeType;
100 
101  MaskInteriorVoxels(const TreeT& tree): mAcc(tree) {}
102 
103  template<typename LeafNodeType>
104  void operator()(LeafNodeType& leaf, size_t /*leafIndex*/) const
105  {
106  const auto* refLeaf = mAcc.probeConstLeaf(leaf.origin());
107  if (refLeaf) {
108  for (auto iter = leaf.beginValueOff(); iter; ++iter) {
109  const auto pos = iter.pos();
110  leaf.setActiveState(pos, math::isNegative(refLeaf->getValue(pos)));
111  }
112  }
113  }
114 
115 private:
117 };
118 
119 
120 ////////////////////////////////////////
121 
122 
123 template<typename TreeT>
125 {
126 public:
127  using MaskTreeT = typename TreeT::template ValueConverter<MaskValueType>::Type;
129 
130  CopyLeafNodes(const TreeT&, const MaskLeafManagerT&);
131 
132  void run(bool threaded = true);
133 
134  typename TreeT::Ptr tree() const { return mNewTree; }
135 
136  CopyLeafNodes(CopyLeafNodes&, tbb::split);
137  void operator()(const tbb::blocked_range<size_t>&);
138  void join(const CopyLeafNodes& rhs) { mNewTree->merge(*rhs.mNewTree); }
139 
140 private:
141  const MaskTreeT* mClipMask;
142  const TreeT* mTree;
143  const MaskLeafManagerT* mLeafNodes;
144  typename TreeT::Ptr mNewTree;
145 };
146 
147 
148 template<typename TreeT>
149 CopyLeafNodes<TreeT>::CopyLeafNodes(const TreeT& tree, const MaskLeafManagerT& leafNodes)
150  : mTree(&tree)
151  , mLeafNodes(&leafNodes)
152  , mNewTree(new TreeT(mTree->background()))
153 {
154 }
155 
156 
157 template<typename TreeT>
159  : mTree(rhs.mTree)
160  , mLeafNodes(rhs.mLeafNodes)
161  , mNewTree(new TreeT(mTree->background()))
162 {
163 }
164 
165 
166 template<typename TreeT>
167 void
169 {
170  if (threaded) tbb::parallel_reduce(mLeafNodes->getRange(), *this);
171  else (*this)(mLeafNodes->getRange());
172 }
173 
174 
175 template<typename TreeT>
176 void
177 CopyLeafNodes<TreeT>::operator()(const tbb::blocked_range<size_t>& range)
178 {
179  tree::ValueAccessor<TreeT> acc(*mNewTree);
180  tree::ValueAccessor<const TreeT> refAcc(*mTree);
181 
182  for (auto n = range.begin(); n != range.end(); ++n) {
183  const auto& maskLeaf = mLeafNodes->leaf(n);
184  const auto& ijk = maskLeaf.origin();
185  const auto* refLeaf = refAcc.probeConstLeaf(ijk);
186 
187  auto* newLeaf = acc.touchLeaf(ijk);
188 
189  if (refLeaf) {
190  for (auto it = maskLeaf.cbeginValueOn(); it; ++it) {
191  const auto pos = it.pos();
192  newLeaf->setValueOnly(pos, refLeaf->getValue(pos));
193  newLeaf->setActiveState(pos, refLeaf->isValueOn(pos));
194  }
195  } else {
196  typename TreeT::ValueType value;
197  bool isActive = refAcc.probeValue(ijk, value);
198 
199  for (auto it = maskLeaf.cbeginValueOn(); it; ++it) {
200  const auto pos = it.pos();
201  newLeaf->setValueOnly(pos, value);
202  newLeaf->setActiveState(pos, isActive);
203  }
204  }
205  }
206 }
207 
208 
209 ////////////////////////////////////////
210 
211 
213 {
214  static const char* name() { return "bin"; }
215  static int radius() { return 2; }
216  static bool mipmap() { return false; }
217  static bool consistent() { return true; }
218 
219  template<class TreeT>
220  static bool sample(const TreeT& inTree,
221  const Vec3R& inCoord, typename TreeT::ValueType& result)
222  {
223  Coord ijk;
224  ijk[0] = int(std::floor(inCoord[0]));
225  ijk[1] = int(std::floor(inCoord[1]));
226  ijk[2] = int(std::floor(inCoord[2]));
227  return inTree.probeValue(ijk, result);
228  }
229 };
230 
231 
232 ////////////////////////////////////////
233 
234 
235 // Convert a grid of one type to a grid of another type
236 template<typename FromGridT, typename ToGridT>
238 {
239  using FromGridCPtrT = typename FromGridT::ConstPtr;
240  using ToGridPtrT = typename ToGridT::Ptr;
241  ToGridPtrT operator()(const FromGridCPtrT& grid) { return ToGridPtrT(new ToGridT(*grid)); }
242 };
243 
244 // Partial specialization that avoids copying when
245 // the input and output grid types are the same
246 template<typename GridT>
247 struct ConvertGrid<GridT, GridT>
248 {
249  using GridCPtrT = typename GridT::ConstPtr;
250  GridCPtrT operator()(const GridCPtrT& grid) { return grid; }
251 };
252 
253 
254 ////////////////////////////////////////
255 
256 
257 // Convert a grid of arbitrary type to a mask grid with the same tree configuration
258 // and return a pointer to the new grid.
259 /// @private
260 template<typename GridT>
262  typename GridT::template ValueConverter<MaskValueType>::Type::Ptr>::type
263 convertToMaskGrid(const GridT& grid)
264 {
265  using MaskGridT = typename GridT::template ValueConverter<MaskValueType>::Type;
266  auto mask = MaskGridT::create(/*background=*/false);
267  mask->topologyUnion(grid);
268  mask->setTransform(grid.constTransform().copy());
269  return mask;
270 }
271 
272 // Overload that avoids any processing if the input grid is already a mask grid
273 /// @private
274 template<typename GridT>
276  typename GridT::ConstPtr>::type
277 convertToMaskGrid(const GridT& grid)
278 {
279  return grid.copy(); // shallow copy
280 }
281 
282 
283 ////////////////////////////////////////
284 
285 
286 /// @private
287 template<typename GridType>
288 inline typename GridType::Ptr
289 doClip(
290  const GridType& grid,
291  const typename GridType::template ValueConverter<MaskValueType>::Type& clipMask,
292  bool keepInterior)
293 {
294  using TreeT = typename GridType::TreeType;
295  using MaskTreeT = typename GridType::TreeType::template ValueConverter<MaskValueType>::Type;
296 
297  const auto gridClass = grid.getGridClass();
298  const auto& tree = grid.tree();
299 
300  MaskTreeT gridMask(false);
301  gridMask.topologyUnion(tree);
302 
303  if (gridClass == GRID_LEVEL_SET) {
304  tree::LeafManager<MaskTreeT> leafNodes(gridMask);
305  leafNodes.foreach(MaskInteriorVoxels<TreeT>(tree));
306 
307  tree::ValueAccessor<const TreeT> acc(tree);
308 
309  typename MaskTreeT::ValueAllIter iter(gridMask);
310  iter.setMaxDepth(MaskTreeT::ValueAllIter::LEAF_DEPTH - 1);
311 
312  for ( ; iter; ++iter) {
313  iter.setActiveState(math::isNegative(acc.getValue(iter.getCoord())));
314  }
315  }
316 
317  if (keepInterior) {
318  gridMask.topologyIntersection(clipMask.constTree());
319  } else {
320  gridMask.topologyDifference(clipMask.constTree());
321  }
322 
323  typename GridType::Ptr outGrid;
324  {
325  // Copy voxel values and states.
326  tree::LeafManager<const MaskTreeT> leafNodes(gridMask);
327  CopyLeafNodes<TreeT> maskOp(tree, leafNodes);
328  maskOp.run();
329  outGrid = GridType::create(maskOp.tree());
330  }
331  {
332  // Copy tile values and states.
333  tree::ValueAccessor<const TreeT> refAcc(tree);
334  tree::ValueAccessor<const MaskTreeT> maskAcc(gridMask);
335 
336  typename TreeT::ValueAllIter it(outGrid->tree());
337  it.setMaxDepth(TreeT::ValueAllIter::LEAF_DEPTH - 1);
338  for ( ; it; ++it) {
339  Coord ijk = it.getCoord();
340 
341  if (maskAcc.isValueOn(ijk)) {
342  typename TreeT::ValueType value;
343  bool isActive = refAcc.probeValue(ijk, value);
344 
345  it.setValue(value);
346  if (!isActive) it.setValueOff();
347  }
348  }
349  }
350 
351  outGrid->setTransform(grid.transform().copy());
352  if (gridClass != GRID_LEVEL_SET) outGrid->setGridClass(gridClass);
353 
354  return outGrid;
355 }
356 
357 } // namespace clip_internal
358 
359 
360 ////////////////////////////////////////
361 
362 
363 /// @private
364 template<typename GridType>
366 inline typename GridType::Ptr
367 clip(const GridType& grid, const BBoxd& bbox, bool keepInterior)
368 {
369  using MaskValueT = clip_internal::MaskValueType;
370  using MaskGridT = typename GridType::template ValueConverter<MaskValueT>::Type;
371 
372  // Transform the world-space bounding box into the source grid's index space.
373  Vec3d idxMin, idxMax;
374  math::calculateBounds(grid.constTransform(), bbox.min(), bbox.max(), idxMin, idxMax);
375  CoordBBox region(Coord::floor(idxMin), Coord::floor(idxMax));
376  // Construct a boolean mask grid that is true inside the index-space bounding box
377  // and false everywhere else.
378  MaskGridT clipMask(/*background=*/false);
379  clipMask.fill(region, /*value=*/true, /*active=*/true);
380 
381  return clip_internal::doClip(grid, clipMask, keepInterior);
382 }
383 
384 
385 /// @private
386 template<typename SrcGridType, typename ClipTreeType>
388 inline typename SrcGridType::Ptr
389 clip(const SrcGridType& srcGrid, const Grid<ClipTreeType>& clipGrid, bool keepInterior)
390 {
391  using MaskValueT = clip_internal::MaskValueType;
392  using ClipGridType = Grid<ClipTreeType>;
393  using SrcMaskGridType = typename SrcGridType::template ValueConverter<MaskValueT>::Type;
394  using ClipMaskGridType = typename ClipGridType::template ValueConverter<MaskValueT>::Type;
395 
396  // Convert the clipping grid to a boolean-valued mask grid with the same tree configuration.
397  auto maskGrid = clip_internal::convertToMaskGrid(clipGrid);
398 
399  // Resample the mask grid into the source grid's index space.
400  if (srcGrid.constTransform() != maskGrid->constTransform()) {
401  auto resampledMask = ClipMaskGridType::create(/*background=*/false);
402  resampledMask->setTransform(srcGrid.constTransform().copy());
403  tools::resampleToMatch<clip_internal::BoolSampler>(*maskGrid, *resampledMask);
404  tools::prune(resampledMask->tree());
405  maskGrid = resampledMask;
406  }
407 
408  // Convert the mask grid to a mask grid with the same tree configuration as the source grid.
409  auto clipMask = clip_internal::ConvertGrid<
410  /*from=*/ClipMaskGridType, /*to=*/SrcMaskGridType>()(maskGrid);
411 
412  // Clip the source grid against the mask grid.
413  return clip_internal::doClip(srcGrid, *clipMask, keepInterior);
414 }
415 
416 } // namespace tools
417 } // namespace OPENVDB_VERSION_NAME
418 } // namespace openvdb
419 
420 #endif // OPENVDB_TOOLS_CLIP_HAS_BEEN_INCLUDED
421 
422 // Copyright (c) 2012-2017 DreamWorks Animation LLC
423 // All rights reserved. This software is distributed under the
424 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
ToGridPtrT operator()(const FromGridCPtrT &grid)
Definition: Clip.h:241
GLenum GLint * range
Definition: glcorearb.h:1924
#define OPENVDB_STATIC_SPECIALIZATION
Macro for determining if there are sufficient C++0x/C++11 features.
Definition: Platform.h:91
void operator()(LeafNodeType &leaf, size_t) const
Definition: Clip.h:104
png_infop png_color_16p * background
Definition: png.h:2326
static bool sample(const TreeT &inTree, const Vec3R &inCoord, typename TreeT::ValueType &result)
Definition: Clip.h:220
GLint GLuint mask
Definition: glcorearb.h:123
typename TreeT::template ValueConverter< MaskValueType >::Type MaskTreeT
Definition: Clip.h:127
CopyLeafNodes(const TreeT &, const MaskLeafManagerT &)
Definition: Clip.h:149
bool isNegative(const Type &x)
Return true if x is less than zero.
Definition: Math.h:354
GLdouble n
Definition: glcorearb.h:2007
const LeafNodeT * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z), or nullptr if no such node exists...
const Vec3T & min() const
Return a const reference to the minimum point of the BBox.
Definition: BBox.h:84
#define OPENVDB_VERSION_NAME
Definition: version.h:43
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
OPENVDB_API void calculateBounds(const Transform &t, const Vec3d &minWS, const Vec3d &maxWS, Vec3d &minIS, Vec3d &maxIS)
Calculate an axis-aligned bounding box in index space from an axis-aligned bounding box in world spac...
Defined various multi-threaded utility functions for trees.
LeafNodeT * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one, but preserve the values and active states of all voxels.
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:115
OPENVDB_STATIC_SPECIALIZATION GridType::Ptr clip(const GridType &grid, const BBoxd &bbox, bool keepInterior=true)
Clip the given grid against a world-space bounding box and return a new grid containing the result...
Definition: Clip.h:367
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54
const Vec3T & max() const
Return a const reference to the maximum point of the BBox.
Definition: BBox.h:87
int floor(T x)
Definition: ImathFun.h:150
GLsizei const GLfloat * value
Definition: glcorearb.h:823
typedef int
Definition: png.h:1175
math::BBox< Vec3d > BBoxd
Definition: Types.h:87
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
#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:374
void operator()(const tbb::blocked_range< size_t > &)
Definition: Clip.h:177
bool probeValue(const Coord &xyz, ValueType &value) const
Return the active state of the voxel as well as its value.
tree::LeafManager< const MaskTreeT > MaskLeafManagerT
Definition: Clip.h:128