GCC Code Coverage Report

Line	Branch	Exec	Source
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>
15			#include <openvdb/util/NullInterrupter.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 {
31			OPENVDB_USE_VERSION_NAMESPACE
32			namespace OPENVDB_VERSION_NAME {
33			namespace tools {
34
35			/// @brief Level set fracturing
36			template<class GridType, class InterruptType = util::NullInterrupter>
37			class LevelSetFracture
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>
153		✗	LevelSetFracture<GridType, InterruptType>::LevelSetFracture(InterruptType* interrupter)
154			: mInterrupter(interrupter)
155		✗	, mFragments()
156			{
157			}
158
159
160			template<class GridType, class InterruptType>
161			void
162		✗	LevelSetFracture<GridType, InterruptType>::fracture(GridPtrList& grids, const GridType& cutter,
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
237		✗	LevelSetFracture<GridType, InterruptType>::isValidFragment(GridType& grid) const
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
324			#include <openvdb/util/ExplicitInstantiation.h>
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
338