GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/Merge.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 396 433 91.5%
Functions: 90 447 20.1%
Branches: 581 1005 57.8%
Line Branch Exec Source
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file Merge.h
5 ///
6 /// @brief Functions to efficiently merge grids
7 ///
8 /// @author Dan Bailey
9
10 #ifndef OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_MERGE_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/tree/NodeManager.h>
18 #include <openvdb/tools/NodeVisitor.h>
19 #include <openvdb/openvdb.h>
20
21 #include <memory>
22 #include <unordered_map>
23 #include <unordered_set>
24
25 namespace openvdb {
26 OPENVDB_USE_VERSION_NAMESPACE
27 namespace OPENVDB_VERSION_NAME {
28 namespace tools {
29
30
31 /// @brief Convenience class that contains a pointer to a tree to be stolen or
32 /// deep copied depending on the tag dispatch class used and a subset of
33 /// methods to retrieve data from the tree.
34 ///
35 /// @details The primary purpose of this class is to be able to create an array
36 /// of TreeToMerge objects that each store a tree to be stolen or a tree to be
37 /// deep-copied in an arbitrary order. Certain operations such as floating-point
38 /// addition are non-associative so the order in which they are merged is
39 /// important for the operation to remain deterministic regardless of how the
40 /// data is being extracted from the tree.
41 ///
42 /// @note Stealing data requires a non-const tree pointer. There is a constructor
43 /// to pass in a tree shared pointer for cases where it is desirable for this class
44 /// to maintain shared ownership.
45 template <typename TreeT>
46 37 struct TreeToMerge
47 {
48 using TreeType = std::remove_const_t<TreeT>;
49 using RootNodeType = typename TreeType::RootNodeType;
50 using ValueType = typename TreeType::ValueType;
51 using MaskTreeType = typename TreeT::template ValueConverter<ValueMask>::Type;
52
53 TreeToMerge() = delete;
54
55 /// @brief Non-const pointer tree constructor for stealing data.
56
2/4
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
 176 TreeToMerge(TreeType& tree, Steal)
57
22/47
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 1 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✓ Branch 24 taken 1 times.
✗ Branch 25 not taken.
✓ Branch 27 taken 1 times.
✗ Branch 28 not taken.
✓ Branch 30 taken 1 times.
✗ Branch 31 not taken.
✓ Branch 33 taken 1 times.
✗ Branch 34 not taken.
✓ Branch 36 taken 1 times.
✗ Branch 37 not taken.
✓ Branch 39 taken 1 times.
✗ Branch 40 not taken.
✓ Branch 42 taken 1 times.
✗ Branch 43 not taken.
✓ Branch 45 taken 1 times.
✗ Branch 46 not taken.
✓ Branch 48 taken 1 times.
✗ Branch 49 not taken.
✓ Branch 51 taken 1 times.
✗ Branch 52 not taken.
✓ Branch 54 taken 1 times.
✗ Branch 55 not taken.
✓ Branch 57 taken 1 times.
✗ Branch 58 not taken.
✓ Branch 60 taken 1 times.
✗ Branch 61 not taken.
✓ Branch 63 taken 1 times.
✗ Branch 64 not taken.
✓ Branch 66 taken 1 times.
✗ Branch 67 not taken.
✓ Branch 69 taken 1 times.
✗ Branch 70 not taken.
 201 : mTree(&tree), mSteal(true) { }
58 /// @brief Non-const shared pointer tree constructor for stealing data.
59 1 TreeToMerge(typename TreeType::Ptr treePtr, Steal)
60
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 : mTreePtr(treePtr), mTree(mTreePtr.get()), mSteal(true) { }
61
62 /// @brief Const tree pointer constructor for deep-copying data. As the
63 /// tree is not mutable and thus cannot be pruned, a lightweight mask tree
64 /// with the same topology is created that can be pruned to use as a
65 /// reference. Initialization of this mask tree can optionally be disabled
66 /// for delayed construction.
67
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 24 TreeToMerge(const TreeType& tree, DeepCopy, bool initialize = true)
68
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
 24 : mTree(&tree), mSteal(false)
69 {
70
3/4
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 1 times.
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
 24 if (mTree && initialize) this->initializeMask();
71 }
72
73 /// @brief Non-const tree pointer constructor for deep-copying data. The
74 /// tree is not intended to be modified so is not pruned, instead a
75 /// lightweight mask tree with the same topology is created that can be
76 /// pruned to use as a reference. Initialization of this mask tree can
77 /// optionally be disabled for delayed construction.
78 13 TreeToMerge(TreeType& tree, DeepCopy tag, bool initialize = true)
79
2/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 12 : TreeToMerge(static_cast<const TreeType&>(tree), tag, initialize) { }
80
81 /// @brief Reset the non-const tree shared pointer. This is primarily
82 /// used to preserve the order of trees to merge in a container but have
83 /// the data in the tree be lazily loaded or resampled.
84 void reset(typename TreeType::Ptr treePtr, Steal);
85
86 /// @brief Return a pointer to the tree to be stolen.
87
6/12
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 6 TreeType* treeToSteal() { return mSteal ? const_cast<TreeType*>(mTree) : nullptr; }
88 /// @brief Return a pointer to the tree to be deep-copied.
89
6/12
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 1 times.
 6 const TreeType* treeToDeepCopy() { return mSteal ? nullptr : mTree; }
90
91 /// @brief Retrieve a const pointer to the root node.
92 const RootNodeType* rootPtr() const;
93
94 /// @brief Return a pointer to the node of type @c NodeT that contains
95 /// voxel (x, y, z). If no such node exists, return @c nullptr.
96 template<typename NodeT>
97 const NodeT* probeConstNode(const Coord& ijk) const;
98
99 /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z).
100 /// If the tree is non-const, steal the node and replace it with an inactive
101 /// background-value tile.
102 /// If the tree is const, deep-copy the node and modify the mask tree to prune the node.
103 template <typename NodeT>
104 std::unique_ptr<NodeT> stealOrDeepCopyNode(const Coord& ijk);
105
106 /// @brief Add a tile containing voxel (x, y, z) at the level of NodeT,
107 /// deleting the existing branch if necessary.
108 template <typename NodeT>
109 void addTile(const Coord& ijk, const ValueType& value, bool active);
110
111 // build a lightweight mask using a union of the const tree where leaf nodes
112 // are converted into active tiles
113 void initializeMask();
114
115 // returns true if mask has been initialized
116 bool hasMask() const;
117
118 // returns MaskTree pointer or nullptr
119 ✗ MaskTreeType* mask() { return mMaskTree.ptr.get(); }
120 ✗ const MaskTreeType* mask() const { return mMaskTree.ptr.get(); }
121
122 private:
123 struct MaskPtr;
124 struct MaskUnionOp;
125
126 typename TreeType::Ptr mTreePtr;
127 const TreeType* mTree;
128 MaskPtr mMaskTree;
129 bool mSteal;
130 }; // struct TreeToMerge
131
132
133 /// @brief Wrapper around unique_ptr that deep-copies mask on copy construction
134 template <typename TreeT>
135 struct TreeToMerge<TreeT>::MaskPtr
136 {
137 std::unique_ptr<MaskTreeType> ptr;
138
139 MaskPtr() = default;
140 ✗ ~MaskPtr() = default;
141 MaskPtr(MaskPtr&& other) = default;
142 MaskPtr& operator=(MaskPtr&& other) = default;
143 ✗ MaskPtr(const MaskPtr& other)
144 ✗ : ptr(bool(other.ptr) ? std::make_unique<MaskTreeType>(*other.ptr) : nullptr) { }
145 ✗ MaskPtr& operator=(const MaskPtr& other)
146 {
147 ✗ if (bool(other.ptr)) ptr = std::make_unique<MaskTreeType>(*other.ptr);
148 else ptr.reset();
149 ✗ return *this;
150 }
151 };
152
153 /// @brief DynamicNodeManager operator used to generate a mask of the input
154 /// tree, but with dense leaf nodes replaced with active tiles for compactness
155 template <typename TreeT>
156 struct TreeToMerge<TreeT>::MaskUnionOp
157 {
158 using MaskT = MaskTreeType;
159 using RootT = typename MaskT::RootNodeType;
160 using LeafT = typename MaskT::LeafNodeType;
161
162 30 explicit MaskUnionOp(const TreeT& tree) : mTree(tree) { }
163 bool operator()(RootT& root, size_t) const;
164 template<typename NodeT>
165 bool operator()(NodeT& node, size_t) const;
166 ✗ bool operator()(LeafT&, size_t) const { return false; }
167 private:
168 const TreeT& mTree;
169 }; // struct TreeToMerge<TreeT>::MaskUnionOp
170
171
172 ////////////////////////////////////////
173
174
175 /// @brief DynamicNodeManager operator to merge trees using a CSG union or intersection.
176 /// @note This class modifies the topology of the tree so is designed to be used
177 /// from DynamicNodeManager::foreachTopDown().
178 /// @details A union and an intersection are opposite operations to each other so
179 /// implemented in a combined class. Use the CsgUnionOp and CsgIntersectionOp aliases
180 /// for convenience.
181 template<typename TreeT, bool Union>
182
100/200
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✓ Branch 24 taken 1 times.
✗ Branch 25 not taken.
✓ Branch 28 taken 1 times.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✓ Branch 32 taken 1 times.
✓ Branch 34 taken 1 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 1 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 1 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 1 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 1 times.
✗ Branch 47 not taken.
✓ Branch 49 taken 1 times.
✗ Branch 50 not taken.
✓ Branch 52 taken 1 times.
✗ Branch 53 not taken.
✓ Branch 55 taken 1 times.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✓ Branch 61 taken 1 times.
✗ Branch 62 not taken.
✓ Branch 64 taken 1 times.
✗ Branch 65 not taken.
✓ Branch 67 taken 1 times.
✗ Branch 68 not taken.
✓ Branch 70 taken 1 times.
✗ Branch 71 not taken.
✓ Branch 73 taken 1 times.
✗ Branch 74 not taken.
✓ Branch 76 taken 1 times.
✗ Branch 77 not taken.
✓ Branch 79 taken 1 times.
✗ Branch 80 not taken.
✓ Branch 82 taken 1 times.
✗ Branch 83 not taken.
✓ Branch 85 taken 1 times.
✗ Branch 86 not taken.
✓ Branch 88 taken 1 times.
✗ Branch 89 not taken.
✓ Branch 91 taken 1 times.
✗ Branch 92 not taken.
✓ Branch 94 taken 1 times.
✗ Branch 95 not taken.
✓ Branch 97 taken 1 times.
✗ Branch 98 not taken.
✓ Branch 100 taken 1 times.
✗ Branch 101 not taken.
✓ Branch 103 taken 1 times.
✗ Branch 104 not taken.
✓ Branch 106 taken 1 times.
✗ Branch 107 not taken.
✓ Branch 109 taken 1 times.
✗ Branch 110 not taken.
✓ Branch 112 taken 1 times.
✗ Branch 113 not taken.
✓ Branch 115 taken 1 times.
✗ Branch 116 not taken.
✓ Branch 118 taken 1 times.
✗ Branch 119 not taken.
✓ Branch 121 taken 1 times.
✗ Branch 122 not taken.
✓ Branch 124 taken 1 times.
✗ Branch 125 not taken.
✓ Branch 131 taken 1 times.
✗ Branch 132 not taken.
✓ Branch 134 taken 1 times.
✗ Branch 135 not taken.
✓ Branch 137 taken 1 times.
✗ Branch 138 not taken.
✓ Branch 140 taken 1 times.
✗ Branch 141 not taken.
✓ Branch 143 taken 1 times.
✗ Branch 144 not taken.
✓ Branch 146 taken 1 times.
✗ Branch 147 not taken.
✓ Branch 149 taken 1 times.
✗ Branch 150 not taken.
✓ Branch 154 taken 1 times.
✗ Branch 155 not taken.
✓ Branch 157 taken 1 times.
✗ Branch 158 not taken.
✓ Branch 160 taken 1 times.
✗ Branch 161 not taken.
✓ Branch 163 taken 1 times.
✗ Branch 164 not taken.
✓ Branch 166 taken 1 times.
✗ Branch 167 not taken.
✓ Branch 169 taken 1 times.
✗ Branch 170 not taken.
✓ Branch 233 taken 1 times.
✗ Branch 234 not taken.
✓ Branch 240 taken 1 times.
✗ Branch 241 not taken.
✓ Branch 243 taken 1 times.
✗ Branch 244 not taken.
✓ Branch 247 taken 1 times.
✗ Branch 248 not taken.
✓ Branch 250 taken 1 times.
✗ Branch 251 not taken.
✓ Branch 253 taken 1 times.
✗ Branch 254 not taken.
✓ Branch 257 taken 1 times.
✗ Branch 258 not taken.
✗ Branch 260 not taken.
✓ Branch 261 taken 1 times.
✓ Branch 263 taken 1 times.
✗ Branch 264 not taken.
✓ Branch 266 taken 1 times.
✗ Branch 267 not taken.
✓ Branch 269 taken 1 times.
✗ Branch 270 not taken.
✓ Branch 272 taken 1 times.
✗ Branch 273 not taken.
✓ Branch 275 taken 1 times.
✗ Branch 276 not taken.
✓ Branch 278 taken 1 times.
✗ Branch 279 not taken.
✓ Branch 281 taken 1 times.
✗ Branch 282 not taken.
✓ Branch 284 taken 1 times.
✗ Branch 285 not taken.
✓ Branch 287 taken 1 times.
✗ Branch 288 not taken.
✓ Branch 290 taken 1 times.
✗ Branch 291 not taken.
✓ Branch 293 taken 1 times.
✗ Branch 294 not taken.
✓ Branch 296 taken 1 times.
✗ Branch 297 not taken.
✓ Branch 299 taken 1 times.
✗ Branch 300 not taken.
✓ Branch 302 taken 1 times.
✗ Branch 303 not taken.
✓ Branch 305 taken 1 times.
✗ Branch 306 not taken.
✓ Branch 308 taken 1 times.
✗ Branch 309 not taken.
✓ Branch 311 taken 1 times.
✗ Branch 312 not taken.
✓ Branch 314 taken 1 times.
✗ Branch 315 not taken.
✓ Branch 317 taken 1 times.
✗ Branch 318 not taken.
✓ Branch 320 taken 1 times.
✗ Branch 321 not taken.
✓ Branch 323 taken 1 times.
✗ Branch 324 not taken.
✓ Branch 326 taken 1 times.
✗ Branch 327 not taken.
✓ Branch 329 taken 1 times.
✗ Branch 330 not taken.
✓ Branch 332 taken 1 times.
✗ Branch 333 not taken.
✓ Branch 335 taken 1 times.
✗ Branch 336 not taken.
✓ Branch 338 taken 1 times.
✗ Branch 339 not taken.
✓ Branch 341 taken 1 times.
✗ Branch 342 not taken.
✓ Branch 344 taken 1 times.
✗ Branch 345 not taken.
✓ Branch 347 taken 1 times.
✗ Branch 348 not taken.
✓ Branch 350 taken 1 times.
✗ Branch 351 not taken.
✓ Branch 357 taken 1 times.
✗ Branch 358 not taken.
✓ Branch 360 taken 1 times.
✗ Branch 361 not taken.
✓ Branch 363 taken 1 times.
✗ Branch 364 not taken.
✓ Branch 366 taken 1 times.
✗ Branch 367 not taken.
✓ Branch 369 taken 1 times.
✗ Branch 370 not taken.
✓ Branch 372 taken 1 times.
✗ Branch 373 not taken.
✓ Branch 377 taken 1 times.
✗ Branch 378 not taken.
✓ Branch 380 taken 1 times.
✗ Branch 381 not taken.
✓ Branch 383 taken 1 times.
✗ Branch 384 not taken.
✓ Branch 386 taken 1 times.
✗ Branch 387 not taken.
 137 struct CsgUnionOrIntersectionOp
183 {
184 using ValueT = typename TreeT::ValueType;
185 using RootT = typename TreeT::RootNodeType;
186 using LeafT = typename TreeT::LeafNodeType;
187
188 /// @brief Convenience constructor to CSG union or intersect a single
189 /// non-const tree with another. This constructor takes a Steal or DeepCopy
190 /// tag dispatch class.
191 template <typename TagT>
192
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 99 CsgUnionOrIntersectionOp(TreeT& tree, TagT tag) { mTreesToMerge.emplace_back(tree, tag); }
193
194 /// @brief Convenience constructor to CSG union or intersect a single
195 /// const tree with another. This constructor requires a DeepCopy tag
196 /// dispatch class.
197 ✗ CsgUnionOrIntersectionOp(const TreeT& tree, DeepCopy tag) { mTreesToMerge.emplace_back(tree, tag); }
198
199 /// @brief Constructor to CSG union or intersect a container of multiple
200 /// const or non-const tree pointers. A Steal tag requires a container of
201 /// non-const trees, a DeepCopy tag will accept either const or non-const
202 /// trees.
203 template <typename TreesT, typename TagT>
204 154 CsgUnionOrIntersectionOp(TreesT& trees, TagT tag)
205 154 {
206
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 77 times.
 346 for (auto* tree : trees) {
207
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 192 if (tree) {
208
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 192 mTreesToMerge.emplace_back(*tree, tag);
209 }
210 }
211 154 }
212
213 /// @brief Constructor to accept a vector of TreeToMerge objects, primarily
214 /// used when mixing const/non-const trees.
215 /// @note Union/intersection order is preserved.
216 4 explicit CsgUnionOrIntersectionOp(const std::vector<TreeToMerge<TreeT>>& trees)
217
8/16
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 1 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 1 times.
✗ Branch 23 not taken.
 4 : mTreesToMerge(trees) { }
218
219 /// @brief Constructor to accept a deque of TreeToMerge objects, primarily
220 /// used when mixing const/non-const trees.
221 /// @note Union/intersection order is preserved.
222 ✗ explicit CsgUnionOrIntersectionOp(const std::deque<TreeToMerge<TreeT>>& trees)
223 ✗ : mTreesToMerge(trees.cbegin(), trees.cend()) { }
224
225 /// @brief Return true if no trees being merged
226 ✗ bool empty() const { return mTreesToMerge.empty(); }
227
228 /// @brief Return the number of trees being merged
229 ✗ size_t size() const { return mTreesToMerge.size(); }
230
231 // Processes the root node. Required by the NodeManager
232 bool operator()(RootT& root, size_t idx) const;
233
234 // Processes the internal nodes. Required by the NodeManager
235 template<typename NodeT>
236 bool operator()(NodeT& node, size_t idx) const;
237
238 // Processes the leaf nodes. Required by the NodeManager
239 bool operator()(LeafT& leaf, size_t idx) const;
240
241 private:
242 // on processing the root node, the background value is stored, retrieve it
243 // and check that the root node has already been processed
244 const ValueT& background() const;
245
246 mutable std::vector<TreeToMerge<TreeT>> mTreesToMerge;
247 mutable const ValueT* mBackground = nullptr;
248 }; // struct CsgUnionOrIntersectionOp
249
250
251 template <typename TreeT>
252 using CsgUnionOp = CsgUnionOrIntersectionOp<TreeT, /*Union=*/true>;
253
254 template <typename TreeT>
255 using CsgIntersectionOp = CsgUnionOrIntersectionOp<TreeT, /*Union=*/false>;
256
257
258 /// @brief DynamicNodeManager operator to merge two trees using a CSG difference.
259 /// @note This class modifies the topology of the tree so is designed to be used
260 /// from DynamicNodeManager::foreachTopDown().
261 template<typename TreeT>
262
22/44
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 1 times.
✗ Branch 20 not taken.
✓ Branch 24 taken 1 times.
✗ Branch 25 not taken.
✓ Branch 27 taken 1 times.
✗ Branch 28 not taken.
✓ Branch 30 taken 1 times.
✗ Branch 31 not taken.
✓ Branch 33 taken 1 times.
✗ Branch 34 not taken.
✓ Branch 36 taken 1 times.
✗ Branch 37 not taken.
✓ Branch 39 taken 1 times.
✗ Branch 40 not taken.
✓ Branch 42 taken 1 times.
✗ Branch 43 not taken.
✓ Branch 45 taken 1 times.
✗ Branch 46 not taken.
✓ Branch 48 taken 1 times.
✗ Branch 49 not taken.
✓ Branch 51 taken 1 times.
✗ Branch 52 not taken.
✓ Branch 56 taken 1 times.
✗ Branch 57 not taken.
✓ Branch 59 taken 1 times.
✗ Branch 60 not taken.
✓ Branch 62 taken 1 times.
✗ Branch 63 not taken.
✓ Branch 67 taken 1 times.
✗ Branch 68 not taken.
✓ Branch 70 taken 1 times.
✗ Branch 71 not taken.
✓ Branch 73 taken 1 times.
✗ Branch 74 not taken.
✓ Branch 76 taken 1 times.
✗ Branch 77 not taken.
✓ Branch 79 taken 1 times.
✗ Branch 80 not taken.
 34 struct CsgDifferenceOp
263 {
264 using ValueT = typename TreeT::ValueType;
265 using RootT = typename TreeT::RootNodeType;
266 using LeafT = typename TreeT::LeafNodeType;
267
268 /// @brief Convenience constructor to CSG difference a single non-const
269 /// tree from another. This constructor takes a Steal or DeepCopy tag
270 /// dispatch class.
271 template <typename TagT>
272
22/44
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 1 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 1 times.
✗ Branch 23 not taken.
✓ Branch 25 taken 1 times.
✗ Branch 26 not taken.
✓ Branch 28 taken 1 times.
✗ Branch 29 not taken.
✓ Branch 31 taken 1 times.
✗ Branch 32 not taken.
✓ Branch 34 taken 1 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 1 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 1 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 1 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 1 times.
✗ Branch 47 not taken.
✓ Branch 49 taken 1 times.
✗ Branch 50 not taken.
✓ Branch 52 taken 1 times.
✗ Branch 53 not taken.
✓ Branch 55 taken 1 times.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✓ Branch 61 taken 1 times.
✗ Branch 62 not taken.
✓ Branch 64 taken 1 times.
✗ Branch 65 not taken.
 26 CsgDifferenceOp(TreeT& tree, TagT tag) : mTree(tree, tag) { }
273 /// @brief Convenience constructor to CSG difference a single const
274 /// tree from another. This constructor requires an explicit DeepCopy tag
275 /// dispatch class.
276
8/16
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 1 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 1 times.
✗ Branch 23 not taken.
 4 CsgDifferenceOp(const TreeT& tree, DeepCopy tag) : mTree(tree, tag) { }
277
278 /// @brief Constructor to CSG difference the tree in a TreeToMerge object
279 /// from another.
280
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 2 explicit CsgDifferenceOp(TreeToMerge<TreeT>& tree) : mTree(tree) { }
281
282 /// @brief Return the number of trees being merged (only ever 1)
283 ✗ size_t size() const { return 1; }
284
285 // Processes the root node. Required by the NodeManager
286 bool operator()(RootT& root, size_t idx) const;
287
288 // Processes the internal nodes. Required by the NodeManager
289 template<typename NodeT>
290 bool operator()(NodeT& node, size_t idx) const;
291
292 // Processes the leaf nodes. Required by the NodeManager
293 bool operator()(LeafT& leaf, size_t idx) const;
294
295 private:
296 // on processing the root node, the background values are stored, retrieve them
297 // and check that the root nodes have already been processed
298 const ValueT& background() const;
299 const ValueT& otherBackground() const;
300
301 // note that this vector is copied in NodeTransformer every time a foreach call is made,
302 // however in typical use cases this cost will be dwarfed by the actual merge algorithm
303 mutable TreeToMerge<TreeT> mTree;
304 mutable const ValueT* mBackground = nullptr;
305 mutable const ValueT* mOtherBackground = nullptr;
306 }; // struct CsgDifferenceOp
307
308
309 /// @brief DynamicNodeManager operator to merge trees using a sum operation.
310 /// @note This class modifies the topology of the tree so is designed to be used
311 /// from DynamicNodeManager::foreachTopDown().
312 template<typename TreeT>
313
9/18
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 1 times.
✗ Branch 22 not taken.
✓ Branch 24 taken 1 times.
✗ Branch 25 not taken.
✓ Branch 28 taken 1 times.
✗ Branch 29 not taken.
✓ Branch 41 taken 1 times.
✗ Branch 42 not taken.
✓ Branch 62 taken 1 times.
✗ Branch 63 not taken.
 29 struct SumMergeOp
314 {
315 using ValueT = typename TreeT::ValueType;
316 using RootT = typename TreeT::RootNodeType;
317 using LeafT = typename TreeT::LeafNodeType;
318
319 /// @brief Convenience constructor to sum a single non-const tree with another.
320 /// This constructor takes a Steal or DeepCopy tag dispatch class.
321 template <typename TagT>
322
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 38 SumMergeOp(TreeT& tree, TagT tag) { mTreesToMerge.emplace_back(tree, tag); }
323
324 /// @brief Convenience constructor to sum a single const tree with another.
325 /// This constructor requires a DeepCopy tag dispatch class.
326 ✗ SumMergeOp(const TreeT& tree, DeepCopy tag) { mTreesToMerge.emplace_back(tree, tag); }
327
328 /// @brief Constructor to sum a container of multiple const or non-const tree pointers.
329 /// A Steal tag requires a container of non-const trees, a DeepCopy tag will accept
330 /// either const or non-const trees.
331 template <typename TreesT, typename TagT>
332 12 SumMergeOp(TreesT& trees, TagT tag)
333 12 {
334
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 36 for (auto* tree : trees) {
335
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 if (tree) {
336
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 mTreesToMerge.emplace_back(*tree, tag);
337 }
338 }
339 12 }
340
341 /// @brief Constructor to accept a vector of TreeToMerge objects, primarily
342 /// used when mixing const/non-const trees.
343 /// @note Sum order is preserved.
344 2 explicit SumMergeOp(const std::vector<TreeToMerge<TreeT>>& trees)
345
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 2 : mTreesToMerge(trees) { }
346
347 /// @brief Constructor to accept a deque of TreeToMerge objects, primarily
348 /// used when mixing const/non-const trees.
349 /// @note Sum order is preserved.
350 ✗ explicit SumMergeOp(const std::deque<TreeToMerge<TreeT>>& trees)
351 ✗ : mTreesToMerge(trees.cbegin(), trees.cend()) { }
352
353 /// @brief Return true if no trees being merged
354 ✗ bool empty() const { return mTreesToMerge.empty(); }
355
356 /// @brief Return the number of trees being merged
357 ✗ size_t size() const { return mTreesToMerge.size(); }
358
359 // Processes the root node. Required by the NodeManager
360 bool operator()(RootT& root, size_t idx) const;
361
362 // Processes the internal nodes. Required by the NodeManager
363 template<typename NodeT>
364 bool operator()(NodeT& node, size_t idx) const;
365
366 // Processes the leaf nodes. Required by the NodeManager
367 bool operator()(LeafT& leaf, size_t idx) const;
368
369 private:
370 // on processing the root node, the background value is stored, retrieve it
371 // and check that the root node has already been processed
372 const ValueT& background() const;
373
374 mutable std::vector<TreeToMerge<TreeT>> mTreesToMerge;
375 mutable const ValueT* mBackground = nullptr;
376 }; // struct SumMergeOp
377
378
379 ////////////////////////////////////////
380
381
382 template<typename TreeT>
383 60 void TreeToMerge<TreeT>::initializeMask()
384 {
385
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 60 if (mSteal) return;
386 60 mMaskTree.ptr.reset(new MaskTreeType);
387
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 MaskUnionOp op(*mTree);
388 60 tree::DynamicNodeManager<MaskTreeType, MaskTreeType::RootNodeType::LEVEL-1> manager(*this->mask());
389
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 manager.foreachTopDown(op);
390 }
391
392 template<typename TreeT>
393 18 bool TreeToMerge<TreeT>::hasMask() const
394 {
395 18 return bool(mMaskTree.ptr);
396 }
397
398 template<typename TreeT>
399
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 6 void TreeToMerge<TreeT>::reset(typename TreeType::Ptr treePtr, Steal)
400 {
401
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 6 if (!treePtr) {
402
2/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 8 OPENVDB_THROW(RuntimeError, "Cannot reset with empty Tree shared pointer.");
403 }
404 4 mSteal = true;
405 mTreePtr = treePtr;
406 4 mTree = mTreePtr.get();
407 }
408
409 template<typename TreeT>
410 const typename TreeToMerge<TreeT>::RootNodeType*
411 17870 TreeToMerge<TreeT>::rootPtr() const
412 {
413 17870 return &mTree->root();
414 }
415
416 template<typename TreeT>
417 template<typename NodeT>
418 const NodeT*
419 27004 TreeToMerge<TreeT>::probeConstNode(const Coord& ijk) const
420 {
421 // test mutable mask first, node may have already been pruned
422
4/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 13489 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 2 times.
 27030 if (!mSteal && !this->mask()->isValueOn(ijk)) return nullptr;
423 27312 return mTree->template probeConstNode<NodeT>(ijk);
424 }
425
426 template<typename TreeT>
427 template<typename NodeT>
428 std::unique_ptr<NodeT>
429 18048 TreeToMerge<TreeT>::stealOrDeepCopyNode(const Coord& ijk)
430 {
431
2/2
✓ Branch 0 taken 9018 times.
✓ Branch 1 taken 6 times.
 18048 if (mSteal) {
432 18036 TreeType* tree = const_cast<TreeType*>(mTree);
433 return std::unique_ptr<NodeT>(
434 tree->root().template stealNode<NodeT>(ijk, mTree->root().background(), false)
435 18036 );
436 } else {
437 12 auto* child = this->probeConstNode<NodeT>(ijk);
438
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 12 if (child) {
439
1/3
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
 12 assert(this->hasMask());
440 24 auto result = std::make_unique<NodeT>(*child);
441 // prune mask tree
442
1/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 24 this->mask()->addTile(NodeT::LEVEL, ijk, false, false);
443 return result;
444 }
445 }
446 return std::unique_ptr<NodeT>();
447 }
448
449 template<typename TreeT>
450 template<typename NodeT>
451 void
452 6954 TreeToMerge<TreeT>::addTile(const Coord& ijk, const ValueType& value, bool active)
453 {
454 // ignore leaf node tiles (values)
455 if (NodeT::LEVEL == 0) return;
456
457
2/2
✓ Branch 0 taken 3475 times.
✓ Branch 1 taken 2 times.
 6954 if (mSteal) {
458 6950 TreeType* tree = const_cast<TreeType*>(mTree);
459 auto* node = tree->template probeNode<NodeT>(ijk);
460
1/2
✓ Branch 0 taken 3456 times.
✗ Branch 1 not taken.
 6912 if (node) {
461 const Index pos = NodeT::coordToOffset(ijk);
462 6918 node->addTile(pos, value, active);
463 }
464 } else {
465 4 auto* node = mTree->template probeConstNode<NodeT>(ijk);
466 // prune mask tree
467 ✗ if (node) {
468
1/3
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
 2 assert(this->hasMask());
469 2 this->mask()->addTile(NodeT::LEVEL, ijk, false, false);
470 }
471 }
472 }
473
474
475 ////////////////////////////////////////
476
477
478 template <typename TreeT>
479 60 bool TreeToMerge<TreeT>::MaskUnionOp::operator()(RootT& root, size_t /*idx*/) const
480 {
481 using ChildT = typename RootT::ChildNodeType;
482
483 60 const Index count = mTree.root().childCount();
484
485 120 std::vector<std::unique_ptr<ChildT>> children(count);
486
487 // allocate new root children
488
489
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 60 tbb::parallel_for(
490 tbb::blocked_range<Index>(0, count),
491 8 [&](tbb::blocked_range<Index>& range)
492 {
493
2/18
✗ 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 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 8 times.
✓ Branch 13 taken 8 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 16 for (Index i = range.begin(); i < range.end(); i++) {
494 16 children[i] = std::make_unique<ChildT>(Coord::max(), true, true);
495 }
496 }
497 );
498
499 // apply origins and add root children to new root node
500
501 size_t i = 0;
502
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 30 times.
 136 for (auto iter = mTree.root().cbeginChildOn(); iter; ++iter) {
503 children[i]->setOrigin(iter->origin());
504
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 root.addChild(children[i].release());
505 16 i++;
506 }
507
508 60 return true;
509 }
510
511 template <typename TreeT>
512 template <typename NodeT>
513 16 bool TreeToMerge<TreeT>::MaskUnionOp::operator()(NodeT& node, size_t /*idx*/) const
514 {
515 using ChildT = typename NodeT::ChildNodeType;
516
517 ✗ const auto* otherNode = mTree.template probeConstNode<NodeT>(node.origin());
518 ✗ if (!otherNode) return false;
519
520 // this mask tree stores active tiles in place of leaf nodes for compactness
521
522 if (NodeT::LEVEL == 1) {
523 ✗ for (auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
524 ✗ node.addTile(iter.pos(), true, true);
525 }
526 } else {
527 ✗ for (auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
528 ✗ auto* child = new ChildT(iter->origin(), true, true);
529 ✗ node.addChild(child);
530 }
531 }
532
533 ✗ return true;
534 }
535
536
537 ////////////////////////////////////////
538
539 /// @cond OPENVDB_DOCS_INTERNAL
540
541 namespace merge_internal {
542
543
544 template <typename BufferT, typename ValueT>
545 struct UnallocatedBuffer
546 {
547
2/2
✓ Branch 0 taken 13126 times.
✓ Branch 1 taken 4 times.
 25806 static void allocateAndFill(BufferT& buffer, const ValueT& background)
548 {
549 if (buffer.empty()) {
550
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 8 if (!buffer.isOutOfCore()) {
551 buffer.allocate();
552 ✗ buffer.fill(background);
553 }
554 }
555 25806 }
556
557
1/2
✓ Branch 0 taken 2420 times.
✗ Branch 1 not taken.
 4828 static bool isPartiallyConstructed(const BufferT& buffer)
558 {
559
1/2
✓ Branch 0 taken 2420 times.
✗ Branch 1 not taken.
 4828 return !buffer.isOutOfCore() && buffer.empty();
560 }
561 }; // struct AllocateAndFillBuffer
562
563 template <typename BufferT>
564 struct UnallocatedBuffer<BufferT, bool>
565 {
566 // do nothing for bool buffers as they cannot be unallocated
567 static void allocateAndFill(BufferT&, const bool&) { }
568 static bool isPartiallyConstructed(const BufferT&) { return false; }
569 }; // struct AllocateAndFillBuffer
570
571
572 // a convenience class that combines nested parallelism with the depth-visit
573 // node visitor which can result in increased performance with large sub-trees
574 template <Index LEVEL>
575 struct Dispatch
576 {
577 template <typename NodeT, typename OpT>
578
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
 16 static void run(NodeT& node, OpT& op)
579 {
580 using ChildT = typename NodeT::ChildNodeType;
581
582 // use nested parallelism if there is more than one child
583
584 Index32 childCount = node.childCount();
585
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
 16 if (childCount > 0) {
586 10 op(node, size_t(0));
587
588 // build linear list of child pointers
589 std::vector<ChildT*> children;
590
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 children.reserve(childCount);
591
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 20 for (auto iter = node.beginChildOn(); iter; ++iter) {
592
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 children.push_back(&(*iter));
593 }
594
595 // parallelize across children
596
2/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 10 tbb::parallel_for(
597 tbb::blocked_range<Index32>(0, childCount),
598 5 [&](tbb::blocked_range<Index32>& range) {
599
6/18
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 3 times.
✓ Branch 13 taken 3 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 1 times.
✓ Branch 17 taken 1 times.
 10 for (Index32 n = range.begin(); n < range.end(); n++) {
600 5 DepthFirstNodeVisitor<ChildT>::visit(*children[n], op);
601 }
602 }
603 );
604 } else {
605 6 DepthFirstNodeVisitor<NodeT>::visit(node, op);
606 }
607 }
608 }; // struct Dispatch
609
610 // when LEVEL = 0, do not attempt nested parallelism
611 template <>
612 struct Dispatch<0>
613 {
614 template <typename NodeT, typename OpT>
615 static void run(NodeT& node, OpT& op)
616 {
617 DepthFirstNodeVisitor<NodeT>::visit(node, op);
618 }
619 };
620
621
622 // an DynamicNodeManager operator to add a value and modify active state
623 // for every tile and voxel in a given subtree
624 template <typename TreeT>
625 struct ApplyTileToNodeOp
626 {
627 using LeafT = typename TreeT::LeafNodeType;
628 using ValueT = typename TreeT::ValueType;
629
630 8 ApplyTileToNodeOp(const ValueT& value, const bool active):
631
0/14
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 8 mValue(value), mActive(active) { }
632
633 template <typename NodeT>
634 26 void operator()(NodeT& node, size_t) const
635 {
636 // TODO: Need to add an InternalNode::setValue(Index offset, ...) to
637 // avoid the cost of using a value iterator or coordToOffset() in the case
638 // where node.isChildMaskOff() is true
639
640
2/2
✓ Branch 0 taken 282614 times.
✓ Branch 1 taken 13 times.
 565254 for (auto iter = node.beginValueAll(); iter; ++iter) {
641 565228 iter.setValue(mValue + *iter);
642 }
643
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 26 if (mActive) node.setValuesOn();
644 }
645
646
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 10 void operator()(LeafT& leaf, size_t) const
647 {
648 8 auto* data = leaf.buffer().data();
649
650
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 8 if (mValue != zeroVal<ValueT>()) {
651
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 3 times.
 3078 for (Index i = 0; i < LeafT::SIZE; ++i) {
652 3072 data[i] += mValue;
653 }
654 }
655
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 10 if (mActive) leaf.setValuesOn();
656 }
657
658 template <typename NodeT>
659 void run(NodeT& node)
660 {
661
3/18
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✓ Branch 19 taken 6 times.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✓ Branch 25 taken 1 times.
✗ Branch 26 not taken.
 8 Dispatch<NodeT::LEVEL>::run(node, *this);
662 8 }
663
664 private:
665 ValueT mValue;
666 bool mActive;
667 }; // struct ApplyTileToNodeOp
668
669
670 } // namespace merge_internal
671
672
673 /// @endcond
674
675 ////////////////////////////////////////
676
677
678 template <typename TreeT, bool Union>
679
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 2 times.
 229 bool CsgUnionOrIntersectionOp<TreeT, Union>::operator()(RootT& root, size_t) const
680 {
681 const bool Intersect = !Union;
682
683
2/2
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 2 times.
 229 if (this->empty()) return false;
684
685 // store the background value
686
1/2
✓ Branch 0 taken 115 times.
✗ Branch 1 not taken.
 225 if (!mBackground) mBackground = &root.background();
687
688 // does the key exist in the root node?
689 auto keyExistsInRoot = [&](const Coord& key) -> bool
690 {
691 96 return root.getValueDepth(key) > -1;
692 };
693
694 // does the key exist in all merge tree root nodes?
695 132 auto keyExistsInAllTrees = [&](const Coord& key) -> bool
696 {
697
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 49 times.
✓ Branch 3 taken 32 times.
 81 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
698 49 const auto* mergeRoot = mergeTree.rootPtr();
699
1/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 49 times.
✗ Branch 3 not taken.
 55 if (!mergeRoot) return false;
700
2/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 4 taken 43 times.
✓ Branch 5 taken 6 times.
 49 if (mergeRoot->getValueDepth(key) == -1) return false;
701 }
702 32 return true;
703 };
704
705 // delete any background tiles
706 225 root.eraseBackgroundTiles();
707
708 // for intersection, delete any root node keys that are not present in all trees
709 if (Intersect) {
710 // find all tile coordinates to delete
711 std::vector<Coord> toDelete;
712
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 47 times.
 226 for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
713 38 const Coord& key = valueIter.getCoord();
714
4/6
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 18 times.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 38 if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
715 }
716 // find all child coordinates to delete
717
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 47 times.
 226 for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
718 38 const Coord& key = childIter.getCoord();
719
4/6
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
✓ Branch 4 taken 14 times.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 38 if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
720 }
721 // only mechanism to delete elements in root node is to delete background tiles,
722 // so insert background tiles (which will replace any child nodes) and then delete
723
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 47 times.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 106 for (Coord& key : toDelete) root.addTile(key, *mBackground, false);
724
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 94 root.eraseBackgroundTiles();
725 }
726
727 // find all tile values in this root and track inside/outside and active state
728 // note that level sets should never contain active tiles, but we handle them anyway
729
730 225 constexpr uint8_t ACTIVE_TILE = 0x1;
731 225 constexpr uint8_t INSIDE_TILE = 0x2;
732 225 constexpr uint8_t OUTSIDE_TILE = 0x4;
733
734 constexpr uint8_t INSIDE_STATE = Union ? INSIDE_TILE : OUTSIDE_TILE;
735 constexpr uint8_t OUTSIDE_STATE = Union ? OUTSIDE_TILE : INSIDE_TILE;
736
737 225 const ValueT insideBackground = Union ? -this->background() : this->background();
738
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 39 times.
 225 const ValueT outsideBackground = -insideBackground;
