HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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<
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<
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<
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  {
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
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
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:446
GLuint segment
Definition: glew.h:12701
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
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
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:178
void operator()(const typename TreeT::ValueOnCIter &iter) const
Definition: Composite.h:830
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
GLenum src
Definition: glcorearb.h:1792
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 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 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
DynamicNodeManager operator to merge trees using a CSG union or intersection.
Definition: Merge.h:179
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:1070
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
SYS_FORCE_INLINE const_iterator end() const
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
const AValueType & a() const
Get the A input value.
Definition: Types.h:486
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 OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
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
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:106
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
const GLdouble * v
Definition: glcorearb.h:836
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
const std::enable_if< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:120
GLsizei const GLchar *const * string
Definition: glcorearb.h:813
DynamicNodeManager operator to merge two trees using a CSG difference.
Definition: Merge.h:259
Defined various multi-threaded utility functions for trees.
Tag dispatch class that distinguishes constructors that steal.
Definition: Types.h:564
void operator()(const typename TreeT::LeafCIter &leafIter) const
Definition: Composite.h:837
const std::enable_if< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:112
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
GLdouble n
Definition: glcorearb.h:2007
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
const void * ptr(const T *p)
Definition: format.h:3603
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...
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 compReplace(GridOrTreeT &a, const GridOrTreeT &b)
Copy the active voxels of B into A.
Definition: Composite.h:851
GA_API const UT_StringHolder N
GLsizei const GLfloat * value
Definition: glcorearb.h:823
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
**If you just want to fire and args
Definition: thread.h:615
GLenum GLint * range
Definition: glcorearb.h:1924
#define SIZE
Definition: simple.C:40
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
Functions to efficiently merge grids.
const BValueType & b() const
Get the B input value.
Definition: Types.h:488
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
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
GLenum GLenum dst
Definition: glcorearb.h:1792
GLboolean r
Definition: glcorearb.h:1221
ImageBuf OIIO_API zero(ROI roi, int nthreads=0)
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:102
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:114
CombineArgs & setResult(const AValueType &val)
Set the output value.
Definition: Types.h:496
arg_join< It, Sentinel, char > join(It begin, Sentinel end, string_view sep)
Definition: format.h:3681
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
std::enable_if<!std::is_integral< T >::value, T >::type divide(const T &a, const T &b)
Definition: Composite.h:129