10 #ifndef OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED
19 #include <unordered_map>
20 #include <unordered_set>
42 template <
typename TreeT>
48 using MaskTreeType =
typename TreeT::template ValueConverter<ValueMask>::Type;
54 : mTree(&tree), mSteal(true) { }
57 : mTreePtr(treePtr), mTree(mTreePtr.get()), mSteal(true) { }
65 : mTree(&tree), mSteal(false)
67 if (mTree &&
initialize) this->initializeMask();
81 void reset(
typename TreeType::Ptr treePtr,
Steal);
89 const RootNodeType* rootPtr()
const;
93 template<
typename NodeT>
94 const NodeT* probeConstNode(
const Coord& ijk)
const;
100 template <
typename NodeT>
101 std::unique_ptr<NodeT> stealOrDeepCopyNode(
const Coord& ijk);
105 template <
typename NodeT>
106 void addTile(
const Coord& ijk,
const ValueType& value,
bool active);
110 void initializeMask();
113 bool hasMask()
const;
123 typename TreeType::Ptr mTreePtr;
124 const TreeType* mTree;
131 template <
typename TreeT>
134 std::unique_ptr<MaskTreeType>
ptr;
141 : ptr(bool(other.ptr) ?
std::make_unique<
MaskTreeType>(*other.ptr) : nullptr) { }
144 ptr.reset(
bool(other.
ptr) ? std::make_unique<MaskTreeType>(*other.
ptr) :
nullptr);
151 template <
typename TreeT>
155 using RootT =
typename MaskT::RootNodeType;
156 using LeafT =
typename MaskT::LeafNodeType;
159 bool operator()(RootT& root,
size_t)
const;
160 template<
typename NodeT>
161 bool operator()(NodeT& node,
size_t)
const;
177 template<
typename TreeT,
bool Union>
180 using ValueT =
typename TreeT::ValueType;
181 using RootT =
typename TreeT::RootNodeType;
182 using LeafT =
typename TreeT::LeafNodeType;
187 template <
typename TagT>
199 template <
typename TreesT,
typename TagT>
202 for (
auto* tree : trees) {
204 mTreesToMerge.emplace_back(*tree, tag);
213 : mTreesToMerge(trees) { }
219 : mTreesToMerge(trees.cbegin(), trees.cend()) { }
222 bool empty()
const {
return mTreesToMerge.empty(); }
225 size_t size()
const {
return mTreesToMerge.size(); }
228 bool operator()(RootT& root,
size_t idx)
const;
231 template<
typename NodeT>
232 bool operator()(NodeT& node,
size_t idx)
const;
235 bool operator()(LeafT& leaf,
size_t idx)
const;
240 const ValueT& background()
const;
242 mutable std::vector<TreeToMerge<TreeT>> mTreesToMerge;
243 mutable const ValueT* mBackground =
nullptr;
247 template <
typename TreeT>
250 template <
typename TreeT>
257 template<
typename TreeT>
260 using ValueT =
typename TreeT::ValueType;
261 using RootT =
typename TreeT::RootNodeType;
262 using LeafT =
typename TreeT::LeafNodeType;
267 template <
typename TagT>
279 size_t size()
const {
return 1; }
282 bool operator()(RootT& root,
size_t idx)
const;
285 template<
typename NodeT>
286 bool operator()(NodeT& node,
size_t idx)
const;
289 bool operator()(LeafT& leaf,
size_t idx)
const;
294 const ValueT& background()
const;
295 const ValueT& otherBackground()
const;
300 mutable const ValueT* mBackground =
nullptr;
301 mutable const ValueT* mOtherBackground =
nullptr;
308 template<
typename TreeT>
315 manager.foreachTopDown(op);
318 template<
typename TreeT>
321 return bool(mMaskTree.ptr);
324 template<
typename TreeT>
332 mTree = mTreePtr.get();
335 template<
typename TreeT>
339 return &mTree->root();
342 template<
typename TreeT>
343 template<
typename NodeT>
348 if (!mSteal && !this->mask()->isValueOn(ijk))
return nullptr;
349 return mTree->template probeConstNode<NodeT>(ijk);
352 template<
typename TreeT>
353 template<
typename NodeT>
354 std::unique_ptr<NodeT>
359 return std::unique_ptr<NodeT>(
360 tree->root().template stealNode<NodeT>(ijk, mTree->root().background(),
false)
363 auto* child = this->probeConstNode<NodeT>(ijk);
365 assert(this->hasMask());
366 auto result = std::make_unique<NodeT>(*child);
368 this->mask()->addTile(NodeT::LEVEL, ijk,
false,
false);
372 return std::unique_ptr<NodeT>();
375 template<
typename TreeT>
376 template<
typename NodeT>
381 if (NodeT::LEVEL == 0)
return;
385 auto* node = tree->template probeNode<NodeT>(ijk);
387 const Index pos = NodeT::coordToOffset(ijk);
388 node->addTile(pos, value, active);
391 auto* node = mTree->template probeConstNode<NodeT>(ijk);
394 assert(this->hasMask());
395 this->mask()->addTile(NodeT::LEVEL, ijk,
false,
false);
404 template <
typename TreeT>
407 using ChildT =
typename RootT::ChildNodeType;
409 const Index count = mTree.root().childCount();
411 std::vector<std::unique_ptr<ChildT>> children(count);
416 tbb::blocked_range<Index>(0, count),
417 [&](tbb::blocked_range<Index>& range)
419 for (
Index i = range.begin(); i < range.end(); i++) {
420 children[i] = std::make_unique<ChildT>(Coord::max(), true, true);
428 for (
auto iter = mTree.root().cbeginChildOn(); iter; ++iter) {
429 children[i]->setOrigin(iter->origin());
430 root.addChild(children[i].release());
437 template <
typename TreeT>
438 template <
typename NodeT>
441 using ChildT =
typename NodeT::ChildNodeType;
443 const auto* otherNode = mTree.template probeConstNode<NodeT>(node.origin());
444 if (!otherNode)
return false;
448 if (NodeT::LEVEL == 1) {
449 for (
auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
450 node.addTile(iter.pos(),
true,
true);
453 for (
auto iter = otherNode->cbeginChildOn(); iter; ++iter) {
454 auto* child =
new ChildT(iter->origin(),
true,
true);
455 node.addChild(child);
466 namespace merge_internal {
469 template <
typename BufferT,
typename ValueT>
474 if (!buffer.isOutOfCore() && buffer.empty()) {
476 buffer.fill(background);
482 return !buffer.isOutOfCore() && buffer.empty();
486 template <
typename BufferT>
501 template <
typename TreeT,
bool Union>
504 const bool Intersect = !Union;
506 if (this->empty())
return false;
509 if (!mBackground) mBackground = &root.background();
512 auto keyExistsInRoot = [&](
const Coord& key) ->
bool
514 return root.getValueDepth(key) > -1;
518 auto keyExistsInAllTrees = [&](
const Coord& key) ->
bool
521 const auto* mergeRoot = mergeTree.rootPtr();
522 if (!mergeRoot)
return false;
523 if (mergeRoot->getValueDepth(key) == -1)
return false;
529 root.eraseBackgroundTiles();
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);
540 for (
auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
541 const Coord& key = childIter.getCoord();
542 if (!keyExistsInAllTrees(key)) toDelete.push_back(key);
546 for (
Coord& key : toDelete) root.addTile(key, *mBackground,
false);
547 root.eraseBackgroundTiles();
553 constexpr uint8_t ACTIVE_TILE = 0x1;
554 constexpr uint8_t INSIDE_TILE = 0x2;
555 constexpr uint8_t OUTSIDE_TILE = 0x4;
557 constexpr uint8_t INSIDE_STATE = Union ? INSIDE_TILE : OUTSIDE_TILE;
558 constexpr uint8_t OUTSIDE_STATE = Union ? OUTSIDE_TILE : INSIDE_TILE;
560 const ValueT insideBackground = Union ? -this->background() : this->background();
561 const ValueT outsideBackground = -insideBackground;
563 auto getTileFlag = [&](
auto& valueIter) -> uint8_t
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;
573 std::unordered_map<
Coord, uint8_t> tiles;
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)});
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()) {
592 tiles.insert({key, getTileFlag(valueIter)});
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;
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;
614 if (Union || keyExistsInRoot(key)) {
615 root.addTile(key, insideBackground, state);
620 std::unordered_set<Coord> children;
622 if (root.getTableSize() > 0) {
623 for (
auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
624 const Coord& key = childIter.getCoord();
625 children.insert(key);
629 bool continueRecurse =
false;
635 const auto* mergeRoot = mergeTree.rootPtr();
636 if (!mergeRoot)
continue;
637 for (
auto childIter = mergeRoot->cbeginChildOn(); childIter; ++childIter) {
638 const Coord& key = childIter.getCoord();
641 if (Intersect && !keyExistsInRoot(key))
continue;
644 if (children.count(key)) {
645 continueRecurse =
true;
650 auto it = tiles.find(key);
651 if (it != tiles.end() && it->second == INSIDE_STATE)
continue;
653 auto childPtr = mergeTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
654 childPtr->resetBackground(mergeRoot->background(), root.background());
655 if (childPtr) root.addChild(childPtr.release());
657 children.insert(key);
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;
670 if (Union || keyExistsInRoot(key)) {
671 root.addTile(key, outsideBackground, state);
678 root.eraseBackgroundTiles();
680 return continueRecurse;
683 template<
typename TreeT,
bool Union>
684 template<
typename NodeT>
687 using NonConstNodeT =
typename std::remove_const<NodeT>::type;
689 if (this->empty())
return false;
691 const ValueT insideBackground = Union ? -this->background() : this->background();
692 const ValueT outsideBackground = -insideBackground;
694 using NodeMaskT =
typename NodeT::NodeMaskType;
698 NodeMaskT invalidTile;
700 auto isValid = [](
const ValueT& value)
702 return Union ? value < zeroVal<ValueT>() : value > zeroVal<ValueT>();
705 auto isInvalid = [](
const ValueT& value)
707 return Union ? value > zeroVal<ValueT>() : value < zeroVal<ValueT>();
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());
718 bool continueRecurse =
false;
722 auto* mergeNode = mergeTree.template probeConstNode<NonConstNodeT>(node.origin());
724 if (!mergeNode)
continue;
728 for (
auto iter = mergeNode->cbeginValueAll(); iter; ++iter) {
729 Index pos = iter.pos();
731 if (validTile.isOn(pos))
continue;
733 if (isValid(iter.getValue())) {
734 node.addTile(pos, insideBackground, iter.isValueOn());
735 validTile.setOn(pos);
741 for (
auto iter = mergeNode->cbeginChildOn(); iter; ++iter) {
742 Index pos = iter.pos();
743 const Coord& ijk = iter.getCoord();
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);
750 childPtr->resetBackground(mergeTree.rootPtr()->background(), this->background());
751 node.addChild(childPtr.release());
753 invalidTile.setOff(pos);
757 continueRecurse =
true;
762 return continueRecurse;
765 template <
typename TreeT,
bool Union>
768 using LeafT =
typename TreeT::LeafNodeType;
769 using ValueT =
typename LeafT::ValueType;
770 using BufferT =
typename LeafT::Buffer;
772 if (this->empty())
return false;
774 const ValueT background = Union ? this->background() : -this->background();
780 leaf.buffer(), background);
783 const LeafT* mergeLeaf = mergeTree.template probeConstNode<LeafT>(leaf.origin());
784 if (!mergeLeaf)
continue;
788 mergeLeaf->buffer())) {
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);
796 leaf.setValueOnly(i, newValue);
797 leaf.setActiveState(i, mergeLeaf->isValueOn(i));
805 template <
typename TreeT,
bool Union>
818 template <
typename TreeT>
822 if (!mBackground) mBackground = &root.background();
823 if (!mOtherBackground) mOtherBackground = &mTree.rootPtr()->background();
828 constexpr uint8_t ACTIVE_TILE = 0x1;
829 constexpr uint8_t INSIDE_TILE = 0x2;
830 constexpr uint8_t CHILD = 0x4;
832 auto getTileFlag = [&](
auto& valueIter) -> uint8_t
835 const ValueT& value = valueIter.getValue();
836 if (value < zeroVal<ValueT>()) flag |= INSIDE_TILE;
837 if (valueIter.isValueOn()) flag |= ACTIVE_TILE;
842 root.eraseBackgroundTiles();
844 std::unordered_map<
Coord, uint8_t> flags;
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)});
855 for (
auto childIter = root.cbeginChildOn(); childIter; ++childIter) {
856 const Coord& key = childIter.getCoord();
857 flags.insert({key, CHILD});
861 bool continueRecurse =
false;
863 const auto* mergeRoot = mTree.rootPtr();
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);
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) {
885 continueRecurse =
true;
886 }
else if (otherFlag & INSIDE_TILE) {
887 auto childPtr = mTree.template stealOrDeepCopyNode<typename RootT::ChildNodeType>(key);
889 childPtr->resetBackground(this->otherBackground(), this->background());
891 root.addChild(childPtr.release());
899 root.eraseBackgroundTiles();
901 return continueRecurse;
904 template<
typename TreeT>
905 template<
typename NodeT>
908 using NonConstNodeT =
typename std::remove_const<NodeT>::type;
910 using NodeMaskT =
typename NodeT::NodeMaskType;
914 NodeMaskT insideTile;
915 for (
auto iter = node.cbeginValueAll(); iter; ++iter) {
916 if (iter.getValue() < zeroVal<ValueT>()) {
917 insideTile.setOn(iter.pos());
921 bool continueRecurse =
false;
923 auto* mergeNode = mTree.template probeConstNode<NonConstNodeT>(node.origin());
925 if (!mergeNode)
return continueRecurse;
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());
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);
946 childPtr->resetBackground(this->otherBackground(), this->background());
948 node.addChild(childPtr.release());
950 }
else if (node.isChildMaskOn(pos)) {
953 continueRecurse =
true;
957 return continueRecurse;
960 template <
typename TreeT>
963 using LeafT =
typename TreeT::LeafNodeType;
964 using ValueT =
typename LeafT::ValueType;
965 using BufferT =
typename LeafT::Buffer;
971 leaf.buffer(), this->background());
973 const LeafT* mergeLeaf = mTree.template probeConstNode<LeafT>(leaf.origin());
974 if (!mergeLeaf)
return false;
980 mergeLeaf->buffer())) {
984 for (
Index i = 0 ; i < LeafT::SIZE; i++) {
985 const ValueT& aValue = leaf.getValue(i);
987 if (aValue < bValue) {
988 leaf.setValueOnly(i, bValue);
989 leaf.setActiveState(i, mergeLeaf->isValueOn(i));
996 template <
typename TreeT>
1001 assert(mBackground);
1002 return *mBackground;
1005 template <
typename TreeT>
1006 const typename CsgDifferenceOp<TreeT>::ValueT&
1007 CsgDifferenceOp<TreeT>::otherBackground()
const
1010 assert(mOtherBackground);
1011 return *mOtherBackground;
1019 #endif // OPENVDB_TOOLS_MERGE_HAS_BEEN_INCLUDED