739
740 auto getTileFlag = [&](auto& valueIter) -> uint8_t
741 {
742 uint8_t flag(0);
743 const ValueT& value = valueIter.getValue();
744
4/6
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 94 if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
745
3/6
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
 54 else if (value > zeroVal<ValueT>()) flag |= OUTSIDE_TILE;
746 18 if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
747 return flag;
748 };
749
750 std::unordered_map<Coord, /*flags*/uint8_t> tiles;
751
752
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 39 times.
 225 if (root.getTableSize() > 0) {
753
2/2
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 76 times.
 350 for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
754
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 25 times.
 56 const Coord& key = valueIter.getCoord();
755 56 tiles.insert({key, getTileFlag(valueIter)});
756 }
757 }
758
759 // find all tiles values in other roots and replace outside tiles with inside tiles
760
761
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 115 times.
 476 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
762
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 251 const auto* mergeRoot = mergeTree.rootPtr();
763
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 251 if (!mergeRoot) continue;
764
2/2
✓ Branch 1 taken 60 times.
✓ Branch 2 taken 128 times.
 622 for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
765 120 const Coord& key = valueIter.getCoord();
766
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 32 times.
 120 auto it = tiles.find(key);
767
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 32 times.
 120 if (it == tiles.end()) {
768 // if no tile with this key, insert it
769 56 tiles.insert({key, getTileFlag(valueIter)});
770 } else {
771 // replace an outside tile with an inside tile
772 64 const uint8_t flag = it->second;
773
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 13 times.
 64 if (flag & OUTSIDE_STATE) {
774 const uint8_t newFlag = getTileFlag(valueIter);
775
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 5 times.
 38 if (newFlag & INSIDE_STATE) {
776 28 it->second = newFlag;
777 }
778 }
779 }
780 }
781 }
782
783 // insert all inside tiles
784
785
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 115 times.
 337 for (auto it : tiles) {
786 112 const uint8_t flag = it.second;
787
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 18 times.
 112 if (flag & INSIDE_STATE) {
788 const Coord& key = it.first;
789 76 const bool state = flag & ACTIVE_TILE;
790 // for intersection, only add the tile if the key already exists in the tree
791
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 3 times.
 34 if (Union || keyExistsInRoot(key)) {
792
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 70 root.addTile(key, insideBackground, state);
793 }
794 }
795 }
796
797 std::unordered_set<Coord> children;
798
799
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 33 times.
 225 if (root.getTableSize() > 0) {
800
2/2
✓ Branch 1 taken 108 times.
✓ Branch 2 taken 82 times.
 521 for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
801
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 203 const Coord& key = childIter.getCoord();
802 children.insert(key);
803 }
804 }
805
806 bool continueRecurse = false;
807
808 // find all children in other roots and insert them if a child or tile with this key
809 // does not already exist or if the child will replace an outside tile
810
811
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 115 times.
 476 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
