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