GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/Composite.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 230 278 82.7%
Functions: 79 219 36.1%
Branches: 244 612 39.9%
Line Branch Exec Source
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file Composite.h
5 ///
6 /// @brief Functions to efficiently perform various compositing operations on grids
7 ///
8 /// @authors Peter Cucka, Mihai Alden, Ken Museth
9
10 #ifndef OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
12
13 #include <openvdb/Platform.h>
14 #include <openvdb/Exceptions.h>
15 #include <openvdb/Types.h>
16 #include <openvdb/Grid.h>
17 #include <openvdb/math/Math.h> // for isExactlyEqual()
18 #include <openvdb/openvdb.h>
19 #include "Merge.h"
20 #include "ValueTransformer.h" // for transformValues()
21 #include "Prune.h"// for prune
22 #include "SignedFloodFill.h" // for signedFloodFill()
23
24 #include <tbb/blocked_range.h>
25 #include <tbb/parallel_for.h>
26 #include <tbb/parallel_reduce.h>
27 #include <tbb/task_group.h>
28
29 #include <type_traits>
30 #include <functional>
31
32 namespace openvdb {
33 OPENVDB_USE_VERSION_NAMESPACE
34 namespace OPENVDB_VERSION_NAME {
35 namespace tools {
36
37 /// @brief Given two level set grids, replace the A grid with the union of A and B.
38 /// @throw ValueError if the background value of either grid is not greater than zero.
39 /// @note This operation always leaves the B grid empty.
40 template<typename GridOrTreeT>
41 void csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
42 /// @brief Given two level set grids, replace the A grid with the intersection of A and B.
43 /// @throw ValueError if the background value of either grid is not greater than zero.
44 /// @note This operation always leaves the B grid empty.
45 template<typename GridOrTreeT>
46 void csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
47 /// @brief Given two level set grids, replace the A grid with the difference A / B.
48 /// @throw ValueError if the background value of either grid is not greater than zero.
49 /// @note This operation always leaves the B grid empty.
50 template<typename GridOrTreeT>
51 void csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
52
53 /// @brief Threaded CSG union operation that produces a new grid or tree from
54 /// immutable inputs.
55 /// @return The CSG union of the @a and @b level set inputs.
56 template<typename GridOrTreeT>
57 typename GridOrTreeT::Ptr csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
58 /// @brief Threaded CSG intersection operation that produces a new grid or tree from
59 /// immutable inputs.
60 /// @return The CSG intersection of the @a and @b level set inputs.
61 template<typename GridOrTreeT>
62 typename GridOrTreeT::Ptr csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
63 /// @brief Threaded CSG difference operation that produces a new grid or tree from
64 /// immutable inputs.
65 /// @return The CSG difference of the @a and @b level set inputs.
66 template<typename GridOrTreeT>
67 typename GridOrTreeT::Ptr csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b);
68
69 /// @brief Given grids A and B, compute max(a, b) per voxel (using sparse traversal).
70 /// Store the result in the A grid and leave the B grid empty.
71 template<typename GridOrTreeT>
72 void compMax(GridOrTreeT& a, GridOrTreeT& b);
73 /// @brief Given grids A and B, compute min(a, b) per voxel (using sparse traversal).
74 /// Store the result in the A grid and leave the B grid empty.
75 template<typename GridOrTreeT>
76 void compMin(GridOrTreeT& a, GridOrTreeT& b);
77 /// @brief Given grids A and B, compute a + b per voxel (using sparse traversal).
78 /// Store the result in the A grid and leave the B grid empty.
79 template<typename GridOrTreeT>
80 void compSum(GridOrTreeT& a, GridOrTreeT& b);
81 /// @brief Given grids A and B, compute a * b per voxel (using sparse traversal).
82 /// Store the result in the A grid and leave the B grid empty.
83 template<typename GridOrTreeT>
84 void compMul(GridOrTreeT& a, GridOrTreeT& b);
85 /// @brief Given grids A and B, compute a / b per voxel (using sparse traversal).
86 /// Store the result in the A grid and leave the B grid empty.
87 template<typename GridOrTreeT>
88 void compDiv(GridOrTreeT& a, GridOrTreeT& b);
89
90 /// Copy the active voxels of B into A.
91 template<typename GridOrTreeT>
92 void compReplace(GridOrTreeT& a, const GridOrTreeT& b);
93
94
95 ////////////////////////////////////////
96
97
98 namespace composite {
99
100 // composite::min() and composite::max() for non-vector types compare with operator<().
101 template<typename T> inline
102 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type& // = T if T is not a vector type
103 min(const T& a, const T& b) { return std::min(a, b); }
104
105 template<typename T> inline
106 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type&
107 max(const T& a, const T& b) { return std::max(a, b); }
108
109
110 // composite::min() and composite::max() for OpenVDB vector types compare by magnitude.
111 template<typename T> inline
112 const typename std::enable_if<VecTraits<T>::IsVec, T>::type& // = T if T is a vector type
113
2/2
✓ Branch 0 taken 37375 times.
✓ Branch 1 taken 37375 times.
 149500 min(const T& a, const T& b)
114 {
115 const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
116
3/4
✓ Branch 0 taken 37375 times.
✓ Branch 1 taken 37375 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 37375 times.
 149500 return (aMag < bMag ? a : (bMag < aMag ? b : std::min(a, b)));
117 }
118
119 template<typename T> inline
120 const typename std::enable_if<VecTraits<T>::IsVec, T>::type&
121
2/2
✓ Branch 0 taken 37375 times.
✓ Branch 1 taken 37375 times.
 149500 max(const T& a, const T& b)
122 {
123 const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
124
3/4
✓ Branch 0 taken 37375 times.
✓ Branch 1 taken 37375 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 37375 times.
 149500 return (aMag < bMag ? b : (bMag < aMag ? a : std::max(a, b)));
125 }
126
127
128 template<typename T> inline
129 typename std::enable_if<!std::is_integral<T>::value, T>::type // = T if T is not an integer type
130 112125 divide(const T& a, const T& b) { return a / b; }
131
132 template<typename T> inline
133 typename std::enable_if<std::is_integral<T>::value, T>::type // = T if T is an integer type
134 divide(const T& a, const T& b)
135 {
136 const T zero(0);
137
2/8
✗ Branch 0 not taken.
✓ Branch 1 taken 37375 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 37375 times.
 74750 if (b != zero) return a / b;
138
4/8
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 37374 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 37374 times.
✓ Branch 7 taken 1 times.
 74750 if (a == zero) return 0;
139
2/8
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 37372 times.
 37374 return (a > 0 ? std::numeric_limits<T>::max() : -std::numeric_limits<T>::max());
140 }
141
142 // If b is true, return a / 1 = a.
143 // If b is false and a is true, return 1 / 0 = inf = MAX_BOOL = 1 = a.
144 // If b is false and a is false, return 0 / 0 = NaN = 0 = a.
145 inline bool divide(bool a, bool /*b*/) { return a; }
146
147
148 /// @cond OPENVDB_DOCS_INTERNAL
149
150 enum CSGOperation { CSG_UNION, CSG_INTERSECTION, CSG_DIFFERENCE };
151
152 template<typename TreeType, CSGOperation Operation>
153 3 struct BuildPrimarySegment
154 {
155 using ValueType = typename TreeType::ValueType;
156 using TreePtrType = typename TreeType::Ptr;
157 using LeafNodeType = typename TreeType::LeafNodeType;
158 using NodeMaskType = typename LeafNodeType::NodeMaskType;
159 using RootNodeType = typename TreeType::RootNodeType;
160 using NodeChainType = typename RootNodeType::NodeChainType;
161 using InternalNodeType = typename NodeChainType::template Get<1>;
162
163 6 BuildPrimarySegment(const TreeType& lhs, const TreeType& rhs)
164 6 : mSegment(new TreeType(lhs.background()))
165 , mLhsTree(&lhs)
166 6 , mRhsTree(&rhs)
167 {
168 }
169
170
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 void operator()() const
171 {
172 std::vector<const LeafNodeType*> leafNodes;
173
174 {
175 std::vector<const InternalNodeType*> internalNodes;
176
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 mLhsTree->getNodes(internalNodes);
177
178 12 ProcessInternalNodes op(internalNodes, *mRhsTree, *mSegment, leafNodes);
179
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
180 }
181
182 6 ProcessLeafNodes op(leafNodes, *mRhsTree, *mSegment);
183
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
184 }
185
186 TreePtrType& segment() { return mSegment; }
187
188 private:
189
190 struct ProcessInternalNodes {
191
192
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 ProcessInternalNodes(std::vector<const InternalNodeType*>& lhsNodes,
193 const TreeType& rhsTree, TreeType& outputTree,
194 std::vector<const LeafNodeType*>& outputLeafNodes)
195
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 : mLhsNodes(lhsNodes.empty() ? nullptr : &lhsNodes.front())
196 , mRhsTree(&rhsTree)
197 , mLocalTree(mRhsTree->background())
198 , mOutputTree(&outputTree)
199 , mLocalLeafNodes()
200
3/12
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 , mOutputLeafNodes(&outputLeafNodes)
201 {
202 }
203
204 5 ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
205 5 : mLhsNodes(other.mLhsNodes)
206 5 , mRhsTree(other.mRhsTree)
207 , mLocalTree(mRhsTree->background())
208 , mOutputTree(&mLocalTree)
209 , mLocalLeafNodes()
210 5 , mOutputLeafNodes(&mLocalLeafNodes)
211 {
212 }
213
214 10 void join(ProcessInternalNodes& other)
215 {
216 10 mOutputTree->merge(*other.mOutputTree);
217 20 mOutputLeafNodes->insert(mOutputLeafNodes->end(),
218 10 other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
219 }
220
221 48 void operator()(const tbb::blocked_range<size_t>& range)
222 {
223 48 tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
224
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
225
226 std::vector<const LeafNodeType*> tmpLeafNodes;
227
228
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 96 for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
229
230 48 const InternalNodeType& lhsNode = *mLhsNodes[n];
231 const Coord& ijk = lhsNode.origin();
232 48 const InternalNodeType * rhsNode =
233 rhsAcc.template probeConstNode<InternalNodeType>(ijk);
234
235
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 48 if (rhsNode) {
236
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 lhsNode.getNodes(*mOutputLeafNodes);
237 } else {
238 if (Operation == CSG_INTERSECTION) {
239
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
 8 if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
240 tmpLeafNodes.clear();
241 ✗ lhsNode.getNodes(tmpLeafNodes);
242 ✗ for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
243 ✗ outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
244 }
245 }
246 } else { // Union & Difference
247
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 16 if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
248 tmpLeafNodes.clear();
249
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 lhsNode.getNodes(tmpLeafNodes);
250
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 8 times.
 200 for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
251
3/6
✓ Branch 1 taken 92 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 92 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 92 times.
✗ Branch 8 not taken.
 184 outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
252 }
253 }
254 }
255 }
256 } // end range loop
257 }
258
259 InternalNodeType const * const * const mLhsNodes;
260 TreeType const * const mRhsTree;
261 TreeType mLocalTree;
262 TreeType * const mOutputTree;
263
264 std::vector<const LeafNodeType*> mLocalLeafNodes;
265 std::vector<const LeafNodeType*> * const mOutputLeafNodes;
266 }; // struct ProcessInternalNodes
267
268
3/12
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 29 taken 1 times.
✗ Branch 30 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
 14 struct ProcessLeafNodes {
269
270
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 ProcessLeafNodes(std::vector<const LeafNodeType*>& lhsNodes,
271 const TreeType& rhsTree, TreeType& output)
272
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 : mLhsNodes(lhsNodes.empty() ? nullptr : &lhsNodes.front())
273 , mRhsTree(&rhsTree)
274 , mLocalTree(mRhsTree->background())
275
3/12
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 , mOutputTree(&output)
276 {
277 }
278
279 11 ProcessLeafNodes(ProcessLeafNodes& other, tbb::split)
280 11 : mLhsNodes(other.mLhsNodes)
281 11 , mRhsTree(other.mRhsTree)
282 , mLocalTree(mRhsTree->background())
283 11 , mOutputTree(&mLocalTree)
284 {
285 }
286
287 11 void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
288
289 324 void operator()(const tbb::blocked_range<size_t>& range)
290 {
291 324 tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
292
1/2
✓ Branch 1 taken 162 times.
✗ Branch 2 not taken.
 324 tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
293
294
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 162 times.
 648 for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
295
296 324 const LeafNodeType& lhsNode = *mLhsNodes[n];
297 const Coord& ijk = lhsNode.origin();
298
299 const LeafNodeType* rhsNodePt = rhsAcc.probeConstLeaf(ijk);
300
301
2/2
✓ Branch 0 taken 123 times.
✓ Branch 1 taken 39 times.
 324 if (rhsNodePt) { // combine overlapping nodes
302
303
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 246 LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
304
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 246 ValueType * outputData = outputNode->buffer().data();
305 NodeMaskType& outputMask = outputNode->getValueMask();
306
307
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 246 const ValueType * lhsData = lhsNode.buffer().data();
308 const NodeMaskType& lhsMask = lhsNode.getValueMask();
309
310
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 246 const ValueType * rhsData = rhsNodePt->buffer().data();
311 const NodeMaskType& rhsMask = rhsNodePt->getValueMask();
312
313 if (Operation == CSG_INTERSECTION) {
314
2/2
✓ Branch 0 taken 20992 times.
✓ Branch 1 taken 41 times.
 42066 for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
315 41984 const bool fromRhs = lhsData[pos] < rhsData[pos];
316
2/2
✓ Branch 0 taken 13294 times.
✓ Branch 1 taken 7698 times.
 41984 outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
317
2/2
✓ Branch 0 taken 7698 times.
✓ Branch 1 taken 13294 times.
 41984 outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
318 }
319 } else if (Operation == CSG_DIFFERENCE){
320
2/2
✓ Branch 0 taken 20992 times.
✓ Branch 1 taken 41 times.
 42066 for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
321
2/2
✓ Branch 0 taken 14883 times.
✓ Branch 1 taken 6109 times.
 41984 const ValueType rhsVal = math::negative(rhsData[pos]);
322 41984 const bool fromRhs = lhsData[pos] < rhsVal;
323
2/2
✓ Branch 0 taken 14883 times.
✓ Branch 1 taken 6109 times.
 41984 outputData[pos] = fromRhs ? rhsVal : lhsData[pos];
324
2/2
✓ Branch 0 taken 6109 times.
✓ Branch 1 taken 14883 times.
 41984 outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
325 }
326 } else { // Union
327
2/2
✓ Branch 0 taken 20992 times.
✓ Branch 1 taken 41 times.
 42066 for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
328 41984 const bool fromRhs = lhsData[pos] > rhsData[pos];
329
2/2
✓ Branch 0 taken 12521 times.
✓ Branch 1 taken 8471 times.
 41984 outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
330
2/2
✓ Branch 0 taken 8471 times.
✓ Branch 1 taken 12521 times.
 41984 outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
331 }
332 }
333
334 } else {
335 if (Operation == CSG_INTERSECTION) {
336
3/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 10 times.
 26 if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
337
3/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
 6 outputAcc.addLeaf(new LeafNodeType(lhsNode));
338 }
339 } else { // Union & Difference
340
3/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 6 times.
 52 if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
341
3/6
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
 40 outputAcc.addLeaf(new LeafNodeType(lhsNode));
342 }
343 }
344 }
345 } // end range loop
346 }
347
348 LeafNodeType const * const * const mLhsNodes;
349 TreeType const * const mRhsTree;
350 TreeType mLocalTree;
351 TreeType * const mOutputTree;
352 }; // struct ProcessLeafNodes
353
354 TreePtrType mSegment;
355 TreeType const * const mLhsTree;
356 TreeType const * const mRhsTree;
357 }; // struct BuildPrimarySegment
358
359
360 template<typename TreeType, CSGOperation Operation>
361
3/12
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
 6 struct BuildSecondarySegment
