OpenVDB  9.1.1
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>
19 #include <openvdb/openvdb.h>
20 
21 #include <memory>
22 #include <unordered_map>
23 #include <unordered_set>
24 
25 namespace openvdb {
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>
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.
57  : mTree(&tree), mSteal(true) { }
58  /// @brief Non-const shared pointer tree constructor for stealing data.
59  TreeToMerge(typename TreeType::Ptr treePtr, Steal)
60  : 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  TreeToMerge(const TreeType& tree, DeepCopy, bool initialize = true)
68  : mTree(&tree), mSteal(false)
69  {
70  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  TreeToMerge(TreeType& tree, DeepCopy tag, bool initialize = true)
79  : 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  TreeType* treeToSteal() { return mSteal ? const_cast<TreeType*>(mTree) : nullptr; }
88  /// @brief Return a pointer to the tree to be deep-copied.
89  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 {
159  using RootT = typename MaskT::RootNodeType;
160  using LeafT = typename MaskT::LeafNodeType;
161 
162  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>
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  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  CsgUnionOrIntersectionOp(TreesT& trees, TagT tag)
205  {
206  for (auto* tree : trees) {
207  if (tree) {
208  mTreesToMerge.emplace_back(*tree, tag);
209  }
210  }
211  }
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  explicit CsgUnionOrIntersectionOp(const std::vector<TreeToMerge<TreeT>>& trees)
217  : 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>
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  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  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  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>
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  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  SumMergeOp(TreesT& trees, TagT tag)
333  {
334  for (auto* tree : trees) {
335  if (tree) {
336  mTreesToMerge.emplace_back(*tree, tag);
337  }
338  }
339  }
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  explicit SumMergeOp(const std::vector<TreeToMerge<TreeT>>& trees)
345  : 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>
384 {
385  if (mSteal) return;
386  mMaskTree.ptr.reset(new MaskTreeType);
387  MaskUnionOp op(*mTree);
388  tree::DynamicNodeManager<MaskTreeType, MaskTreeType::RootNodeType::LEVEL-1> manager(*this->mask());
389  manager.foreachTopDown(op);
390 }
391 
392 template<typename TreeT>
394 {
395  return bool(mMaskTree.ptr);
396 }
397 
398 template<typename TreeT>
399 void TreeToMerge<TreeT>::reset(typename TreeType::Ptr treePtr, Steal)
400 {
401  if (!treePtr) {
402  OPENVDB_THROW(RuntimeError, "Cannot reset with empty Tree shared pointer.");
403  }
404  mSteal = true;
405  mTreePtr = treePtr;
406  mTree = mTreePtr.get();
407 }
408 
409 template<typename TreeT>
410 const typename TreeToMerge<TreeT>::RootNodeType*
412 {
413  return &mTree->root();
414 }
415 
416 template<typename TreeT>
417 template<typename NodeT>
418 const NodeT*
419 TreeToMerge<TreeT>::probeConstNode(const Coord& ijk) const
420 {
421  // test mutable mask first, node may have already been pruned
422  if (!mSteal && !this->mask()->isValueOn(ijk)) return nullptr;
423  return mTree->template probeConstNode<NodeT>(ijk);
424 }
425 
426 template<typename TreeT>
427 template<typename NodeT>
428 std::unique_ptr<NodeT>
430 {
431  if (mSteal) {
432  TreeType* tree = const_cast<TreeType*>(mTree);
433  return std::unique_ptr<NodeT>(
434  tree->root().template stealNode<NodeT>(ijk, mTree->root().background(), false)
435  );
436  } else {
437  auto* child = this->probeConstNode<NodeT>(ijk);
438  if (child) {
439  assert(this->hasMask());
440  auto result = std::make_unique<NodeT>(*child);
441  // prune mask tree
442  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 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  if (mSteal) {
458  TreeType* tree = const_cast<TreeType*>(mTree);
459  auto* node = tree->template probeNode<NodeT>(ijk);
460  if (node) {
461  const Index pos = NodeT::coordToOffset(ijk);
462  node->addTile(pos, value, active);
463  }
464  } else {
465  auto* node = mTree->template probeConstNode<NodeT>(ijk);
466  // prune mask tree
467  if (node) {
468  assert(this->hasMask());
469  this->mask()->addTile(NodeT::LEVEL, ijk, false, false);
470  }
471  }
472 }
473 
474 
475 ////////////////////////////////////////
476 
477 
478 template <typename TreeT>
479 bool TreeToMerge<TreeT>::MaskUnionOp::operator()(RootT& root, size_t /*idx*/) const
480 {
481  using ChildT = typename RootT::ChildNodeType;
482 
483  const Index count = mTree.root().childCount();
484 
485  std::vector<std::unique_ptr<ChildT>> children(count);
486 
487  // allocate new root children
488 
489  tbb::parallel_for(
490  tbb::blocked_range<Index>(0, count),
491  [&](tbb::blocked_range<Index>& range)
492  {
493  for (Index i = range.begin(); i < range.end(); i++) {
494  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  for (auto iter = mTree.root().cbeginChildOn(); iter; ++iter) {
503  children[i]->setOrigin(iter->origin());
504  root.addChild(children[i].release());
505  i++;
506  }
507 
508  return true;
509 }
510 
511 template <typename TreeT>
512 template <typename NodeT>
513 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  static void allocateAndFill(BufferT& buffer, const ValueT& background)
548  {
549  if (buffer.empty()) {
550  if (!buffer.isOutOfCore()) {
551  buffer.allocate();
552  buffer.fill(background);
553  }
554  }
555  }
556 
557  static bool isPartiallyConstructed(const BufferT& buffer)
558  {
559  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  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  if (childCount > 0) {
586  op(node, size_t(0));
587 
588  // build linear list of child pointers
589  std::vector<ChildT*> children;
590  children.reserve(childCount);
591  for (auto iter = node.beginChildOn(); iter; ++iter) {
592  children.push_back(&(*iter));
593  }
594 
595  // parallelize across children
596  tbb::parallel_for(
597  tbb::blocked_range<Index32>(0, childCount),
598  [&](tbb::blocked_range<Index32>& range) {
599  for (Index32 n = range.begin(); n < range.end(); n++) {
600  DepthFirstNodeVisitor<ChildT>::visit(*children[n], op);
601  }
602  }
603  );
604  } else {
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  {
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  ApplyTileToNodeOp(const ValueT& value, const bool active):
631  mValue(value), mActive(active) { }
632 
633  template <typename NodeT>
634  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  for (auto iter = node.beginValueAll(); iter; ++iter) {
641  iter.setValue(mValue + *iter);
642  }
643  if (mActive) node.setValuesOn();
644  }
645 
646  void operator()(LeafT& leaf, size_t) const
647  {
648  auto* data = leaf.buffer().data();
649 
650  if (mValue != zeroVal<ValueT>()) {
651  for (Index i = 0; i < LeafT::SIZE; ++i) {
652  data[i] += mValue;
653  }
654  }
655  if (mActive) leaf.setValuesOn();
656  }
657 
658  template <typename NodeT>
659  void run(NodeT& node)
660  {
661  Dispatch<NodeT::LEVEL>::run(node, *this);
662  }
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>
680 {
681  const bool Intersect = !Union;
682 
683  if (this->empty()) return false;
684 
685  // store the background value
686  if (!mBackground) mBackground = &root.background();
687 
688  // does the key exist in the root node?
689  auto keyExistsInRoot = [&](const Coord& key) -> bool
690  {
691  return root.getValueDepth(key) > -1;
692  };
693 
694  // does the key exist in all merge tree root nodes?
695  auto keyExistsInAllTrees = [&](const Coord& key) -> bool
696  {
697  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
698  const auto* mergeRoot = mergeTree.rootPtr();
699  if (!mergeRoot) return false;
700  if (mergeRoot->getValueDepth(key) == -1) return false;
701  }
702  return true;
703  };
704 
705  // delete any background tiles
706  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  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
713  const Coord& key = valueIter.getCoord();
714  if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
715  }
716  // find all child coordinates to delete
717  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
718  const Coord& key = childIter.getCoord();
719  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  for (Coord& key : toDelete) root.addTile(key, *mBackground, false);
724  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  constexpr uint8_t ACTIVE_TILE = 0x1;
731  constexpr uint8_t INSIDE_TILE = 0x2;
732  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  const ValueT insideBackground = Union ? -this->background() : this->background();
738  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  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
745  else if (value > zeroVal<ValueT>()) flag |= OUTSIDE_TILE;
746  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
747  return flag;
748  };
749 
750  std::unordered_map<Coord, /*flags*/uint8_t> tiles;
751 
752  if (root.getTableSize() > 0) {
753  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
754  const Coord& key = valueIter.getCoord();
755  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  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
762  const auto* mergeRoot = mergeTree.rootPtr();
763  if (!mergeRoot) continue;
764  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
765  const Coord& key = valueIter.getCoord();
766  auto it = tiles.find(key);
767  if (it == tiles.end()) {
768  // if no tile with this key, insert it
769  tiles.insert({key, getTileFlag(valueIter)});
770  } else {
771  // replace an outside tile with an inside tile
772  const uint8_t flag = it->second;
773  if (flag & OUTSIDE_STATE) {
774  const uint8_t newFlag = getTileFlag(valueIter);
775  if (newFlag & INSIDE_STATE) {
776  it->second = newFlag;
777  }
778  }
779  }
780  }
781  }
782 
783  // insert all inside tiles
784 
785  for (auto it : tiles) {
786  const uint8_t flag = it.second;
787  if (flag & INSIDE_STATE) {
788  const Coord& key = it.first;
789  const bool state = flag & ACTIVE_TILE;
790  // for intersection, only add the tile if the key already exists in the tree
791  if (Union || keyExistsInRoot(key)) {
792  root.addTile(key, insideBackground, state);
793  }
794  }
795  }
796 
797  std::unordered_set<Coord> children;
798 
799  if (root.getTableSize() > 0) {
800  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
801  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  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
812  const auto* mergeRoot = mergeTree.rootPtr();
813  if (!mergeRoot) continue;
814  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
815  const Coord& key = childIter.getCoord();
816 
817  // for intersection, only add child nodes if the key already exists in the tree
818  if (Intersect && !keyExistsInRoot(key)) continue;
819 
820  // if child already exists, merge recursion will need to continue to resolve conflict
821  if (children.count(key)) {
822  continueRecurse = true;
823  continue;
824  }
825 
826  // if an inside tile exists, do nothing
827  auto it = tiles.find(key);
828  if (it != tiles.end() && it->second == INSIDE_STATE) continue;
829 
830  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
831  childPtr->resetBackground(mergeRoot->background(), root.background());
832  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  for (auto it : tiles) {
841  const uint8_t flag = it.second;
842  if (flag & OUTSIDE_STATE) {
843  const Coord& key = it.first;
844  if (!children.count(key)) {
845  const bool state = flag & ACTIVE_TILE;
846  // for intersection, only add the tile if the key already exists in the tree
847  if (Union || keyExistsInRoot(key)) {
848  root.addTile(key, outsideBackground, state);
849  }
850  }
851  }
852  }
853 
854  // finish by removing any background tiles
855  root.eraseBackgroundTiles();
856 
857  return continueRecurse;
858 }
859 
860 template<typename TreeT, bool Union>
861 template<typename NodeT>
863 {
864  using NonConstNodeT = typename std::remove_const<NodeT>::type;
865 
866  if (this->empty()) return false;
867 
868  const ValueT insideBackground = Union ? -this->background() : this->background();
869  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  return Union ? value < zeroVal<ValueT>() : value > zeroVal<ValueT>();
880  };
881 
882  auto isInvalid = [](const ValueT& value)
883  {
884  return Union ? value > zeroVal<ValueT>() : value < zeroVal<ValueT>();
885  };
886 
887  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
888  if (isValid(iter.getValue())) {
889  validTile.setOn(iter.pos());
890  } else if (isInvalid(iter.getValue())) {
891  invalidTile.setOn(iter.pos());
892  }
893  }
894 
895  bool continueRecurse = false;
896 
897  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
898 
899  auto* mergeNode = mergeTree.template probeConstNode<NonConstNodeT>(node.origin());
900 
901  if (!mergeNode) continue;
902 
903  // iterate over all tiles
904 
905  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
906  Index pos = iter.pos();
907  // source node contains an inside tile, so ignore
908  if (validTile.isOn(pos)) continue;
909  // this node contains an inside tile, so turn into an inside tile
910  if (isValid(iter.getValue())) {
911  node.addTile(pos, insideBackground, iter.isValueOn());
912  validTile.setOn(pos);
913  }
914  }
915 
916  // iterate over all child nodes
917 
918  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
919  Index pos = iter.pos();
920  const Coord& ijk = iter.getCoord();
921  // source node contains an inside tile, so ensure other node has no child
922  if (validTile.isOn(pos)) {
923  mergeTree.template addTile<NonConstNodeT>(ijk, outsideBackground, false);
924  } else if (invalidTile.isOn(pos)) {
925  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
926  if (childPtr) {
927  childPtr->resetBackground(mergeTree.rootPtr()->background(), this->background());
928  node.addChild(childPtr.release());
929  }
930  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>
944 {
945  using LeafT = typename TreeT::LeafNodeType;
946  using ValueT = typename LeafT::ValueType;
947  using BufferT = typename LeafT::Buffer;
948 
949  if (this->empty()) return false;
950 
951  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  merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
957  leaf.buffer(), background);
958 
959  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
960  const LeafT* mergeLeaf = mergeTree.template probeConstNode<LeafT>(leaf.origin());
961  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  if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
965  mergeLeaf->buffer())) {
966  continue;
967  }
968 
969  for (Index i = 0 ; i < LeafT::SIZE; i++) {
970  const ValueT& newValue = mergeLeaf->getValue(i);
971  const bool doMerge = Union ? newValue < leaf.getValue(i) : newValue > leaf.getValue(i);
972  if (doMerge) {
973  leaf.setValueOnly(i, newValue);
974  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
975  }
976  }
977  }
978 
979  return false;
980 }
981 
982 template <typename TreeT, bool Union>
985 {
986  // this operator is only intended to be used with foreachTopDown()
987  assert(mBackground);
988  return *mBackground;
989 }
990 
991 
992 ////////////////////////////////////////
993 
994 
995 template <typename TreeT>
996 bool CsgDifferenceOp<TreeT>::operator()(RootT& root, size_t) const
997 {
998  // store the background values
999  if (!mBackground) mBackground = &root.background();
1000  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  constexpr uint8_t ACTIVE_TILE = 0x1;
1006  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  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
1014  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
1015  return flag;
1016  };
1017 
1018  // delete any background tiles
1019  root.eraseBackgroundTiles();
1020 
1021  std::unordered_map<Coord, /*flags*/uint8_t> flags;
1022 
1023  if (root.getTableSize() > 0) {
1024  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1025  const Coord& key = valueIter.getCoord();
1026  const uint8_t flag = getTileFlag(valueIter);
1027  if (flag & INSIDE_TILE) {
1028  flags.insert({key, getTileFlag(valueIter)});
1029  }
1030  }
1031 
1032  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1033  const Coord& key = childIter.getCoord();
1034  flags.insert({key, CHILD});
1035  }
1036  }
1037 
1038  bool continueRecurse = false;
1039 
1040  const auto* mergeRoot = mTree.rootPtr();
1041 
1042  if (mergeRoot) {
1043  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1044  const Coord& key = valueIter.getCoord();
1045  const uint8_t flag = getTileFlag(valueIter);
1046  if (flag & INSIDE_TILE) {
1047  auto it = flags.find(key);
1048  if (it != flags.end()) {
1049  const bool state = flag & ACTIVE_TILE;
1050  root.addTile(key, this->background(), state);
1051  }
1052  }
1053  }
1054 
1055  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1056  const Coord& key = childIter.getCoord();
1057  auto it = flags.find(key);
1058  if (it != flags.end()) {
1059  const uint8_t otherFlag = it->second;
1060  if (otherFlag & CHILD) {
1061  // if child already exists, merge recursion will need to continue to resolve conflict
1062  continueRecurse = true;
1063  } else if (otherFlag & INSIDE_TILE) {
1064  auto childPtr = mTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
1065  if (childPtr) {
1066  childPtr->resetBackground(this->otherBackground(), this->background());
1067  childPtr->negate();
1068  root.addChild(childPtr.release());
1069  }
1070  }
1071  }
1072  }
1073  }
1074 
1075  // finish by removing any background tiles
1076  root.eraseBackgroundTiles();
1077 
1078  return continueRecurse;
1079 }
1080 
1081 template<typename TreeT>
1082 template<typename NodeT>
1083 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  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
1093  if (iter.getValue() < zeroVal<ValueT>()) {
1094  insideTile.setOn(iter.pos());
1095  }
1096  }
1097 
1098  bool continueRecurse = false;
1099 
1100  auto* mergeNode = mTree.template probeConstNode<NonConstNodeT>(node.origin());
1101 
1102  if (!mergeNode) return continueRecurse;
1103 
1104  // iterate over all tiles
1105 
1106  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
1107  Index pos = iter.pos();
1108  if (iter.getValue() < zeroVal<ValueT>()) {
1109  if (insideTile.isOn(pos) || node.isChildMaskOn(pos)) {
1110  node.addTile(pos, this->background(), iter.isValueOn());
1111  }
1112  }
1113  }
1114 
1115  // iterate over all children
1116 
1117  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
1118  Index pos = iter.pos();
1119  const Coord& ijk = iter.getCoord();
1120  if (insideTile.isOn(pos)) {
1121  auto childPtr = mTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
1122  if (childPtr) {
1123  childPtr->resetBackground(this->otherBackground(), this->background());
1124  childPtr->negate();
1125  node.addChild(childPtr.release());
1126  }
1127  } 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  return continueRecurse;
1135 }
1136 
1137 template <typename TreeT>
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  merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
1148  leaf.buffer(), this->background());
1149 
1150  const LeafT* mergeLeaf = mTree.template probeConstNode<LeafT>(leaf.origin());
1151  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  if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
1157  mergeLeaf->buffer())) {
1158  return false;
1159  }
1160 
1161  for (Index i = 0 ; i < LeafT::SIZE; i++) {
1162  const ValueT& aValue = leaf.getValue(i);
1163  ValueT bValue = math::negative(mergeLeaf->getValue(i));
1164  if (aValue < bValue) { // a = max(a, -b)
1165  leaf.setValueOnly(i, bValue);
1166  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
1167  }
1168  }
1169 
1170  return false;
1171 }
1172 
1173 template <typename TreeT>
1174 const typename CsgDifferenceOp<TreeT>::ValueT&
1176 {
1177  // this operator is only intended to be used with foreachTopDown()
1178  assert(mBackground);
1179  return *mBackground;
1180 }
1181 
1182 template <typename TreeT>
1183 const typename CsgDifferenceOp<TreeT>::ValueT&
1185 {
1186  // this operator is only intended to be used with foreachTopDown()
1187  assert(mOtherBackground);
1188  return *mOtherBackground;
1189 }
1190 
1191 
1192 ////////////////////////////////////////
1193 
1194 
1195 template <typename TreeT>
1196 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  if (this->empty()) return false;
1203 
1204  // store the background value
1205  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  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  if (root.getTableSize() > 0) {
1222  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1223  const Coord& key = valueIter.getCoord();
1224  children.insert({key, TILE});
1225  }
1226 
1227  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1228  const Coord& key = childIter.getCoord();
1229  children.insert({key, CHILD | TARGET_CHILD});
1230  }
1231  }
1232 
1233  // find all tiles and child nodes in other roots
1234 
1235  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1236  const auto* mergeRoot = mergeTree.rootPtr();
1237  if (!mergeRoot) continue;
1238 
1239  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1240  const Coord& key = valueIter.getCoord();
1241  auto it = children.find(key);
1242  if (it == children.end()) {
1243  // if no element with this key, insert it
1244  children.insert({key, TILE});
1245  } else {
1246  // mark as tile
1247  it->second |= TILE;
1248  }
1249  }
1250 
1251  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1252  const Coord& key = childIter.getCoord();
1253  auto it = children.find(key);
1254  if (it == children.end()) {
1255  // if no element with this key, insert it
1256  children.insert({key, CHILD});
1257  } else {
1258  // mark as child
1259  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  for (const auto& it : children) {
1267  if (!keyExistsInRoot(root, it.first)) {
1268  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  for (const auto& it : children) {
1275 
1276  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  if (it.second & TARGET_CHILD) continue;
1281 
1282  ValueT value;
1283  const bool active = root.probeValue(key, value);
1284 
1285  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1286  const auto* mergeRoot = mergeTree.rootPtr();
1287  if (!mergeRoot) continue;
1288  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  auto childPtr = mergeTree.template stealOrDeepCopyNode<ChildT>(key);
1297  childPtr->resetBackground(mergeRoot->background(), root.background());
1298  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  root.addChild(childPtr.release());
1303  }
1304  break;
1305  }
1306 
1307  ValueT mergeValue;
1308  const bool mergeActive = mergeRoot->probeValue(key, mergeValue);
1309 
1310  if (active || mergeActive) {
1311  value += mergeValue;
1312  root.addTile(key, value, true);
1313  } else {
1314  value += mergeValue;
1315  root.addTile(key, value, false);
1316  }
1317 
1318  // reset tile value to zero to prevent it being merged twice
1319  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 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  if (this->empty()) return false;
1334 
1335  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1336  const auto* mergeRoot = mergeTree.rootPtr();
1337  if (!mergeRoot) continue;
1338 
1339  const auto* mergeNode = mergeRoot->template probeConstNode<NonConstNodeT>(node.origin());
1340  if (mergeNode) {
1341  // merge node
1342 
1343  for (auto iter = node.beginValueAll(); iter; ++iter) {
1344  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  const bool mergeActive = mergeNode->probeValue(iter.getCoord(), mergeValue);
1357  iter.setValue(*iter + mergeValue);
1358  if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1359  }
1360  }
1361 
1362  } else {
1363  // merge tile or background value
1364 
1365  ValueT mergeValue;
1366  const bool mergeActive = mergeRoot->probeValue(node.origin(), mergeValue);
1367  for (auto iter = node.beginValueAll(); iter; ++iter) {
1368  iter.setValue(*iter + mergeValue);
1369  if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1370  }
1371  }
1372  }
1373 
1374  return true;
1375 }
1376 
1377 template <typename TreeT>
1378 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  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  merge_internal::UnallocatedBuffer<BufferT, ValueT>::allocateAndFill(
1396  leaf.buffer(), this->background());
1397 
1398  auto* data = leaf.buffer().data();
1399 
1400  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1401  const RootT* mergeRoot = mergeTree.rootPtr();
1402  if (!mergeRoot) continue;
1403 
1404  const RootChildT* mergeRootChild = mergeRoot->template probeConstNode<NonConstRootChildT>(ijk);
1405  const LeafT* mergeLeaf = mergeRootChild ?
1406  mergeRootChild->template probeConstNode<NonConstLeafT>(ijk) : nullptr;
1407  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  if (merge_internal::UnallocatedBuffer<BufferT, ValueT>::isPartiallyConstructed(
1414  mergeLeaf->buffer())) {
1415  return false;
1416  }
1417 
1418  for (Index i = 0; i < LeafT::SIZE; ++i) {
1419  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  bool mergeActive = mergeRootChild ?
1428  mergeRootChild->probeValue(ijk, mergeValue) : mergeRoot->probeValue(ijk, mergeValue);
1429 
1430  if (mergeValue != zeroVal<ValueT>()) {
1431  for (Index i = 0; i < LeafT::SIZE; ++i) {
1432  data[i] += mergeValue;
1433  }
1434  }
1435 
1436  if (mergeActive) leaf.setValuesOn();
1437  }
1438  }
1439 
1440  return false;
1441 }
1442 
1443 template <typename TreeT>
1444 const typename SumMergeOp<TreeT>::ValueT&
1446 {
1447  // this operator is only intended to be used with foreachTopDown()
1448  assert(mBackground);
1449  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
1462 #endif
1463 
1473 
1483 
1486 
1489 
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
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:322
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:266
ChildT * child
Definition: GridBuilder.h:1286
CsgUnionOrIntersectionOp(TreeT &tree, TagT tag)
Convenience constructor to CSG union or intersect a single non-const tree with another. This constructor takes a Steal or DeepCopy tag dispatch class.
Definition: Merge.h:192
Index32 Index
Definition: Types.h:54
typename TreeT::RootNodeType RootT
Definition: Merge.h:265
const MaskTreeType * mask() const
Definition: Merge.h:120
Tag dispatch class that distinguishes constructors that steal.
Definition: Types.h:648
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
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:67
#define OPENVDB_INSTANTIATE_STRUCT
Definition: version.h.in:144
std::unique_ptr< MaskTreeType > ptr
Definition: Merge.h:137
void addTile(const Coord &ijk, const ValueType &value, bool active)
Add a tile containing voxel (x, y, z) at the level of NodeT, deleting the existing branch if necessar...
Definition: Merge.h:452
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:186
Definition: NodeManager.h:36
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:78
MaskPtr(const MaskPtr &other)
Definition: Merge.h:143
Definition: Exceptions.h:63
Implementation of a depth-first node visitor.
typename MaskT::LeafNodeType LeafT
Definition: Merge.h:160
Definition: Coord.h:587
CsgUnionOrIntersectionOp(TreesT &trees, TagT tag)
Constructor to CSG union or intersect a container of multiple const or non-const tree pointers...
Definition: Merge.h:204
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:350
typename TreeT::RootNodeType RootT
Definition: Merge.h:316
SumMergeOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to sum a single const tree with another. This constructor requires a DeepCopy...
Definition: Merge.h:326
typename TreeT::ValueType ValueT
Definition: Merge.h:264
DynamicNodeManager operator to merge two trees using a CSG difference.
Definition: Merge.h:262
CsgUnionOrIntersectionOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to CSG union or intersect a single const tree with another. This constructor requires a DeepCopy tag dispatch class.
Definition: Merge.h:197
TreeToMerge(typename TreeType::Ptr treePtr, Steal)
Non-const shared pointer tree constructor for stealing data.
Definition: Merge.h:59
typename TreeType::RootNodeType RootNodeType
Definition: Merge.h:49
MaskTreeType MaskT
Definition: Merge.h:158
bool empty() const
Return true if no trees being merged.
Definition: Merge.h:354
Convenience class that contains a pointer to a tree to be stolen or deep copied depending on the tag ...
Definition: Merge.h:46
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:399
uint32_t Index32
Definition: Types.h:52
TreeToMerge(TreeType &tree, Steal)
Non-const pointer tree constructor for stealing data.
Definition: Merge.h:56
bool operator()(LeafT &, size_t) const
Definition: Merge.h:166
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:222
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:128
size_t size() const
Return the number of trees being merged (only ever 1)
Definition: Merge.h:283
MaskTreeType * mask()
Definition: Merge.h:119
typename TreeType::ValueType ValueType
Definition: Merge.h:50
OPENVDB_IMPORT void initialize()
Global registration of native Grid, Transform, Metadata and Point attribute types. Also initializes blosc (if enabled).
DynamicNodeManager operator used to generate a mask of the input tree, but with dense leaf nodes repl...
Definition: Merge.h:156
bool empty() const
Return true if no trees being merged.
Definition: Merge.h:226
std::remove_const_t< TreeT > TreeType
Definition: Merge.h:48
Definition: Exceptions.h:13
typename TreeT::RootNodeType RootT
Definition: Merge.h:185
Tag dispatch class that distinguishes constructors that deep copy.
Definition: Types.h:646
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:317
size_t size() const
Return the number of trees being merged.
Definition: Merge.h:357
MaskPtr & operator=(const MaskPtr &other)
Definition: Merge.h:145
ValueT value
Definition: GridBuilder.h:1287
typename MaskT::RootNodeType RootT
Definition: Merge.h:159
DynamicNodeManager operator to merge trees using a CSG union or intersection.
Definition: Merge.h:182
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:344
DynamicNodeManager operator to merge trees using a sum operation.
Definition: Merge.h:313
MaskUnionOp(const TreeT &tree)
Definition: Merge.h:162
typename TreeT::ValueType ValueT
Definition: Merge.h:184
typename TreeT::ValueType ValueT
Definition: Merge.h:315
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.
bool isValid(GridType gridType, GridClass gridClass)
return true if the combination of GridType and GridClass is valid.
Definition: NanoVDB.h:520
Wrapper around unique_ptr that deep-copies mask on copy construction.
Definition: Merge.h:135
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
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:216
typename TreeT::template ValueConverter< ValueMask >::Type MaskTreeType
Definition: Merge.h:51
Visit all nodes that are downstream of a specific node in depth-first order and apply a user-supplied...
Definition: NodeVisitor.h:189
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
size_t size() const
Return the number of trees being merged.
Definition: Merge.h:229
CsgDifferenceOp(TreeToMerge< TreeT > &tree)
Constructor to CSG difference the tree in a TreeToMerge object from another.
Definition: Merge.h:280
const TreeType * treeToDeepCopy()
Return a pointer to the tree to be deep-copied.
Definition: Merge.h:89
CsgDifferenceOp(TreeT &tree, TagT tag)
Convenience constructor to CSG difference a single non-const tree from another. This constructor take...
Definition: Merge.h:272
CsgDifferenceOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to CSG difference a single const tree from another. This constructor requires...
Definition: Merge.h:276
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:202
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:332
TreeType * treeToSteal()
Return a pointer to the tree to be stolen.
Definition: Merge.h:87