OpenVDB  9.1.0
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)
111  : minValue(std::numeric_limits<ValueType>::max())
112  , maxValue(-minValue)
113  , mNodes(nodes.empty() ? nullptr : &nodes.front())
114  {
115  }
116 
117  FindMinMaxVoxelValue(FindMinMaxVoxelValue& rhs, tbb::split)
118  : minValue(std::numeric_limits<ValueType>::max())
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
266 LevelSetFracture<GridType, InterruptType>::segmentFragments(GridPtrList& grids) const
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
286 LevelSetFracture<GridType, InterruptType>::process(
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 
327 OPENVDB_INSTANTIATE_CLASS LevelSetFracture<FloatGrid, util::NullInterrupter>;
328 OPENVDB_INSTANTIATE_CLASS LevelSetFracture<DoubleGrid, util::NullInterrupter>;
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
Functions to efficiently perform various compositing operations on grids.
Miscellaneous utility methods that operate primarily or exclusively on level set grids.
Tag dispatch class that distinguishes shallow copy constructors from deep copy constructors.
Definition: Types.h:641
SharedPtr< Transform > Ptr
Definition: Transform.h:42
Level set fracturing.
Definition: LevelSetFracture.h:38
GridPtrList & fragments()
Return a list of new fragments, not including the residuals from the input grids.
Definition: LevelSetFracture.h:74
std::list< typename GridType::Ptr > GridPtrList
Definition: LevelSetFracture.h:42
std::vector< math::Quats > QuatsList
Definition: LevelSetFracture.h:41
typename GridPtrList::iterator GridPtrListIter
Definition: LevelSetFracture.h:43
void clear()
Remove all elements from the fragment list.
Definition: LevelSetFracture.h:77
std::vector< Vec3s > Vec3sList
Definition: LevelSetFracture.h:40
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
GridType
List of types that are currently supported by NanoVDB.
Definition: NanoVDB.h:216
@ Z_AXIS
Definition: Math.h:907
@ X_AXIS
Definition: Math.h:905
@ Y_AXIS
Definition: Math.h:906
Vec3< float > Vec3s
Definition: Vec3.h:667
@ XYZ_ROTATION
Definition: Math.h:912
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:103
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
void segmentSDF(const GridOrTreeType &volume, std::vector< typename GridOrTreeType::Ptr > &segments)
Separates disjoint SDF surfaces into distinct grids or trees.
Definition: LevelSetUtil.h:2552
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
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:49
Index32 Index
Definition: Types.h:54
uint64_t Index64
Definition: Types.h:53
openvdb::GridBase::Ptr GridPtr
Definition: Utils.h:35
Definition: Exceptions.h:13
Definition: Coord.h:587
Base class for interrupters.
Definition: NullInterrupter.h:26
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202
#define OPENVDB_INSTANTIATE_CLASS
Definition: version.h.in:143