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