OpenVDB 10.0.1
Loading...
Searching...
No Matches
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
30namespace openvdb {
32namespace OPENVDB_VERSION_NAME {
33namespace tools {
34
35/// @brief Level set fracturing
36template<class GridType, class InterruptType = util::NullInterrupter>
38{
39public:
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
79private:
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
102namespace level_set_fracture_internal {
103
104
105template<typename LeafNodeType>
106struct 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
152template<class GridType, class InterruptType>
154 : mInterrupter(interrupter)
155 , mFragments()
156{
157}
158
159
160template<class GridType, class InterruptType>
161void
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
235template<class GridType, class InterruptType>
236bool
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
264template<class GridType, class InterruptType>
265void
266LevelSetFracture<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
284template<class GridType, class InterruptType>
285void
286LevelSetFracture<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
327OPENVDB_INSTANTIATE_CLASS LevelSetFracture<FloatGrid, util::NullInterrupter>;
328OPENVDB_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
@ Z_AXIS
Definition: Math.h:904
@ X_AXIS
Definition: Math.h:902
@ Y_AXIS
Definition: Math.h:903
@ XYZ_ROTATION
Definition: Math.h:909
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:110
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:958
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:944
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:49
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:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
#define OPENVDB_INSTANTIATE_CLASS
Definition: version.h.in:153