812
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 251 const auto* mergeRoot = mergeTree.rootPtr();
813
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 128 times.
 251 if (!mergeRoot) continue;
814
2/2
✓ Branch 1 taken 114 times.
✓ Branch 2 taken 128 times.
 717 for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
815 215 const Coord& key = childIter.getCoord();
816
817 // for intersection, only add child nodes if the key already exists in the tree
818
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 16 times.
 188 if (Intersect && !keyExistsInRoot(key)) continue;
819
820 // if child already exists, merge recursion will need to continue to resolve conflict
821
2/2
✓ Branch 0 taken 67 times.
✓ Branch 1 taken 37 times.
 195 if (children.count(key)) {
822 continueRecurse = true;
823 128 continue;
824 }
825
826 // if an inside tile exists, do nothing
827
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 27 times.
 67 auto it = tiles.find(key);
828
4/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 6 times.
 67 if (it != tiles.end() && it->second == INSIDE_STATE) continue;
829
830
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 118 auto childPtr = mergeTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
831
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 59 childPtr->resetBackground(mergeRoot->background(), root.background());
832
2/4
✓ Branch 0 taken 33 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 33 times.
✗ Branch 4 not taken.
 59 if (childPtr) root.addChild(childPtr.release());
833
834 children.insert(key);
835 }
836 }
837
838 // insert all outside tiles that don't replace an inside tile or a child node
839
840
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 115 times.
 337 for (auto it : tiles) {
841 112 const uint8_t flag = it.second;
842
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 38 times.
 112 if (flag & OUTSIDE_STATE) {
843 const Coord& key = it.first;
844
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 10 times.
 36 if (!children.count(key)) {
845 16 const bool state = flag & ACTIVE_TILE;
846 // for intersection, only add the tile if the key already exists in the tree
847
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 10 if (Union || keyExistsInRoot(key)) {
848
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 root.addTile(key, outsideBackground, state);
849 }
850 }
851 }
852 }
853
854 // finish by removing any background tiles
855
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 225 root.eraseBackgroundTiles();
856
857 return continueRecurse;
858 }
859
860 template<typename TreeT, bool Union>
861 template<typename NodeT>
862
1/2
✓ Branch 0 taken 288 times.
✗ Branch 1 not taken.
 576 bool CsgUnionOrIntersectionOp<TreeT, Union>::operator()(NodeT& node, size_t) const
