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