HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
LevelSetFracture.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 tools/LevelSetFracture.h
32 ///
33 /// @brief Divide volumes represented by level set grids into multiple,
34 /// disjoint pieces by intersecting them with one or more "cutter" volumes,
35 /// also represented by level sets.
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 
44 #include "Composite.h" // for csgIntersectionCopy() and csgDifferenceCopy()
45 #include "GridTransformer.h" // for resampleToMatch()
46 #include "LevelSetUtil.h" // for sdfSegmentation()
47 
48 #include <limits>
49 #include <list>
50 
51 #include <tbb/blocked_range.h>
52 #include <tbb/parallel_reduce.h>
53 
54 
55 namespace openvdb {
57 namespace OPENVDB_VERSION_NAME {
58 namespace tools {
59 
60 /// @brief Level set fracturing
61 template<class GridType, class InterruptType = util::NullInterrupter>
63 {
64 public:
65  typedef std::vector<Vec3s> Vec3sList;
66  typedef std::vector<math::Quats> QuatsList;
67  typedef std::list<typename GridType::Ptr> GridPtrList;
68  typedef typename GridPtrList::iterator GridPtrListIter;
69 
70 
71  /// @brief Default constructor
72  ///
73  /// @param interrupter optional interrupter object
74  explicit LevelSetFracture(InterruptType* interrupter = NULL);
75 
76  /// @brief Divide volumes represented by level set grids into multiple,
77  /// disjoint pieces by intersecting them with one or more "cutter" volumes,
78  /// also represented by level sets.
79  /// @details If desired, the process can be applied iteratively, so that
80  /// fragments created with one cutter are subdivided by other cutters.
81  ///
82  /// @note The incoming @a grids and the @a cutter are required to have matching
83  /// transforms and narrow band widths!
84  ///
85  /// @param grids list of grids to fracture. The residuals of the
86  /// fractured grids will remain in this list
87  /// @param cutter a level set grid to use as the cutter object
88  /// @param segment toggle to split disjoint fragments into their own grids
89  /// @param points optional list of world space points at which to instance the
90  /// cutter object (if null, use the cutter's current position only)
91  /// @param rotations optional list of custom rotations for each cutter instance
92  /// @param cutterOverlap toggle to allow consecutive cutter instances to fracture
93  /// previously generated fragments
94  void fracture(GridPtrList& grids, const GridType& cutter, bool segment = false,
95  const Vec3sList* points = NULL, const QuatsList* rotations = NULL,
96  bool cutterOverlap = true);
97 
98  /// Return a list of new fragments, not including the residuals from the input grids.
99  GridPtrList& fragments() { return mFragments; }
100 
101  /// Remove all elements from the fragment list.
102  void clear() { mFragments.clear(); }
103 
104 private:
105  // disallow copy by assignment
106  void operator=(const LevelSetFracture&) {}
107 
108  bool wasInterrupted(int percent = -1) const {
109  return mInterrupter && mInterrupter->wasInterrupted(percent);
110  }
111 
112  bool isValidFragment(GridType&) const;
113  void segmentFragments(GridPtrList&) const;
114  void process(GridPtrList&, const GridType& cutter);
115 
116  InterruptType* mInterrupter;
117  GridPtrList mFragments;
118 };
119 
120 
121 ////////////////////////////////////////
122 
123 
124 // Internal utility objects and implementation details
125 
126 namespace level_set_fracture_internal {
127 
128 
129 template<typename LeafNodeType>
131 
132  typedef typename LeafNodeType::ValueType ValueType;
133 
134  FindMinMaxVoxelValue(const std::vector<const LeafNodeType*>& nodes)
135  : minValue(std::numeric_limits<ValueType>::max())
136  , maxValue(-minValue)
137  , mNodes(nodes.empty() ? NULL : &nodes.front())
138  {
139  }
140 
142  : minValue(std::numeric_limits<ValueType>::max())
143  , maxValue(-minValue)
144  , mNodes(rhs.mNodes)
145  {
146  }
147 
148  void operator()(const tbb::blocked_range<size_t>& range) {
149  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
150  const ValueType* data = mNodes[n]->buffer().data();
151  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
152  minValue = std::min(minValue, data[i]);
153  maxValue = std::max(maxValue, data[i]);
154  }
155  }
156  }
157 
161  }
162 
164 
165  LeafNodeType const * const * const mNodes;
166 }; // struct FindMinMaxVoxelValue
167 
168 
169 } // namespace level_set_fracture_internal
170 
171 
172 ////////////////////////////////////////
173 
174 
175 template<class GridType, class InterruptType>
177  : mInterrupter(interrupter)
178  , mFragments()
179 {
180 }
181 
182 
183 template<class GridType, class InterruptType>
184 void
186  bool segmentation, const Vec3sList* points, const QuatsList* rotations, bool cutterOverlap)
187 {
188  // We can process all incoming grids with the same cutter instance,
189  // this optimization is enabled by the requirement of having matching
190  // transforms between all incoming grids and the cutter object.
191  if (points && points->size() != 0) {
192 
193 
194  math::Transform::Ptr originalCutterTransform = cutter.transform().copy();
195  GridType cutterGrid(*const_cast<GridType*>(&cutter), ShallowCopy());
196 
197  const bool hasInstanceRotations =
198  points && rotations && points->size() == rotations->size();
199 
200  // for each instance point..
201  for (size_t p = 0, P = points->size(); p < P; ++p) {
202  int percent = int((float(p) / float(P)) * 100.0);
203  if (wasInterrupted(percent)) break;
204 
205  GridType instCutterGrid;
206  instCutterGrid.setTransform(originalCutterTransform->copy());
207  math::Transform::Ptr xform = originalCutterTransform->copy();
208 
209  if (hasInstanceRotations) {
210  const Vec3s& rot = (*rotations)[p].eulerAngles(math::XYZ_ROTATION);
211  xform->preRotate(rot[0], math::X_AXIS);
212  xform->preRotate(rot[1], math::Y_AXIS);
213  xform->preRotate(rot[2], math::Z_AXIS);
214  xform->postTranslate((*points)[p]);
215  } else {
216  xform->postTranslate((*points)[p]);
217  }
218 
219  cutterGrid.setTransform(xform);
220 
221  // Since there is no scaling, use the generic resampler instead of
222  // the more expensive level set rebuild tool.
223  if (mInterrupter != NULL) {
224 
225  if (hasInstanceRotations) {
226  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, *mInterrupter);
227  } else {
228  doResampleToMatch<PointSampler>(cutterGrid, instCutterGrid, *mInterrupter);
229  }
230  } else {
231  util::NullInterrupter interrupter;
232  if (hasInstanceRotations) {
233  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, interrupter);
234  } else {
235  doResampleToMatch<PointSampler>(cutterGrid, instCutterGrid, interrupter);
236  }
237  }
238 
239  if (wasInterrupted(percent)) break;
240 
241  if (cutterOverlap && !mFragments.empty()) process(mFragments, instCutterGrid);
242  process(grids, instCutterGrid);
243  }
244 
245  } else {
246  // use cutter in place
247  if (cutterOverlap && !mFragments.empty()) process(mFragments, cutter);
248  process(grids, cutter);
249  }
250 
251  if (segmentation) {
252  segmentFragments(mFragments);
253  segmentFragments(grids);
254  }
255 }
256 
257 
258 template<class GridType, class InterruptType>
259 bool
261 {
262  typedef typename GridType::TreeType::LeafNodeType LeafNodeType;
263 
264  if (grid.tree().leafCount() < 9) {
265 
266  std::vector<const LeafNodeType*> nodes;
267  grid.tree().getNodes(nodes);
268 
269  Index64 activeVoxelCount = 0;
270 
271  for (size_t n = 0, N = nodes.size(); n < N; ++n) {
272  activeVoxelCount += nodes[n]->onVoxelCount();
273  }
274 
275  if (activeVoxelCount < 27) return false;
276 
277  level_set_fracture_internal::FindMinMaxVoxelValue<LeafNodeType> op(nodes);
278  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
279 
280  if ((op.minValue < 0) == (op.maxValue < 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  std::vector<typename GridType::Ptr> segments;
296  segmentSDF(*(*it), segments);
297 
298  for (size_t n = 0, N = segments.size(); n < N; ++n) {
299  newFragments.push_back(segments[n]);
300  }
301  }
302 
303  grids.swap(newFragments);
304 }
305 
306 
307 template<class GridType, class InterruptType>
308 void
309 LevelSetFracture<GridType, InterruptType>::process(
310  GridPtrList& grids, const GridType& cutter)
311 {
312  typedef typename GridType::Ptr GridPtr;
313  GridPtrList newFragments;
314 
315  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
316 
317  if (wasInterrupted()) break;
318 
319  GridPtr& grid = *it;
320 
321  GridPtr fragment = csgIntersectionCopy(*grid, cutter);
322  if (!isValidFragment(*fragment)) continue;
323 
324  GridPtr residual = csgDifferenceCopy(*grid, cutter);
325  if (!isValidFragment(*residual)) continue;
326 
327  newFragments.push_back(fragment);
328 
329  grid->tree().clear();
330  grid->tree().merge(residual->tree());
331  }
332 
333  if (!newFragments.empty()) {
334  mFragments.splice(mFragments.end(), newFragments);
335  }
336 }
337 
338 } // namespace tools
339 } // namespace OPENVDB_VERSION_NAME
340 } // namespace openvdb
341 
342 #endif // OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
343 
344 // Copyright (c) 2012-2017 DreamWorks Animation LLC
345 // All rights reserved. This software is distributed under the
346 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void clear()
Remove all elements from the fragment list.
GLenum GLint * range
Definition: glcorearb.h:1924
Functions to efficiently perform various compositing operations on grids.
Tag dispatch class that distinguishes shallow copy constructors from deep copy constructors.
Definition: Types.h:500
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128
GA_API const UT_StringHolder rot
Dummy NOOP interrupter class defining interface.
png_uint_32 i
Definition: png.h:2877
OPENVDB_STATIC_SPECIALIZATION GridOrTreeT::Ptr csgDifferenceCopy(const GridOrTreeT &a, const GridOrTreeT &b)
Threaded CSG difference operation that produces a new grid or tree from immutable inputs...
Definition: Composite.h:1087
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
SYS_FORCE_INLINE const_iterator end() const
GLdouble n
Definition: glcorearb.h:2007
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...
#define OPENVDB_VERSION_NAME
Definition: version.h:43
std::list< typename GridType::Ptr > GridPtrList
LevelSetFracture(InterruptType *interrupter=NULL)
Default constructor.
GLboolean * data
Definition: glcorearb.h:130
Miscellaneous utility methods that operate primarily or exclusively on level set grids.
typedef int
Definition: png.h:1175
GA_API const UT_StringHolder N
GridPtrList & fragments()
Return a list of new fragments, not including the residuals from the input grids. ...
void segmentSDF(const GridOrTreeType &volume, std::vector< typename GridOrTreeType::Ptr > &segments)
Separates disjoint SDF surfaces into distinct grids or trees.
#define SIZE
Definition: simple.C:40
OPENVDB_STATIC_SPECIALIZATION GridOrTreeT::Ptr csgIntersectionCopy(const GridOrTreeT &a, const GridOrTreeT &b)
Threaded CSG intersection operation that produces a new grid or tree from immutable inputs...
Definition: Composite.h:1073
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
bool wasInterrupted(T *i, int percent=-1)