863 {
864 using NonConstNodeT = typename std::remove_const<NodeT>::type;
865
866
1/2
✓ Branch 0 taken 288 times.
✗ Branch 1 not taken.
 576 if (this->empty()) return false;
867
868 576 const ValueT insideBackground = Union ? -this->background() : this->background();
869 576 const ValueT outsideBackground = -insideBackground;
870
871 using NodeMaskT = typename NodeT::NodeMaskType;
872
873 // store temporary masks to track inside and outside tile states
874 NodeMaskT validTile;
875 NodeMaskT invalidTile;
876
877 auto isValid = [](const ValueT& value)
878 {
879 11050192 return Union ? value < zeroVal<ValueT>() : value > zeroVal<ValueT>();
880 };
881
882 auto isInvalid = [](const ValueT& value)
883 {
884 6534496 return Union ? value > zeroVal<ValueT>() : value < zeroVal<ValueT>();
885 };
886
887
2/2
✓ Branch 0 taken 4261074 times.
✓ Branch 1 taken 288 times.
 8522724 for (auto iter = node.cbeginValueAll(); iter; ++iter) {
888
2/2
✓ Branch 0 taken 314186 times.
✓ Branch 1 taken 3946888 times.
 8522148 if (isValid(iter.getValue())) {
889 628372 validTile.setOn(iter.pos());
890
1/2
✓ Branch 0 taken 3946888 times.
✗ Branch 1 not taken.
 7893776 } else if (isInvalid(iter.getValue())) {
891 7893776 invalidTile.setOn(iter.pos());
892 }
893 }
894
895 bool continueRecurse = false;
896
897
2/2
✓ Branch 0 taken 292 times.
✓ Branch 1 taken 288 times.
 1160 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
898
899 584 auto* mergeNode = mergeTree.template probeConstNode<NonConstNodeT>(node.origin());
900
901
2/2
✓ Branch 0 taken 159 times.
✓ Branch 1 taken 133 times.
 584 if (!mergeNode) continue;
902
903 // iterate over all tiles
904
905
2/2
✓ Branch 0 taken 2451822 times.
✓ Branch 1 taken 133 times.
 4903910 for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
906 Index pos = iter.pos();
907 // source node contains an inside tile, so ignore
908
2/2
✓ Branch 1 taken 287294 times.
✓ Branch 2 taken 2164528 times.
 4903644 if (validTile.isOn(pos)) continue;
909 // this node contains an inside tile, so turn into an inside tile
910
2/2
✓ Branch 0 taken 210208 times.
✓ Branch 1 taken 1954320 times.
 4329056 if (isValid(iter.getValue())) {
911 420416 node.addTile(pos, insideBackground, iter.isValueOn());
912 420416 validTile.setOn(pos);
913 }
914 }
915
916 // iterate over all child nodes
917
918
2/2
✓ Branch 0 taken 13970 times.
✓ Branch 1 taken 133 times.
 28206 for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
