OpenVDB  3.1.0
LevelSetFracture.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_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
38 #define OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
39 
40 #include <openvdb/Grid.h>
41 #include <openvdb/math/Quat.h>
43 #include <openvdb/tools/Prune.h>
46 #include "Composite.h" // for csgIntersection() and csgDifference()
47 #include "GridTransformer.h" // for resampleToMatch()
48 
49 #include <limits>
50 #include <list>
51 #include <deque>
52 
53 
54 namespace openvdb {
56 namespace OPENVDB_VERSION_NAME {
57 namespace tools {
58 
60 template<class GridType, class InterruptType = util::NullInterrupter>
62 {
63 public:
64  typedef std::vector<Vec3s> Vec3sList;
65  typedef std::vector<math::Quats> QuatsList;
66  typedef std::list<typename GridType::Ptr> GridPtrList;
67  typedef typename GridPtrList::iterator GridPtrListIter;
68 
69 
73  explicit LevelSetFracture(InterruptType* interrupter = NULL);
74 
93  void fracture(GridPtrList& grids, const GridType& cutter, bool segment = false,
94  const Vec3sList* points = NULL, const QuatsList* rotations = NULL,
95  bool cutterOverlap = true);
96 
98  GridPtrList& fragments() { return mFragments; }
99 
101  void clear() { mFragments.clear(); }
102 
103 private:
104  // disallow copy by assignment
105  void operator=(const LevelSetFracture&) {}
106 
107  bool wasInterrupted(int percent = -1) const {
108  return mInterrupter && mInterrupter->wasInterrupted(percent);
109  }
110 
111  bool isValidFragment(GridType&) const;
112  void segmentFragments(GridPtrList&) const;
113  void process(GridPtrList&, const GridType& cutter);
114 
115  InterruptType* mInterrupter;
116  GridPtrList mFragments;
117 };
118 
119 
121 
122 
123 // Internal utility objects and implementation details
124 
125 namespace internal {
126 
129 template<typename GridType, typename InterruptType>
130 inline std::vector<typename GridType::Ptr>
131 segment(GridType& grid, InterruptType* interrupter = NULL)
132 {
133  typedef typename GridType::Ptr GridPtr;
134  typedef typename GridType::TreeType TreeType;
135  typedef typename TreeType::Ptr TreePtr;
136  typedef typename TreeType::ValueType ValueType;
137 
138  std::vector<GridPtr> segments;
139 
140  while (grid.activeVoxelCount() > 0) {
141 
142  if (interrupter && interrupter->wasInterrupted()) break;
143 
144  // Deep copy the grid's metadata (tree and transform are shared)
145  GridPtr segment(new GridType(grid, ShallowCopy()));
146  // Make the transform unique and insert an empty tree
147  segment->setTransform(grid.transform().copy());
148  TreePtr tree(new TreeType(grid.background()));
149  segment->setTree(tree);
150 
151  std::deque<Coord> coordList;
152  coordList.push_back(grid.tree().beginLeaf()->beginValueOn().getCoord());
153 
154  Coord ijk, n_ijk;
155  ValueType value;
156 
157  typename tree::ValueAccessor<TreeType> sourceAcc(grid.tree());
158  typename tree::ValueAccessor<TreeType> targetAcc(segment->tree());
159 
160  while (!coordList.empty()) {
161 
162  if (interrupter && interrupter->wasInterrupted()) break;
163 
164  ijk = coordList.back();
165  coordList.pop_back();
166 
167  if (!sourceAcc.probeValue(ijk, value)) continue;
168  if (targetAcc.isValueOn(ijk)) continue;
169 
170  targetAcc.setValue(ijk, value);
171  sourceAcc.setValueOff(ijk);
172 
173  for (int n = 0; n < 6; n++) {
174  n_ijk = ijk + util::COORD_OFFSETS[n];
175  if (!targetAcc.isValueOn(n_ijk) && sourceAcc.isValueOn(n_ijk)) {
176  coordList.push_back(n_ijk);
177  }
178  }
179  }
180 
181  tools::pruneInactive(grid.tree());
182  tools::signedFloodFill(segment->tree());
183  segments.push_back(segment);
184  }
185  return segments;
186 }
187 
188 
189 template<class TreeType>
191 {
192 public:
194  typedef typename TreeType::ValueType ValueType;
195 
196  // LeafArray = openvdb::tree::LeafManager<TreeType> leafs(myTree)
197  MinMaxVoxel(LeafArray&);
198 
199  void runParallel();
200  void runSerial();
201 
202  const ValueType& minVoxel() const { return mMin; }
203  const ValueType& maxVoxel() const { return mMax; }
204 
205  inline MinMaxVoxel(const MinMaxVoxel<TreeType>&, tbb::split);
206  inline void operator()(const tbb::blocked_range<size_t>&);
207  inline void join(const MinMaxVoxel<TreeType>&);
208 
209 private:
210  LeafArray& mLeafArray;
211  ValueType mMin, mMax;
212 };
213 
214 
215 template <class TreeType>
217  : mLeafArray(leafs)
218  , mMin(std::numeric_limits<ValueType>::max())
219  , mMax(-mMin)
220 {
221 }
222 
223 
224 template <class TreeType>
225 inline
227  : mLeafArray(rhs.mLeafArray)
228  , mMin(std::numeric_limits<ValueType>::max())
229  , mMax(-mMin)
230 {
231 }
232 
233 
234 template <class TreeType>
235 void
237 {
238  tbb::parallel_reduce(mLeafArray.getRange(), *this);
239 }
240 
241 
242 template <class TreeType>
243 void
245 {
246  (*this)(mLeafArray.getRange());
247 }
248 
249 
250 template <class TreeType>
251 inline void
252 MinMaxVoxel<TreeType>::operator()(const tbb::blocked_range<size_t>& range)
253 {
254  typename TreeType::LeafNodeType::ValueOnCIter iter;
255 
256  for (size_t n = range.begin(); n < range.end(); ++n) {
257  iter = mLeafArray.leaf(n).cbeginValueOn();
258  for (; iter; ++iter) {
259  const ValueType value = iter.getValue();
260  mMin = std::min(mMin, value);
261  mMax = std::max(mMax, value);
262  }
263  }
264 }
265 
266 
267 template <class TreeType>
268 inline void
270 {
271  mMin = std::min(mMin, rhs.mMin);
272  mMax = std::max(mMax, rhs.mMax);
273 }
274 
275 
276 } // namespace internal
277 
278 
280 
281 
282 template<class GridType, class InterruptType>
284  : mInterrupter(interrupter)
285  , mFragments()
286 {
287 }
288 
289 
290 template<class GridType, class InterruptType>
291 void
292 LevelSetFracture<GridType, InterruptType>::fracture(GridPtrList& grids, const GridType& cutter,
293  bool segmentation, const Vec3sList* points, const QuatsList* rotations, bool cutterOverlap)
294 {
295  // We can process all incoming grids with the same cutter instance,
296  // this optimization is enabled by the requirement of having matching
297  // transforms between all incoming grids and the cutter object.
298  if (points && points->size() != 0) {
299 
300  math::Transform::Ptr originalCutterTransform = cutter.transform().copy();
301  GridType cutterGrid(cutter, ShallowCopy());
302 
303  const bool hasInstanceRotations =
304  points && rotations && points->size() == rotations->size();
305 
306  // for each instance point..
307  for (size_t p = 0, P = points->size(); p < P; ++p) {
308 
309  int percent = int((float(p) / float(P)) * 100.0);
310  if (wasInterrupted(percent)) break;
311 
312  GridType instCutterGrid;
313  instCutterGrid.setTransform(originalCutterTransform->copy());
314  math::Transform::Ptr xform = originalCutterTransform->copy();
315 
316  if (hasInstanceRotations) {
317  const Vec3s& rot = (*rotations)[p].eulerAngles(math::XYZ_ROTATION);
318  xform->preRotate(rot[0], math::X_AXIS);
319  xform->preRotate(rot[1], math::Y_AXIS);
320  xform->preRotate(rot[2], math::Z_AXIS);
321  xform->postTranslate((*points)[p]);
322  } else {
323  xform->postTranslate((*points)[p]);
324  }
325 
326  cutterGrid.setTransform(xform);
327 
328  if (wasInterrupted()) break;
329 
330  // Since there is no scaling, use the generic resampler instead of
331  // the more expensive level set rebuild tool.
332  if (mInterrupter != NULL) {
333  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, *mInterrupter);
334  } else {
335  util::NullInterrupter interrupter;
336  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, interrupter);
337  }
338 
339  if (cutterOverlap && !mFragments.empty()) process(mFragments, instCutterGrid);
340  process(grids, instCutterGrid);
341  }
342 
343  } else {
344  // use cutter in place
345  if (cutterOverlap && !mFragments.empty()) process(mFragments, cutter);
346  process(grids, cutter);
347  }
348 
349  if (segmentation) {
350  segmentFragments(mFragments);
351  segmentFragments(grids);
352  }
353 }
354 
355 
356 template<class GridType, class InterruptType>
357 bool
359 {
360  typedef typename GridType::TreeType TreeType;
361  if (grid.activeVoxelCount() < 27) return false;
362 
363  // Check if valid level-set
364  {
365  tree::LeafManager<TreeType> leafs(grid.tree());
366  internal::MinMaxVoxel<TreeType> minmax(leafs);
367  minmax.runParallel();
368 
369  if ((minmax.minVoxel() < 0) == (minmax.maxVoxel() < 0)) return false;
370  }
371 
372  return true;
373 }
374 
375 
376 template<class GridType, class InterruptType>
377 void
378 LevelSetFracture<GridType, InterruptType>::segmentFragments(GridPtrList& grids) const
379 {
380  GridPtrList newFragments;
381 
382  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
383 
384  if (wasInterrupted()) break;
385 
386  std::vector<typename GridType::Ptr> segments = internal::segment(*(*it), mInterrupter);
387  for (size_t n = 0, N = segments.size(); n < N; ++n) {
388 
389  if (wasInterrupted()) break;
390 
391  if (isValidFragment(*segments[n])) {
392  newFragments.push_back(segments[n]);
393  }
394  }
395  }
396 
397  grids.swap(newFragments);
398 }
399 
400 
401 template<class GridType, class InterruptType>
402 void
403 LevelSetFracture<GridType, InterruptType>::process(
404  GridPtrList& grids, const GridType& cutter)
405 {
406  typedef typename GridType::Ptr GridPtr;
407 
408  GridPtrList newFragments;
409 
410  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
411 
412  if (wasInterrupted()) break;
413 
414  GridPtr grid = *it;
415 
416  // gen new fragment
417  GridPtr fragment = grid->deepCopy();
418  csgIntersection(*fragment, *cutter.deepCopy());
419 
420  if (wasInterrupted()) break;
421 
422  if (!isValidFragment(*fragment)) continue;
423 
424  // update residual
425  GridPtr residual = grid->deepCopy();
426  csgDifference(*residual, *cutter.deepCopy());
427 
428  if (wasInterrupted()) break;
429 
430  if (!isValidFragment(*residual)) continue;
431 
432  newFragments.push_back(fragment);
433 
434  grid->tree().clear();
435  grid->tree().merge(residual->tree());
436  }
437 
438  if (!newFragments.empty()) {
439  mFragments.splice(mFragments.end(), newFragments);
440  }
441 }
442 
443 } // namespace tools
444 } // namespace OPENVDB_VERSION_NAME
445 } // namespace openvdb
446 
447 #endif // OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
448 
449 // Copyright (c) 2012-2015 DreamWorks Animation LLC
450 // All rights reserved. This software is distributed under the
451 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
OPENVDB_STATIC_SPECIALIZATION void csgIntersection(GridOrTreeT &a, GridOrTreeT &b, bool prune=true)
Given two level set grids, replace the A grid with the intersection of A and B.
Definition: Composite.h:562
std::vector< math::Quats > QuatsList
Definition: LevelSetFracture.h:65
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:76
GridPtrList & fragments()
Return a list of new fragments, not including the residuals from the input grids. ...
Definition: LevelSetFracture.h:98
MinMaxVoxel(LeafArray &)
Definition: LevelSetFracture.h:216
tree::LeafManager< TreeType > LeafArray
Definition: LevelSetFracture.h:193
void fracture(GridPtrList &grids, const GridType &cutter, bool segment=false, const Vec3sList *points=NULL, const QuatsList *rotations=NULL, bool cutterOverlap=true)
Divide volumes represented by level set grids into multiple, disjoint pieces by intersecting them wit...
Definition: LevelSetFracture.h:292
Functions to efficiently perform various compositing operations on grids.
Definition: Math.h:841
std::list< typename GridType::Ptr > GridPtrList
Definition: LevelSetFracture.h:66
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:114
GridPtrList::iterator GridPtrListIter
Definition: LevelSetFracture.h:67
void runParallel()
Definition: LevelSetFracture.h:236
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:105
Defined various multi-threaded utility functions for trees.
const ValueType & minVoxel() const
Definition: LevelSetFracture.h:202
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Dummy NOOP interrupter class defining interface.
Definition: NullInterrupter.h:52
void clear()
Remove all elements from the fragment list.
Definition: LevelSetFracture.h:101
LevelSetFracture(InterruptType *interrupter=NULL)
Default constructor.
Definition: LevelSetFracture.h:283
Propagates the sign of distance values from the active voxels in the narrow band to the inactive valu...
boost::shared_ptr< Transform > Ptr
Definition: Transform.h:69
Definition: Exceptions.h:39
TreeType::ValueType ValueType
Definition: LevelSetFracture.h:194
Definition: LevelSetFracture.h:190
void runSerial()
Definition: LevelSetFracture.h:244
Level set fracturing.
Definition: LevelSetFracture.h:61
Definition: Math.h:840
const ValueType & maxVoxel() const
Definition: LevelSetFracture.h:203
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:280
void operator()(const tbb::blocked_range< size_t > &)
Definition: LevelSetFracture.h:252
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
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:109
Definition: Types.h:416
std::vector< Vec3s > Vec3sList
Definition: LevelSetFracture.h:64
OPENVDB_API const Coord COORD_OFFSETS[26]
coordinate offset table for neighboring voxels
std::vector< typename GridType::Ptr > segment(GridType &grid, InterruptType *interrupter=NULL)
Segmentation scheme, splits disjoint fragments into separate grids.
Definition: LevelSetFracture.h:131
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
void join(const MinMaxVoxel< TreeType > &)
Definition: LevelSetFracture.h:269
Vec3< float > Vec3s
Definition: Vec3.h:642
Definition: Math.h:839
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: ValueAccessor.h:287
OPENVDB_STATIC_SPECIALIZATION void csgDifference(GridOrTreeT &a, GridOrTreeT &b, bool prune=true)
Given two level set grids, replace the A grid with the difference A / B.
Definition: Composite.h:574