OpenVDB  8.0.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>
18 
19 #include <unordered_map>
20 #include <unordered_set>
21 
22 namespace openvdb {
24 namespace OPENVDB_VERSION_NAME {
25 namespace tools {
26 
27 
42 template <typename TreeT>
44 {
45  using TreeType = std::remove_const_t<TreeT>;
46  using RootNodeType = typename TreeType::RootNodeType;
47  using ValueType = typename TreeType::ValueType;
48  using MaskTreeType = typename TreeT::template ValueConverter<ValueMask>::Type;
49 
50  TreeToMerge() = delete;
51 
54  : mTree(&tree), mSteal(true) { }
56  TreeToMerge(typename TreeType::Ptr treePtr, Steal)
57  : mTreePtr(treePtr), mTree(mTreePtr.get()), mSteal(true) { }
58 
64  TreeToMerge(const TreeType& tree, DeepCopy, bool initialize = true)
65  : mTree(&tree), mSteal(false)
66  {
67  if (mTree && initialize) this->initializeMask();
68  }
69 
75  TreeToMerge(TreeType& tree, DeepCopy tag, bool initialize = true)
76  : TreeToMerge(static_cast<const TreeType&>(tree), tag, initialize) { }
77 
81  void reset(typename TreeType::Ptr treePtr, Steal);
82 
84  TreeType* treeToSteal() { return mSteal ? const_cast<TreeType*>(mTree) : nullptr; }
86  const TreeType* treeToDeepCopy() { return mSteal ? nullptr : mTree; }
87 
89  const RootNodeType* rootPtr() const;
90 
93  template<typename NodeT>
94  const NodeT* probeConstNode(const Coord& ijk) const;
95 
100  template <typename NodeT>
101  std::unique_ptr<NodeT> stealOrDeepCopyNode(const Coord& ijk);
102 
105  template <typename NodeT>
106  void addTile(const Coord& ijk, const ValueType& value, bool active);
107 
108  // build a lightweight mask using a union of the const tree where leaf nodes
109  // are converted into active tiles
110  void initializeMask();
111 
112  // returns true if mask has been initialized
113  bool hasMask() const;
114 
115  // returns MaskTree pointer or nullptr
116  MaskTreeType* mask() { return mMaskTree.ptr.get(); }
117  const MaskTreeType* mask() const { return mMaskTree.ptr.get(); }
118 
119 private:
120  struct MaskPtr;
121  struct MaskUnionOp;
122 
123  typename TreeType::Ptr mTreePtr;
124  const TreeType* mTree;
125  MaskPtr mMaskTree;
126  bool mSteal;
127 }; // struct TreeToMerge
128 
129 
131 template <typename TreeT>
132 struct TreeToMerge<TreeT>::MaskPtr
133 {
134  std::unique_ptr<MaskTreeType> ptr;
135 
136  MaskPtr() = default;
137  ~MaskPtr() = default;
138  MaskPtr(MaskPtr&& other) = default;
139  MaskPtr& operator=(MaskPtr&& other) = default;
140  MaskPtr(const MaskPtr& other)
141  : ptr(bool(other.ptr) ? std::make_unique<MaskTreeType>(*other.ptr) : nullptr) { }
142  MaskPtr& operator=(const MaskPtr& other)
143  {
144  ptr.reset(bool(other.ptr) ? std::make_unique<MaskTreeType>(*other.ptr) : nullptr);
145  return *this;
146  }
147 };
148 
151 template <typename TreeT>
152 struct TreeToMerge<TreeT>::MaskUnionOp
153 {
155  using RootT = typename MaskT::RootNodeType;
156  using LeafT = typename MaskT::LeafNodeType;
157 
158  explicit MaskUnionOp(const TreeT& tree) : mTree(tree) { }
159  bool operator()(RootT& root, size_t) const;
160  template<typename NodeT>
161  bool operator()(NodeT& node, size_t) const;
162  bool operator()(LeafT&, size_t) const { return false; }
163 private:
164  const TreeT& mTree;
165 }; // struct TreeToMerge<TreeT>::MaskUnionOp
166 
167 
169 
170 
177 template<typename TreeT, bool Union>
179 {
180  using ValueT = typename TreeT::ValueType;
181  using RootT = typename TreeT::RootNodeType;
182  using LeafT = typename TreeT::LeafNodeType;
183 
187  template <typename TagT>
188  CsgUnionOrIntersectionOp(TreeT& tree, TagT tag) { mTreesToMerge.emplace_back(tree, tag); }
189 
193  CsgUnionOrIntersectionOp(const TreeT& tree, DeepCopy tag) { mTreesToMerge.emplace_back(tree, tag); }
194 
199  template <typename TreesT, typename TagT>
200  CsgUnionOrIntersectionOp(TreesT& trees, TagT tag)
201  {
202  for (auto* tree : trees) {
203  if (tree) {
204  mTreesToMerge.emplace_back(*tree, tag);
205  }
206  }
207  }
208 
212  explicit CsgUnionOrIntersectionOp(const std::vector<TreeToMerge<TreeT>>& trees)
213  : mTreesToMerge(trees) { }
214 
218  explicit CsgUnionOrIntersectionOp(const std::deque<TreeToMerge<TreeT>>& trees)
219  : mTreesToMerge(trees.cbegin(), trees.cend()) { }
220 
222  bool empty() const { return mTreesToMerge.empty(); }
223 
225  size_t size() const { return mTreesToMerge.size(); }
226 
227  // Processes the root node. Required by the NodeManager
228  bool operator()(RootT& root, size_t idx) const;
229 
230  // Processes the internal nodes. Required by the NodeManager
231  template<typename NodeT>
232  bool operator()(NodeT& node, size_t idx) const;
233 
234  // Processes the leaf nodes. Required by the NodeManager
235  bool operator()(LeafT& leaf, size_t idx) const;
236 
237 private:
238  // on processing the root node, the background value is stored, retrieve it
239  // and check that the root node has already been processed
240  const ValueT& background() const;
241 
242  mutable std::vector<TreeToMerge<TreeT>> mTreesToMerge;
243  mutable const ValueT* mBackground = nullptr;
244 }; // struct CsgUnionOrIntersectionOp
245 
246 
247 template <typename TreeT>
248 using CsgUnionOp = CsgUnionOrIntersectionOp<TreeT, /*Union=*/true>;
249 
250 template <typename TreeT>
251 using CsgIntersectionOp = CsgUnionOrIntersectionOp<TreeT, /*Union=*/false>;
252 
253 
257 template<typename TreeT>
259 {
260  using ValueT = typename TreeT::ValueType;
261  using RootT = typename TreeT::RootNodeType;
262  using LeafT = typename TreeT::LeafNodeType;
263 
267  template <typename TagT>
268  CsgDifferenceOp(TreeT& tree, TagT tag) : mTree(tree, tag) { }
272  CsgDifferenceOp(const TreeT& tree, DeepCopy tag) : mTree(tree, tag) { }
273 
276  explicit CsgDifferenceOp(TreeToMerge<TreeT>& tree) : mTree(tree) { }
277 
279  size_t size() const { return 1; }
280 
281  // Processes the root node. Required by the NodeManager
282  bool operator()(RootT& root, size_t idx) const;
283 
284  // Processes the internal nodes. Required by the NodeManager
285  template<typename NodeT>
286  bool operator()(NodeT& node, size_t idx) const;
287 
288  // Processes the leaf nodes. Required by the NodeManager
289  bool operator()(LeafT& leaf, size_t idx) const;
290 
291 private:
292  // on processing the root node, the background values are stored, retrieve them
293  // and check that the root nodes have already been processed
294  const ValueT& background() const;
295  const ValueT& otherBackground() const;
296 
297  // note that this vector is copied in NodeTransformer every time a foreach call is made,
298  // however in typical use cases this cost will be dwarfed by the actual merge algorithm
299  mutable TreeToMerge<TreeT> mTree;
300  mutable const ValueT* mBackground = nullptr;
301  mutable const ValueT* mOtherBackground = nullptr;
302 }; // struct CsgDifferenceOp
303 
304 
306 
307 
308 template<typename TreeT>
310 {
311  if (mSteal) return;
312  mMaskTree.ptr.reset(new MaskTreeType);
313  MaskUnionOp op(*mTree);
314  tree::DynamicNodeManager<MaskTreeType, MaskTreeType::RootNodeType::LEVEL-1> manager(*this->mask());
315  manager.foreachTopDown(op);
316 }
317 
318 template<typename TreeT>
320 {
321  return bool(mMaskTree.ptr);
322 }
323 
324 template<typename TreeT>
325 void TreeToMerge<TreeT>::reset(typename TreeType::Ptr treePtr, Steal)
326 {
327  if (!treePtr) {
328  OPENVDB_THROW(RuntimeError, "Cannot reset with empty Tree shared pointer.");
329  }
330  mSteal = true;
331  mTreePtr = treePtr;
332  mTree = mTreePtr.get();
333 }
334 
335 template<typename TreeT>
336 const typename TreeToMerge<TreeT>::RootNodeType*
338 {
339  return &mTree->root();
340 }
341 
342 template<typename TreeT>
343 template<typename NodeT>
344 const NodeT*
346 {
347  // test mutable mask first, node may have already been pruned
348  if (!mSteal && !this->mask()->isValueOn(ijk)) return nullptr;
349  return mTree->template probeConstNode<NodeT>(ijk);
350 }
351 
352 template<typename TreeT>
353 template<typename NodeT>
354 std::unique_ptr<NodeT>
356 {
357  if (mSteal) {
358  TreeType* tree = const_cast<TreeType*>(mTree);
359  return std::unique_ptr<NodeT>(
360  tree->root().template stealNode<NodeT>(ijk, mTree->root().background(), false)
361  );
362  } else {
363  auto* child = this->probeConstNode<NodeT>(ijk);
364  if (child) {
365  assert(this->hasMask());
366  auto result = std::make_unique<NodeT>(*child);
367  // prune mask tree
368  this->mask()->addTile(NodeT::LEVEL, ijk, false, false);
369  return result;
370  }
371  }
372  return std::unique_ptr<NodeT>();
373 }
374 
375 template<typename TreeT>
376 template<typename NodeT>
377 void
378 TreeToMerge<TreeT>::addTile(const Coord& ijk, const ValueType& value, bool active)
379 {
380  // ignore leaf node tiles (values)
381  if (NodeT::LEVEL == 0) return;
382 
383  if (mSteal) {
384  TreeType* tree = const_cast<TreeType*>(mTree);
385  auto* node = tree->template probeNode<NodeT>(ijk);
386  if (node) {
387  const Index pos = NodeT::coordToOffset(ijk);
388  node->addTile(pos, value, active);
389  }
390  } else {
391  auto* node = mTree->template probeConstNode<NodeT>(ijk);
392  // prune mask tree
393  if (node) {
394  assert(this->hasMask());
395  this->mask()->addTile(NodeT::LEVEL, ijk, false, false);
396  }
397  }
398 }
399 
400 
402 
403 
404 template <typename TreeT>
405 bool TreeToMerge<TreeT>::MaskUnionOp::operator()(RootT& root, size_t /*idx*/) const
406 {
407  using ChildT = typename RootT::ChildNodeType;
408 
409  const Index count = mTree.root().childCount();
410 
411  std::vector<std::unique_ptr<ChildT>> children(count);
412 
413  // allocate new root children
414 
415  tbb::parallel_for(
416  tbb::blocked_range<Index>(0, count),
417  [&](tbb::blocked_range<Index>& range)
418  {
419  for (Index i = range.begin(); i < range.end(); i++) {
420  children[i] = std::make_unique<ChildT>(Coord::max(), true, true);
421  }
422  }
423  );
424 
425  // apply origins and add root children to new root node
426 
427  size_t i = 0;
428  for (auto iter = mTree.root().cbeginChildOn(); iter; ++iter) {
429  children[i]->setOrigin(iter->origin());
430  root.addChild(children[i].release());
431  i++;
432  }
433 
434  return true;
435 }
436 
437 template <typename TreeT>
438 template <typename NodeT>
439 bool TreeToMerge<TreeT>::MaskUnionOp::operator()(NodeT& node, size_t /*idx*/) const
440 {
441  using ChildT = typename NodeT::ChildNodeType;
442 
443  const auto* otherNode = mTree.template probeConstNode<NodeT>(node.origin());
444  if (!otherNode) return false;
445 
446  // this mask tree stores active tiles in place of leaf nodes for compactness
447 
448  if (NodeT::LEVEL == 1) {
449  for (auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
450  node.addTile(iter.pos(), true, true);
451  }
452  } else {
453  for (auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
454  auto* child = new ChildT(iter->origin(), true, true);
455  node.addChild(child);
456  }
457  }
458 
459  return true;
460 }
461 
462 
464 
465 
466 namespace merge_internal {
467 
468 
469 template <typename BufferT, typename ValueT>
471 {
472  static void allocateAndFill(BufferT& buffer, const ValueT& background)
473  {
474  if (!buffer.isOutOfCore() && buffer.empty()) {
475  buffer.allocate();
476  buffer.fill(background);
477  }
478  }
479 
480  static bool isPartiallyConstructed(const BufferT& buffer)
481  {
482  return !buffer.isOutOfCore() && buffer.empty();
483  }
484 }; // struct AllocateAndFillBuffer
485 
486 template <typename BufferT>
487 struct UnallocatedBuffer<BufferT, bool>
488 {
489  // do nothing for bool buffers as they cannot be unallocated
490  static void allocateAndFill(BufferT&, const bool&) { }
491  static bool isPartiallyConstructed(const BufferT&) { return false; }
492 }; // struct AllocateAndFillBuffer
493 
494 
495 } // namespace merge_internal
496 
497 
499 
500 
501 template <typename TreeT, bool Union>
503 {
504  const bool Intersect = !Union;
505 
506  if (this->empty()) return false;
507 
508  // store the background value
509  if (!mBackground) mBackground = &root.background();
510 
511  // does the key exist in the root node?
512  auto keyExistsInRoot = [&](const Coord& key) -> bool
513  {
514  return root.getValueDepth(key) > -1;
515  };
516 
517  // does the key exist in all merge tree root nodes?
518  auto keyExistsInAllTrees = [&](const Coord& key) -> bool
519  {
520  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
521  const auto* mergeRoot = mergeTree.rootPtr();
522  if (!mergeRoot) return false;
523  if (mergeRoot->getValueDepth(key) == -1) return false;
524  }
525  return true;
526  };
527 
528  // delete any background tiles
529  root.eraseBackgroundTiles();
530 
531  // for intersection, delete any root node keys that are not present in all trees
532  if (Intersect) {
533  // find all tile coordinates to delete
534  std::vector<Coord> toDelete;
535  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
536  const Coord& key = valueIter.getCoord();
537  if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
538  }
539  // find all child coordinates to delete
540  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
541  const Coord& key = childIter.getCoord();
542  if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
543  }
544  // only mechanism to delete elements in root node is to delete background tiles,
545  // so insert background tiles (which will replace any child nodes) and then delete
546  for (Coord& key : toDelete) root.addTile(key, *mBackground, false);
547  root.eraseBackgroundTiles();
548  }
549 
550  // find all tile values in this root and track inside/outside and active state
551  // note that level sets should never contain active tiles, but we handle them anyway
552 
553  constexpr uint8_t ACTIVE_TILE = 0x1;
554  constexpr uint8_t INSIDE_TILE = 0x2;
555  constexpr uint8_t OUTSIDE_TILE = 0x4;
556 
557  constexpr uint8_t INSIDE_STATE = Union ? INSIDE_TILE : OUTSIDE_TILE;
558  constexpr uint8_t OUTSIDE_STATE = Union ? OUTSIDE_TILE : INSIDE_TILE;
559 
560  const ValueT insideBackground = Union ? -this->background() : this->background();
561  const ValueT outsideBackground = -insideBackground;
562 
563  auto getTileFlag = [&](auto& valueIter) -> uint8_t
564  {
565  uint8_t flag(0);
566  const ValueT& value = valueIter.getValue();
567  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
568  else if (value > zeroVal<ValueT>()) flag |= OUTSIDE_TILE;
569  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
570  return flag;
571  };
572 
573  std::unordered_map<Coord, /*flags*/uint8_t> tiles;
574 
575  if (root.getTableSize() > 0) {
576  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
577  const Coord& key = valueIter.getCoord();
578  tiles.insert({key, getTileFlag(valueIter)});
579  }
580  }
581 
582  // find all tiles values in other roots and replace outside tiles with inside tiles
583 
584  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
585  const auto* mergeRoot = mergeTree.rootPtr();
586  if (!mergeRoot) continue;
587  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
588  const Coord& key = valueIter.getCoord();
589  auto it = tiles.find(key);
590  if (it == tiles.end()) {
591  // if no tile with this key, insert it
592  tiles.insert({key, getTileFlag(valueIter)});
593  } else {
594  // replace an outside tile with an inside tile
595  const uint8_t flag = it->second;
596  if (flag & OUTSIDE_STATE) {
597  const uint8_t newFlag = getTileFlag(valueIter);
598  if (newFlag & INSIDE_STATE) {
599  it->second = newFlag;
600  }
601  }
602  }
603  }
604  }
605 
606  // insert all inside tiles
607 
608  for (auto it : tiles) {
609  const uint8_t flag = it.second;
610  if (flag & INSIDE_STATE) {
611  const Coord& key = it.first;
612  const bool state = flag & ACTIVE_TILE;
613  // for intersection, only add the tile if the key already exists in the tree
614  if (Union || keyExistsInRoot(key)) {
615  root.addTile(key, insideBackground, state);
616  }
617  }
618  }
619 
620  std::unordered_set<Coord> children;
621 
622  if (root.getTableSize() > 0) {
623  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
624  const Coord& key = childIter.getCoord();
625  children.insert(key);
626  }
627  }
628 
629  bool continueRecurse = false;
630 
631  // find all children in other roots and insert them if a child or tile with this key
632  // does not already exist or if the child will replace an outside tile
633 
634  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
635  const auto* mergeRoot = mergeTree.rootPtr();
636  if (!mergeRoot) continue;
637  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
638  const Coord& key = childIter.getCoord();
639 
640  // for intersection, only add child nodes if the key already exists in the tree
641  if (Intersect && !keyExistsInRoot(key)) continue;
642 
643  // if child already exists, merge recursion will need to continue to resolve conflict
644  if (children.count(key)) {
645  continueRecurse = true;
646  continue;
647  }
648 
649  // if an inside tile exists, do nothing
650  auto it = tiles.find(key);
651  if (it != tiles.end() && it->second == INSIDE_STATE) continue;
652 
653  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
654  childPtr->resetBackground(mergeRoot->background(), root.background());
655  if (childPtr) root.addChild(childPtr.release());
656 
657  children.insert(key);
658  }
659  }
660 
661  // insert all outside tiles that don't replace an inside tile or a child node
662 
663  for (auto it : tiles) {
664  const uint8_t flag = it.second;
665  if (flag & OUTSIDE_STATE) {
666  const Coord& key = it.first;
667  if (!children.count(key)) {
668  const bool state = flag & ACTIVE_TILE;
669  // for intersection, only add the tile if the key already exists in the tree
670  if (Union || keyExistsInRoot(key)) {
671  root.addTile(key, outsideBackground, state);
672  }
673  }
674  }
675  }
676 
677  // finish by removing any background tiles
678  root.eraseBackgroundTiles();
679 
680  return continueRecurse;
681 }
682 
683 template<typename TreeT, bool Union>
684 template<typename NodeT>
686 {
687  using NonConstNodeT = typename std::remove_const<NodeT>::type;
688 
689  if (this->empty()) return false;
690 
691  const ValueT insideBackground = Union ? -this->background() : this->background();
692  const ValueT outsideBackground = -insideBackground;
693 
694  using NodeMaskT = typename NodeT::NodeMaskType;
695 
696  // store temporary masks to track inside and outside tile states
697  NodeMaskT validTile;
698  NodeMaskT invalidTile;
699 
700  auto isValid = [](const ValueT& value)
701  {
702  return Union ? value < zeroVal<ValueT>() : value > zeroVal<ValueT>();
703  };
704 
705  auto isInvalid = [](const ValueT& value)
706  {
707  return Union ? value > zeroVal<ValueT>() : value < zeroVal<ValueT>();
708  };
709 
710  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
711  if (isValid(iter.getValue())) {
712  validTile.setOn(iter.pos());
713  } else if (isInvalid(iter.getValue())) {
714  invalidTile.setOn(iter.pos());
715  }
716  }
717 
718  bool continueRecurse = false;
719 
720  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
721 
722  auto* mergeNode = mergeTree.template probeConstNode<NonConstNodeT>(node.origin());
723 
724  if (!mergeNode) continue;
725 
726  // iterate over all tiles
727 
728  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
729  Index pos = iter.pos();
730  // source node contains an inside tile, so ignore
731  if (validTile.isOn(pos)) continue;
732  // this node contains an inside tile, so turn into an inside tile
733  if (isValid(iter.getValue())) {
734  node.addTile(pos, insideBackground, iter.isValueOn());
735  validTile.setOn(pos);
736  }
737  }
738 
739  // iterate over all child nodes
740 
741  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
742  Index pos = iter.pos();
743  const Coord& ijk = iter.getCoord();
744  // source node contains an inside tile, so ensure other node has no child
745  if (validTile.isOn(pos)) {
746  mergeTree.template addTile<NonConstNodeT>(ijk, outsideBackground, false);
747  } else if (invalidTile.isOn(pos)) {
748  auto childPtr = mergeTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
749  if (childPtr) {
750  childPtr->resetBackground(mergeTree.rootPtr()->background(), this->background());
751  node.addChild(childPtr.release());
752  }
753  invalidTile.setOff(pos);
754  } else {
755  // if both source and target are child nodes, merge recursion needs to continue
756  // along this branch to resolve the conflict
757  continueRecurse = true;
758  }
759  }
760  }
761 
762  return continueRecurse;
763 }
764 
765 template <typename TreeT, bool Union>
767 {
768  using LeafT = typename TreeT::LeafNodeType;
769  using ValueT = typename LeafT::ValueType;
770  using BufferT = typename LeafT::Buffer;
771 
772  if (this->empty()) return false;
773 
774  const ValueT background = Union ? this->background() : -this->background();
775 
776  // if buffer is not out-of-core and empty, leaf node must have only been
777  // partially constructed, so allocate and fill with background value
778 
780  leaf.buffer(), background);
781 
782  for (TreeToMerge<TreeT>& mergeTree : mTreesToMerge) {
783  const LeafT* mergeLeaf = mergeTree.template probeConstNode<LeafT>(leaf.origin());
784  if (!mergeLeaf) continue;
785  // if buffer is not out-of-core yet empty, leaf node must have only been
786  // partially constructed, so skip merge
788  mergeLeaf->buffer())) {
789  continue;
790  }
791 
792  for (Index i = 0 ; i < LeafT::SIZE; i++) {
793  const ValueT& newValue = mergeLeaf->getValue(i);
794  const bool doMerge = Union ? newValue < leaf.getValue(i) : newValue > leaf.getValue(i);
795  if (doMerge) {
796  leaf.setValueOnly(i, newValue);
797  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
798  }
799  }
800  }
801 
802  return false;
803 }
804 
805 template <typename TreeT, bool Union>
808 {
809  // this operator is only intended to be used with foreachTopDown()
810  assert(mBackground);
811  return *mBackground;
812 }
813 
814 
816 
817 
818 template <typename TreeT>
819 bool CsgDifferenceOp<TreeT>::operator()(RootT& root, size_t) const
820 {
821  // store the background values
822  if (!mBackground) mBackground = &root.background();
823  if (!mOtherBackground) mOtherBackground = &mTree.rootPtr()->background();
824 
825  // find all tile values in this root and track inside/outside and active state
826  // note that level sets should never contain active tiles, but we handle them anyway
827 
828  constexpr uint8_t ACTIVE_TILE = 0x1;
829  constexpr uint8_t INSIDE_TILE = 0x2;
830  constexpr uint8_t CHILD = 0x4;
831 
832  auto getTileFlag = [&](auto& valueIter) -> uint8_t
833  {
834  uint8_t flag(0);
835  const ValueT& value = valueIter.getValue();
836  if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
837  if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
838  return flag;
839  };
840 
841  // delete any background tiles
842  root.eraseBackgroundTiles();
843 
844  std::unordered_map<Coord, /*flags*/uint8_t> flags;
845 
846  if (root.getTableSize() > 0) {
847  for (auto valueIter = root.cbeginValueAll(); valueIter; ++valueIter) {
848  const Coord& key = valueIter.getCoord();
849  const uint8_t flag = getTileFlag(valueIter);
850  if (flag & INSIDE_TILE) {
851  flags.insert({key, getTileFlag(valueIter)});
852  }
853  }
854 
855  for (auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
856  const Coord& key = childIter.getCoord();
857  flags.insert({key, CHILD});
858  }
859  }
860 
861  bool continueRecurse = false;
862 
863  const auto* mergeRoot = mTree.rootPtr();
864 
865  if (mergeRoot) {
866  for (auto valueIter = mergeRoot->cbeginValueAll(); valueIter; ++valueIter) {
867  const Coord& key = valueIter.getCoord();
868  const uint8_t flag = getTileFlag(valueIter);
869  if (flag & INSIDE_TILE) {
870  auto it = flags.find(key);
871  if (it != flags.end()) {
872  const bool state = flag & ACTIVE_TILE;
873  root.addTile(key, this->background(), state);
874  }
875  }
876  }
877 
878  for (auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
879  const Coord& key = childIter.getCoord();
880  auto it = flags.find(key);
881  if (it != flags.end()) {
882  const uint8_t otherFlag = it->second;
883  if (otherFlag & CHILD) {
884  // if child already exists, merge recursion will need to continue to resolve conflict
885  continueRecurse = true;
886  } else if (otherFlag & INSIDE_TILE) {
887  auto childPtr = mTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
888  if (childPtr) {
889  childPtr->resetBackground(this->otherBackground(), this->background());
890  childPtr->negate();
891  root.addChild(childPtr.release());
892  }
893  }
894  }
895  }
896  }
897 
898  // finish by removing any background tiles
899  root.eraseBackgroundTiles();
900 
901  return continueRecurse;
902 }
903 
904 template<typename TreeT>
905 template<typename NodeT>
906 bool CsgDifferenceOp<TreeT>::operator()(NodeT& node, size_t) const
907 {
908  using NonConstNodeT = typename std::remove_const<NodeT>::type;
909 
910  using NodeMaskT = typename NodeT::NodeMaskType;
911 
912  // store temporary mask to track inside tile state
913 
914  NodeMaskT insideTile;
915  for (auto iter = node.cbeginValueAll(); iter; ++iter) {
916  if (iter.getValue() < zeroVal<ValueT>()) {
917  insideTile.setOn(iter.pos());
918  }
919  }
920 
921  bool continueRecurse = false;
922 
923  auto* mergeNode = mTree.template probeConstNode<NonConstNodeT>(node.origin());
924 
925  if (!mergeNode) return continueRecurse;
926 
927  // iterate over all tiles
928 
929  for (auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
930  Index pos = iter.pos();
931  if (iter.getValue() < zeroVal<ValueT>()) {
932  if (insideTile.isOn(pos) || node.isChildMaskOn(pos)) {
933  node.addTile(pos, this->background(), iter.isValueOn());
934  }
935  }
936  }
937 
938  // iterate over all children
939 
940  for (auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
941  Index pos = iter.pos();
942  const Coord& ijk = iter.getCoord();
943  if (insideTile.isOn(pos)) {
944  auto childPtr = mTree.template stealOrDeepCopyNode<typename NodeT::ChildNodeType>(ijk);
945  if (childPtr) {
946  childPtr->resetBackground(this->otherBackground(), this->background());
947  childPtr->negate();
948  node.addChild(childPtr.release());
949  }
950  } else if (node.isChildMaskOn(pos)) {
951  // if both source and target are child nodes, merge recursion needs to continue
952  // along this branch to resolve the conflict
953  continueRecurse = true;
954  }
955  }
956 
957  return continueRecurse;
958 }
959 
960 template <typename TreeT>
961 bool CsgDifferenceOp<TreeT>::operator()(LeafT& leaf, size_t) const
962 {
963  using LeafT = typename TreeT::LeafNodeType;
964  using ValueT = typename LeafT::ValueType;
965  using BufferT = typename LeafT::Buffer;
966 
967  // if buffer is not out-of-core and empty, leaf node must have only been
968  // partially constructed, so allocate and fill with background value
969 
971  leaf.buffer(), this->background());
972 
973  const LeafT* mergeLeaf = mTree.template probeConstNode<LeafT>(leaf.origin());
974  if (!mergeLeaf) return false;
975 
976  // if buffer is not out-of-core yet empty, leaf node must have only been
977  // partially constructed, so skip merge
978 
980  mergeLeaf->buffer())) {
981  return false;
982  }
983 
984  for (Index i = 0 ; i < LeafT::SIZE; i++) {
985  const ValueT& aValue = leaf.getValue(i);
986  ValueT bValue = math::negative(mergeLeaf->getValue(i));
987  if (aValue < bValue) { // a = max(a, -b)
988  leaf.setValueOnly(i, bValue);
989  leaf.setActiveState(i, mergeLeaf->isValueOn(i));
990  }
991  }
992 
993  return false;
994 }
995 
996 template <typename TreeT>
997 const typename CsgDifferenceOp<TreeT>::ValueT&
999 {
1000  // this operator is only intended to be used with foreachTopDown()
1001  assert(mBackground);
1002  return *mBackground;
1003 }
1004 
1005 template <typename TreeT>
1006 const typename CsgDifferenceOp<TreeT>::ValueT&
1007 CsgDifferenceOp<TreeT>::otherBackground() const
1008 {
1009  // this operator is only intended to be used with foreachTopDown()
1010  assert(mOtherBackground);
1011  return *mOtherBackground;
1012 }
1013 
1014 
1015 } // namespace tools
1016 } // namespace OPENVDB_VERSION_NAME
1017 } // namespace openvdb
1018 
1019 #endif // OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
openvdb::v8_0::tools::merge_internal::UnallocatedBuffer::allocateAndFill
static void allocateAndFill(BufferT &buffer, const ValueT &background)
Definition: Merge.h:472
Types.h
openvdb::v8_0::initialize
OPENVDB_IMPORT void initialize()
Global registration of basic types.
openvdb::v8_0::RuntimeError
Definition: openvdb/Exceptions.h:63
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp::RootT
typename MaskT::RootNodeType RootT
Definition: Merge.h:155
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::CsgUnionOrIntersectionOp
CsgUnionOrIntersectionOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to CSG union or intersect a single const tree with another....
Definition: Merge.h:193
openvdb::v8_0::Index
Index32 Index
Definition: openvdb/Types.h:32
openvdb::v8_0::tools::CsgDifferenceOp::CsgDifferenceOp
CsgDifferenceOp(TreeT &tree, TagT tag)
Convenience constructor to CSG difference a single non-const tree from another. This constructor take...
Definition: Merge.h:268
NodeManager.h
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp::MaskT
MaskTreeType MaskT
Definition: Merge.h:154
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::CsgUnionOrIntersectionOp
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:218
openvdb::v8_0::tools::TreeToMerge::treeToSteal
TreeType * treeToSteal()
Return a pointer to the tree to be stolen.
Definition: Merge.h:84
openvdb::v8_0::tools::TreeToMerge::ValueType
typename TreeType::ValueType ValueType
Definition: Merge.h:47
openvdb::v8_0::tools::TreeToMerge::mask
const MaskTreeType * mask() const
Definition: Merge.h:117
openvdb::v8_0::tools::CsgDifferenceOp::ValueT
typename TreeT::ValueType ValueT
Definition: Merge.h:260
openvdb::v8_0::math::Coord
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:26
openvdb::v8_0::tools::TreeToMerge::MaskPtr::ptr
std::unique_ptr< MaskTreeType > ptr
Definition: Merge.h:134
openvdb::v8_0::tools::merge_internal::UnallocatedBuffer< BufferT, bool >::allocateAndFill
static void allocateAndFill(BufferT &, const bool &)
Definition: Merge.h:490
openvdb::v8_0::tools::CsgDifferenceOp::size
size_t size() const
Return the number of trees being merged (only ever 1)
Definition: Merge.h:279
openvdb::v8_0::tools::TreeToMerge::MaskPtr::operator=
MaskPtr & operator=(const MaskPtr &other)
Definition: Merge.h:142
openvdb::v8_0::tools::TreeToMerge::MaskTreeType
typename TreeT::template ValueConverter< ValueMask >::Type MaskTreeType
Definition: Merge.h:48
openvdb::v8_0::tools::CsgDifferenceOp
DynamicNodeManager operator to merge two trees using a CSG difference.
Definition: Merge.h:259
openvdb::v8_0::tools::TreeToMerge::TreeToMerge
TreeToMerge(TreeType &tree, Steal)
Non-const pointer tree constructor for stealing data.
Definition: Merge.h:53
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp::operator()
bool operator()(LeafT &, size_t) const
Definition: Merge.h:162
openvdb::v8_0::tools::TreeToMerge::MaskPtr::MaskPtr
MaskPtr()=default
OPENVDB_THROW
#define OPENVDB_THROW(exception, message)
Definition: openvdb/Exceptions.h:74
Platform.h
Grid.h
openvdb::v8_0::tree::DynamicNodeManager
Definition: NodeManager.h:858
openvdb::v8_0::tools::TreeToMerge::MaskPtr::~MaskPtr
~MaskPtr()=default
openvdb::v8_0::tools::TreeToMerge::treeToDeepCopy
const TreeType * treeToDeepCopy()
Return a pointer to the tree to be deep-copied.
Definition: Merge.h:86
openvdb::v8_0::tools::CsgDifferenceOp::CsgDifferenceOp
CsgDifferenceOp(const TreeT &tree, DeepCopy tag)
Convenience constructor to CSG difference a single const tree from another. This constructor requires...
Definition: Merge.h:272
openvdb::v8_0::tools::merge_internal::UnallocatedBuffer< BufferT, bool >::isPartiallyConstructed
static bool isPartiallyConstructed(const BufferT &)
Definition: Merge.h:491
openvdb::v8_0::tools::TreeToMerge::MaskPtr::operator=
MaskPtr & operator=(MaskPtr &&other)=default
openvdb::v8_0::tools::TreeToMerge::TreeToMerge
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:75
openvdb::v8_0::tools::TreeToMerge::TreeToMerge
TreeToMerge(typename TreeType::Ptr treePtr, Steal)
Non-const shared pointer tree constructor for stealing data.
Definition: Merge.h:56
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::size
size_t size() const
Return the number of trees being merged.
Definition: Merge.h:225
openvdb::v8_0::tools::TreeToMerge::mask
MaskTreeType * mask()
Definition: Merge.h:116
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp
DynamicNodeManager operator used to generate a mask of the input tree, but with dense leaf nodes repl...
Definition: Merge.h:153
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::RootT
typename TreeT::RootNodeType RootT
Definition: Merge.h:181
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::CsgUnionOrIntersectionOp
CsgUnionOrIntersectionOp(TreeT &tree, TagT tag)
Convenience constructor to CSG union or intersect a single non-const tree with another....
Definition: Merge.h:188
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp::LeafT
typename MaskT::LeafNodeType LeafT
Definition: Merge.h:156
openvdb::v8_0::tools::CsgUnionOrIntersectionOp
DynamicNodeManager operator to merge trees using a CSG union or intersection.
Definition: Merge.h:179
OPENVDB_USE_VERSION_NAMESPACE
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:153
openvdb::v8_0::tools::TreeToMerge::TreeToMerge
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:64
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::empty
bool empty() const
Return true if no trees being merged.
Definition: Merge.h:222
openvdb::v8_0::tools::merge_internal::UnallocatedBuffer::isPartiallyConstructed
static bool isPartiallyConstructed(const BufferT &buffer)
Definition: Merge.h:480
openvdb::v8_0::DeepCopy
Tag dispatch class that distinguishes constructors that deep copy.
Definition: openvdb/Types.h:544
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::LeafT
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:182
openvdb::v8_0::tools::TreeToMerge::reset
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:325
std
Definition: Coord.h:587
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::CsgUnionOrIntersectionOp
CsgUnionOrIntersectionOp(TreesT &trees, TagT tag)
Constructor to CSG union or intersect a container of multiple const or non-const tree pointers....
Definition: Merge.h:200
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::ValueT
typename TreeT::ValueType ValueT
Definition: Merge.h:180
openvdb::v8_0::tools::TreeToMerge::RootNodeType
typename TreeType::RootNodeType RootNodeType
Definition: Merge.h:46
openvdb::v8_0::tools::TreeToMerge::MaskPtr::MaskPtr
MaskPtr(const MaskPtr &other)
Definition: Merge.h:140
OPENVDB_VERSION_NAME
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:101
openvdb::v8_0::tools::TreeToMerge::TreeType
std::remove_const_t< TreeT > TreeType
Definition: Merge.h:45
openvdb::v8_0::tools::TreeToMerge::MaskUnionOp::MaskUnionOp
MaskUnionOp(const TreeT &tree)
Definition: Merge.h:158
openvdb::v8_0::tools::TreeToMerge::TreeToMerge
TreeToMerge()=delete
openvdb::v8_0::tools::CsgDifferenceOp::CsgDifferenceOp
CsgDifferenceOp(TreeToMerge< TreeT > &tree)
Constructor to CSG difference the tree in a TreeToMerge object from another.
Definition: Merge.h:276
openvdb::v8_0::tools::CsgUnionOrIntersectionOp::CsgUnionOrIntersectionOp
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:212
openvdb::v8_0::tools::TreeToMerge
Convenience class that contains a pointer to a tree to be stolen or deep copied depending on the tag ...
Definition: Merge.h:44
openvdb
Definition: openvdb/Exceptions.h:13
Exceptions.h
openvdb::v8_0::tools::TreeToMerge::MaskPtr
Wrapper around unique_ptr that deep-copies mask on copy construction.
Definition: Merge.h:133
openvdb::v8_0::tools::merge_internal::UnallocatedBuffer
Definition: Merge.h:471
openvdb::v8_0::tools::CsgDifferenceOp::RootT
typename TreeT::RootNodeType RootT
Definition: Merge.h:261
openvdb::v8_0::math::negative
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
openvdb::v8_0::tools::CsgDifferenceOp::LeafT
typename TreeT::LeafNodeType LeafT
Definition: Merge.h:262
openvdb::v8_0::Steal
Tag dispatch class that distinguishes constructors that steal.
Definition: openvdb/Types.h:546
openvdb::v8_0::tools::TreeToMerge::MaskPtr::MaskPtr
MaskPtr(MaskPtr &&other)=default