919 Index pos = iter.pos();
920 27940 const Coord& ijk = iter.getCoord();
921 // source node contains an inside tile, so ensure other node has no child
922
2/2
✓ Branch 1 taken 3458 times.
✓ Branch 2 taken 10512 times.
 27940 if (validTile.isOn(pos)) {
923 6916 mergeTree.template addTile<NonConstNodeT>(ijk, outsideBackground, false);
924
2/2
✓ Branch 1 taken 8641 times.
✓ Branch 2 taken 1871 times.
 21024 } else if (invalidTile.isOn(pos)) {
925 34564 auto childPtr = mergeTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
926
1/2
✓ Branch 0 taken 8641 times.
✗ Branch 1 not taken.
 17282 if (childPtr) {
927
4/7
✓ Branch 1 taken 8341 times.
✓ Branch 2 taken 300 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8341 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8341 times.
✗ Branch 8 not taken.
 17282 childPtr->resetBackground(mergeTree.rootPtr()->background(), this->background());
928 17282 node.addChild(childPtr.release());
929 }
930 17282 invalidTile.setOff(pos);
931 } else {
932 // if both source and target are child nodes, merge recursion needs to continue
933 // along this branch to resolve the conflict
934 continueRecurse = true;
935 }
936 }
937 }
938
939 return continueRecurse;
940 }
941
942 template <typename TreeT, bool Union>
943
1/2
✓ Branch 0 taken 11307 times.
✗ Branch 1 not taken.
 22160 bool CsgUnionOrIntersectionOp<TreeT, Union>::operator()(LeafT& leaf, size_t) const
