OpenVDB  8.0.1
Composite.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
9 
10 #ifndef OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
11 #define OPENVDB_TOOLS_COMPOSITE_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/math/Math.h> // for isExactlyEqual()
18 #include "Merge.h"
19 #include "ValueTransformer.h" // for transformValues()
20 #include "Prune.h"// for prune
21 #include "SignedFloodFill.h" // for signedFloodFill()
22 
23 #include <tbb/blocked_range.h>
24 #include <tbb/parallel_for.h>
25 #include <tbb/parallel_reduce.h>
26 #include <tbb/task_group.h>
27 #include <tbb/task_scheduler_init.h>
28 
29 #include <type_traits>
30 #include <functional>
31 
32 namespace openvdb {
34 namespace OPENVDB_VERSION_NAME {
35 namespace tools {
36 
40 template<typename GridOrTreeT>
41 inline void csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
45 template<typename GridOrTreeT>
46 inline void csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
50 template<typename GridOrTreeT>
51 inline void csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
52 
56 template<typename GridOrTreeT>
57 inline typename GridOrTreeT::Ptr csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
61 template<typename GridOrTreeT>
62 inline typename GridOrTreeT::Ptr csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
66 template<typename GridOrTreeT>
67 inline typename GridOrTreeT::Ptr csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b);
68 
71 template<typename GridOrTreeT>
72 inline void compMax(GridOrTreeT& a, GridOrTreeT& b);
75 template<typename GridOrTreeT>
76 inline void compMin(GridOrTreeT& a, GridOrTreeT& b);
79 template<typename GridOrTreeT>
80 inline void compSum(GridOrTreeT& a, GridOrTreeT& b);
83 template<typename GridOrTreeT>
84 inline void compMul(GridOrTreeT& a, GridOrTreeT& b);
87 template<typename GridOrTreeT>
88 inline void compDiv(GridOrTreeT& a, GridOrTreeT& b);
89 
91 template<typename GridOrTreeT>
92 inline void compReplace(GridOrTreeT& a, const GridOrTreeT& b);
93 
94 
96 
97 
98 namespace composite {
99 
100 // composite::min() and composite::max() for non-vector types compare with operator<().
101 template<typename T> inline
102 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type& // = T if T is not a vector type
103 min(const T& a, const T& b) { return std::min(a, b); }
104 
105 template<typename T> inline
106 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type&
107 max(const T& a, const T& b) { return std::max(a, b); }
108 
109 
110 // composite::min() and composite::max() for OpenVDB vector types compare by magnitude.
111 template<typename T> inline
112 const typename std::enable_if<VecTraits<T>::IsVec, T>::type& // = T if T is a vector type
113 min(const T& a, const T& b)
114 {
115  const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
116  return (aMag < bMag ? a : (bMag < aMag ? b : std::min(a, b)));
117 }
118 
119 template<typename T> inline
120 const typename std::enable_if<VecTraits<T>::IsVec, T>::type&
121 max(const T& a, const T& b)
122 {
123  const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
124  return (aMag < bMag ? b : (bMag < aMag ? a : std::max(a, b)));
125 }
126 
127 
128 template<typename T> inline
129 typename std::enable_if<!std::is_integral<T>::value, T>::type // = T if T is not an integer type
130 divide(const T& a, const T& b) { return a / b; }
131 
132 template<typename T> inline
133 typename std::enable_if<std::is_integral<T>::value, T>::type // = T if T is an integer type
134 divide(const T& a, const T& b)
135 {
136  const T zero(0);
137  if (b != zero) return a / b;
138  if (a == zero) return 0;
140 }
141 
142 // If b is true, return a / 1 = a.
143 // If b is false and a is true, return 1 / 0 = inf = MAX_BOOL = 1 = a.
144 // If b is false and a is false, return 0 / 0 = NaN = 0 = a.
145 inline bool divide(bool a, bool /*b*/) { return a; }
146 
147 
149 
150 template<typename TreeType, CSGOperation Operation>
152 {
153  using ValueType = typename TreeType::ValueType;
154  using TreePtrType = typename TreeType::Ptr;
155  using LeafNodeType = typename TreeType::LeafNodeType;
156  using NodeMaskType = typename LeafNodeType::NodeMaskType;
157  using RootNodeType = typename TreeType::RootNodeType;
158  using NodeChainType = typename RootNodeType::NodeChainType;
159  using InternalNodeType = typename NodeChainType::template Get<1>;
160 
161  BuildPrimarySegment(const TreeType& lhs, const TreeType& rhs)
162  : mSegment(new TreeType(lhs.background()))
163  , mLhsTree(&lhs)
164  , mRhsTree(&rhs)
165  {
166  }
167 
168  void operator()() const
169  {
170  std::vector<const LeafNodeType*> leafNodes;
171 
172  {
173  std::vector<const InternalNodeType*> internalNodes;
174  mLhsTree->getNodes(internalNodes);
175 
176  ProcessInternalNodes op(internalNodes, *mRhsTree, *mSegment, leafNodes);
177  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
178  }
179 
180  ProcessLeafNodes op(leafNodes, *mRhsTree, *mSegment);
181  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
182  }
183 
184  TreePtrType& segment() { return mSegment; }
185 
186 private:
187 
188  struct ProcessInternalNodes {
189 
190  ProcessInternalNodes(std::vector<const InternalNodeType*>& lhsNodes,
191  const TreeType& rhsTree, TreeType& outputTree,
192  std::vector<const LeafNodeType*>& outputLeafNodes)
193  : mLhsNodes(lhsNodes.empty() ? nullptr : &lhsNodes.front())
194  , mRhsTree(&rhsTree)
195  , mLocalTree(mRhsTree->background())
196  , mOutputTree(&outputTree)
197  , mLocalLeafNodes()
198  , mOutputLeafNodes(&outputLeafNodes)
199  {
200  }
201 
202  ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
203  : mLhsNodes(other.mLhsNodes)
204  , mRhsTree(other.mRhsTree)
205  , mLocalTree(mRhsTree->background())
206  , mOutputTree(&mLocalTree)
207  , mLocalLeafNodes()
208  , mOutputLeafNodes(&mLocalLeafNodes)
209  {
210  }
211 
212  void join(ProcessInternalNodes& other)
213  {
214  mOutputTree->merge(*other.mOutputTree);
215  mOutputLeafNodes->insert(mOutputLeafNodes->end(),
216  other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
217  }
218 
219  void operator()(const tbb::blocked_range<size_t>& range)
220  {
221  tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
222  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
223 
224  std::vector<const LeafNodeType*> tmpLeafNodes;
225 
226  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
227 
228  const InternalNodeType& lhsNode = *mLhsNodes[n];
229  const Coord& ijk = lhsNode.origin();
230  const InternalNodeType * rhsNode =
231  rhsAcc.template probeConstNode<InternalNodeType>(ijk);
232 
233  if (rhsNode) {
234  lhsNode.getNodes(*mOutputLeafNodes);
235  } else {
236  if (Operation == CSG_INTERSECTION) {
237  if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
238  tmpLeafNodes.clear();
239  lhsNode.getNodes(tmpLeafNodes);
240  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
241  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
242  }
243  }
244  } else { // Union & Difference
245  if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
246  tmpLeafNodes.clear();
247  lhsNode.getNodes(tmpLeafNodes);
248  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
249  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
250  }
251  }
252  }
253  }
254  } // end range loop
255  }
256 
257  InternalNodeType const * const * const mLhsNodes;
258  TreeType const * const mRhsTree;
259  TreeType mLocalTree;
260  TreeType * const mOutputTree;
261 
262  std::vector<const LeafNodeType*> mLocalLeafNodes;
263  std::vector<const LeafNodeType*> * const mOutputLeafNodes;
264  }; // struct ProcessInternalNodes
265 
266  struct ProcessLeafNodes {
267 
268  ProcessLeafNodes(std::vector<const LeafNodeType*>& lhsNodes,
269  const TreeType& rhsTree, TreeType& output)
270  : mLhsNodes(lhsNodes.empty() ? nullptr : &lhsNodes.front())
271  , mRhsTree(&rhsTree)
272  , mLocalTree(mRhsTree->background())
273  , mOutputTree(&output)
274  {
275  }
276 
277  ProcessLeafNodes(ProcessLeafNodes& other, tbb::split)
278  : mLhsNodes(other.mLhsNodes)
279  , mRhsTree(other.mRhsTree)
280  , mLocalTree(mRhsTree->background())
281  , mOutputTree(&mLocalTree)
282  {
283  }
284 
285  void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
286 
287  void operator()(const tbb::blocked_range<size_t>& range)
288  {
289  tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
290  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
291 
292  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
293 
294  const LeafNodeType& lhsNode = *mLhsNodes[n];
295  const Coord& ijk = lhsNode.origin();
296 
297  const LeafNodeType* rhsNodePt = rhsAcc.probeConstLeaf(ijk);
298 
299  if (rhsNodePt) { // combine overlapping nodes
300 
301  LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
302  ValueType * outputData = outputNode->buffer().data();
303  NodeMaskType& outputMask = outputNode->getValueMask();
304 
305  const ValueType * lhsData = lhsNode.buffer().data();
306  const NodeMaskType& lhsMask = lhsNode.getValueMask();
307 
308  const ValueType * rhsData = rhsNodePt->buffer().data();
309  const NodeMaskType& rhsMask = rhsNodePt->getValueMask();
310 
311  if (Operation == CSG_INTERSECTION) {
312  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
313  const bool fromRhs = lhsData[pos] < rhsData[pos];
314  outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
315  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
316  }
317  } else if (Operation == CSG_DIFFERENCE){
318  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
319  const ValueType rhsVal = math::negative(rhsData[pos]);
320  const bool fromRhs = lhsData[pos] < rhsVal;
321  outputData[pos] = fromRhs ? rhsVal : lhsData[pos];
322  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
323  }
324  } else { // Union
325  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
326  const bool fromRhs = lhsData[pos] > rhsData[pos];
327  outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
328  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
329  }
330  }
331 
332  } else {
333  if (Operation == CSG_INTERSECTION) {
334  if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
335  outputAcc.addLeaf(new LeafNodeType(lhsNode));
336  }
337  } else { // Union & Difference
338  if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
339  outputAcc.addLeaf(new LeafNodeType(lhsNode));
340  }
341  }
342  }
343  } // end range loop
344  }
345 
346  LeafNodeType const * const * const mLhsNodes;
347  TreeType const * const mRhsTree;
348  TreeType mLocalTree;
349  TreeType * const mOutputTree;
350  }; // struct ProcessLeafNodes
351 
352  TreePtrType mSegment;
353  TreeType const * const mLhsTree;
354  TreeType const * const mRhsTree;
355 }; // struct BuildPrimarySegment
356 
357 
358 template<typename TreeType, CSGOperation Operation>
360 {
361  using ValueType = typename TreeType::ValueType;
362  using TreePtrType = typename TreeType::Ptr;
363  using LeafNodeType = typename TreeType::LeafNodeType;
364  using NodeMaskType = typename LeafNodeType::NodeMaskType;
365  using RootNodeType = typename TreeType::RootNodeType;
366  using NodeChainType = typename RootNodeType::NodeChainType;
367  using InternalNodeType = typename NodeChainType::template Get<1>;
368 
369  BuildSecondarySegment(const TreeType& lhs, const TreeType& rhs)
370  : mSegment(new TreeType(lhs.background()))
371  , mLhsTree(&lhs)
372  , mRhsTree(&rhs)
373  {
374  }
375 
376  void operator()() const
377  {
378  std::vector<const LeafNodeType*> leafNodes;
379 
380  {
381  std::vector<const InternalNodeType*> internalNodes;
382  mRhsTree->getNodes(internalNodes);
383 
384  ProcessInternalNodes op(internalNodes, *mLhsTree, *mSegment, leafNodes);
385  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
386  }
387 
388  ProcessLeafNodes op(leafNodes, *mLhsTree, *mSegment);
389  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
390  }
391 
392  TreePtrType& segment() { return mSegment; }
393 
394 private:
395 
396  struct ProcessInternalNodes {
397 
398  ProcessInternalNodes(std::vector<const InternalNodeType*>& rhsNodes,
399  const TreeType& lhsTree, TreeType& outputTree,
400  std::vector<const LeafNodeType*>& outputLeafNodes)
401  : mRhsNodes(rhsNodes.empty() ? nullptr : &rhsNodes.front())
402  , mLhsTree(&lhsTree)
403  , mLocalTree(mLhsTree->background())
404  , mOutputTree(&outputTree)
405  , mLocalLeafNodes()
406  , mOutputLeafNodes(&outputLeafNodes)
407  {
408  }
409 
410  ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
411  : mRhsNodes(other.mRhsNodes)
412  , mLhsTree(other.mLhsTree)
413  , mLocalTree(mLhsTree->background())
414  , mOutputTree(&mLocalTree)
415  , mLocalLeafNodes()
416  , mOutputLeafNodes(&mLocalLeafNodes)
417  {
418  }
419 
420  void join(ProcessInternalNodes& other)
421  {
422  mOutputTree->merge(*other.mOutputTree);
423  mOutputLeafNodes->insert(mOutputLeafNodes->end(),
424  other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
425  }
426 
427  void operator()(const tbb::blocked_range<size_t>& range)
428  {
429  tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
430  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
431 
432  std::vector<const LeafNodeType*> tmpLeafNodes;
433 
434  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
435 
436  const InternalNodeType& rhsNode = *mRhsNodes[n];
437  const Coord& ijk = rhsNode.origin();
438  const InternalNodeType * lhsNode =
439  lhsAcc.template probeConstNode<InternalNodeType>(ijk);
440 
441  if (lhsNode) {
442  rhsNode.getNodes(*mOutputLeafNodes);
443  } else {
444  if (Operation == CSG_INTERSECTION) {
445  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
446  tmpLeafNodes.clear();
447  rhsNode.getNodes(tmpLeafNodes);
448  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
449  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
450  }
451  }
452  } else if (Operation == CSG_DIFFERENCE) {
453  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
454  tmpLeafNodes.clear();
455  rhsNode.getNodes(tmpLeafNodes);
456  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
457  LeafNodeType* outputNode = new LeafNodeType(*tmpLeafNodes[i]);
458  outputNode->negate();
459  outputAcc.addLeaf(outputNode);
460  }
461  }
462  } else { // Union
463  if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
464  tmpLeafNodes.clear();
465  rhsNode.getNodes(tmpLeafNodes);
466  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
467  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
468  }
469  }
470  }
471  }
472  } // end range loop
473  }
474 
475  InternalNodeType const * const * const mRhsNodes;
476  TreeType const * const mLhsTree;
477  TreeType mLocalTree;
478  TreeType * const mOutputTree;
479 
480  std::vector<const LeafNodeType*> mLocalLeafNodes;
481  std::vector<const LeafNodeType*> * const mOutputLeafNodes;
482  }; // struct ProcessInternalNodes
483 
484  struct ProcessLeafNodes {
485 
486  ProcessLeafNodes(std::vector<const LeafNodeType*>& rhsNodes,
487  const TreeType& lhsTree, TreeType& output)
488  : mRhsNodes(rhsNodes.empty() ? nullptr : &rhsNodes.front())
489  , mLhsTree(&lhsTree)
490  , mLocalTree(mLhsTree->background())
491  , mOutputTree(&output)
492  {
493  }
494 
495  ProcessLeafNodes(ProcessLeafNodes& rhs, tbb::split)
496  : mRhsNodes(rhs.mRhsNodes)
497  , mLhsTree(rhs.mLhsTree)
498  , mLocalTree(mLhsTree->background())
499  , mOutputTree(&mLocalTree)
500  {
501  }
502 
503  void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
504 
505  void operator()(const tbb::blocked_range<size_t>& range)
506  {
507  tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
508  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
509 
510  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
511 
512  const LeafNodeType& rhsNode = *mRhsNodes[n];
513  const Coord& ijk = rhsNode.origin();
514 
515  const LeafNodeType* lhsNode = lhsAcc.probeConstLeaf(ijk);
516 
517  if (!lhsNode) {
518  if (Operation == CSG_INTERSECTION) {
519  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
520  outputAcc.addLeaf(new LeafNodeType(rhsNode));
521  }
522  } else if (Operation == CSG_DIFFERENCE) {
523  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
524  LeafNodeType* outputNode = new LeafNodeType(rhsNode);
525  outputNode->negate();
526  outputAcc.addLeaf(outputNode);
527  }
528  } else { // Union
529  if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
530  outputAcc.addLeaf(new LeafNodeType(rhsNode));
531  }
532  }
533  }
534  } // end range loop
535  }
536 
537  LeafNodeType const * const * const mRhsNodes;
538  TreeType const * const mLhsTree;
539  TreeType mLocalTree;
540  TreeType * const mOutputTree;
541  }; // struct ProcessLeafNodes
542 
543  TreePtrType mSegment;
544  TreeType const * const mLhsTree;
545  TreeType const * const mRhsTree;
546 }; // struct BuildSecondarySegment
547 
548 
549 template<CSGOperation Operation, typename TreeType>
550 inline typename TreeType::Ptr
551 doCSGCopy(const TreeType& lhs, const TreeType& rhs)
552 {
554  BuildSecondarySegment<TreeType, Operation> secondary(lhs, rhs);
555 
556  // Exploiting nested parallelism
557  tbb::task_group tasks;
558  tasks.run(primary);
559  tasks.run(secondary);
560  tasks.wait();
561 
562  primary.segment()->merge(*secondary.segment());
563 
564  // The leafnode (level = 0) sign is set in the segment construction.
565  tools::signedFloodFill(*primary.segment(), /*threaded=*/true, /*grainSize=*/1, /*minLevel=*/1);
566 
567  return primary.segment();
568 }
569 
570 
572 
573 
574 template<typename TreeType>
576 {
577  using TreeTypePtr = typename TreeType::Ptr;
578  static TreeTypePtr construct(const TreeType&, TreeTypePtr& tree) { return tree; }
579 };
580 
581 
582 template<typename TreeType>
583 struct GridOrTreeConstructor<Grid<TreeType> >
584 {
587  using TreeTypePtr = typename TreeType::Ptr;
588 
589  static GridTypePtr construct(const GridType& grid, TreeTypePtr& tree) {
590  GridTypePtr maskGrid(GridType::create(tree));
591  maskGrid->setTransform(grid.transform().copy());
592  maskGrid->insertMeta(grid);
593  return maskGrid;
594  }
595 };
596 
597 
599 
602 template <typename LeafT>
603 using LeafPairList = std::vector<std::pair<LeafT*, LeafT*>>;
605 
611 template <typename TreeT>
612 inline void transferLeafNodes(TreeT &srcTree, TreeT &dstTree,
613  LeafPairList<typename TreeT::LeafNodeType> &overlapping)
614 {
615  using LeafT = typename TreeT::LeafNodeType;
616  tree::ValueAccessor<TreeT> acc(dstTree);//destination
617  std::vector<LeafT*> srcLeafNodes;
618  srcLeafNodes.reserve(srcTree.leafCount());
619  srcTree.stealNodes(srcLeafNodes);
620  srcTree.clear();
621  for (LeafT *srcLeaf : srcLeafNodes) {
622  LeafT *dstLeaf = acc.probeLeaf(srcLeaf->origin());
623  if (dstLeaf) {
624  overlapping.emplace_back(dstLeaf, srcLeaf);//dst, src
625  } else {
626  acc.addLeaf(srcLeaf);
627  }
628  }
629 }
631 
634 template <typename TreeT, typename OpT>
635 inline
636 typename std::enable_if<
637  !std::is_same<typename TreeT::ValueType, bool>::value &&
638  !std::is_same<typename TreeT::BuildType, ValueMask>::value &&
639  std::is_same<typename TreeT::LeafNodeType::Buffer::ValueType,
640  typename TreeT::LeafNodeType::Buffer::StorageType>::value>::type
641 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
642 {
643  using LeafT = typename TreeT::LeafNodeType;
644  LeafPairList<LeafT> overlapping;//dst, src
645  transferLeafNodes(srcTree, dstTree, overlapping);
646 
647  using RangeT = tbb::blocked_range<size_t>;
648  tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
649  for (auto i = r.begin(); i != r.end(); ++i) {
650  LeafT *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
651  dstLeaf->getValueMask() |= srcLeaf->getValueMask();
652  auto *ptr = dstLeaf->buffer().data();
653  for (auto v = srcLeaf->cbeginValueOn(); v; ++v) op(ptr[v.pos()], *v);
654  delete srcLeaf;
655  }
656  });
657 }
659 
662 template <typename TreeT, typename OpT>
663 inline
664 typename std::enable_if<
665  std::is_same<typename TreeT::BuildType, ValueMask>::value &&
666  std::is_same<typename TreeT::ValueType, bool>::value>::type
667 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT)
668 {
669  using LeafT = typename TreeT::LeafNodeType;
670  LeafPairList<LeafT> overlapping;//dst, src
671  transferLeafNodes(srcTree, dstTree, overlapping);
672 
673  using RangeT = tbb::blocked_range<size_t>;
674  tbb::parallel_for(RangeT(0, overlapping.size()), [&overlapping](const RangeT& r) {
675  for (auto i = r.begin(); i != r.end(); ++i) {
676  overlapping[i].first->getValueMask() |= overlapping[i].second->getValueMask();
677  delete overlapping[i].second;
678  }
679  });
680 }
681 
684 template <typename TreeT, typename OpT>
685 inline
686 typename std::enable_if<
687  std::is_same<typename TreeT::ValueType, bool>::value &&
688  !std::is_same<typename TreeT::BuildType, ValueMask>::value>::type
689 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
690 {
691  using LeafT = typename TreeT::LeafNodeType;
692  LeafPairList<LeafT> overlapping;//dst, src
693  transferLeafNodes(srcTree, dstTree, overlapping);
694 
695  using RangeT = tbb::blocked_range<size_t>;
696  using WordT = typename LeafT::Buffer::WordType;
697  tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
698  for (auto i = r.begin(); i != r.end(); ++i) {
699  LeafT *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
700  WordT *w1 = dstLeaf->buffer().data();
701  const WordT *w2 = srcLeaf->buffer().data();
702  const WordT *w3 = &(srcLeaf->getValueMask().template getWord<WordT>(0));
703  for (Index32 n = LeafT::Buffer::WORD_COUNT; n--; ++w1) {
704  WordT tmp = *w1, state = *w3++;
705  op (tmp, *w2++);
706  *w1 = (state & tmp) | (~state & *w1);//inactive values are unchanged
707  }
708  dstLeaf->getValueMask() |= srcLeaf->getValueMask();
709  delete srcLeaf;
710  }
711  });
712 }
714 
717 template <typename TreeT>
718 struct CopyOp
719 {
720  using ValueT = typename TreeT::ValueType;
721  CopyOp() = default;
722  void operator()(ValueT& dst, const ValueT& src) const { dst = src; }
723 };
725 
726 template <typename TreeT>
727 inline void validateLevelSet(const TreeT& tree, const std::string& gridName = std::string(""))
728 {
729  using ValueT = typename TreeT::ValueType;
730  const ValueT zero = zeroVal<ValueT>();
731  if (!(tree.background() > zero)) {
732  std::stringstream ss;
733  ss << "expected grid ";
734  if (!gridName.empty()) ss << gridName << " ";
735  ss << "outside value > 0, got " << tree.background();
736  OPENVDB_THROW(ValueError, ss.str());
737  }
738  if (!(-tree.background() < zero)) {
739  std::stringstream ss;
740  ss << "expected grid ";
741  if (!gridName.empty()) ss << gridName << " ";
742  ss << "inside value < 0, got " << -tree.background();
743  OPENVDB_THROW(ValueError, ss.str());
744  }
745 }
746 
747 } // namespace composite
748 
749 
750 template<typename GridOrTreeT>
751 inline void
752 compMax(GridOrTreeT& aTree, GridOrTreeT& bTree)
753 {
754  using Adapter = TreeAdapter<GridOrTreeT>;
755  using TreeT = typename Adapter::TreeType;
756  using ValueT = typename TreeT::ValueType;
757  struct Local {
758  static inline void op(CombineArgs<ValueT>& args) {
759  args.setResult(composite::max(args.a(), args.b()));
760  }
761  };
762  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
763 }
764 
765 
766 template<typename GridOrTreeT>
767 inline void
768 compMin(GridOrTreeT& aTree, GridOrTreeT& bTree)
769 {
770  using Adapter = TreeAdapter<GridOrTreeT>;
771  using TreeT = typename Adapter::TreeType;
772  using ValueT = typename TreeT::ValueType;
773  struct Local {
774  static inline void op(CombineArgs<ValueT>& args) {
775  args.setResult(composite::min(args.a(), args.b()));
776  }
777  };
778  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
779 }
780 
781 
782 template<typename GridOrTreeT>
783 inline void
784 compSum(GridOrTreeT& aTree, GridOrTreeT& bTree)
785 {
786  using Adapter = TreeAdapter<GridOrTreeT>;
787  using TreeT = typename Adapter::TreeType;
788  struct Local {
789  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
790  args.setResult(args.a() + args.b());
791  }
792  };
793  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
794 }
795 
796 
797 template<typename GridOrTreeT>
798 inline void
799 compMul(GridOrTreeT& aTree, GridOrTreeT& bTree)
800 {
801  using Adapter = TreeAdapter<GridOrTreeT>;
802  using TreeT = typename Adapter::TreeType;
803  struct Local {
804  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
805  args.setResult(args.a() * args.b());
806  }
807  };
808  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
809 }
810 
811 
812 template<typename GridOrTreeT>
813 inline void
814 compDiv(GridOrTreeT& aTree, GridOrTreeT& bTree)
815 {
816  using Adapter = TreeAdapter<GridOrTreeT>;
817  using TreeT = typename Adapter::TreeType;
818  struct Local {
819  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
820  args.setResult(composite::divide(args.a(), args.b()));
821  }
822  };
823  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
824 }
825 
826 
828 
829 
830 template<typename TreeT>
832 {
833  TreeT* const aTree;
834 
835  CompReplaceOp(TreeT& _aTree): aTree(&_aTree) {}
836 
838  void operator()(const typename TreeT::ValueOnCIter& iter) const
839  {
840  CoordBBox bbox;
841  iter.getBoundingBox(bbox);
842  aTree->fill(bbox, *iter);
843  }
844 
845  void operator()(const typename TreeT::LeafCIter& leafIter) const
846  {
847  tree::ValueAccessor<TreeT> acc(*aTree);
848  for (typename TreeT::LeafCIter::LeafNodeT::ValueOnCIter iter =
849  leafIter->cbeginValueOn(); iter; ++iter)
850  {
851  acc.setValue(iter.getCoord(), *iter);
852  }
853  }
854 };
855 
856 
857 template<typename GridOrTreeT>
858 inline void
859 compReplace(GridOrTreeT& aTree, const GridOrTreeT& bTree)
860 {
861  using Adapter = TreeAdapter<GridOrTreeT>;
862  using TreeT = typename Adapter::TreeType;
863  using ValueOnCIterT = typename TreeT::ValueOnCIter;
864 
865  // Copy active states (but not values) from B to A.
866  Adapter::tree(aTree).topologyUnion(Adapter::tree(bTree));
867 
868  CompReplaceOp<TreeT> op(Adapter::tree(aTree));
869 
870  // Copy all active tile values from B to A.
871  ValueOnCIterT iter = bTree.cbeginValueOn();
872  iter.setMaxDepth(iter.getLeafDepth() - 1); // don't descend into leaf nodes
873  foreach(iter, op, /*threaded=*/false);
874 
875  // Copy all active voxel values from B to A.
876  foreach(Adapter::tree(bTree).cbeginLeaf(), op);
877 }
878 
879 
881 
882 
883 template<typename GridOrTreeT>
884 inline void
885 csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune)
886 {
887  using Adapter = TreeAdapter<GridOrTreeT>;
888  using TreeT = typename Adapter::TreeType;
889  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
890  composite::validateLevelSet(aTree, "A");
891  composite::validateLevelSet(bTree, "B");
892  CsgUnionOp<TreeT> op(bTree, Steal());
893  tree::DynamicNodeManager<TreeT> nodeManager(aTree);
894  nodeManager.foreachTopDown(op);
895  if (prune) tools::pruneLevelSet(aTree);
896 }
897 
898 template<typename GridOrTreeT>
899 inline void
900 csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune)
901 {
902  using Adapter = TreeAdapter<GridOrTreeT>;
903  using TreeT = typename Adapter::TreeType;
904  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
905  composite::validateLevelSet(aTree, "A");
906  composite::validateLevelSet(bTree, "B");
907  CsgIntersectionOp<TreeT> op(bTree, Steal());
908  tree::DynamicNodeManager<TreeT> nodeManager(aTree);
909  nodeManager.foreachTopDown(op);
910  if (prune) tools::pruneLevelSet(aTree);
911 }
912 
913 template<typename GridOrTreeT>
914 inline void
915 csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune)
916 {
917  using Adapter = TreeAdapter<GridOrTreeT>;
918  using TreeT = typename Adapter::TreeType;
919  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
920  composite::validateLevelSet(aTree, "A");
921  composite::validateLevelSet(bTree, "B");
922  CsgDifferenceOp<TreeT> op(bTree, Steal());
923  tree::DynamicNodeManager<TreeT> nodeManager(aTree);
924  nodeManager.foreachTopDown(op);
925  if (prune) tools::pruneLevelSet(aTree);
926 }
927 
928 
929 template<typename GridOrTreeT>
930 inline typename GridOrTreeT::Ptr
931 csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
932 {
933  using Adapter = TreeAdapter<GridOrTreeT>;
934  using TreePtrT = typename Adapter::TreeType::Ptr;
935 
936  TreePtrT output = composite::doCSGCopy<composite::CSG_UNION>(
937  Adapter::tree(a), Adapter::tree(b));
938 
940 }
941 
942 
943 template<typename GridOrTreeT>
944 inline typename GridOrTreeT::Ptr
945 csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
946 {
947  using Adapter = TreeAdapter<GridOrTreeT>;
948  using TreePtrT = typename Adapter::TreeType::Ptr;
949 
950  TreePtrT output = composite::doCSGCopy<composite::CSG_INTERSECTION>(
951  Adapter::tree(a), Adapter::tree(b));
952 
954 }
955 
956 
957 template<typename GridOrTreeT>
958 inline typename GridOrTreeT::Ptr
959 csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b)
960 {
961  using Adapter = TreeAdapter<GridOrTreeT>;
962  using TreePtrT = typename Adapter::TreeType::Ptr;
963 
964  TreePtrT output = composite::doCSGCopy<composite::CSG_DIFFERENCE>(
965  Adapter::tree(a), Adapter::tree(b));
966 
968 }
969 
971 
993 template<typename TreeT, typename OpT = composite::CopyOp<TreeT> >
994 inline void
995 compActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op = composite::CopyOp<TreeT>())
996 {
997  composite::doCompActiveLeafVoxels<TreeT, OpT>(srcTree, dstTree, op);
998 }
999 
1000 
1001 } // namespace tools
1002 } // namespace OPENVDB_VERSION_NAME
1003 } // namespace openvdb
1004 
1005 #endif // OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Functions to efficiently merge grids.
Defined various multi-threaded utility functions for trees.
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: openvdb/Types.h:429
CombineArgs & setResult(const AValueType &val)
Set the output value.
Definition: openvdb/Types.h:478
const AValueType & a() const
Get the A input value.
Definition: openvdb/Types.h:468
const BValueType & b() const
Get the B input value.
Definition: openvdb/Types.h:470
math::Transform & transform()
Return a reference to this grid's transform, which might be shared with other grids.
Definition: Grid.h:415
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:577
SharedPtr< Grid > Ptr
Definition: Grid.h:579
Tag dispatch class that distinguishes constructors that steal.
Definition: openvdb/Types.h:546
Definition: openvdb/Exceptions.h:65
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:249
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:26
const Int32 * data() const
Definition: Coord.h:140
Ptr copy() const
Definition: Transform.h:50
Definition: NodeManager.h:858
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:932
Definition: ValueAccessor.h:183
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active.
Definition: ValueAccessor.h:250
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
const std::enable_if< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:121
TreeType::Ptr doCSGCopy(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:551
void validateLevelSet(const TreeT &tree, const std::string &gridName=std::string(""))
Definition: Composite.h:727
bool divide(bool a, bool)
Definition: Composite.h:145
CSGOperation
Definition: Composite.h:148
@ CSG_DIFFERENCE
Definition: Composite.h:148
@ CSG_UNION
Definition: Composite.h:148
@ CSG_INTERSECTION
Definition: Composite.h:148
const std::enable_if< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:113
void compDiv(GridOrTreeT &a, GridOrTreeT &b)
Given grids A and B, compute a / b per voxel (using sparse traversal). Store the result in the A grid...
Definition: Composite.h:814
void csgUnion(GridOrTreeT &a, GridOrTreeT &b, bool prune=true)
Given two level set grids, replace the A grid with the union of A and B.
Definition: Composite.h:885
void compReplace(GridOrTreeT &a, const GridOrTreeT &b)
Copy the active voxels of B into A.
Definition: Composite.h:859
void compActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op=composite::CopyOp< TreeT >())
Composite the active values in leaf nodes, i.e. active voxels, of a source tree into a destination tr...
Definition: Composite.h:995
void csgDifference(GridOrTreeT &a, GridOrTreeT &b, bool prune=true)
Given two level set grids, replace the A grid with the difference A / B.
Definition: Composite.h:915
void pruneLevelSet(TreeT &tree, bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing nodes whose values are all inactive with inactive ...
Definition: Prune.h:389
GridOrTreeT::Ptr csgDifferenceCopy(const GridOrTreeT &a, const GridOrTreeT &b)
Threaded CSG difference operation that produces a new grid or tree from immutable inputs.
Definition: Composite.h:959
void csgIntersection(GridOrTreeT &a, GridOrTreeT &b, bool prune=true)
Given two level set grids, replace the A grid with the intersection of A and B.
Definition: Composite.h:900
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:334
GridOrTreeT::Ptr csgUnionCopy(const GridOrTreeT &a, const GridOrTreeT &b)
Threaded CSG union operation that produces a new grid or tree from immutable inputs.
Definition: Composite.h:931
void compSum(GridOrTreeT &a, GridOrTreeT &b)
Given grids A and B, compute a + b per voxel (using sparse traversal). Store the result in the A grid...
Definition: Composite.h:784
void compMax(GridOrTreeT &a, GridOrTreeT &b)
Given grids A and B, compute max(a, b) per voxel (using sparse traversal). Store the result in the A ...
Definition: Composite.h:752
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:266
void compMul(GridOrTreeT &a, GridOrTreeT &b)
Given grids A and B, compute a * b per voxel (using sparse traversal). Store the result in the A grid...
Definition: Composite.h:799
void compMin(GridOrTreeT &a, GridOrTreeT &b)
Given grids A and B, compute min(a, b) per voxel (using sparse traversal). Store the result in the A ...
Definition: Composite.h:768
GridOrTreeT::Ptr csgIntersectionCopy(const GridOrTreeT &a, const GridOrTreeT &b)
Threaded CSG intersection operation that produces a new grid or tree from immutable inputs.
Definition: Composite.h:945
Index32 Index
Definition: openvdb/Types.h:32
Definition: openvdb/Exceptions.h:13
#define OPENVDB_THROW(exception, message)
Definition: openvdb/Exceptions.h:74
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1078
Definition: Composite.h:832
void operator()(const typename TreeT::LeafCIter &leafIter) const
Definition: Composite.h:845
TreeT *const aTree
Definition: Composite.h:833
void operator()(const typename TreeT::ValueOnCIter &iter) const
Definition: Composite.h:838
CompReplaceOp(TreeT &_aTree)
Definition: Composite.h:835
DynamicNodeManager operator to merge two trees using a CSG difference.
Definition: Merge.h:259
DynamicNodeManager operator to merge trees using a CSG union or intersection.
Definition: Merge.h:179
typename TreeType::ValueType ValueType
Definition: Composite.h:153
typename NodeChainType::template Get< 1 > InternalNodeType
Definition: Composite.h:159
BuildPrimarySegment(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:161
typename TreeType::RootNodeType RootNodeType
Definition: Composite.h:157
typename RootNodeType::NodeChainType NodeChainType
Definition: Composite.h:158
typename TreeType::LeafNodeType LeafNodeType
Definition: Composite.h:155
void operator()() const
Definition: Composite.h:168
TreePtrType & segment()
Definition: Composite.h:184
typename TreeType::Ptr TreePtrType
Definition: Composite.h:154
typename LeafNodeType::NodeMaskType NodeMaskType
Definition: Composite.h:156
typename TreeType::ValueType ValueType
Definition: Composite.h:361
typename NodeChainType::template Get< 1 > InternalNodeType
Definition: Composite.h:367
typename TreeType::RootNodeType RootNodeType
Definition: Composite.h:365
typename RootNodeType::NodeChainType NodeChainType
Definition: Composite.h:366
BuildSecondarySegment(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:369
typename TreeType::LeafNodeType LeafNodeType
Definition: Composite.h:363
void operator()() const
Definition: Composite.h:376
TreePtrType & segment()
Definition: Composite.h:392
typename TreeType::Ptr TreePtrType
Definition: Composite.h:362
typename LeafNodeType::NodeMaskType NodeMaskType
Definition: Composite.h:364
static GridTypePtr construct(const GridType &grid, TreeTypePtr &tree)
Definition: Composite.h:589
typename TreeType::Ptr TreeTypePtr
Definition: Composite.h:587
typename Grid< TreeType >::Ptr GridTypePtr
Definition: Composite.h:586
static TreeTypePtr construct(const TreeType &, TreeTypePtr &tree)
Definition: Composite.h:578
typename TreeType::Ptr TreeTypePtr
Definition: Composite.h:577
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:101
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:153