OpenVDB  9.0.1
LevelSetFracture.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file tools/LevelSetFracture.h
5 ///
6 /// @brief Divide volumes represented by level set grids into multiple,
7 /// disjoint pieces by intersecting them with one or more "cutter" volumes,
8 /// also represented by level sets.
9 
10 #ifndef OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
12 
13 #include <openvdb/Grid.h>
14 #include <openvdb/math/Quat.h>
16 
17 #include "Composite.h" // for csgIntersectionCopy() and csgDifferenceCopy()
18 #include "GridTransformer.h" // for resampleToMatch()
19 #include "LevelSetUtil.h" // for sdfSegmentation()
20 
21 #include <algorithm> // for std::max(), std::min()
22 #include <limits>
23 #include <list>
24 #include <vector>
25 
26 #include <tbb/blocked_range.h>
27 #include <tbb/parallel_reduce.h>
28 
29 
30 namespace openvdb {
32 namespace OPENVDB_VERSION_NAME {
33 namespace tools {
34 
35 /// @brief Level set fracturing
36 template<class GridType, class InterruptType = util::NullInterrupter>
38 {
39 public:
40  using Vec3sList = std::vector<Vec3s>;
41  using QuatsList = std::vector<math::Quats>;
42  using GridPtrList = std::list<typename GridType::Ptr>;
43  using GridPtrListIter = typename GridPtrList::iterator;
44 
45 
46  /// @brief Default constructor
47  ///
48  /// @param interrupter optional interrupter object
49  explicit LevelSetFracture(InterruptType* interrupter = nullptr);
50 
51  /// @brief Divide volumes represented by level set grids into multiple,
52  /// disjoint pieces by intersecting them with one or more "cutter" volumes,
53  /// also represented by level sets.
54  /// @details If desired, the process can be applied iteratively, so that
55  /// fragments created with one cutter are subdivided by other cutters.
56  ///
57  /// @note The incoming @a grids and the @a cutter are required to have matching
58  /// transforms and narrow band widths!
59  ///
60  /// @param grids list of grids to fracture. The residuals of the
61  /// fractured grids will remain in this list
62  /// @param cutter a level set grid to use as the cutter object
63  /// @param segment toggle to split disjoint fragments into their own grids
64  /// @param points optional list of world space points at which to instance the
65  /// cutter object (if null, use the cutter's current position only)
66  /// @param rotations optional list of custom rotations for each cutter instance
67  /// @param cutterOverlap toggle to allow consecutive cutter instances to fracture
68  /// previously generated fragments
69  void fracture(GridPtrList& grids, const GridType& cutter, bool segment = false,
70  const Vec3sList* points = nullptr, const QuatsList* rotations = nullptr,
71  bool cutterOverlap = true);
72 
73  /// Return a list of new fragments, not including the residuals from the input grids.
74  GridPtrList& fragments() { return mFragments; }
75 
76  /// Remove all elements from the fragment list.
77  void clear() { mFragments.clear(); }
78 
79 private:
80  // disallow copy by assignment
81  void operator=(const LevelSetFracture&) {}
82 
83  bool wasInterrupted(int percent = -1) const {
84  return mInterrupter && mInterrupter->wasInterrupted(percent);
85  }
86 
87  bool isValidFragment(GridType&) const;
88  void segmentFragments(GridPtrList&) const;
89  void process(GridPtrList&, const GridType& cutter);
90 
91  InterruptType* mInterrupter;
92  GridPtrList mFragments;
93 };
94 
95 
96 ////////////////////////////////////////
97 
98 /// @cond OPENVDB_DOCS_INTERNAL
99 
100 // Internal utility objects and implementation details
101 
102 namespace level_set_fracture_internal {
103 
104 
105 template<typename LeafNodeType>
106 struct FindMinMaxVoxelValue {
107 
108  using ValueType = typename LeafNodeType::ValueType;
109 
110  FindMinMaxVoxelValue(const std::vector<const LeafNodeType*>& nodes)
112  , maxValue(-minValue)
113  , mNodes(nodes.empty() ? nullptr : &nodes.front())
114  {
115  }
116 
117  FindMinMaxVoxelValue(FindMinMaxVoxelValue& rhs, tbb::split)
119  , maxValue(-minValue)
120  , mNodes(rhs.mNodes)
121  {
122  }
123 
124  void operator()(const tbb::blocked_range<size_t>& range) {
125  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
126  const ValueType* data = mNodes[n]->buffer().data();
127  for (Index i = 0; i < LeafNodeType::SIZE; ++i) {
128  minValue = std::min(minValue, data[i]);
129  maxValue = std::max(maxValue, data[i]);
130  }
131  }
132  }
133 
134  void join(FindMinMaxVoxelValue& rhs) {
135  minValue = std::min(minValue, rhs.minValue);
136  maxValue = std::max(maxValue, rhs.maxValue);
137  }
138 
139  ValueType minValue, maxValue;
140 
141  LeafNodeType const * const * const mNodes;
142 }; // struct FindMinMaxVoxelValue
143 
144 
145 } // namespace level_set_fracture_internal
146 
147 /// @endcond
148 
149 ////////////////////////////////////////
150 
151 
152 template<class GridType, class InterruptType>
154  : mInterrupter(interrupter)
155  , mFragments()
156 {
157 }
158 
159 
160 template<class GridType, class InterruptType>
161 void
163  bool segmentation, const Vec3sList* points, const QuatsList* rotations, bool cutterOverlap)
164 {
165  // We can process all incoming grids with the same cutter instance,
166  // this optimization is enabled by the requirement of having matching
167  // transforms between all incoming grids and the cutter object.
168  if (points && points->size() != 0) {
169 
170 
171  math::Transform::Ptr originalCutterTransform = cutter.transform().copy();
172  GridType cutterGrid(*const_cast<GridType*>(&cutter), ShallowCopy());
173 
174  const bool hasInstanceRotations =
175  points && rotations && points->size() == rotations->size();
176 
177  // for each instance point..
178  for (size_t p = 0, P = points->size(); p < P; ++p) {
179  int percent = int((float(p) / float(P)) * 100.0);
180  if (wasInterrupted(percent)) break;
181 
182  GridType instCutterGrid;
183  instCutterGrid.setTransform(originalCutterTransform->copy());
184  math::Transform::Ptr xform = originalCutterTransform->copy();
185 
186  if (hasInstanceRotations) {
187  const Vec3s& rot = (*rotations)[p].eulerAngles(math::XYZ_ROTATION);
188  xform->preRotate(rot[0], math::X_AXIS);
189  xform->preRotate(rot[1], math::Y_AXIS);
190  xform->preRotate(rot[2], math::Z_AXIS);
191  xform->postTranslate((*points)[p]);
192  } else {
193  xform->postTranslate((*points)[p]);
194  }
195 
196  cutterGrid.setTransform(xform);
197 
198  // Since there is no scaling, use the generic resampler instead of
199  // the more expensive level set rebuild tool.
200  if (mInterrupter != nullptr) {
201 
202  if (hasInstanceRotations) {
203  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, *mInterrupter);
204  } else {
205  doResampleToMatch<PointSampler>(cutterGrid, instCutterGrid, *mInterrupter);
206  }
207  } else {
208  util::NullInterrupter interrupter;
209  if (hasInstanceRotations) {
210  doResampleToMatch<BoxSampler>(cutterGrid, instCutterGrid, interrupter);
211  } else {
212  doResampleToMatch<PointSampler>(cutterGrid, instCutterGrid, interrupter);
213  }
214  }
215 
216  if (wasInterrupted(percent)) break;
217 
218  if (cutterOverlap && !mFragments.empty()) process(mFragments, instCutterGrid);
219  process(grids, instCutterGrid);
220  }
221 
222  } else {
223  // use cutter in place
224  if (cutterOverlap && !mFragments.empty()) process(mFragments, cutter);
225  process(grids, cutter);
226  }
227 
228  if (segmentation) {
229  segmentFragments(mFragments);
230  segmentFragments(grids);
231  }
232 }
233 
234 
235 template<class GridType, class InterruptType>
236 bool
238 {
239  using LeafNodeType = typename GridType::TreeType::LeafNodeType;
240 
241  if (grid.tree().leafCount() < 9) {
242 
243  std::vector<const LeafNodeType*> nodes;
244  grid.tree().getNodes(nodes);
245 
246  Index64 activeVoxelCount = 0;
247 
248  for (size_t n = 0, N = nodes.size(); n < N; ++n) {
249  activeVoxelCount += nodes[n]->onVoxelCount();
250  }
251 
252  if (activeVoxelCount < 27) return false;
253 
254  level_set_fracture_internal::FindMinMaxVoxelValue<LeafNodeType> op(nodes);
255  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, nodes.size()), op);
256 
257  if ((op.minValue < 0) == (op.maxValue < 0)) return false;
258  }
259 
260  return true;
261 }
262 
263 
264 template<class GridType, class InterruptType>
265 void
267 {
268  GridPtrList newFragments;
269 
270  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
271 
272  std::vector<typename GridType::Ptr> segments;
273  segmentSDF(*(*it), segments);
274 
275  for (size_t n = 0, N = segments.size(); n < N; ++n) {
276  newFragments.push_back(segments[n]);
277  }
278  }
279 
280  grids.swap(newFragments);
281 }
282 
283 
284 template<class GridType, class InterruptType>
285 void
287  GridPtrList& grids, const GridType& cutter)
288 {
289  using GridPtr = typename GridType::Ptr;
290  GridPtrList newFragments;
291 
292  for (GridPtrListIter it = grids.begin(); it != grids.end(); ++it) {
293 
294  if (wasInterrupted()) break;
295 
296  GridPtr& grid = *it;
297 
298  GridPtr fragment = csgIntersectionCopy(*grid, cutter);
299  if (!isValidFragment(*fragment)) continue;
300 
301  GridPtr residual = csgDifferenceCopy(*grid, cutter);
302  if (!isValidFragment(*residual)) continue;
303 
304  newFragments.push_back(fragment);
305 
306  grid->tree().clear();
307  grid->tree().merge(residual->tree());
308  }
309 
310  if (!newFragments.empty()) {
311  mFragments.splice(mFragments.end(), newFragments);
312  }
313 }
314 
315 
316 ////////////////////////////////////////
317 
318 
319 // Explicit Template Instantiation
320 
321 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
322 
323 #ifdef OPENVDB_INSTANTIATE_LEVELSETFRACTURE
325 #endif
326 
329 
330 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
331 
332 
333 } // namespace tools
334 } // namespace OPENVDB_VERSION_NAME
335 } // namespace openvdb
336 
337 #endif // OPENVDB_TOOLS_LEVELSETFRACTURE_HAS_BEEN_INCLUDED
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:49
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:938
Definition: Math.h:912
Functions to efficiently perform various compositing operations on grids.
Base class for interrupters.
Definition: NullInterrupter.h:25
SharedPtr< Transform > Ptr
Definition: Transform.h:42
typename GridPtrList::iterator GridPtrListIter
Definition: LevelSetFracture.h:43
GridPtrList & fragments()
Return a list of new fragments, not including the residuals from the input grids. ...
Definition: LevelSetFracture.h:74
openvdb::GridBase::Ptr GridPtr
Definition: Utils.h:35
std::vector< Vec3s > Vec3sList
Definition: LevelSetFracture.h:40
std::vector< math::Quats > QuatsList
Definition: LevelSetFracture.h:41
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
Tag dispatch class that distinguishes shallow copy constructors from deep copy constructors.
Definition: Types.h:641
Definition: Math.h:907
uint64_t Index64
Definition: Types.h:53
Definition: Exceptions.h:13
void segmentSDF(const GridOrTreeType &volume, std::vector< typename GridOrTreeType::Ptr > &segments)
Separates disjoint SDF surfaces into distinct grids or trees.
Definition: LevelSetUtil.h:2552
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...
Definition: LevelSetFracture.h:162
Index32 Index
Definition: Types.h:54
Level set fracturing.
Definition: LevelSetFracture.h:37
#define OPENVDB_INSTANTIATE_CLASS
Definition: version.h.in:143
GridType
List of types that are currently supported by NanoVDB.
Definition: NanoVDB.h:216
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:952
Definition: Math.h:906
Vec3< float > Vec3s
Definition: Vec3.h:667
Miscellaneous utility methods that operate primarily or exclusively on level set grids.
std::list< typename GridType::Ptr > GridPtrList
Definition: LevelSetFracture.h:42
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:103
Definition: Math.h:905
void clear()
Remove all elements from the fragment list.
Definition: LevelSetFracture.h:77
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202