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