944 {
945 using LeafT = typename TreeT::LeafNodeType;
946 using ValueT = typename LeafT::ValueType;
947 using BufferT = typename LeafT::Buffer;
948
949
1/2
✓ Branch 0 taken 11307 times.
✗ Branch 1 not taken.
 22160 if (this->empty()) return false;
950
951 22160 const ValueT background = Union ? this->background() : -this->background();
952
953 // if buffer is not out-of-core and empty, leaf node must have only been
954 // partially constructed, so allocate and fill with background value
955
956 22160 merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
957 leaf.buffer(), background);
958
959
2/2
✓ Branch 0 taken 11309 times.
✓ Branch 1 taken 11307 times.
 44324 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
960 22164 const LeafT* mergeLeaf = mergeTree.template probeConstNode<LeafT>(leaf.origin());
961
2/2
✓ Branch 0 taken 9504 times.
✓ Branch 1 taken 1805 times.
 22164 if (!mergeLeaf) continue;
962 // if buffer is not out-of-core yet empty, leaf node must have only been
963 // partially constructed, so skip merge
964
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1805 times.
 3598 if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
965 mergeLeaf->buffer())) {
966 ✗ continue;
967 }
968
969
2/2
✓ Branch 0 taken 924160 times.
✓ Branch 1 taken 1805 times.
 1845774 for (Index i = 0 ; i < LeafT::SIZE; i++) {
970 1842176 const ValueT& newValue = mergeLeaf->getValue(i);
971 1842176 const bool doMerge = Union ? newValue < leaf.getValue(i) : newValue > leaf.getValue(i);
972
2/2
✓ Branch 0 taken 339910 times.
✓ Branch 1 taken 584250 times.
 1842176 if (doMerge) {
973 678515 leaf.setValueOnly(i, newValue);
974 678515 leaf.setActiveState(i, mergeLeaf->isValueOn(i));
975 }
976 }
977 }
978
979 22160 return false;
980 }
981
982 template <typename TreeT, bool Union>
983 const typename CsgUnionOrIntersectionOp<TreeT, Union>::ValueT&
984 39917 CsgUnionOrIntersectionOp<TreeT, Union>::background() const
985 {
986 // this operator is only intended to be used with foreachTopDown()
987
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20351 times.
 39917 assert(mBackground);
988 39917 return *mBackground;
989 }
990
991
992 ////////////////////////////////////////
993
994
995 template <typename TreeT>
996 50 bool CsgDifferenceOp<TreeT>::operator()(RootT& root, size_t) const
997 {
998 // store the background values
999
1/2
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
 50 if (!mBackground) mBackground = &root.background();
1000
1/2
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
 50 if (!mOtherBackground) mOtherBackground = &mTree.rootPtr()->background();
1001
1002 // find all tile values in this root and track inside/outside and active state
1003 // note that level sets should never contain active tiles, but we handle them anyway
1004
1005 50 constexpr uint8_t ACTIVE_TILE = 0x1;
1006 50 constexpr uint8_t INSIDE_TILE = 0x2;
1007 constexpr uint8_t CHILD = 0x4;
1008
1009 auto getTileFlag = [&](auto& valueIter) -> uint8_t
1010 {
1011 uint8_t flag(0);
1012 const ValueT& value = valueIter.getValue();
1013 46 if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
1014 32 if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
1015 return flag;
1016 };
1017
1018 // delete any background tiles
1019 50 root.eraseBackgroundTiles();
1020
1021 std::unordered_map<Coord, /*flags*/uint8_t> flags;
1022
1023
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 2 times.
 50 if (root.getTableSize() > 0) {
1024
2/2
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 23 times.
 110 for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1025
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
 18 const Coord& key = valueIter.getCoord();
1026 const uint8_t flag = getTileFlag(valueIter);
1027
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
 18 if (flag & INSIDE_TILE) {
1028 10 flags.insert({key, getTileFlag(valueIter)});
1029 }
1030 }
1031
1032
2/2
✓ Branch 1 taken 44 times.
✓ Branch 2 taken 23 times.
 180 for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1033
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 88 const Coord& key = childIter.getCoord();
1034 88 flags.insert({key, CHILD});
1035 }
1036 }
1037
1038 bool continueRecurse = false;
1039
1040
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 50 const auto* mergeRoot = mTree.rootPtr();
1041
1042
1/2
✓ Branch 0 taken 25 times.
✗ Branch 1 not taken.
 50 if (mergeRoot) {
1043
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 25 times.
 128 for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1044
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 9 times.
 28 const Coord& key = valueIter.getCoord();
1045 const uint8_t flag = getTileFlag(valueIter);
1046
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 9 times.
 28 if (flag & INSIDE_TILE) {
1047
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 10 auto it = flags.find(key);
1048
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 10 if (it != flags.end()) {
1049 8 const bool state = flag & ACTIVE_TILE;
1050
2/5
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 8 root.addTile(key, this->background(), state);
1051 }
1052 }
1053 }
1054
1055
2/2
✓ Branch 1 taken 35 times.
✓ Branch 2 taken 25 times.
 170 for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1056 70 const Coord& key = childIter.getCoord();
1057
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 1 times.
 70 auto it = flags.find(key);
