OpenVDB  8.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 //
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 
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 
55  : mTree(&tree), mSteal(true) { }
57  TreeToMerge(typename TreeType::Ptr treePtr, Steal)
58  : mTreePtr(treePtr), mTree(mTreePtr.get()), mSteal(true) { }
59 
65  TreeToMerge(const TreeType& tree, DeepCopy, bool initialize = true)
66  : mTree(&tree), mSteal(false)
67  {
68  if (mTree && initialize) this->initializeMask();
69  }
70 
76  TreeToMerge(TreeType& tree, DeepCopy tag, bool initialize = true)
77  : TreeToMerge(static_cast<const TreeType&>(tree), tag, initialize) { }
78 
82  void reset(typename TreeType::Ptr treePtr, Steal);
83 
85  TreeType* treeToSteal() { return mSteal ? const_cast<TreeType*>(mTree) : nullptr; }
87  const TreeType* treeToDeepCopy() { return mSteal ? nullptr : mTree; }
88 
90  const RootNodeType* rootPtr() const;
91 
94  template<typename NodeT>
95  const NodeT* probeConstNode(const Coord& ijk) const;
96 
101  template <typename NodeT>
102  std::unique_ptr<NodeT> stealOrDeepCopyNode(const Coord& ijk);
103 
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 
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 
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 
170 
171 
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 
188  template <typename TagT>
189  CsgUnionOrIntersectionOp(TreeT& tree, TagT tag) { mTreesToMerge.emplace_back(tree, tag); }
190 
194  CsgUnionOrIntersectionOp(const TreeT& tree, DeepCopy tag) { mTreesToMerge.emplace_back(tree, tag); }
195 
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 
213  explicit CsgUnionOrIntersectionOp(const std::vector<TreeToMerge<TreeT>>& trees)
214  : mTreesToMerge(trees) { }
215 
219  explicit CsgUnionOrIntersectionOp(const std::deque<TreeToMerge<TreeT>>& trees)
220  : mTreesToMerge(trees.cbegin(), trees.cend()) { }
221 
223  bool empty() const { return mTreesToMerge.empty(); }
224 
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 
258 template<typename TreeT>
260 {
261  using ValueT = typename TreeT::ValueType;
262  using RootT = typename TreeT::RootNodeType;
263  using LeafT = typename TreeT::LeafNodeType;
264 
268  template <typename TagT>
269  CsgDifferenceOp(TreeT& tree, TagT tag) : mTree(tree, tag) { }
273  CsgDifferenceOp(const TreeT& tree, DeepCopy tag) : mTree(tree, tag) { }
274 
277  explicit CsgDifferenceOp(TreeToMerge<TreeT>& tree) : mTree(tree) { }
278 
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 
309 template<typename TreeT>
311 {
312  using ValueT = typename TreeT::ValueType;
313  using RootT = typename TreeT::RootNodeType;
314  using LeafT = typename TreeT::LeafNodeType;
315 
318  template <typename TagT>
319  SumMergeOp(TreeT& tree, TagT tag) { mTreesToMerge.emplace_back(tree, tag); }
320 
323  SumMergeOp(const TreeT& tree, DeepCopy tag) { mTreesToMerge.emplace_back(tree, tag); }
324 
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 
341  explicit SumMergeOp(const std::vector<TreeToMerge<TreeT>>& trees)
342  : mTreesToMerge(trees) { }
343 
347  explicit SumMergeOp(const std::deque<TreeToMerge<TreeT>>& trees)
348  : mTreesToMerge(trees.cbegin(), trees.cend()) { }
349 
351  bool empty() const { return mTreesToMerge.empty(); }
352 
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 
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 
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 
486  tbb::parallel_for(
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 
535 
536 
537 namespace merge_internal {
538 
539 
540 template <typename BufferT, typename ValueT>
542 {
543  static void allocateAndFill(BufferT& buffer, const ValueT& background)
544  {
545  if (buffer.empty()) {
546  if (!buffer.isOutOfCore()) {
547  buffer.allocate();
548  buffer.fill(background);
549  }
550  }
551  }
552 
553  static bool isPartiallyConstructed(const BufferT& buffer)
554  {
555  return !buffer.isOutOfCore() && buffer.empty();
556  }
557 }; // struct AllocateAndFillBuffer
558 
559 template <typename BufferT>
560 struct UnallocatedBuffer<BufferT, bool>
561 {
562  // do nothing for bool buffers as they cannot be unallocated
563  static void allocateAndFill(BufferT&, const bool&) { }
564  static bool isPartiallyConstructed(const BufferT&) { return false; }
565 }; // struct AllocateAndFillBuffer
566 
567 
568 // a convenience class that combines nested parallelism with the depth-visit
569 // node visitor which can result in increased performance with large sub-trees
570 template <Index LEVEL>
571 struct Dispatch
572 {
573  template <typename NodeT, typename OpT>
574  static void run(NodeT& node, OpT& op)
575  {
576  using ChildT = typename NodeT::ChildNodeType;
577 
578  // use nested parallelism if there is more than one child
579 
580  Index32 childCount = node.childCount();
581  if (childCount > 0) {
582  op(node, size_t(0));
583 
584  // build linear list of child pointers
585  std::vector<ChildT*> children;
586  children.reserve(childCount);
587  for (auto iter = node.beginChildOn(); iter; ++iter) {
588  children.push_back(&(*iter));
589  }
590 
591  // parallelize across children
592  tbb::parallel_for(
593  tbb::blocked_range<Index32>(0, childCount),
594  [&](tbb::blocked_range<Index32>& range) {
595  for (Index32 n = range.begin(); n < range.end(); n++) {
596  DepthFirstNodeVisitor<ChildT>::visit(*children[n], op);
597  }
598  }
599  );
600  } else {
602  }
603  }
604 }; // struct Dispatch
605 
606 // when LEVEL = 0, do not attempt nested parallelism
607 template <>
608 struct Dispatch<0>
609 {
610  template <typename NodeT, typename OpT>
611  static void run(NodeT& node, OpT& op)
612  {
614  }
615 };
616 
617 
618 // an DynamicNodeManager operator to add a value and modify active state
619 // for every tile and voxel in a given subtree
620 template <typename TreeT>
622 {
623  using LeafT = typename TreeT::LeafNodeType;
624  using ValueT = typename TreeT::ValueType;
625 
626  ApplyTileToNodeOp(const ValueT& value, const bool active):
627  mValue(value), mActive(active) { }
628 
629  template <typename NodeT>
630  void operator()(NodeT& node, size_t) const
631  {
632  // TODO: Need to add an InternalNode::setValue(Index offset, ...) to
633  // avoid the cost of using a value iterator or coordToOffset() in the case
634  // where node.isChildMaskOff() is true
635 
636  for (auto iter = node.beginValueAll(); iter; ++iter) {
637  iter.setValue(mValue + *iter);
638  }
639  if (mActive) node.setValuesOn();
640  }
641 
642  void operator()(LeafT& leaf, size_t) const
643  {
644  auto* data = leaf.buffer().data();
645 
646  if (mValue != zeroVal<ValueT>()) {
647  for (Index i = 0; i < LeafT::SIZE; ++i) {
648  data[i] += mValue;
649  }
650  }
651  if (mActive) leaf.setValuesOn();
652  }
653 
654  template <typename NodeT>
655  void run(NodeT& node)
656  {
657  Dispatch<NodeT::LEVEL>::run(node, *this);
658  }
659 
660 private:
661  ValueT mValue;
662  bool mActive;
663 }; // struct ApplyTileToNodeOp
664 
665 
666 } // namespace merge_internal
667 
668 
670 
671 
672 template <typename TreeT, bool Union>
674 {
675  const bool Intersect = !Union;
676 
677  if (this->empty()) return false;
678 
679  // store the background value
680  if (!mBackground) mBackground = &root.background();
681 
682  // does the key exist in the root node?
683  auto keyExistsInRoot = [&](const Coord& key) -> bool
684  {
685  return root.getValueDepth(key) > -1;
686  };
687 
688  // does the key exist in all merge tree root nodes?
689  auto keyExistsInAllTrees = [&](const Coord& key) -> bool
690  {
691  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
692  const auto* mergeRoot = mergeTree.rootPtr();
693  if (!mergeRoot) return false;
694  if (mergeRoot->getValueDepth(key) == -1) return false;
695  }
696  return true;
697  };
698 
699  // delete any background tiles
700  root.eraseBackgroundTiles();
701 
702  // for intersection, delete any root node keys that are not present in all trees
703  if (Intersect) {
704  // find all tile coordinates to delete
705  std::vector<Coord> toDelete;
706  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
707  const Coord& key = valueIter.getCoord();
708  if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
709  }
710  // find all child coordinates to delete
711  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
712  const Coord& key = childIter.getCoord();
713  if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
714  }
715  // only mechanism to delete elements in root node is to delete background tiles,
716  // so insert background tiles (which will replace any child nodes) and then delete
717  for (Coord& key : toDelete) root.addTile(key, *mBackground, false);
718  root.eraseBackgroundTiles();
719  }
720 
721  // find all tile values in this root and track inside/outside and active state
722  // note that level sets should never contain active tiles, but we handle them anyway
723 
724  constexpr uint8_t ACTIVE_TILE = 0x1;
725  constexpr uint8_t INSIDE_TILE = 0x2;
726  constexpr uint8_t OUTSIDE_TILE = 0x4;
727 
728  constexpr uint8_t INSIDE_STATE = Union ? INSIDE_TILE : OUTSIDE_TILE;
729  constexpr uint8_t OUTSIDE_STATE = Union ? OUTSIDE_TILE : INSIDE_TILE;
730 
731  const ValueT insideBackground = Union ? -this->background() : this->background();
732  const ValueT outsideBackground = -insideBackground;
733 
734  auto getTileFlag = [&](auto& valueIter) -> uint8_t
735  {
736  uint8_t flag(0);
737  const ValueT& value = valueIter.getValue();
738  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
739  else if (value > zeroVal<ValueT>()) flag |= OUTSIDE_TILE;
740  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
741  return flag;
742  };
743 
744  std::unordered_map<Coord, /*flags*/uint8_t> tiles;
745 
746  if (root.getTableSize() > 0) {
747  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
748  const Coord& key = valueIter.getCoord();
749  tiles.insert({key, getTileFlag(valueIter)});
750  }
751  }
752 
753  // find all tiles values in other roots and replace outside tiles with inside tiles
754 
755  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
756  const auto* mergeRoot = mergeTree.rootPtr();
757  if (!mergeRoot) continue;
758  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
759  const Coord& key = valueIter.getCoord();
760  auto it = tiles.find(key);
761  if (it == tiles.end()) {
762  // if no tile with this key, insert it
763  tiles.insert({key, getTileFlag(valueIter)});
764  } else {
765  // replace an outside tile with an inside tile
766  const uint8_t flag = it->second;
767  if (flag & OUTSIDE_STATE) {
768  const uint8_t newFlag = getTileFlag(valueIter);
769  if (newFlag & INSIDE_STATE) {
770  it->second = newFlag;
771  }
772  }
773  }
774  }
775  }
776 
777  // insert all inside tiles
778 
779  for (auto it : tiles) {
780  const uint8_t flag = it.second;
781  if (flag & INSIDE_STATE) {
782  const Coord& key = it.first;
783  const bool state = flag & ACTIVE_TILE;
784  // for intersection, only add the tile if the key already exists in the tree
785  if (Union || keyExistsInRoot(key)) {
786  root.addTile(key, insideBackground, state);
787  }
788  }
789  }
790 
791  std::unordered_set<Coord> children;
792 
793  if (root.getTableSize() > 0) {
794  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
795  const Coord& key = childIter.getCoord();
796  children.insert(key);
797  }
798  }
799 
800  bool continueRecurse = false;
801 
802  // find all children in other roots and insert them if a child or tile with this key
803  // does not already exist or if the child will replace an outside tile
804 
805  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
806  const auto* mergeRoot = mergeTree.rootPtr();
807  if (!mergeRoot) continue;
808  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
809  const Coord& key = childIter.getCoord();
810 
811  // for intersection, only add child nodes if the key already exists in the tree
812  if (Intersect && !keyExistsInRoot(key)) continue;
813 
814  // if child already exists, merge recursion will need to continue to resolve conflict
815  if (children.count(key)) {
816  continueRecurse = true;
817  continue;
818  }
819 
820  // if an inside tile exists, do nothing
821  auto it = tiles.find(key);
822  if (it != tiles.end() && it->second == INSIDE_STATE) continue;
823 
824  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
825  childPtr->resetBackground(mergeRoot->background(), root.background());
826  if (childPtr) root.addChild(childPtr.release());
827 
828  children.insert(key);
829  }
830  }
831 
832  // insert all outside tiles that don't replace an inside tile or a child node
833 
834  for (auto it : tiles) {
835  const uint8_t flag = it.second;
836  if (flag & OUTSIDE_STATE) {
837  const Coord& key = it.first;
838  if (!children.count(key)) {
839  const bool state = flag & ACTIVE_TILE;
840  // for intersection, only add the tile if the key already exists in the tree
841  if (Union || keyExistsInRoot(key)) {
842  root.addTile(key, outsideBackground, state);
843  }
844  }
845  }
846  }
847 
848  // finish by removing any background tiles
849  root.eraseBackgroundTiles();
850 
851  return continueRecurse;
852 }
853 
854 template<typename TreeT, bool Union>
855 template<typename NodeT>
857 {
858  using NonConstNodeT = typename std::remove_const<NodeT>::type;
859 
860  if (this->empty()) return false;
861 
862  const ValueT insideBackground = Union ? -this->background() : this->background();
863  const ValueT outsideBackground = -insideBackground;
864 
865  using NodeMaskT = typename NodeT::NodeMaskType;
866 
867  // store temporary masks to track inside and outside tile states
868  NodeMaskT validTile;
869  NodeMaskT invalidTile;
870 
871  auto isValid = [](const ValueT& value)
872  {
873  return Union ? value < zeroVal<ValueT>() : value > zeroVal<ValueT>();
874  };
875 
876  auto isInvalid = [](const ValueT& value)
877  {
878  return Union ? value > zeroVal<ValueT>() : value < zeroVal<ValueT>();
879  };
880 
881  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
882  if (isValid(iter.getValue())) {
883  validTile.setOn(iter.pos());
884  } else if (isInvalid(iter.getValue())) {
885  invalidTile.setOn(iter.pos());
886  }
887  }
888 
889  bool continueRecurse = false;
890 
891  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
892 
893  auto* mergeNode = mergeTree.template probeConstNode<NonConstNodeT>(node.origin());
894 
895  if (!mergeNode) continue;
896 
897  // iterate over all tiles
898 
899  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
900  Index pos = iter.pos();
901  // source node contains an inside tile, so ignore
902  if (validTile.isOn(pos)) continue;
903  // this node contains an inside tile, so turn into an inside tile
904  if (isValid(iter.getValue())) {
905  node.addTile(pos, insideBackground, iter.isValueOn());
906  validTile.setOn(pos);
907  }
908  }
909 
910  // iterate over all child nodes
911 
912  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
913  Index pos = iter.pos();
914  const Coord& ijk = iter.getCoord();
915  // source node contains an inside tile, so ensure other node has no child
916  if (validTile.isOn(pos)) {
917  mergeTree.template addTile<NonConstNodeT>(ijk, outsideBackground, false);
918  } else if (invalidTile.isOn(pos)) {
919  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
920  if (childPtr) {
921  childPtr->resetBackground(mergeTree.rootPtr()->background(), this->background());
922  node.addChild(childPtr.release());
923  }
924  invalidTile.setOff(pos);
925  } else {
926  // if both source and target are child nodes, merge recursion needs to continue
927  // along this branch to resolve the conflict
928  continueRecurse = true;
929  }
930  }
931  }
932 
933  return continueRecurse;
934 }
935 
936 template <typename TreeT, bool Union>
938 {
939  using LeafT = typename TreeT::LeafNodeType;
940  using ValueT = typename LeafT::ValueType;
941  using BufferT = typename LeafT::Buffer;
942 
943  if (this->empty()) return false;
944 
945  const ValueT background = Union ? this->background() : -this->background();
946 
947  // if buffer is not out-of-core and empty, leaf node must have only been
948  // partially constructed, so allocate and fill with background value
949 
951  leaf.buffer(), background);
952 
953  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
954  const LeafT* mergeLeaf = mergeTree.template probeConstNode<LeafT>(leaf.origin());
955  if (!mergeLeaf) continue;
956  // if buffer is not out-of-core yet empty, leaf node must have only been
957  // partially constructed, so skip merge
959  mergeLeaf->buffer())) {
960  continue;
961  }
962 
963  for (Index i = 0 ; i < LeafT::SIZE; i++) {
964  const ValueT& newValue = mergeLeaf->getValue(i);
965  const bool doMerge = Union ? newValue < leaf.getValue(i) : newValue > leaf.getValue(i);
966  if (doMerge) {
967  leaf.setValueOnly(i, newValue);
968  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
969  }
970  }
971  }
972 
973  return false;
974 }
975 
976 template <typename TreeT, bool Union>
979 {
980  // this operator is only intended to be used with foreachTopDown()
981  assert(mBackground);
982  return *mBackground;
983 }
984 
985 
987 
988 
989 template <typename TreeT>
990 bool CsgDifferenceOp<TreeT>::operator()(RootT& root, size_t) const
991 {
992  // store the background values
993  if (!mBackground) mBackground = &root.background();
994  if (!mOtherBackground) mOtherBackground = &mTree.rootPtr()->background();
995 
996  // find all tile values in this root and track inside/outside and active state
997  // note that level sets should never contain active tiles, but we handle them anyway
998 
999  constexpr uint8_t ACTIVE_TILE = 0x1;
1000  constexpr uint8_t INSIDE_TILE = 0x2;
1001  constexpr uint8_t CHILD = 0x4;
1002 
1003  auto getTileFlag = [&](auto& valueIter) -> uint8_t
1004  {
1005  uint8_t flag(0);
1006  const ValueT& value = valueIter.getValue();
1007  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
1008  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
1009  return flag;
1010  };
1011 
1012  // delete any background tiles
1013  root.eraseBackgroundTiles();
1014 
1015  std::unordered_map<Coord, /*flags*/uint8_t> flags;
1016 
1017  if (root.getTableSize() > 0) {
1018  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1019  const Coord& key = valueIter.getCoord();
1020  const uint8_t flag = getTileFlag(valueIter);
1021  if (flag & INSIDE_TILE) {
1022  flags.insert({key, getTileFlag(valueIter)});
1023  }
1024  }
1025 
1026  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1027  const Coord& key = childIter.getCoord();
1028  flags.insert({key, CHILD});
1029  }
1030  }
1031 
1032  bool continueRecurse = false;
1033 
1034  const auto* mergeRoot = mTree.rootPtr();
1035 
1036  if (mergeRoot) {
1037  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1038  const Coord& key = valueIter.getCoord();
1039  const uint8_t flag = getTileFlag(valueIter);
1040  if (flag & INSIDE_TILE) {
1041  auto it = flags.find(key);
1042  if (it != flags.end()) {
1043  const bool state = flag & ACTIVE_TILE;
1044  root.addTile(key, this->background(), state);
1045  }
1046  }
1047  }
1048 
1049  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1050  const Coord& key = childIter.getCoord();
1051  auto it = flags.find(key);
1052  if (it != flags.end()) {
1053  const uint8_t otherFlag = it->second;
1054  if (otherFlag & CHILD) {
1055  // if child already exists, merge recursion will need to continue to resolve conflict
1056  continueRecurse = true;
1057  } else if (otherFlag & INSIDE_TILE) {
1058  auto childPtr = mTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
1059  if (childPtr) {
1060  childPtr->resetBackground(this->otherBackground(), this->background());
1061  childPtr->negate();
1062  root.addChild(childPtr.release());
1063  }
1064  }
1065  }
1066  }
1067  }
1068 
1069  // finish by removing any background tiles
1070  root.eraseBackgroundTiles();
1071 
1072  return continueRecurse;
1073 }
1074 
1075 template<typename TreeT>
1076 template<typename NodeT>
1077 bool CsgDifferenceOp<TreeT>::operator()(NodeT& node, size_t) const
1078 {
1079  using NonConstNodeT = typename std::remove_const<NodeT>::type;
1080 
1081  using NodeMaskT = typename NodeT::NodeMaskType;
1082 
1083  // store temporary mask to track inside tile state
1084 
1085  NodeMaskT insideTile;
1086  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
1087  if (iter.getValue() < zeroVal<ValueT>()) {
1088  insideTile.setOn(iter.pos());
1089  }
1090  }
1091 
1092  bool continueRecurse = false;
1093 
1094  auto* mergeNode = mTree.template probeConstNode<NonConstNodeT>(node.origin());
1095 
1096  if (!mergeNode) return continueRecurse;
1097 
1098  // iterate over all tiles
1099 
1100  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
1101  Index pos = iter.pos();
1102  if (iter.getValue() < zeroVal<ValueT>()) {
1103  if (insideTile.isOn(pos) || node.isChildMaskOn(pos)) {
1104  node.addTile(pos, this->background(), iter.isValueOn());
1105  }
1106  }
1107  }
1108 
1109  // iterate over all children
1110 
1111  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
1112  Index pos = iter.pos();
1113  const Coord& ijk = iter.getCoord();
1114  if (insideTile.isOn(pos)) {
1115  auto childPtr = mTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
1116  if (childPtr) {
1117  childPtr->resetBackground(this->otherBackground(), this->background());
1118  childPtr->negate();
1119  node.addChild(childPtr.release());
1120  }
1121  } else if (node.isChildMaskOn(pos)) {
1122  // if both source and target are child nodes, merge recursion needs to continue
1123  // along this branch to resolve the conflict
1124  continueRecurse = true;
1125  }
1126  }
1127 
1128  return continueRecurse;
1129 }
1130 
1131 template <typename TreeT>
1133 {
1134  using LeafT = typename TreeT::LeafNodeType;
1135  using ValueT = typename LeafT::ValueType;
1136  using BufferT = typename LeafT::Buffer;
1137 
1138  // if buffer is not out-of-core and empty, leaf node must have only been
1139  // partially constructed, so allocate and fill with background value
1140 
1142  leaf.buffer(), this->background());
1143 
1144  const LeafT* mergeLeaf = mTree.template probeConstNode<LeafT>(leaf.origin());
1145  if (!mergeLeaf) return false;
1146 
1147  // if buffer is not out-of-core yet empty, leaf node must have only been
1148  // partially constructed, so skip merge
1149 
1151  mergeLeaf->buffer())) {
1152  return false;
1153  }
1154 
1155  for (Index i = 0 ; i < LeafT::SIZE; i++) {
1156  const ValueT& aValue = leaf.getValue(i);
1157  ValueT bValue = math::negative(mergeLeaf->getValue(i));
1158  if (aValue < bValue) { // a = max(a, -b)
1159  leaf.setValueOnly(i, bValue);
1160  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
1161  }
1162  }
1163 
1164  return false;
1165 }
1166 
1167 template <typename TreeT>
1168 const typename CsgDifferenceOp<TreeT>::ValueT&
1170 {
1171  // this operator is only intended to be used with foreachTopDown()
1172  assert(mBackground);
1173  return *mBackground;
1174 }
1175 
1176 template <typename TreeT>
1177 const typename CsgDifferenceOp<TreeT>::ValueT&
1179 {
1180  // this operator is only intended to be used with foreachTopDown()
1181  assert(mOtherBackground);
1182  return *mOtherBackground;
1183 }
1184 
1185 
1187 
1188 
1189 template <typename TreeT>
1190 bool SumMergeOp<TreeT>::operator()(RootT& root, size_t) const
1191 {
1192  using ValueT = typename RootT::ValueType;
1193  using ChildT = typename RootT::ChildNodeType;
1194  using NonConstChildT = typename std::remove_const<ChildT>::type;
1195 
1196  if (this->empty()) return false;
1197 
1198  // store the background value
1199  if (!mBackground) mBackground = &root.background();
1200 
1201  // does the key exist in the root node?
1202  auto keyExistsInRoot = [](const auto& rootToTest, const Coord& key) -> bool
1203  {
1204  return rootToTest.getValueDepth(key) > -1;
1205  };
1206 
1207  constexpr uint8_t TILE = 0x1;
1208  constexpr uint8_t CHILD = 0x2;
1209  constexpr uint8_t TARGET_CHILD = 0x4; // child already exists in the target tree
1210 
1211  std::unordered_map<Coord, /*flags*/uint8_t> children;
1212 
1213  // find all tiles and child nodes in our root
1214 
1215  if (root.getTableSize() > 0) {
1216  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
1217  const Coord& key = valueIter.getCoord();
1218  children.insert({key, TILE});
1219  }
1220 
1221  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
1222  const Coord& key = childIter.getCoord();
1223  children.insert({key, CHILD | TARGET_CHILD});
1224  }
1225  }
1226 
1227  // find all tiles and child nodes in other roots
1228 
1229  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1230  const auto* mergeRoot = mergeTree.rootPtr();
1231  if (!mergeRoot) continue;
1232 
1233  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
1234  const Coord& key = valueIter.getCoord();
1235  auto it = children.find(key);
1236  if (it == children.end()) {
1237  // if no element with this key, insert it
1238  children.insert({key, TILE});
1239  } else {
1240  // mark as tile
1241  it->second |= TILE;
1242  }
1243  }
1244 
1245  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
1246  const Coord& key = childIter.getCoord();
1247  auto it = children.find(key);
1248  if (it == children.end()) {
1249  // if no element with this key, insert it
1250  children.insert({key, CHILD});
1251  } else {
1252  // mark as child
1253  it->second |= CHILD;
1254  }
1255  }
1256  }
1257 
1258  // if any coords do not already exist in the root, insert an inactive background tile
1259 
1260  for (const auto& it : children) {
1261  if (!keyExistsInRoot(root, it.first)) {
1262  root.addTile(it.first, root.background(), false);
1263  }
1264  }
1265 
1266  // for each coord, merge each tile into the root until a child is found, then steal it
1267 
1268  for (const auto& it : children) {
1269 
1270  const Coord& key = it.first;
1271 
1272  // do nothing if the target root already contains a child node,
1273  // merge recursion will need to continue to resolve conflict
1274  if (it.second & TARGET_CHILD) continue;
1275 
1276  ValueT value;
1277  const bool active = root.probeValue(key, value);
1278 
1279  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1280  const auto* mergeRoot = mergeTree.rootPtr();
1281  if (!mergeRoot) continue;
1282  if (!keyExistsInRoot(*mergeRoot, key)) continue;
1283 
1284  // steal or deep-copy the first child node that is encountered,
1285  // then cease processing of this root node coord as merge recursion
1286  // will need to continue to resolve conflict
1287 
1288  const auto* mergeNode = mergeRoot->template probeConstNode<ChildT>(key);
1289  if (mergeNode) {
1290  auto childPtr = mergeTree.template stealOrDeepCopyNode<ChildT>(key);
1291  childPtr->resetBackground(mergeRoot->background(), root.background());
1292  if (childPtr) {
1293  // apply tile value and active state to the sub-tree
1294  merge_internal::ApplyTileToNodeOp<TreeT> applyOp(value, active);
1295  applyOp.run(*childPtr);
1296  root.addChild(childPtr.release());
1297  }
1298  break;
1299  }
1300 
1301  ValueT mergeValue;
1302  const bool mergeActive = mergeRoot->probeValue(key, mergeValue);
1303 
1304  if (active || mergeActive) {
1305  value += mergeValue;
1306  root.addTile(key, value, true);
1307  } else {
1308  value += mergeValue;
1309  root.addTile(key, value, false);
1310  }
1311 
1312  // reset tile value to zero to prevent it being merged twice
1313  mergeTree.template addTile<NonConstChildT>(key, zeroVal<ValueT>(), false);
1314  }
1315  }
1316 
1317  return true;
1318 }
1319 
1320 template<typename TreeT>
1321 template<typename NodeT>
1322 bool SumMergeOp<TreeT>::operator()(NodeT& node, size_t) const
1323 {
1324  using ChildT = typename NodeT::ChildNodeType;
1325  using NonConstNodeT = typename std::remove_const<NodeT>::type;
1326 
1327  if (this->empty()) return false;
1328 
1329  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1330  const auto* mergeRoot = mergeTree.rootPtr();
1331  if (!mergeRoot) continue;
1332 
1333  const auto* mergeNode = mergeRoot->template probeConstNode<NonConstNodeT>(node.origin());
1334  if (mergeNode) {
1335  // merge node
1336 
1337  for (auto iter = node.beginValueAll(); iter; ++iter) {
1338  if (mergeNode->isChildMaskOn(iter.pos())) {
1339  // steal child node
1340  auto childPtr = mergeTree.template stealOrDeepCopyNode<ChildT>(iter.getCoord());
1341  childPtr->resetBackground(mergeRoot->background(), this->background());
1342  if (childPtr) {
1343  // apply tile value and active state to the sub-tree
1344  merge_internal::ApplyTileToNodeOp<TreeT> applyOp(*iter, iter.isValueOn());
1345  applyOp.run(*childPtr);
1346  node.addChild(childPtr.release());
1347  }
1348  } else {
1349  ValueT mergeValue;
1350  const bool mergeActive = mergeNode->probeValue(iter.getCoord(), mergeValue);
1351  iter.setValue(*iter + mergeValue);
1352  if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1353  }
1354  }
1355 
1356  } else {
1357  // merge tile or background value
1358 
1359  ValueT mergeValue;
1360  const bool mergeActive = mergeRoot->probeValue(node.origin(), mergeValue);
1361  for (auto iter = node.beginValueAll(); iter; ++iter) {
1362  iter.setValue(*iter + mergeValue);
1363  if (mergeActive && !iter.isValueOn()) iter.setValueOn();
1364  }
1365  }
1366  }
1367 
1368  return true;
1369 }
1370 
1371 template <typename TreeT>
1372 bool SumMergeOp<TreeT>::operator()(LeafT& leaf, size_t) const
1373 {
1374  using RootT = typename TreeT::RootNodeType;
1375  using RootChildT = typename RootT::ChildNodeType;
1376  using NonConstRootChildT = typename std::remove_const<RootChildT>::type;
1377  using LeafT = typename TreeT::LeafNodeType;
1378  using ValueT = typename LeafT::ValueType;
1379  using BufferT = typename LeafT::Buffer;
1380  using NonConstLeafT = typename std::remove_const<LeafT>::type;
1381 
1382  if (this->empty()) return false;
1383 
1384  const Coord& ijk = leaf.origin();
1385 
1386  // if buffer is not out-of-core and empty, leaf node must have only been
1387  // partially constructed, so allocate and fill with background value
1388 
1390  leaf.buffer(), this->background());
1391 
1392  auto* data = leaf.buffer().data();
1393 
1394  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
1395  const RootT* mergeRoot = mergeTree.rootPtr();
1396  if (!mergeRoot) continue;
1397 
1398  const RootChildT* mergeRootChild = mergeRoot->template probeConstNode<NonConstRootChildT>(ijk);
1399  const LeafT* mergeLeaf = mergeRootChild ?
1400  mergeRootChild->template probeConstNode<NonConstLeafT>(ijk) : nullptr;
1401  if (mergeLeaf) {
1402  // merge leaf
1403 
1404  // if buffer is not out-of-core yet empty, leaf node must have only been
1405  // partially constructed, so skip merge
1406 
1408  mergeLeaf->buffer())) {
1409  return false;
1410  }
1411 
1412  for (Index i = 0; i < LeafT::SIZE; ++i) {
1413  data[i] += mergeLeaf->getValue(i);
1414  }
1415 
1416  leaf.getValueMask() |= mergeLeaf->getValueMask();
1417  } else {
1418  // merge root tile or background value
1419 
1420  ValueT mergeValue;
1421  bool mergeActive = mergeRootChild ?
1422  mergeRootChild->probeValue(ijk, mergeValue) : mergeRoot->probeValue(ijk, mergeValue);
1423 
1424  if (mergeValue != zeroVal<ValueT>()) {
1425  for (Index i = 0; i < LeafT::SIZE; ++i) {
1426  data[i] += mergeValue;
1427  }
1428  }
1429 
1430  if (mergeActive) leaf.setValuesOn();
1431  }
1432  }
1433 
1434  return false;
1435 }
1436 
1437 template <typename TreeT>
1438 const typename SumMergeOp<TreeT>::ValueT&
1440 {
1441  // this operator is only intended to be used with foreachTopDown()
1442  assert(mBackground);
1443  return *mBackground;
1444 }
1445 
1446 
1447 
1448 } // namespace tools
1449 } // namespace OPENVDB_VERSION_NAME
1450 } // namespace openvdb
1451 
1452 #endif // OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
ApplyTileToNodeOp(const ValueT &value, const bool active)
Definition: Merge.h:626
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
DynamicNodeManager operator to merge trees using a CSG union or intersection.
Definition: Merge.h:179
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
const TreeType * treeToDeepCopy()
Return a pointer to the tree to be deep-copied.
Definition: Merge.h:87
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
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
#define OPENVDB_THROW(exception, message)
Definition: openvdb/Exceptions.h:74
uint32_t Index32
Definition: openvdb/Types.h:48
MaskPtr(const MaskPtr &other)
Definition: Merge.h:141
Definition: NodeManager.h:36
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:183
TreeType * treeToSteal()
Return a pointer to the tree to be stolen.
Definition: Merge.h:85
size_t size() const
Return the number of trees being merged (only ever 1)
Definition: Merge.h:280
MaskTreeType * mask()
Definition: Merge.h:117
bool operator()(LeafT &, size_t) const
Definition: Merge.h:163
MaskTreeType MaskT
Definition: Merge.h:155
Implementation of a depth-first node visitor.
std::unique_ptr< MaskTreeType > ptr
Definition: Merge.h:135
typename TreeT::template ValueConverter< ValueMask >::Type MaskTreeType
Definition: Merge.h:49
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:314
CsgDifferenceOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to CSG difference a single const tree from another. This constructor requires...
Definition: Merge.h:273
bool empty() const
Return true if no trees being merged.
Definition: Merge.h:351
typename TreeT::RootNodeType RootT
Definition: Merge.h:313
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
OPENVDB_IMPORT void initialize()
Global registration of basic types.
Visit all nodes that are downstream of a specific node in depth-first order and apply a user-supplied...
Definition: NodeVisitor.h:189
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:201
MaskUnionOp(const TreeT &tree)
Definition: Merge.h:159
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:263
static bool isPartiallyConstructed(const BufferT &buffer)
Definition: Merge.h:553
CsgDifferenceOp(TreeT &tree, TagT tag)
Convenience constructor to CSG difference a single non-const tree from another. This constructor take...
Definition: Merge.h:269
DynamicNodeManager operator used to generate a mask of the input tree, but with dense leaf nodes repl...
Definition: Merge.h:153
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
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
size_t size() const
Return the number of trees being merged.
Definition: Merge.h:354
Index32 Index
Definition: openvdb/Types.h:50
const MaskTreeType * mask() const
Definition: Merge.h:118
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:623
void run(NodeT &node)
Definition: Merge.h:655
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
typename MaskT::RootNodeType RootT
Definition: Merge.h:156
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
void operator()(NodeT &node, size_t) const
Definition: Merge.h:630
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
Tag dispatch class that distinguishes constructors that deep copy.
Definition: openvdb/Types.h:562
Convenience class that contains a pointer to a tree to be stolen or deep copied depending on the tag ...
Definition: Merge.h:44
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
static void allocateAndFill(BufferT &buffer, const ValueT &background)
Definition: Merge.h:543
TreeToMerge(typename TreeType::Ptr treePtr, Steal)
Non-const shared pointer tree constructor for stealing data.
Definition: Merge.h:57
std::remove_const_t< TreeT > TreeType
Definition: Merge.h:46
Definition: openvdb/Exceptions.h:63
bool empty() const
Return true if no trees being merged.
Definition: Merge.h:223
static bool isPartiallyConstructed(const BufferT &)
Definition: Merge.h:564
Definition: openvdb/Exceptions.h:13
typename TreeT::RootNodeType RootT
Definition: Merge.h:182
typename TreeT::ValueType ValueT
Definition: Merge.h:312
TreeToMerge(TreeType &tree, Steal)
Non-const pointer tree constructor for stealing data.
Definition: Merge.h:54
static void run(NodeT &node, OpT &op)
Definition: Merge.h:611
typename TreeType::ValueType ValueType
Definition: Merge.h:48
CsgDifferenceOp(TreeToMerge< TreeT > &tree)
Constructor to CSG difference the tree in a TreeToMerge object from another.
Definition: Merge.h:277
DynamicNodeManager operator to merge trees using a sum operation.
Definition: Merge.h:310
typename TreeT::RootNodeType RootT
Definition: Merge.h:262
typename TreeT::ValueType ValueT
Definition: Merge.h:261
typename TreeT::ValueType ValueT
Definition: Merge.h:181
void run(const char *ax, openvdb::GridBase &grid)
Run a full AX pipeline (parse, compile and execute) on a single OpenVDB Grid.
typename TreeT::ValueType ValueT
Definition: Merge.h:624
Wrapper around unique_ptr that deep-copies mask on copy construction.
Definition: Merge.h:133
typename TreeType::RootNodeType RootNodeType
Definition: Merge.h:47
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
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
void operator()(LeafT &leaf, size_t) const
Definition: Merge.h:642
static void run(NodeT &node, OpT &op)
Definition: Merge.h:574
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
Tag dispatch class that distinguishes constructors that steal.
Definition: openvdb/Types.h:564
typename MaskT::LeafNodeType LeafT
Definition: Merge.h:157
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
static void allocateAndFill(BufferT &, const bool &)
Definition: Merge.h:563
size_t size() const
Return the number of trees being merged.
Definition: Merge.h:226
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
DynamicNodeManager operator to merge two trees using a CSG difference.
Definition: Merge.h:259
MaskPtr & operator=(const MaskPtr &other)
Definition: Merge.h:143
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:178