362 {
363 using ValueType = typename TreeType::ValueType;
364 using TreePtrType = typename TreeType::Ptr;
365 using LeafNodeType = typename TreeType::LeafNodeType;
366 using NodeMaskType = typename LeafNodeType::NodeMaskType;
367 using RootNodeType = typename TreeType::RootNodeType;
368 using NodeChainType = typename RootNodeType::NodeChainType;
369 using InternalNodeType = typename NodeChainType::template Get<1>;
370
371 6 BuildSecondarySegment(const TreeType& lhs, const TreeType& rhs)
372 6 : mSegment(new TreeType(lhs.background()))
373 , mLhsTree(&lhs)
374 6 , mRhsTree(&rhs)
375 {
376 }
377
378
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 void operator()() const
379 {
380 std::vector<const LeafNodeType*> leafNodes;
381
382 {
383 std::vector<const InternalNodeType*> internalNodes;
384
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 mRhsTree->getNodes(internalNodes);
385
386 12 ProcessInternalNodes op(internalNodes, *mLhsTree, *mSegment, leafNodes);
387
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
388 }
389
390 6 ProcessLeafNodes op(leafNodes, *mLhsTree, *mSegment);
391
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
392 }
393
394 TreePtrType& segment() { return mSegment; }
395
396 private:
397
398 struct ProcessInternalNodes {
399
400
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 ProcessInternalNodes(std::vector<const InternalNodeType*>& rhsNodes,
401 const TreeType& lhsTree, TreeType& outputTree,
402 std::vector<const LeafNodeType*>& outputLeafNodes)
403
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 : mRhsNodes(rhsNodes.empty() ? nullptr : &rhsNodes.front())
404 , mLhsTree(&lhsTree)
405 , mLocalTree(mLhsTree->background())
406 , mOutputTree(&outputTree)
407 , mLocalLeafNodes()
408
3/12
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 , mOutputLeafNodes(&outputLeafNodes)
409 {
410 }
411
412 ✗ ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
413 ✗ : mRhsNodes(other.mRhsNodes)
414 ✗ , mLhsTree(other.mLhsTree)
415 , mLocalTree(mLhsTree->background())
416 , mOutputTree(&mLocalTree)
417 , mLocalLeafNodes()
418 ✗ , mOutputLeafNodes(&mLocalLeafNodes)
419 {
420 }
421
422 ✗ void join(ProcessInternalNodes& other)
423 {
424 ✗ mOutputTree->merge(*other.mOutputTree);
425 ✗ mOutputLeafNodes->insert(mOutputLeafNodes->end(),
426 ✗ other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
427 }
428
429 24 void operator()(const tbb::blocked_range<size_t>& range)
430 {
431 24 tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
432
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
433
434 std::vector<const LeafNodeType*> tmpLeafNodes;
435
436
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
 48 for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
437
438 24 const InternalNodeType& rhsNode = *mRhsNodes[n];
439 const Coord& ijk = rhsNode.origin();
440 24 const InternalNodeType * lhsNode =
441 lhsAcc.template probeConstNode<InternalNodeType>(ijk);
442
443
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 if (lhsNode) {
444
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 rhsNode.getNodes(*mOutputLeafNodes);
445 } else {
446 if (Operation == CSG_INTERSECTION) {
447 ✗ if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
448 tmpLeafNodes.clear();
449 ✗ rhsNode.getNodes(tmpLeafNodes);
450 ✗ for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
451 ✗ outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
452 }
453 }
454 } else if (Operation == CSG_DIFFERENCE) {
455 ✗ if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
456 tmpLeafNodes.clear();
457 ✗ rhsNode.getNodes(tmpLeafNodes);
458 ✗ for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
459 ✗ LeafNodeType* outputNode = new LeafNodeType(*tmpLeafNodes[i]);
460 ✗ outputNode->negate();
461 ✗ outputAcc.addLeaf(outputNode);
462 }
463 }
464 } else { // Union
465 ✗ if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
466 tmpLeafNodes.clear();
467 ✗ rhsNode.getNodes(tmpLeafNodes);
468 ✗ for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
469 ✗ outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
470 }
471 }
472 }
473 }
474 } // end range loop
475 }
476
477 InternalNodeType const * const * const mRhsNodes;
478 TreeType const * const mLhsTree;
479 TreeType mLocalTree;
480 TreeType * const mOutputTree;
481
482 std::vector<const LeafNodeType*> mLocalLeafNodes;
483 std::vector<const LeafNodeType*> * const mOutputLeafNodes;
484 }; // struct ProcessInternalNodes
485
486
3/12
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 29 taken 1 times.
✗ Branch 30 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
 3 struct ProcessLeafNodes {
487
488
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 ProcessLeafNodes(std::vector<const LeafNodeType*>& rhsNodes,
489 const TreeType& lhsTree, TreeType& output)
490
3/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 3 : mRhsNodes(rhsNodes.empty() ? nullptr : &rhsNodes.front())
491 , mLhsTree(&lhsTree)
492 , mLocalTree(mLhsTree->background())
493
3/12
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 , mOutputTree(&output)
494 {
495 }
496
497 ✗ ProcessLeafNodes(ProcessLeafNodes& rhs, tbb::split)
498 ✗ : mRhsNodes(rhs.mRhsNodes)
499 ✗ , mLhsTree(rhs.mLhsTree)
500 , mLocalTree(mLhsTree->background())
501 ✗ , mOutputTree(&mLocalTree)
502 {
503 }
504
505 ✗ void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
506
507 570 void operator()(const tbb::blocked_range<size_t>& range)
508 {
509 570 tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
510
1/2
✓ Branch 1 taken 285 times.
✗ Branch 2 not taken.
 570 tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
511
512
2/2
✓ Branch 0 taken 285 times.
✓ Branch 1 taken 285 times.
 1140 for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
513
514 570 const LeafNodeType& rhsNode = *mRhsNodes[n];
515 const Coord& ijk = rhsNode.origin();
516
517 const LeafNodeType* lhsNode = lhsAcc.probeConstLeaf(ijk);
518
519
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 123 times.
 570 if (!lhsNode) {
520 if (Operation == CSG_INTERSECTION) {
521
2/4
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 54 times.
 108 if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
522 ✗ outputAcc.addLeaf(new LeafNodeType(rhsNode));
523 }
524 } else if (Operation == CSG_DIFFERENCE) {
525
2/4
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 54 times.
 108 if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
526 ✗ LeafNodeType* outputNode = new LeafNodeType(rhsNode);
527 ✗ outputNode->negate();
528 ✗ outputAcc.addLeaf(outputNode);
529 }
530 } else { // Union
531
2/4
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 54 times.
✗ Branch 4 not taken.
 108 if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
532
3/6
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 54 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 54 times.
✗ Branch 8 not taken.
 108 outputAcc.addLeaf(new LeafNodeType(rhsNode));
533 }
534 }
535 }
536 } // end range loop
537 }
538
539 LeafNodeType const * const * const mRhsNodes;
540 TreeType const * const mLhsTree;
541 TreeType mLocalTree;
542 TreeType * const mOutputTree;
543 }; // struct ProcessLeafNodes
544
545 TreePtrType mSegment;
546 TreeType const * const mLhsTree;
547 TreeType const * const mRhsTree;
548 }; // struct BuildSecondarySegment
549
550
551 template<CSGOperation Operation, typename TreeType>
552 typename TreeType::Ptr
553 6 doCSGCopy(const TreeType& lhs, const TreeType& rhs)
554 {
555 6 BuildPrimarySegment<TreeType, Operation> primary(lhs, rhs);
556
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 BuildSecondarySegment<TreeType, Operation> secondary(lhs, rhs);
557
558 // Exploiting nested parallelism
559 tbb::task_group tasks;
560
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tasks.run(primary);
561
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tasks.run(secondary);
562
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tasks.wait();
563
564
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 primary.segment()->merge(*secondary.segment());
565
566 // The leafnode (level = 0) sign is set in the segment construction.
567
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 tools::signedFloodFill(*primary.segment(), /*threaded=*/true, /*grainSize=*/1, /*minLevel=*/1);
568
569 6 return primary.segment();
570 }
571
572
573 ////////////////////////////////////////
574
575
576 template<typename TreeType>
577 struct GridOrTreeConstructor
578 {
579 using TreeTypePtr = typename TreeType::Ptr;
580 static TreeTypePtr construct(const TreeType&, TreeTypePtr& tree) { return tree; }
581 };
582
583
584 template<typename TreeType>
585 struct GridOrTreeConstructor<Grid<TreeType> >
586 {
587 using GridType = Grid<TreeType>;
588 using GridTypePtr = typename Grid<TreeType>::Ptr;
589 using TreeTypePtr = typename TreeType::Ptr;
590
591 6 static GridTypePtr construct(const GridType& grid, TreeTypePtr& tree) {
592
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 12 GridTypePtr maskGrid(GridType::create(tree));
593
3/8
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 12 maskGrid->setTransform(grid.transform().copy());
594
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 maskGrid->insertMeta(grid);
595 6 return maskGrid;
596 }
597 };
598
599
600 ////////////////////////////////////////
601
602 /// List of pairs of leaf node pointers
603 template <typename LeafT>
604 using LeafPairList = std::vector<std::pair<LeafT*, LeafT*>>;
605
606 /// Transfers leaf nodes from a source tree into a
607 /// destination tree, unless it already exists in the destination tree
608 /// in which case pointers to both leaf nodes are added to a list for
609 /// subsequent compositing operations.
610 template <typename TreeT>
611 10 void transferLeafNodes(TreeT &srcTree, TreeT &dstTree,
612 LeafPairList<typename TreeT::LeafNodeType> &overlapping)
613 {
614 using LeafT = typename TreeT::LeafNodeType;
615 tree::ValueAccessor<TreeT> acc(dstTree);//destination
616 std::vector<LeafT*> srcLeafNodes;
617
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 10 srcLeafNodes.reserve(srcTree.leafCount());
618 srcTree.stealNodes(srcLeafNodes);
619
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 srcTree.clear();
620
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 30 for (LeafT *srcLeaf : srcLeafNodes) {
621 20 LeafT *dstLeaf = acc.probeLeaf(srcLeaf->origin());
622
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 20 if (dstLeaf) {
623
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 overlapping.emplace_back(dstLeaf, srcLeaf);//dst, src
624 } else {
625
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 acc.addLeaf(srcLeaf);
626 }
627 }
628 10 }
629
630 /// Template specialization of compActiveLeafVoxels
631 template <typename TreeT, typename OpT>
632 inline
633 typename std::enable_if<
634 !std::is_same<typename TreeT::ValueType, bool>::value &&
635 !std::is_same<typename TreeT::BuildType, ValueMask>::value &&
636 std::is_same<typename TreeT::LeafNodeType::Buffer::ValueType,
637 typename TreeT::LeafNodeType::Buffer::StorageType>::value>::type
638
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
639 {
640 using LeafT = typename TreeT::LeafNodeType;
641 LeafPairList<LeafT> overlapping;//dst, src
642
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 transferLeafNodes(srcTree, dstTree, overlapping);
643
644 using RangeT = tbb::blocked_range<size_t>;
645
2/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
646
6/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 1 times.
 6 for (auto i = r.begin(); i != r.end(); ++i) {
647 3 LeafT *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
648 dstLeaf->getValueMask() |= srcLeaf->getValueMask();
649 3 auto *ptr = dstLeaf->buffer().data();
650
6/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 1 times.
 8 for (auto v = srcLeaf->cbeginValueOn(); v; ++v) op(ptr[v.pos()], *v);
651
3/6
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 6 delete srcLeaf;
652 }
653 });
654 6 }
655
656 /// Template specialization of compActiveLeafVoxels
657 template <typename TreeT, typename OpT>
658 inline
659 typename std::enable_if<
660 std::is_same<typename TreeT::BuildType, ValueMask>::value &&
661 std::is_same<typename TreeT::ValueType, bool>::value>::type
662
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT)
663 {
664 using LeafT = typename TreeT::LeafNodeType;
665 LeafPairList<LeafT> overlapping;//dst, src
666
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 transferLeafNodes(srcTree, dstTree, overlapping);
667
668 using RangeT = tbb::blocked_range<size_t>;
669
3/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 4 tbb::parallel_for(RangeT(0, overlapping.size()), [&overlapping](const RangeT& r) {
670
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 for (auto i = r.begin(); i != r.end(); ++i) {
671 1 overlapping[i].first->getValueMask() |= overlapping[i].second->getValueMask();
672
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 delete overlapping[i].second;
673 }
674 });
675 1 }
676
677 /// Template specialization of compActiveLeafVoxels
678 template <typename TreeT, typename OpT>
679 inline
680 typename std::enable_if<
681 std::is_same<typename TreeT::ValueType, bool>::value &&
682 !std::is_same<typename TreeT::BuildType, ValueMask>::value>::type
683
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
684 {
685 using LeafT = typename TreeT::LeafNodeType;
686 LeafPairList<LeafT> overlapping;//dst, src
687
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 transferLeafNodes(srcTree, dstTree, overlapping);
688
689 using RangeT = tbb::blocked_range<size_t>;
690 using WordT = typename LeafT::Buffer::WordType;
691
2/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 3 tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
692
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 for (auto i = r.begin(); i != r.end(); ++i) {
693 1 LeafT *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
694 WordT *w1 = dstLeaf->buffer().data();
695 const WordT *w2 = srcLeaf->buffer().data();
696 const WordT *w3 = &(srcLeaf->getValueMask().template getWord<WordT>(0));
697
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 1 times.
 9 for (Index32 n = LeafT::Buffer::WORD_COUNT; n--; ++w1) {
698 8 WordT tmp = *w1, state = *w3++;
699 8 op (tmp, *w2++);
700 8 *w1 = (state & tmp) | (~state & *w1);//inactive values are unchanged
701 }
702 dstLeaf->getValueMask() |= srcLeaf->getValueMask();
703
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 delete srcLeaf;
704 }
705 });
706 1 }
707
708 /// Default functor for compActiveLeafVoxels
709 template <typename TreeT>
710 struct CopyOp
711 {
712 using ValueT = typename TreeT::ValueType;
713 CopyOp() = default;
714 1 void operator()(ValueT& dst, const ValueT& src) const { dst = src; }
715 };
716
717 template <typename TreeT>
718
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 113 void validateLevelSet(const TreeT& tree, const std::string& gridName = std::string(""))
719 {
720 using ValueT = typename TreeT::ValueType;
721 const ValueT zero = zeroVal<ValueT>();
722
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 60 times.
 113 if (!(tree.background() > zero)) {
723 6 std::stringstream ss;
724
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ss << "expected grid ";
725
2/4
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 6 if (!gridName.empty()) ss << gridName << " ";
726
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ss << "outside value > 0, got " << tree.background();
727
2/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 15 OPENVDB_THROW(ValueError, ss.str());
728 }
729
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 60 times.
 110 if (!(-tree.background() < zero)) {
730 ✗ std::stringstream ss;
731 ✗ ss << "expected grid ";
732 ✗ if (!gridName.empty()) ss << gridName << " ";
733 ✗ ss << "inside value < 0, got " << -tree.background();
734 ✗ OPENVDB_THROW(ValueError, ss.str());
735 }
736 110 }
737
738 /// @endcond
739
740 } // namespace composite
741
742
743 template<typename GridOrTreeT>
744 void
745 14 compMax(GridOrTreeT& aTree, GridOrTreeT& bTree)
746 {
747 using Adapter = TreeAdapter<GridOrTreeT>;
748 using TreeT = typename Adapter::TreeType;
749 using ValueT = typename TreeT::ValueType;
750 struct Local {
751
2/2
✓ Branch 0 taken 71564 times.
✓ Branch 1 taken 572868 times.
 793933 static inline void op(CombineArgs<ValueT>& args) {
752 74750 args.setResult(composite::max(args.a(), args.b()));
753 793933 }
754 };
755 Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
756 14 }
757
758
759 template<typename GridOrTreeT>
760 void
761 8 compMin(GridOrTreeT& aTree, GridOrTreeT& bTree)
762 {
763 using Adapter = TreeAdapter<GridOrTreeT>;
764 using TreeT = typename Adapter::TreeType;
765 using ValueT = typename TreeT::ValueType;
766 struct Local {
767 149500 static inline void op(CombineArgs<ValueT>& args) {
768 74750 args.setResult(composite::min(args.a(), args.b()));
769 }
770 };
771 Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
772 }
773
774
775 template<typename GridOrTreeT>
776 void
777 10 compSum(GridOrTreeT& aTree, GridOrTreeT& bTree)
778 {
779 using Adapter = TreeAdapter<GridOrTreeT>;
780 using TreeT = typename Adapter::TreeType;
781 struct Local {
782 196584 static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
783 196584 args.setResult(args.a() + args.b());
784 }
785 };
786 Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
787 }
788
789
790 template<typename GridOrTreeT>
791 void
792 8 compMul(GridOrTreeT& aTree, GridOrTreeT& bTree)
793 {
794 using Adapter = TreeAdapter<GridOrTreeT>;
795 using TreeT = typename Adapter::TreeType;
796 struct Local {
797 149500 static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
798 149500 args.setResult(args.a() * args.b());
799 }
800 };
801 Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
802 8 }
803
804
805 template<typename GridOrTreeT>
806 void
807 13 compDiv(GridOrTreeT& aTree, GridOrTreeT& bTree)
808 {
809 using Adapter = TreeAdapter<GridOrTreeT>;
810 using TreeT = typename Adapter::TreeType;
811 struct Local {
812
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 37375 times.
 261625 static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
813 74750 args.setResult(composite::divide(args.a(), args.b()));
814 261625 }
815 };
816 Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
817 13 }
818
819
820 ////////////////////////////////////////
821
822
823 template<typename TreeT>
824 struct CompReplaceOp
825 {
826 TreeT* const aTree;
827
828 4 CompReplaceOp(TreeT& _aTree): aTree(&_aTree) {}
829
830 /// @note fill operation is not thread safe
831 ✗ void operator()(const typename TreeT::ValueOnCIter& iter) const
832 {
833 ✗ CoordBBox bbox;
834 ✗ iter.getBoundingBox(bbox);
835 ✗ aTree->fill(bbox, *iter);
836 }
837
838 8 void operator()(const typename TreeT::LeafCIter& leafIter) const
839 {
840 8 tree::ValueAccessor<TreeT> acc(*aTree);
841
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
 36 for (typename TreeT::LeafCIter::LeafNodeT::ValueOnCIter iter =
842 leafIter->cbeginValueOn(); iter; ++iter)
843 {
844
2/6
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 28 acc.setValue(iter.getCoord(), *iter);
845 }
846 }
847 };
848
849
850 template<typename GridOrTreeT>
851 void
852 8 compReplace(GridOrTreeT& aTree, const GridOrTreeT& bTree)
853 {
854 using Adapter = TreeAdapter<GridOrTreeT>;
855 using TreeT = typename Adapter::TreeType;
856 using ValueOnCIterT = typename TreeT::ValueOnCIter;
857
858 // Copy active states (but not values) from B to A.
859 Adapter::tree(aTree).topologyUnion(Adapter::tree(bTree));
860
861 CompReplaceOp<TreeT> op(Adapter::tree(aTree));
862
863 // Copy all active tile values from B to A.
864 ValueOnCIterT iter = bTree.cbeginValueOn();
865 8 iter.setMaxDepth(iter.getLeafDepth() - 1); // don't descend into leaf nodes
866 8 foreach(iter, op, /*threaded=*/false);
867
868 // Copy all active voxel values from B to A.
869 8 foreach(Adapter::tree(bTree).cbeginLeaf(), op);
870 }
871
872
873 ////////////////////////////////////////
874
875
876 template<typename GridOrTreeT>
877 void
878
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 46 csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune)
879 {
880 using Adapter = TreeAdapter<GridOrTreeT>;
881 using TreeT = typename Adapter::TreeType;
882 TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
883
3/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 25 times.
✓ Branch 5 taken 1 times.
 47 composite::validateLevelSet(aTree, "A");
884
2/4
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 25 times.
✗ Branch 5 not taken.
 45 composite::validateLevelSet(bTree, "B");
885 45 CsgUnionOp<TreeT> op(bTree, Steal());
886 45 tree::DynamicNodeManager<TreeT> nodeManager(aTree);
887
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 45 nodeManager.foreachTopDown(op);
888
2/4
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 25 times.
✗ Branch 4 not taken.
 45 if (prune) tools::pruneLevelSet(aTree);
889 45 }
890
891 template<typename GridOrTreeT>
892 void
893
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 1 csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune)
894 {
895 using Adapter = TreeAdapter<GridOrTreeT>;
896 using TreeT = typename Adapter::TreeType;
897 TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
898
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
 2 composite::validateLevelSet(aTree, "A");
899 ✗ composite::validateLevelSet(bTree, "B");
900 ✗ CsgIntersectionOp<TreeT> op(bTree, Steal());
901 ✗ tree::DynamicNodeManager<TreeT> nodeManager(aTree);
902 ✗ nodeManager.foreachTopDown(op);
903 ✗ if (prune) tools::pruneLevelSet(aTree);
904 }
905
906 template<typename GridOrTreeT>
907 void
908
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 11 csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune)
909 {
910 using Adapter = TreeAdapter<GridOrTreeT>;
911 using TreeT = typename Adapter::TreeType;
912 TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
913
3/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 1 times.
 12 composite::validateLevelSet(aTree, "A");
914
3/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 5 times.
✗ Branch 8 not taken.
 20 composite::validateLevelSet(bTree, "B");
915 CsgDifferenceOp<TreeT> op(bTree, Steal());
916 10 tree::DynamicNodeManager<TreeT> nodeManager(aTree);
917
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 nodeManager.foreachTopDown(op);
918
2/4
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 10 if (prune) tools::pruneLevelSet(aTree);
919 }
920
921
922 template<typename GridOrTreeT>
923 typename GridOrTreeT::Ptr
924 2 csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
925 {
926 using Adapter = TreeAdapter<GridOrTreeT>;
927 using TreePtrT = typename Adapter::TreeType::Ptr;
928
929 2 TreePtrT output = composite::doCSGCopy<composite::CSG_UNION>(
930 Adapter::tree(a), Adapter::tree(b));
931
932
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 4 return composite::GridOrTreeConstructor<GridOrTreeT>::construct(a, output);
933 }
934
935
936 template<typename GridOrTreeT>
937 typename GridOrTreeT::Ptr
938 2 csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
939 {
940 using Adapter = TreeAdapter<GridOrTreeT>;
941 using TreePtrT = typename Adapter::TreeType::Ptr;
942
943 2 TreePtrT output = composite::doCSGCopy<composite::CSG_INTERSECTION>(
944 Adapter::tree(a), Adapter::tree(b));
945
946
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 4 return composite::GridOrTreeConstructor<GridOrTreeT>::construct(a, output);
947 }
948
949
950 template<typename GridOrTreeT>
951 typename GridOrTreeT::Ptr
952 1 csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b)
953 {
954 using Adapter = TreeAdapter<GridOrTreeT>;
955 using TreePtrT = typename Adapter::TreeType::Ptr;
956
957 1 TreePtrT output = composite::doCSGCopy<composite::CSG_DIFFERENCE>(
958 Adapter::tree(a), Adapter::tree(b));
959
960 2 return composite::GridOrTreeConstructor<GridOrTreeT>::construct(a, output);
961 }
962
963 ////////////////////////////////////////////////////////
964
965 /// @brief Composite the active values in leaf nodes, i.e. active
966 /// voxels, of a source tree into a destination tree.
967 ///
968 /// @param srcTree source tree from which active voxels are composited.
969 ///
970 /// @param dstTree destination tree into which active voxels are composited.
971 ///
972 /// @param op a functor of the form <tt>void op(T& dst, const T& src)</tt>,
973 /// where @c T is the @c ValueType of the tree, that composites
974 /// a source value into a destination value. By default
975 /// it copies the value from src to dst.
976 ///
977 /// @details All active voxels in the source tree will
978 /// be active in the destination tree, and their value is
979 /// determined by a use-defined functor (OpT op) that operates on the
980 /// source and destination values. The only exception is when
981 /// the tree type is MaskTree, in which case no functor is
982 /// needed since by defintion a MaskTree has no values (only topology).
983 ///
984 /// @warning This function only operated on leaf node values,
985 /// i.e. tile values are ignored.
986 template<typename TreeT, typename OpT = composite::CopyOp<TreeT> >
987 void
988 10 compActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op = composite::CopyOp<TreeT>())
989 {
990 10 composite::doCompActiveLeafVoxels<TreeT, OpT>(srcTree, dstTree, op);
991 10 }
992
993
994 ////////////////////////////////////////
995
996
997 // Explicit Template Instantiation
998
999 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
1000
1001 #ifdef OPENVDB_INSTANTIATE_COMPOSITE
1002 #include <openvdb/util/ExplicitInstantiation.h>
1003 #endif
1004
1005 #define _FUNCTION(TreeT) \
1006 void csgUnion(TreeT&, TreeT&, bool)
1007 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1008 #undef _FUNCTION
1009
1010 #define _FUNCTION(TreeT) \
1011 void csgUnion(Grid<TreeT>&, Grid<TreeT>&, bool)
1012 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1013 #undef _FUNCTION
1014
1015 #define _FUNCTION(TreeT) \
1016 void csgIntersection(TreeT&, TreeT&, bool)
1017 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1018 #undef _FUNCTION
1019
1020 #define _FUNCTION(TreeT) \
1021 void csgIntersection(Grid<TreeT>&, Grid<TreeT>&, bool)
1022 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1023 #undef _FUNCTION
1024
1025 #define _FUNCTION(TreeT) \
1026 void csgDifference(TreeT&, TreeT&, bool)
1027 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1028 #undef _FUNCTION
1029
1030 #define _FUNCTION(TreeT) \
1031 void csgDifference(Grid<TreeT>&, Grid<TreeT>&, bool)
1032 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1033 #undef _FUNCTION
1034
1035 #define _FUNCTION(TreeT) \
1036 TreeT::Ptr csgUnionCopy(const TreeT&, const TreeT&)
1037 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1038 #undef _FUNCTION
1039
1040 #define _FUNCTION(TreeT) \
1041 Grid<TreeT>::Ptr csgUnionCopy(const Grid<TreeT>&, const Grid<TreeT>&)
1042 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1043 #undef _FUNCTION
1044
1045 #define _FUNCTION(TreeT) \
1046 TreeT::Ptr csgIntersectionCopy(const TreeT&, const TreeT&)
1047 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1048 #undef _FUNCTION
1049
1050 #define _FUNCTION(TreeT) \
1051 Grid<TreeT>::Ptr csgIntersectionCopy(const Grid<TreeT>&, const Grid<TreeT>&)
1052 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1053 #undef _FUNCTION
1054
1055 #define _FUNCTION(TreeT) \
1056 TreeT::Ptr csgDifferenceCopy(const TreeT&, const TreeT&)
1057 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1058 #undef _FUNCTION
1059
1060 #define _FUNCTION(TreeT) \
1061 Grid<TreeT>::Ptr csgDifferenceCopy(const Grid<TreeT>&, const Grid<TreeT>&)
1062 OPENVDB_REAL_TREE_INSTANTIATE(_FUNCTION)
1063 #undef _FUNCTION
1064
1065 #define _FUNCTION(TreeT) \
1066 void compMax(TreeT&, TreeT&)
1067 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1068 #undef _FUNCTION
1069
1070 #define _FUNCTION(TreeT) \
1071 void compMax(Grid<TreeT>&, Grid<TreeT>&)
1072 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1073 #undef _FUNCTION
1074
1075 #define _FUNCTION(TreeT) \
1076 void compMin(TreeT&, TreeT&)
1077 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1078 #undef _FUNCTION
1079
1080 #define _FUNCTION(TreeT) \
1081 void compMin(Grid<TreeT>&, Grid<TreeT>&)
1082 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1083 #undef _FUNCTION
1084
1085 #define _FUNCTION(TreeT) \
1086 void compSum(TreeT&, TreeT&)
1087 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1088 #undef _FUNCTION
1089
1090 #define _FUNCTION(TreeT) \
1091 void compSum(Grid<TreeT>&, Grid<TreeT>&)
1092 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1093 #undef _FUNCTION
1094
1095 #define _FUNCTION(TreeT) \
1096 void compDiv(TreeT&, TreeT&)
1097 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1098 #undef _FUNCTION
1099
1100 #define _FUNCTION(TreeT) \
1101 void compDiv(Grid<TreeT>&, Grid<TreeT>&)
1102 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1103 #undef _FUNCTION
1104
1105 #define _FUNCTION(TreeT) \
1106 void compReplace(TreeT&, const TreeT&)
1107 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1108 #undef _FUNCTION
1109
1110 #define _FUNCTION(TreeT) \
1111 void compReplace(Grid<TreeT>&, const Grid<TreeT>&)
1112 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
1113 #undef _FUNCTION
1114
1115 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
1116
1117
1118 } // namespace tools
1119 } // namespace OPENVDB_VERSION_NAME
1120 } // namespace openvdb
1121
1122 #endif // OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
1123