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