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