1058
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 1 times.
 70 if (it != flags.end()) {
1059 68 const uint8_t otherFlag = it->second;
1060
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 31 times.
 68 if (otherFlag & CHILD) {
1061 // if child already exists, merge recursion will need to continue to resolve conflict
1062 continueRecurse = true;
1063
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 6 } else if (otherFlag & INSIDE_TILE) {
1064
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 12 auto childPtr = mTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
1065
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 6 if (childPtr) {
1066
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 childPtr->resetBackground(this->otherBackground(), this->background());
1067
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 childPtr->negate();
1068
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 root.addChild(childPtr.release());
1069 }
1070 }
1071 }
1072 }
1073 }
1074
1075 // finish by removing any background tiles
1076
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 50 root.eraseBackgroundTiles();
1077
1078 50 return continueRecurse;
1079 }
1080
1081 template<typename TreeT>
1082 template<typename NodeT>
1083 144 bool CsgDifferenceOp<TreeT>::operator()(NodeT& node, size_t) const
1084 {
1085 using NonConstNodeT = typename std::remove_const<NodeT>::type;
1086
1087 using NodeMaskT = typename NodeT::NodeMaskType;
1088
1089 // store temporary mask to track inside tile state
1090
1091 NodeMaskT insideTile;
1092
2/2
✓ Branch 0 taken 1382749 times.
✓ Branch 1 taken 72 times.
 2765642 for (auto iter = node.cbeginValueAll(); iter; ++iter) {
1093
2/2
✓ Branch 0 taken 782 times.
✓ Branch 1 taken 1381967 times.
 2765498 if (iter.getValue() < zeroVal<ValueT>()) {
1094 1564 insideTile.setOn(iter.pos());
1095 }
1096 }
1097
1098 bool continueRecurse = false;
1099
1100 144 auto* mergeNode = mTree.template probeConstNode<NonConstNodeT>(node.origin());
1101
1102
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 7 times.
 144 if (!mergeNode) return continueRecurse;
1103
1104 // iterate over all tiles
1105
1106
2/2
✓ Branch 0 taken 1153767 times.
✓ Branch 1 taken 65 times.
 2307664 for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
1107 Index pos = iter.pos();
1108
2/2
✓ Branch 0 taken 233 times.
✓ Branch 1 taken 1153534 times.
 2307534 if (iter.getValue() < zeroVal<ValueT>()) {
1109
4/4
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 161 times.
✓ Branch 3 taken 64 times.
✓ Branch 4 taken 8 times.
 610 if (insideTile.isOn(pos) || node.isChildMaskOn(pos)) {
1110 450 node.addTile(pos, this->background(), iter.isValueOn());
1111 }
1112 }
1113 }
1114
1115 // iterate over all children
1116
1117
2/2
✓ Branch 0 taken 1305 times.
✓ Branch 1 taken 65 times.
 2740 for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
1118 Index pos = iter.pos();
1119 2610 const Coord& ijk = iter.getCoord();
1120
2/2
✓ Branch 1 taken 335 times.
✓ Branch 2 taken 970 times.
 2610 if (insideTile.isOn(pos)) {
1121 1340 auto childPtr = mTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
1122
1/2
✓ Branch 0 taken 335 times.
✗ Branch 1 not taken.
 670 if (childPtr) {
1123
3/6
✓ Branch 1 taken 335 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 335 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 335 times.
✗ Branch 8 not taken.
 670 childPtr->resetBackground(this->otherBackground(), this->background());
1124
1/2
✓ Branch 1 taken 335 times.
✗ Branch 2 not taken.
 670 childPtr->negate();
1125 670 node.addChild(childPtr.release());
1126 }
1127
2/2
✓ Branch 0 taken 645 times.
✓ Branch 1 taken 325 times.
 1940 } else if (node.isChildMaskOn(pos)) {
1128 // if both source and target are child nodes, merge recursion needs to continue
1129 // along this branch to resolve the conflict
1130 continueRecurse = true;
1131 }
1132 }
1133
1134 130 return continueRecurse;
1135 }
1136
1137 template <typename TreeT>
1138 3628 bool CsgDifferenceOp<TreeT>::operator()(LeafT& leaf, size_t) const
1139 {
1140 using LeafT = typename TreeT::LeafNodeType;
1141 using ValueT = typename LeafT::ValueType;
1142 using BufferT = typename LeafT::Buffer;
1143
1144 // if buffer is not out-of-core and empty, leaf node must have only been
1145 // partially constructed, so allocate and fill with background value
1146
1147 3628 merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
1148 leaf.buffer(), this->background());
1149
1150 3628 const LeafT* mergeLeaf = mTree.template probeConstNode<LeafT>(leaf.origin());
1151
2/2
✓ Branch 0 taken 611 times.
✓ Branch 1 taken 1203 times.
 3628 if (!mergeLeaf) return false;
1152
1153 // if buffer is not out-of-core yet empty, leaf node must have only been
1154 // partially constructed, so skip merge
1155
1156
1/2
✓ Branch 1 taken 611 times.
✗ Branch 2 not taken.
 1222 if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
1157 mergeLeaf->buffer())) {
1158 return false;
1159 }
1160
1161
2/2
✓ Branch 0 taken 312832 times.
✓ Branch 1 taken 611 times.
 626886 for (Index i = 0 ; i < LeafT::SIZE; i++) {
1162 625664 const ValueT& aValue = leaf.getValue(i);
1163 625664 ValueT bValue = math::negative(mergeLeaf->getValue(i));
1164
2/2
✓ Branch 0 taken 98767 times.
✓ Branch 1 taken 214065 times.
 625664 if (aValue < bValue) { // a = max(a, -b)
1165 197534 leaf.setValueOnly(i, bValue);
1166 197534 leaf.setActiveState(i, mergeLeaf->isValueOn(i));
1167 }
1168 }
1169
1170 return false;
1171 }
1172
1173 template <typename TreeT>
1174 const typename CsgDifferenceOp<TreeT>::ValueT&
1175 4762 CsgDifferenceOp<TreeT>::background() const
1176 {
1177 // this operator is only intended to be used with foreachTopDown()
1178
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2381 times.
 4762 assert(mBackground);
1179 4762 return *mBackground;
1180 }
1181
1182 template <typename TreeT>
1183 const typename CsgDifferenceOp<TreeT>::ValueT&
1184 676 CsgDifferenceOp<TreeT>::otherBackground() const
1185 {
1186 // this operator is only intended to be used with foreachTopDown()
1187
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 338 times.
 676 assert(mOtherBackground);
1188 676 return *mOtherBackground;
1189 }
1190
1191
1192 ////////////////////////////////////////
1193
1194
1195 template <typename TreeT>
1196
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 38 bool SumMergeOp<TreeT>::operator()(RootT& root, size_t) const
1197 {
1198 using ValueT = typename RootT::ValueType;
1199 using ChildT = typename RootT::ChildNodeType;
1200 using NonConstChildT = typename std::remove_const<ChildT>::type;
1201
1202
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 38 if (this->empty()) return false;
1203
1204 // store the background value
1205
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 38 if (!mBackground) mBackground = &root.background();
1206
1207 // does the key exist in the root node?
1208 auto keyExistsInRoot = [](const auto& rootToTest, const Coord& key) -> bool
1209 {
1210 50 return rootToTest.getValueDepth(key) > -1;
1211 };
1212
1213 constexpr uint8_t TILE = 0x1;
1214 constexpr uint8_t CHILD = 0x2;
1215 constexpr uint8_t TARGET_CHILD = 0x4; // child already exists in the target tree
1216
1217 std::unordered_map<Coord, /*flags*/uint8_t> children;
1218
1219 // find all tiles and child nodes in our root
1220
1221
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 3 times.
 38 if (root.getTableSize() > 0) {
1222
2/2
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 16 times.
 90 for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1223
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 26 const Coord& key = valueIter.getCoord();
1224 26 children.insert({key, TILE});
1225 }
1226
1227
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 16 times.
 88 for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1228
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 const Coord& key = childIter.getCoord();
1229 24 children.insert({key, CHILD | TARGET_CHILD});
1230 }
1231 }
1232
1233 // find all tiles and child nodes in other roots
1234
1235
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 19 times.
 80 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1236
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 42 const auto* mergeRoot = mergeTree.rootPtr();
1237
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 21 times.
 42 if (!mergeRoot) continue;
1238
1239
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 21 times.
 122 for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1240 38 const Coord& key = valueIter.getCoord();
1241
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 11 times.
 38 auto it = children.find(key);
1242
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 11 times.
 38 if (it == children.end()) {
1243 // if no element with this key, insert it
1244 16 children.insert({key, TILE});
1245 } else {
1246 // mark as tile
1247 22 it->second |= TILE;
1248 }
1249 }
1250
1251
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 21 times.
 116 for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1252 32 const Coord& key = childIter.getCoord();
1253
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 15 times.
 32 auto it = children.find(key);
