OpenVDB  3.0.0
LevelSetFracture.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_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
38 #define OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
39 
40 #include <openvdb/Grid.h>
41 #include <openvdb/math/Quat.h>
42 #include <openvdb/tree/LeafManager.h>
43 #include <openvdb/tools/Prune.h>
44 #include <openvdb/tools/SignedFloodFill.h>
45 #include <openvdb/util/NullInterrupter.h>
46 #include "Composite.h" // for csgIntersection() and csgDifference()
47 #include "GridTransformer.h" // for resampleToMatch()
48 #include "LevelSetUtil.h" // for MinMaxVoxel()
49 #include <list>
50 #include <deque>
51 
52 
53 namespace openvdb {
55 namespace OPENVDB_VERSION_NAME {
56 namespace tools {
57 
59 template<class GridType, class InterruptType = util::NullInterrupter>
61 {
62 public:
63  typedef std::vector<Vec3s> Vec3sList;
64  typedef std::vector<math::Quats> QuatsList;
65  typedef std::list<typename GridType::Ptr> GridPtrList;
66  typedef typename GridPtrList::iterator GridPtrListIter;
67 
68 
72  explicit LevelSetFracture(InterruptType* interrupter = NULL);
73 
92  void fracture(GridPtrList& grids, const GridType& cutter, bool segment = false,
93  const Vec3sList* points = NULL, const QuatsList* rotations = NULL,
94  bool cutterOverlap = true);
95 
97  GridPtrList& fragments() { return mFragments; }
98 
100  void clear() { mFragments.clear(); }
101 
102 private:
103  // disallow copy by assignment
104  void operator=(const LevelSetFracture&) {}
105 
106  bool wasInterrupted(int percent = -1) const {
107  return mInterrupter && mInterrupter->wasInterrupted(percent);
108  }
109 
110  bool isValidFragment(GridType&) const;
111  void segmentFragments(GridPtrList&) const;
112  void process(GridPtrList&, const GridType& cutter);
113 
114  InterruptType* mInterrupter;
115  GridPtrList mFragments;
116 };
117 
118 
120 
121 
122 // Internal utility objects and implementation details
123 
124 namespace internal {
125 
128 template<typename GridType, typename InterruptType>
129 inline std::vector<typename GridType::Ptr>
130 segment(GridType& grid, InterruptType* interrupter = NULL)
131 {
132  typedef typename GridType::Ptr GridPtr;
133  typedef typename GridType::TreeType TreeType;
134  typedef typename TreeType::Ptr TreePtr;
135  typedef typename TreeType::ValueType ValueType;
136 
137  std::vector<GridPtr> segments;
138 
139  while (grid.activeVoxelCount() > 0) {
140 
141  if (interrupter && interrupter->wasInterrupted()) break;
142 
143  // Deep copy the grid's metadata (tree and transform are shared)
144  GridPtr segment(new GridType(grid, ShallowCopy()));
145  // Make the transform unique and insert an empty tree
146  segment->setTransform(grid.transform().copy());
147  TreePtr tree(new TreeType(grid.background()));
148  segment->setTree(tree);
149 
150  std::deque<Coord> coordList;
151  coordList.push_back(grid.tree().beginLeaf()->beginValueOn().getCoord());
152 
153  Coord ijk, n_ijk;
154  ValueType value;
155 
156  typename tree::ValueAccessor<TreeType> sourceAcc(grid.tree());
157  typename tree::ValueAccessor<TreeType> targetAcc(segment->tree());
158 
159  while (!coordList.empty()) {
160 
161  if (interrupter && interrupter->wasInterrupted()) break;
162 
163  ijk = coordList.back();
164  coordList.pop_back();
165 
166  if (!sourceAcc.probeValue(ijk, value)) continue;
167  if (targetAcc.isValueOn(ijk)) continue;
168 
169  targetAcc.setValue(ijk, value);
170  sourceAcc.setValueOff(ijk);
171 
172  for (int n = 0; n < 6; n++) {
173  n_ijk = ijk + util::COORD_OFFSETS[n];
174  if (!targetAcc.isValueOn(n_ijk) && sourceAcc.isValueOn(n_ijk)) {
175  coordList.push_back(n_ijk);
176  }
177  }
178  }
179 
180  tools::pruneInactive(grid.tree());
181  tools::signedFloodFill(segment->tree());
182  segments.push_back(segment);
183  }
184  return segments;
185 }
186 
187 } // namespace internal
188 
189 
191 
192 
193 template<class GridType, class InterruptType>
195  : mInterrupter(interrupter)
196  , mFragments()
197 {
198 }
199 
200 
201 template<class GridType, class InterruptType>
202 void
203 LevelSetFracture<GridType, InterruptType>::fracture(GridPtrList& grids, const GridType& cutter,
204  bool segmentation, const Vec3sList* points, const QuatsList* rotations, bool cutterOverlap)
205 {
206  // We can process all incoming grids with the same cutter instance,
207  // this optimization is enabled by the requirement of having matching
208  // transforms between all incoming grids and the cutter object.
209  if (points && points->size() != 0) {
210 
211  math::Transform::Ptr originalCutterTransform = cutter.transform().copy();
212  GridType cutterGrid(cutter, ShallowCopy());
213 
214  const bool hasInstanceRotations =
215  points && rotations && points->size() == rotations->size();
216 
217  // for each instance point..
218  for (size_t p = 0, P = points->size(); p < P; ++p) {
219 
220  int percent = int((float(p) / float(P)) * 100.0);
221  if (wasInterrupted(percent)) break;
222 
223  GridType instCutterGrid;
224  instCutterGrid.setTransform(originalCutterTransform->copy());
225  math::Transform::Ptr xform = originalCutterTransform->copy();
226 
227  if (hasInstanceRotations) {
228  const Vec3s& rot = (*rotations)[p].eulerAngles(math::XYZ_ROTATION);
229  xform->preRotate(rot[0], math::X_AXIS);
230  xform->preRotate(rot[1], math::Y_AXIS);
231  xform->preRotate(rot[2], math::Z_AXIS);
232  xform->postTranslate((*points)[p]);
233  } else {
234  xform->postTranslate((*points)[p]);
235  }
236 
237  cutterGrid.setTransform(xform);
238 
239  if (wasInterrupted()) break;
240 
241  // Since there is no scaling, use the generic resampler instead of
242  // the more expensive level set rebuild tool.
243  if (mInterrupter != NULL) {
244  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, *mInterrupter);
245  } else {
246  util::NullInterrupter interrupter;
247  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, interrupter);
248  }
249 
250  if (cutterOverlap && !mFragments.empty()) process(mFragments, instCutterGrid);
251  process(grids, instCutterGrid);
252  }
253 
254  } else {
255  // use cutter in place
256  if (cutterOverlap && !mFragments.empty()) process(mFragments, cutter);
257  process(grids, cutter);
258  }
259 
260  if (segmentation) {
261  segmentFragments(mFragments);
262  segmentFragments(grids);
263  }
264 }
265 
266 
267 template<class GridType, class InterruptType>
268 bool
270 {
271  typedef typename GridType::TreeType TreeType;
272  if (grid.activeVoxelCount() < 27) return false;
273 
274  // Check if valid level-set
275  {
276  tree::LeafManager<TreeType> leafs(grid.tree());
277  MinMaxVoxel<TreeType> minmax(leafs);
278  minmax.runParallel();
279 
280  if ((minmax.minVoxel() < 0) == (minmax.maxVoxel() < 0)) return false;
281  }
282 
283  return true;
284 }
285 
286 
287 template<class GridType, class InterruptType>
288 void
289 LevelSetFracture<GridType, InterruptType>::segmentFragments(GridPtrList& grids) const
290 {
291  GridPtrList newFragments;
292 
293  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
294 
295  if (wasInterrupted()) break;
296 
297  std::vector<typename GridType::Ptr> segments = internal::segment(*(*it), mInterrupter);
298  for (size_t n = 0, N = segments.size(); n < N; ++n) {
299 
300  if (wasInterrupted()) break;
301 
302  if (isValidFragment(*segments[n])) {
303  newFragments.push_back(segments[n]);
304  }
305  }
306  }
307 
308  grids.swap(newFragments);
309 }
310 
311 
312 template<class GridType, class InterruptType>
313 void
314 LevelSetFracture<GridType, InterruptType>::process(
315  GridPtrList& grids, const GridType& cutter)
316 {
317  typedef typename GridType::Ptr GridPtr;
318 
319  GridPtrList newFragments;
320 
321  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
322 
323  if (wasInterrupted()) break;
324 
325  GridPtr grid = *it;
326 
327  // gen new fragment
328  GridPtr fragment = grid->deepCopy();
329  csgIntersection(*fragment, *cutter.deepCopy());
330 
331  if (wasInterrupted()) break;
332 
333  if (!isValidFragment(*fragment)) continue;
334 
335  // update residual
336  GridPtr residual = grid->deepCopy();
337  csgDifference(*residual, *cutter.deepCopy());
338 
339  if (wasInterrupted()) break;
340 
341  if (!isValidFragment(*residual)) continue;
342 
343  newFragments.push_back(fragment);
344 
345  grid->tree().clear();
346  grid->tree().merge(residual->tree());
347  }
348 
349  if (!newFragments.empty()) {
350  mFragments.splice(mFragments.end(), newFragments);
351  }
352 }
353 
354 } // namespace tools
355 } // namespace OPENVDB_VERSION_NAME
356 } // namespace openvdb
357 
358 #endif // OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
359 
360 // Copyright (c) 2012-2014 DreamWorks Animation LLC
361 // All rights reserved. This software is distributed under the
362 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
std::list< typename GridType::Ptr > GridPtrList
Definition: LevelSetFracture.h:65
GridPtrList::iterator GridPtrListIter
Definition: LevelSetFracture.h:66
boost::shared_ptr< Transform > Ptr
Definition: Transform.h:69
Functions to efficiently perform various compositing operations on grids.
Threaded operator that finds the minimum and maximum values among the active leaf-level voxels of a g...
Definition: LevelSetUtil.h:122
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
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:109
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:64
GridPtrList & fragments()
Return a list of new fragments, not including the residuals from the input grids. ...
Definition: LevelSetFracture.h:97
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 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:203
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:76
Definition: Types.h:421
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Definition: Exceptions.h:39
Level set fracturing.
Definition: LevelSetFracture.h:60
std::vector< Vec3s > Vec3sList
Definition: LevelSetFracture.h:63
Definition: Math.h:823
void clear()
Remove all elements from the fragment list.
Definition: LevelSetFracture.h:100
std::vector< typename GridType::Ptr > segment(GridType &grid, InterruptType *interrupter=NULL)
Segmentation scheme, splits disjoint fragments into separate grids.
Definition: LevelSetFracture.h:130
Miscellaneous utilities that operate primarily or exclusively on level set grids. ...
Dummy NOOP interrupter class defining interface.
Definition: NullInterrupter.h:52
Definition: Math.h:824
OPENVDB_API const Coord COORD_OFFSETS[26]
coordinate offset table for neighboring voxels
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Vec3< float > Vec3s
Definition: Vec3.h:628
Definition: Math.h:825
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:282
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:241