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