1254
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 15 times.
 32 if (it == children.end()) {
1255 // if no element with this key, insert it
1256 2 children.insert({key, CHILD});
1257 } else {
1258 // mark as child
1259 30 it->second |= CHILD;
1260 }
1261 }
1262 }
1263
1264 // if any coords do not already exist in the root, insert an inactive background tile
1265
1266
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 19 times.
 106 for (const auto& it : children) {
1267
2/2
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 25 times.
 68 if (!keyExistsInRoot(root, it.first)) {
1268
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 18 root.addTile(it.first, root.background(), false);
1269 }
1270 }
1271
1272 // for each coord, merge each tile into the root until a child is found, then steal it
1273
1274
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 19 times.
 106 for (const auto& it : children) {
1275
1276 68 const Coord& key = it.first;
1277
1278 // do nothing if the target root already contains a child node,
1279 // merge recursion will need to continue to resolve conflict
1280
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 22 times.
 68 if (it.second & TARGET_CHILD) continue;
1281
1282 ValueT value;
1283
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 44 const bool active = root.probeValue(key, value);
1284
1285
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 14 times.
 78 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1286
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 50 const auto* mergeRoot = mergeTree.rootPtr();
1287
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 54 if (!mergeRoot) continue;
1288
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 23 times.
 50 if (!keyExistsInRoot(*mergeRoot, key)) continue;
1289
1290 // steal or deep-copy the first child node that is encountered,
1291 // then cease processing of this root node coord as merge recursion
1292 // will need to continue to resolve conflict
1293
1294 const auto* mergeNode = mergeRoot->template probeConstNode<ChildT>(key);
1295 if (mergeNode) {
1296
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 32 auto childPtr = mergeTree.template stealOrDeepCopyNode<ChildT>(key);
1297
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 16 childPtr->resetBackground(mergeRoot->background(), root.background());
1298
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 16 if (childPtr) {
1299 // apply tile value and active state to the sub-tree
1300 merge_internal::ApplyTileToNodeOp<TreeT> applyOp(value, active);
1301 applyOp.run(*childPtr);
1302
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 root.addChild(childPtr.release());
1303 }
1304 break;
1305 }
1306
1307 ValueT mergeValue;
1308
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 30 const bool mergeActive = mergeRoot->probeValue(key, mergeValue);
1309
1310
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 8 times.
 30 if (active || mergeActive) {
1311 14 value += mergeValue;
1312
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 14 root.addTile(key, value, true);
1313 } else {
1314 16 value += mergeValue;
1315
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 root.addTile(key, value, false);
1316 }
1317
1318 // reset tile value to zero to prevent it being merged twice
1319
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 30 mergeTree.template addTile<NonConstChildT>(key, zeroVal<ValueT>(), false);
1320 }
1321 }
1322
1323 return true;
1324 }
1325
1326 template<typename TreeT>
1327 template<typename NodeT>
1328 30 bool SumMergeOp<TreeT>::operator()(NodeT& node, size_t) const
1329 {
1330 using ChildT = typename NodeT::ChildNodeType;
1331 using NonConstNodeT = typename std::remove_const<NodeT>::type;
1332
1333 30 if (this->empty()) return false;
1334
1335 62 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1336 32 const auto* mergeRoot = mergeTree.rootPtr();
1337 32 if (!mergeRoot) continue;
1338
1339 11 const auto* mergeNode = mergeRoot->template probeConstNode<NonConstNodeT>(node.origin());
1340 11 if (mergeNode) {
1341 // merge node
1342
1343 311300 for (auto iter = node.beginValueAll(); iter; ++iter) {
1344 311287 if (mergeNode->isChildMaskOn(iter.pos())) {
1345 // steal child node
1346 ✗ auto childPtr = mergeTree.template stealOrDeepCopyNode<ChildT>(iter.getCoord());
1347 ✗ childPtr->resetBackground(mergeRoot->background(), this->background());
1348 ✗ if (childPtr) {
1349 // apply tile value and active state to the sub-tree
1350 ✗ merge_internal::ApplyTileToNodeOp<TreeT> applyOp(*iter, iter.isValueOn());
1351 applyOp.run(*childPtr);
1352 ✗ node.addChild(childPtr.release());
1353 }
1354 } else {
1355 ValueT mergeValue;
1356 311287 const bool mergeActive = mergeNode->probeValue(iter.getCoord(), mergeValue);
1357 311287 iter.setValue(*iter + mergeValue);
1358 311287 if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1359 }
1360 }
1361
1362 } else {
1363 // merge tile or background value
1364
1365 ValueT mergeValue;
1366 19 const bool mergeActive = mergeRoot->probeValue(node.origin(), mergeValue);
1367 421894 for (auto iter = node.beginValueAll(); iter; ++iter) {
1368 421875 iter.setValue(*iter + mergeValue);
1369 421875 if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1370 }
1371 }
1372 }
1373
1374 30 return true;
1375 }
1376
1377 template <typename TreeT>
1378
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 20 bool SumMergeOp<TreeT>::operator()(LeafT& leaf, size_t) const
1379 {
1380 using RootT = typename TreeT::RootNodeType;
1381 using RootChildT = typename RootT::ChildNodeType;
1382 using NonConstRootChildT = typename std::remove_const<RootChildT>::type;
1383 using LeafT = typename TreeT::LeafNodeType;
1384 using ValueT = typename LeafT::ValueType;
1385 using BufferT = typename LeafT::Buffer;
1386 using NonConstLeafT = typename std::remove_const<LeafT>::type;
1387
1388
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 20 if (this->empty()) return false;
1389
1390 const Coord& ijk = leaf.origin();
1391
1392 // if buffer is not out-of-core and empty, leaf node must have only been
1393 // partially constructed, so allocate and fill with background value
1394
1395 20 merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
1396 leaf.buffer(), this->background());
1397
1398 18 auto* data = leaf.buffer().data();
1399
1400
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 10 times.
 42 for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1401 22 const RootT* mergeRoot = mergeTree.rootPtr();
1402
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
 22 if (!mergeRoot) continue;
1403
1404 const RootChildT* mergeRootChild = mergeRoot->template probeConstNode<NonConstRootChildT>(ijk);
1405 10 const LeafT* mergeLeaf = mergeRootChild ?
1406 mergeRootChild->template probeConstNode<NonConstLeafT>(ijk) : nullptr;
1407
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
 20 if (mergeLeaf) {
1408 // merge leaf
1409
1410 // if buffer is not out-of-core yet empty, leaf node must have only been
1411 // partially constructed, so skip merge
1412
1413
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
 8 if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
1414 mergeLeaf->buffer())) {
1415 ✗ return false;
1416 }
1417
1418
2/2
✓ Branch 0 taken 2048 times.
✓ Branch 1 taken 4 times.
 4104 for (Index i = 0; i < LeafT::SIZE; ++i) {
1419 4096 data[i] += mergeLeaf->getValue(i);
1420 }
1421
1422 leaf.getValueMask() |= mergeLeaf->getValueMask();
1423 } else {
1424 // merge root tile or background value
1425
1426 ValueT mergeValue;
1427
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 14 bool mergeActive = mergeRootChild ?
1428 mergeRootChild->probeValue(ijk, mergeValue) : mergeRoot->probeValue(ijk, mergeValue);
1429
1430
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 12 if (mergeValue != zeroVal<ValueT>()) {
1431
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 3 times.
 3078 for (Index i = 0; i < LeafT::SIZE; ++i) {
1432 3072 data[i] += mergeValue;
1433 }
1434 }
1435
1436
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 14 if (mergeActive) leaf.setValuesOn();
1437 }
1438 }
1439
1440 20 return false;
1441 }
1442
1443 template <typename TreeT>
1444 const typename SumMergeOp<TreeT>::ValueT&
1445 10 SumMergeOp<TreeT>::background() const
1446 {
1447 // this operator is only intended to be used with foreachTopDown()
1448 10 assert(mBackground);
1449 10 return *mBackground;
1450 }
1451
1452
1453 ////////////////////////////////////////
1454
1455
1456 // Explicit Template Instantiation
1457
1458 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
1459
1460 #ifdef OPENVDB_INSTANTIATE_MERGE
1461 #include <openvdb/util/ExplicitInstantiation.h>
1462 #endif
1463
1464 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<MaskTree>;
1465 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<BoolTree>;
1466 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<FloatTree>;
1467 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<DoubleTree>;
1468 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<Int32Tree>;
1469 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<Int64Tree>;
1470 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<Vec3STree>;
1471 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<Vec3DTree>;
1472 OPENVDB_INSTANTIATE_STRUCT TreeToMerge<Vec3ITree>;
1473
1474 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<MaskTree>;
1475 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<BoolTree>;
1476 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<FloatTree>;
1477 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<DoubleTree>;
1478 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<Int32Tree>;
1479 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<Int64Tree>;
1480 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<Vec3STree>;
1481 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<Vec3DTree>;
1482 OPENVDB_INSTANTIATE_STRUCT SumMergeOp<Vec3ITree>;
1483
1484 OPENVDB_INSTANTIATE_STRUCT CsgUnionOrIntersectionOp<FloatTree, true>;
1485 OPENVDB_INSTANTIATE_STRUCT CsgUnionOrIntersectionOp<DoubleTree, true>;
1486
1487 OPENVDB_INSTANTIATE_STRUCT CsgUnionOrIntersectionOp<FloatTree, false>;
1488 OPENVDB_INSTANTIATE_STRUCT CsgUnionOrIntersectionOp<DoubleTree, false>;
1489
1490 OPENVDB_INSTANTIATE_STRUCT CsgDifferenceOp<FloatTree>;
1491 OPENVDB_INSTANTIATE_STRUCT CsgDifferenceOp<DoubleTree>;
1492
1493 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
1494
1495
1496 } // namespace tools
1497 } // namespace OPENVDB_VERSION_NAME
1498 } // namespace openvdb
1499
1500 #endif // OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
1501