HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Composite.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2018 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @file Composite.h
32 ///
33 /// @brief Functions to efficiently perform various compositing operations on grids
34 ///
35 /// @authors Peter Cucka, Mihai Alden, Ken Museth
36 
37 #ifndef OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
38 #define OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
39 
40 #include <openvdb/Platform.h>
41 #include <openvdb/Exceptions.h>
42 #include <openvdb/Types.h>
43 #include <openvdb/Grid.h>
44 #include <openvdb/math/Math.h> // for isExactlyEqual()
45 #include "ValueTransformer.h" // for transformValues()
46 #include "Prune.h"// for prune
47 #include "SignedFloodFill.h" // for signedFloodFill()
48 
49 #include <tbb/blocked_range.h>
50 #include <tbb/parallel_for.h>
51 #include <tbb/parallel_reduce.h>
52 #include <tbb/task_group.h>
53 #include <tbb/task_scheduler_init.h>
54 
55 #include <type_traits>
56 #include <functional>
57 
58 namespace openvdb {
60 namespace OPENVDB_VERSION_NAME {
61 namespace tools {
62 
63 /// @brief Given two level set grids, replace the A grid with the union of A and B.
64 /// @throw ValueError if the background value of either grid is not greater than zero.
65 /// @note This operation always leaves the B grid empty.
66 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
67 inline void csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
68 /// @brief Given two level set grids, replace the A grid with the intersection of A and B.
69 /// @throw ValueError if the background value of either grid is not greater than zero.
70 /// @note This operation always leaves the B grid empty.
71 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
72 inline void csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
73 /// @brief Given two level set grids, replace the A grid with the difference A / B.
74 /// @throw ValueError if the background value of either grid is not greater than zero.
75 /// @note This operation always leaves the B grid empty.
76 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
77 inline void csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune = true);
78 
79 /// @brief Threaded CSG union operation that produces a new grid or tree from
80 /// immutable inputs.
81 /// @return The CSG union of the @a and @b level set inputs.
82 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
83 inline typename GridOrTreeT::Ptr csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
84 /// @brief Threaded CSG intersection operation that produces a new grid or tree from
85 /// immutable inputs.
86 /// @return The CSG intersection of the @a and @b level set inputs.
87 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
88 inline typename GridOrTreeT::Ptr csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b);
89 /// @brief Threaded CSG difference operation that produces a new grid or tree from
90 /// immutable inputs.
91 /// @return The CSG difference of the @a and @b level set inputs.
92 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
93 inline typename GridOrTreeT::Ptr csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b);
94 
95 /// @brief Given grids A and B, compute max(a, b) per voxel (using sparse traversal).
96 /// Store the result in the A grid and leave the B grid empty.
97 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
98 inline void compMax(GridOrTreeT& a, GridOrTreeT& b);
99 /// @brief Given grids A and B, compute min(a, b) per voxel (using sparse traversal).
100 /// Store the result in the A grid and leave the B grid empty.
101 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
102 inline void compMin(GridOrTreeT& a, GridOrTreeT& b);
103 /// @brief Given grids A and B, compute a + b per voxel (using sparse traversal).
104 /// Store the result in the A grid and leave the B grid empty.
105 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
106 inline void compSum(GridOrTreeT& a, GridOrTreeT& b);
107 /// @brief Given grids A and B, compute a * b per voxel (using sparse traversal).
108 /// Store the result in the A grid and leave the B grid empty.
109 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
110 inline void compMul(GridOrTreeT& a, GridOrTreeT& b);
111 /// @brief Given grids A and B, compute a / b per voxel (using sparse traversal).
112 /// Store the result in the A grid and leave the B grid empty.
113 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
114 inline void compDiv(GridOrTreeT& a, GridOrTreeT& b);
115 
116 /// Copy the active voxels of B into A.
117 template<typename GridOrTreeT> OPENVDB_STATIC_SPECIALIZATION
118 inline void compReplace(GridOrTreeT& a, const GridOrTreeT& b);
119 
120 
121 ////////////////////////////////////////
122 
123 
124 namespace composite {
125 
126 // composite::min() and composite::max() for non-vector types compare with operator<().
127 template<typename T> inline
128 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type& // = T if T is not a vector type
129 min(const T& a, const T& b) { return std::min(a, b); }
130 
131 template<typename T> inline
132 const typename std::enable_if<!VecTraits<T>::IsVec, T>::type&
133 max(const T& a, const T& b) { return std::max(a, b); }
134 
135 
136 // composite::min() and composite::max() for OpenVDB vector types compare by magnitude.
137 template<typename T> inline
138 const typename std::enable_if<VecTraits<T>::IsVec, T>::type& // = T if T is a vector type
139 min(const T& a, const T& b)
140 {
141  const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
142  return (aMag < bMag ? a : (bMag < aMag ? b : std::min(a, b)));
143 }
144 
145 template<typename T> inline
146 const typename std::enable_if<VecTraits<T>::IsVec, T>::type&
147 max(const T& a, const T& b)
148 {
149  const typename T::ValueType aMag = a.lengthSqr(), bMag = b.lengthSqr();
150  return (aMag < bMag ? b : (bMag < aMag ? a : std::max(a, b)));
151 }
152 
153 
154 template<typename T> inline
155 typename std::enable_if<!std::is_integral<T>::value, T>::type // = T if T is not an integer type
156 divide(const T& a, const T& b) { return a / b; }
157 
158 template<typename T> inline
159 typename std::enable_if<std::is_integral<T>::value, T>::type // = T if T is an integer type
160 divide(const T& a, const T& b)
161 {
162  const T zero(0);
163  if (b != zero) return a / b;
164  if (a == zero) return 0;
166 }
167 
168 // If b is true, return a / 1 = a.
169 // If b is false and a is true, return 1 / 0 = inf = MAX_BOOL = 1 = a.
170 // If b is false and a is false, return 0 / 0 = NaN = 0 = a.
171 inline bool divide(bool a, bool /*b*/) { return a; }
172 
173 
175 
176 template<typename TreeType, CSGOperation Operation>
178 {
179  typedef typename TreeType::ValueType ValueType;
180  typedef typename TreeType::Ptr TreePtrType;
181  typedef typename TreeType::LeafNodeType LeafNodeType;
182  typedef typename LeafNodeType::NodeMaskType NodeMaskType;
183  typedef typename TreeType::RootNodeType RootNodeType;
184  typedef typename RootNodeType::NodeChainType NodeChainType;
185  typedef typename hboost::mpl::at<NodeChainType, hboost::mpl::int_<1> >::type InternalNodeType;
186 
187  BuildPrimarySegment(const TreeType& lhs, const TreeType& rhs)
188  : mSegment(new TreeType(lhs.background()))
189  , mLhsTree(&lhs)
190  , mRhsTree(&rhs)
191  {
192  }
193 
194  void operator()() const
195  {
196  std::vector<const LeafNodeType*> leafNodes;
197 
198  {
199  std::vector<const InternalNodeType*> internalNodes;
200  mLhsTree->getNodes(internalNodes);
201 
202  ProcessInternalNodes op(internalNodes, *mRhsTree, *mSegment, leafNodes);
203  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
204  }
205 
206  ProcessLeafNodes op(leafNodes, *mRhsTree, *mSegment);
207  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
208  }
209 
210  TreePtrType& segment() { return mSegment; }
211 
212 private:
213 
214  struct ProcessInternalNodes {
215 
216  ProcessInternalNodes(std::vector<const InternalNodeType*>& lhsNodes, const TreeType& rhsTree,
217  TreeType& outputTree, std::vector<const LeafNodeType*>& outputLeafNodes)
218  : mLhsNodes(lhsNodes.empty() ? NULL : &lhsNodes.front())
219  , mRhsTree(&rhsTree)
220  , mLocalTree(mRhsTree->background())
221  , mOutputTree(&outputTree)
222  , mLocalLeafNodes()
223  , mOutputLeafNodes(&outputLeafNodes)
224  {
225  }
226 
227  ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
228  : mLhsNodes(other.mLhsNodes)
229  , mRhsTree(other.mRhsTree)
230  , mLocalTree(mRhsTree->background())
231  , mOutputTree(&mLocalTree)
232  , mLocalLeafNodes()
233  , mOutputLeafNodes(&mLocalLeafNodes)
234  {
235  }
236 
237  void join(ProcessInternalNodes& other)
238  {
239  mOutputTree->merge(*other.mOutputTree);
240  mOutputLeafNodes->insert(mOutputLeafNodes->end(),
241  other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
242  }
243 
244  void operator()(const tbb::blocked_range<size_t>& range)
245  {
246  tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
247  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
248 
249  std::vector<const LeafNodeType*> tmpLeafNodes;
250 
251  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
252 
253  const InternalNodeType& lhsNode = *mLhsNodes[n];
254  const Coord& ijk = lhsNode.origin();
255  const InternalNodeType * rhsNode = rhsAcc.template probeConstNode<InternalNodeType>(ijk);
256 
257  if (rhsNode) {
258  lhsNode.getNodes(*mOutputLeafNodes);
259  } else {
260  if (Operation == CSG_INTERSECTION) {
261  if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
262  tmpLeafNodes.clear();
263  lhsNode.getNodes(tmpLeafNodes);
264  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
265  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
266  }
267  }
268  } else { // Union & Difference
269  if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
270  tmpLeafNodes.clear();
271  lhsNode.getNodes(tmpLeafNodes);
272  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
273  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
274  }
275  }
276  }
277  }
278  } // end range loop
279  }
280 
281  InternalNodeType const * const * const mLhsNodes;
282  TreeType const * const mRhsTree;
283  TreeType mLocalTree;
284  TreeType * const mOutputTree;
285 
286  std::vector<const LeafNodeType*> mLocalLeafNodes;
287  std::vector<const LeafNodeType*> * const mOutputLeafNodes;
288  }; // struct ProcessInternalNodes
289 
290  struct ProcessLeafNodes {
291 
292  ProcessLeafNodes(std::vector<const LeafNodeType*>& lhsNodes, const TreeType& rhsTree, TreeType& output)
293  : mLhsNodes(lhsNodes.empty() ? NULL : &lhsNodes.front())
294  , mRhsTree(&rhsTree)
295  , mLocalTree(mRhsTree->background())
296  , mOutputTree(&output)
297  {
298  }
299 
300  ProcessLeafNodes(ProcessLeafNodes& other, tbb::split)
301  : mLhsNodes(other.mLhsNodes)
302  , mRhsTree(other.mRhsTree)
303  , mLocalTree(mRhsTree->background())
304  , mOutputTree(&mLocalTree)
305  {
306  }
307 
308  void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
309 
310  void operator()(const tbb::blocked_range<size_t>& range)
311  {
312  tree::ValueAccessor<const TreeType> rhsAcc(*mRhsTree);
313  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
314 
315  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
316 
317  const LeafNodeType& lhsNode = *mLhsNodes[n];
318  const Coord& ijk = lhsNode.origin();
319 
320  const LeafNodeType* rhsNodePt = rhsAcc.probeConstLeaf(ijk);
321 
322  if (rhsNodePt) { // combine overlapping nodes
323 
324  LeafNodeType* outputNode = outputAcc.touchLeaf(ijk);
325  ValueType * outputData = outputNode->buffer().data();
326  NodeMaskType& outputMask = outputNode->getValueMask();
327 
328  const ValueType * lhsData = lhsNode.buffer().data();
329  const NodeMaskType& lhsMask = lhsNode.getValueMask();
330 
331  const ValueType * rhsData = rhsNodePt->buffer().data();
332  const NodeMaskType& rhsMask = rhsNodePt->getValueMask();
333 
334  if (Operation == CSG_INTERSECTION) {
335  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
336  const bool fromRhs = lhsData[pos] < rhsData[pos];
337  outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
338  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
339  }
340  } else if (Operation == CSG_DIFFERENCE){
341  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
342  const ValueType rhsVal = math::negative(rhsData[pos]);
343  const bool fromRhs = lhsData[pos] < rhsVal;
344  outputData[pos] = fromRhs ? rhsVal : lhsData[pos];
345  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
346  }
347  } else { // Union
348  for (Index pos = 0; pos < LeafNodeType::SIZE; ++pos) {
349  const bool fromRhs = lhsData[pos] > rhsData[pos];
350  outputData[pos] = fromRhs ? rhsData[pos] : lhsData[pos];
351  outputMask.set(pos, fromRhs ? rhsMask.isOn(pos) : lhsMask.isOn(pos));
352  }
353  }
354 
355  } else {
356  if (Operation == CSG_INTERSECTION) {
357  if (rhsAcc.getValue(ijk) < ValueType(0.0)) {
358  outputAcc.addLeaf(new LeafNodeType(lhsNode));
359  }
360  } else { // Union & Difference
361  if (!(rhsAcc.getValue(ijk) < ValueType(0.0))) {
362  outputAcc.addLeaf(new LeafNodeType(lhsNode));
363  }
364  }
365  }
366  } // end range loop
367  }
368 
369  LeafNodeType const * const * const mLhsNodes;
370  TreeType const * const mRhsTree;
371  TreeType mLocalTree;
372  TreeType * const mOutputTree;
373  }; // struct ProcessLeafNodes
374 
375  TreePtrType mSegment;
376  TreeType const * const mLhsTree;
377  TreeType const * const mRhsTree;
378 }; // struct BuildPrimarySegment
379 
380 
381 template<typename TreeType, CSGOperation Operation>
383 {
384  typedef typename TreeType::ValueType ValueType;
385  typedef typename TreeType::Ptr TreePtrType;
386  typedef typename TreeType::LeafNodeType LeafNodeType;
387  typedef typename LeafNodeType::NodeMaskType NodeMaskType;
388  typedef typename TreeType::RootNodeType RootNodeType;
389  typedef typename RootNodeType::NodeChainType NodeChainType;
390  typedef typename hboost::mpl::at<NodeChainType, hboost::mpl::int_<1> >::type InternalNodeType;
391 
392  BuildSecondarySegment(const TreeType& lhs, const TreeType& rhs)
393  : mSegment(new TreeType(lhs.background()))
394  , mLhsTree(&lhs)
395  , mRhsTree(&rhs)
396  {
397  }
398 
399  void operator()() const
400  {
401  std::vector<const LeafNodeType*> leafNodes;
402 
403  {
404  std::vector<const InternalNodeType*> internalNodes;
405  mRhsTree->getNodes(internalNodes);
406 
407  ProcessInternalNodes op(internalNodes, *mLhsTree, *mSegment, leafNodes);
408  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, internalNodes.size()), op);
409  }
410 
411  ProcessLeafNodes op(leafNodes, *mLhsTree, *mSegment);
412  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, leafNodes.size()), op);
413  }
414 
415  TreePtrType& segment() { return mSegment; }
416 
417 private:
418 
419  struct ProcessInternalNodes {
420 
421  ProcessInternalNodes(std::vector<const InternalNodeType*>& rhsNodes, const TreeType& lhsTree,
422  TreeType& outputTree, std::vector<const LeafNodeType*>& outputLeafNodes)
423  : mRhsNodes(rhsNodes.empty() ? NULL : &rhsNodes.front())
424  , mLhsTree(&lhsTree)
425  , mLocalTree(mLhsTree->background())
426  , mOutputTree(&outputTree)
427  , mLocalLeafNodes()
428  , mOutputLeafNodes(&outputLeafNodes)
429  {
430  }
431 
432  ProcessInternalNodes(ProcessInternalNodes& other, tbb::split)
433  : mRhsNodes(other.mRhsNodes)
434  , mLhsTree(other.mLhsTree)
435  , mLocalTree(mLhsTree->background())
436  , mOutputTree(&mLocalTree)
437  , mLocalLeafNodes()
438  , mOutputLeafNodes(&mLocalLeafNodes)
439  {
440  }
441 
442  void join(ProcessInternalNodes& other)
443  {
444  mOutputTree->merge(*other.mOutputTree);
445  mOutputLeafNodes->insert(mOutputLeafNodes->end(),
446  other.mOutputLeafNodes->begin(), other.mOutputLeafNodes->end());
447  }
448 
449  void operator()(const tbb::blocked_range<size_t>& range)
450  {
451  tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
452  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
453 
454  std::vector<const LeafNodeType*> tmpLeafNodes;
455 
456  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
457 
458  const InternalNodeType& rhsNode = *mRhsNodes[n];
459  const Coord& ijk = rhsNode.origin();
460  const InternalNodeType * lhsNode = lhsAcc.template probeConstNode<InternalNodeType>(ijk);
461 
462  if (lhsNode) {
463  rhsNode.getNodes(*mOutputLeafNodes);
464  } else {
465  if (Operation == CSG_INTERSECTION) {
466  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
467  tmpLeafNodes.clear();
468  rhsNode.getNodes(tmpLeafNodes);
469  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
470  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
471  }
472  }
473  } else if (Operation == CSG_DIFFERENCE) {
474  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
475  tmpLeafNodes.clear();
476  rhsNode.getNodes(tmpLeafNodes);
477  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
478  LeafNodeType* outputNode = new LeafNodeType(*tmpLeafNodes[i]);
479  outputNode->negate();
480  outputAcc.addLeaf(outputNode);
481  }
482  }
483  } else { // Union
484  if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
485  tmpLeafNodes.clear();
486  rhsNode.getNodes(tmpLeafNodes);
487  for (size_t i = 0, I = tmpLeafNodes.size(); i < I; ++i) {
488  outputAcc.addLeaf(new LeafNodeType(*tmpLeafNodes[i]));
489  }
490  }
491  }
492  }
493  } // end range loop
494  }
495 
496  InternalNodeType const * const * const mRhsNodes;
497  TreeType const * const mLhsTree;
498  TreeType mLocalTree;
499  TreeType * const mOutputTree;
500 
501  std::vector<const LeafNodeType*> mLocalLeafNodes;
502  std::vector<const LeafNodeType*> * const mOutputLeafNodes;
503  }; // struct ProcessInternalNodes
504 
505  struct ProcessLeafNodes {
506 
507  ProcessLeafNodes(std::vector<const LeafNodeType*>& rhsNodes, const TreeType& lhsTree, TreeType& output)
508  : mRhsNodes(rhsNodes.empty() ? NULL : &rhsNodes.front())
509  , mLhsTree(&lhsTree)
510  , mLocalTree(mLhsTree->background())
511  , mOutputTree(&output)
512  {
513  }
514 
515  ProcessLeafNodes(ProcessLeafNodes& rhs, tbb::split)
516  : mRhsNodes(rhs.mRhsNodes)
517  , mLhsTree(rhs.mLhsTree)
518  , mLocalTree(mLhsTree->background())
519  , mOutputTree(&mLocalTree)
520  {
521  }
522 
523  void join(ProcessLeafNodes& rhs) { mOutputTree->merge(*rhs.mOutputTree); }
524 
525  void operator()(const tbb::blocked_range<size_t>& range)
526  {
527  tree::ValueAccessor<const TreeType> lhsAcc(*mLhsTree);
528  tree::ValueAccessor<TreeType> outputAcc(*mOutputTree);
529 
530  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
531 
532  const LeafNodeType& rhsNode = *mRhsNodes[n];
533  const Coord& ijk = rhsNode.origin();
534 
535  const LeafNodeType* lhsNode = lhsAcc.probeConstLeaf(ijk);
536 
537  if (!lhsNode) {
538  if (Operation == CSG_INTERSECTION) {
539  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
540  outputAcc.addLeaf(new LeafNodeType(rhsNode));
541  }
542  } else if (Operation == CSG_DIFFERENCE) {
543  if (lhsAcc.getValue(ijk) < ValueType(0.0)) {
544  LeafNodeType* outputNode = new LeafNodeType(rhsNode);
545  outputNode->negate();
546  outputAcc.addLeaf(outputNode);
547  }
548  } else { // Union
549  if (!(lhsAcc.getValue(ijk) < ValueType(0.0))) {
550  outputAcc.addLeaf(new LeafNodeType(rhsNode));
551  }
552  }
553  }
554  } // end range loop
555  }
556 
557  LeafNodeType const * const * const mRhsNodes;
558  TreeType const * const mLhsTree;
559  TreeType mLocalTree;
560  TreeType * const mOutputTree;
561  }; // struct ProcessLeafNodes
562 
563  TreePtrType mSegment;
564  TreeType const * const mLhsTree;
565  TreeType const * const mRhsTree;
566 }; // struct BuildSecondarySegment
567 
568 
569 template<CSGOperation Operation, typename TreeType>
570 inline typename TreeType::Ptr
571 doCSGCopy(const TreeType& lhs, const TreeType& rhs)
572 {
574  BuildSecondarySegment<TreeType, Operation> secondary(lhs, rhs);
575 
576  // Exploiting nested parallelism
577  tbb::task_group tasks;
578  tasks.run(primary);
579  tasks.run(secondary);
580  tasks.wait();
581 
582  primary.segment()->merge(*secondary.segment());
583 
584  // The leafnode (level = 0) sign is set in the segment construction.
585  tools::signedFloodFill(*primary.segment(), /*threaded=*/true, /*grainSize=*/1, /*minLevel=*/1);
586 
587  return primary.segment();
588 }
589 
590 
591 ////////////////////////////////////////
592 
593 
594 template<typename TreeType>
596 {
597  typedef typename TreeType::Ptr TreeTypePtr;
598  static TreeTypePtr construct(const TreeType&, TreeTypePtr& tree) { return tree; }
599 };
600 
601 
602 template<typename TreeType>
603 struct GridOrTreeConstructor<Grid<TreeType> >
604 {
607  typedef typename TreeType::Ptr TreeTypePtr;
608 
609  static GridTypePtr construct(const GridType& grid, TreeTypePtr& tree) {
610  GridTypePtr maskGrid(GridType::create(tree));
611  maskGrid->setTransform(grid.transform().copy());
612  maskGrid->insertMeta(grid);
613  return maskGrid;
614  }
615 };
616 
617 
618 ////////////////////////////////////////
619 
620 /// @cond COMPOSITE_INTERNAL
621 /// List of pairs of leaf node pointers
622 template <typename LeafT>
623 using LeafPairList = std::vector<std::pair<LeafT*, LeafT*>>;
624 /// @endcond
625 
626 /// @cond COMPOSITE_INTERNAL
627 /// Transfers leaf nodes from a source tree into a
628 /// desitnation tree, unless it already exists in the destination tree
629 /// in which case pointers to both leaf nodes are added to a list for
630 /// subsequent compositing operations.
631 template <typename TreeT>
632 inline void transferLeafNodes(TreeT &srcTree, TreeT &dstTree,
633  LeafPairList<typename TreeT::LeafNodeType> &overlapping)
634 {
635  using LeafT = typename TreeT::LeafNodeType;
636  tree::ValueAccessor<TreeT> acc(dstTree);//destination
637  std::vector<LeafT*> srcLeafNodes;
638  srcLeafNodes.reserve(srcTree.leafCount());
639  srcTree.stealNodes(srcLeafNodes);
640  srcTree.clear();
641  for (LeafT *srcLeaf : srcLeafNodes) {
642  LeafT *dstLeaf = acc.probeLeaf(srcLeaf->origin());
643  if (dstLeaf) {
644  overlapping.emplace_back(dstLeaf, srcLeaf);//dst, src
645  } else {
646  acc.addLeaf(srcLeaf);
647  }
648  }
649 }
650 /// @endcond
651 
652 /// @cond COMPOSITE_INTERNAL
653 /// Template specailization of compActiveLeafVoxels
654 template <typename TreeT, typename OpT>
655 inline
658  std::is_same<typename TreeT::LeafNodeType::Buffer::ValueType,
659  typename TreeT::LeafNodeType::Buffer::StorageType>::value>::type
660 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
661 {
662  using LeafT = typename TreeT::LeafNodeType;
663  LeafPairList<LeafT> overlapping;//dst, src
664  transferLeafNodes(srcTree, dstTree, overlapping);
665 
666  using RangeT = tbb::blocked_range<size_t>;
667  tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
668  for (auto i = r.begin(); i != r.end(); ++i) {
669  auto *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
670  dstLeaf->getValueMask() |= srcLeaf->getValueMask();
671  auto *ptr = dstLeaf->buffer().data();
672  for (auto v = srcLeaf->cbeginValueOn(); v; ++v) op(ptr[v.pos()], *v);
673  delete srcLeaf;
674  }
675  });
676 }
677 /// @endcond
678 
679 /// @cond COMPOSITE_INTERNAL
680 /// Template specailization of compActiveLeafVoxels
681 template <typename TreeT, typename OpT>
682 inline
685 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT)
686 {
687  using LeafT = typename TreeT::LeafNodeType;
688  LeafPairList<LeafT> overlapping;//dst, src
689  transferLeafNodes(srcTree, dstTree, overlapping);
690 
691  using RangeT = tbb::blocked_range<size_t>;
692  tbb::parallel_for(RangeT(0, overlapping.size()), [&overlapping](const RangeT& r) {
693  for (auto i = r.begin(); i != r.end(); ++i) {
694  overlapping[i].first->getValueMask() |= overlapping[i].second->getValueMask();
695  delete overlapping[i].second;
696  }
697  });
698 }
699 
700 /// @cond COMPOSITE_INTERNAL
701 /// Template specailization of compActiveLeafVoxels
702 template <typename TreeT, typename OpT>
703 inline
706 doCompActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op)
707 {
708  using LeafT = typename TreeT::LeafNodeType;
709  LeafPairList<LeafT> overlapping;//dst, src
710  transferLeafNodes(srcTree, dstTree, overlapping);
711 
712  using RangeT = tbb::blocked_range<size_t>;
713  using WordT = typename LeafT::Buffer::WordType;
714  tbb::parallel_for(RangeT(0, overlapping.size()), [op, &overlapping](const RangeT& r) {
715  for (auto i = r.begin(); i != r.end(); ++i) {
716  LeafT *dstLeaf = overlapping[i].first, *srcLeaf = overlapping[i].second;
717  WordT *w1 = dstLeaf->buffer().data();
718  const WordT *w2 = srcLeaf->buffer().data();
719  const WordT *w3 = &(srcLeaf->getValueMask().template getWord<WordT>(0));
720  for (Index32 n = LeafT::Buffer::WORD_COUNT; n--; ++w1) {
721  WordT tmp = *w1, state = *w3++;
722  op (tmp, *w2++);
723  *w1 = (state & tmp) | (~state & *w1);//inactive values are unchanged
724  }
725  dstLeaf->getValueMask() |= srcLeaf->getValueMask();
726  delete srcLeaf;
727  }
728  });
729 }
730 /// @endcond
731 
732 /// @cond COMPOSITE_INTERNAL
733 /// Default functor for compActiveLeafVoxels
734 template <typename TreeT>
735 struct CopyOp
736 {
737  using ValueT = typename TreeT::ValueType;
738  CopyOp() = default;
739  void operator()(ValueT& dst, const ValueT& src) const { dst = src; }
740 };
741 /// @endcond
742 
743 } // namespace composite
744 
745 
746 template<typename GridOrTreeT>
748 compMax(GridOrTreeT& aTree, GridOrTreeT& bTree)
749 {
750  typedef TreeAdapter<GridOrTreeT> Adapter;
751  typedef typename Adapter::TreeType TreeT;
752  typedef typename TreeT::ValueType ValueT;
753  struct Local {
754  static inline void op(CombineArgs<ValueT>& args) {
755  args.setResult(composite::max(args.a(), args.b()));
756  }
757  };
758  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
759 }
760 
761 
762 template<typename GridOrTreeT>
764 compMin(GridOrTreeT& aTree, GridOrTreeT& bTree)
765 {
766  typedef TreeAdapter<GridOrTreeT> Adapter;
767  typedef typename Adapter::TreeType TreeT;
768  typedef typename TreeT::ValueType ValueT;
769  struct Local {
770  static inline void op(CombineArgs<ValueT>& args) {
771  args.setResult(composite::min(args.a(), args.b()));
772  }
773  };
774  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
775 }
776 
777 
778 template<typename GridOrTreeT>
780 compSum(GridOrTreeT& aTree, GridOrTreeT& bTree)
781 {
782  typedef TreeAdapter<GridOrTreeT> Adapter;
783  typedef typename Adapter::TreeType TreeT;
784  struct Local {
785  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
786  args.setResult(args.a() + args.b());
787  }
788  };
789  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
790 }
791 
792 
793 template<typename GridOrTreeT>
795 compMul(GridOrTreeT& aTree, GridOrTreeT& bTree)
796 {
797  typedef TreeAdapter<GridOrTreeT> Adapter;
798  typedef typename Adapter::TreeType TreeT;
799  struct Local {
800  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
801  args.setResult(args.a() * args.b());
802  }
803  };
804  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
805 }
806 
807 
808 template<typename GridOrTreeT>
810 compDiv(GridOrTreeT& aTree, GridOrTreeT& bTree)
811 {
812  typedef TreeAdapter<GridOrTreeT> Adapter;
813  typedef typename Adapter::TreeType TreeT;
814  struct Local {
815  static inline void op(CombineArgs<typename TreeT::ValueType>& args) {
816  args.setResult(composite::divide(args.a(), args.b()));
817  }
818  };
819  Adapter::tree(aTree).combineExtended(Adapter::tree(bTree), Local::op, /*prune=*/false);
820 }
821 
822 
823 ////////////////////////////////////////
824 
825 
826 template<typename TreeT>
828 {
829  TreeT* const aTree;
830 
831  CompReplaceOp(TreeT& _aTree): aTree(&_aTree) {}
832 
833  /// @note fill operation is not thread safe
834  void operator()(const typename TreeT::ValueOnCIter& iter) const
835  {
836  CoordBBox bbox;
837  iter.getBoundingBox(bbox);
838  aTree->fill(bbox, *iter);
839  }
840 
841  void operator()(const typename TreeT::LeafCIter& leafIter) const
842  {
844  for (typename TreeT::LeafCIter::LeafNodeT::ValueOnCIter iter =
845  leafIter->cbeginValueOn(); iter; ++iter)
846  {
847  acc.setValue(iter.getCoord(), *iter);
848  }
849  }
850 };
851 
852 
853 template<typename GridOrTreeT>
855 compReplace(GridOrTreeT& aTree, const GridOrTreeT& bTree)
856 {
857  typedef TreeAdapter<GridOrTreeT> Adapter;
858  typedef typename Adapter::TreeType TreeT;
859  typedef typename TreeT::ValueOnCIter ValueOnCIterT;
860 
861  // Copy active states (but not values) from B to A.
862  Adapter::tree(aTree).topologyUnion(Adapter::tree(bTree));
863 
864  CompReplaceOp<TreeT> op(Adapter::tree(aTree));
865 
866  // Copy all active tile values from B to A.
867  ValueOnCIterT iter = bTree.cbeginValueOn();
868  iter.setMaxDepth(iter.getLeafDepth() - 1); // don't descend into leaf nodes
869  foreach(iter, op, /*threaded=*/false);
870 
871  // Copy all active voxel values from B to A.
872  foreach(Adapter::tree(bTree).cbeginLeaf(), op);
873 }
874 
875 
876 ////////////////////////////////////////
877 
878 
879 /// Base visitor class for CSG operations
880 /// (not intended to be used polymorphically, so no virtual functions)
881 template<typename TreeType>
883 {
884 public:
885  typedef TreeType TreeT;
886  typedef typename TreeT::ValueType ValueT;
887  typedef typename TreeT::LeafNodeType::ChildAllIter ChildIterT;
888 
889  enum { STOP = 3 };
890 
891  CsgVisitorBase(const TreeT& aTree, const TreeT& bTree):
892  mAOutside(aTree.background()),
893  mAInside(math::negative(mAOutside)),
894  mBOutside(bTree.background()),
895  mBInside(math::negative(mBOutside))
896  {
897  const ValueT zero = zeroVal<ValueT>();
898  if (!(mAOutside > zero)) {
899  OPENVDB_THROW(ValueError,
900  "expected grid A outside value > 0, got " << mAOutside);
901  }
902  if (!(mAInside < zero)) {
903  OPENVDB_THROW(ValueError,
904  "expected grid A inside value < 0, got " << mAInside);
905  }
906  if (!(mBOutside > zero)) {
907  OPENVDB_THROW(ValueError,
908  "expected grid B outside value > 0, got " << mBOutside);
909  }
910  if (!(mBInside < zero)) {
911  OPENVDB_THROW(ValueError,
912  "expected grid B outside value < 0, got " << mBOutside);
913  }
914  }
915 
916 protected:
918 };
919 
920 
921 ////////////////////////////////////////
922 
923 
924 template<typename TreeType>
925 struct CsgUnionVisitor: public CsgVisitorBase<TreeType>
926 {
927  typedef TreeType TreeT;
928  typedef typename TreeT::ValueType ValueT;
929  typedef typename TreeT::LeafNodeType::ChildAllIter ChildIterT;
930 
932 
933  CsgUnionVisitor(const TreeT& a, const TreeT& b): CsgVisitorBase<TreeT>(a, b) {}
934 
935  /// Don't process nodes that are at different tree levels.
936  template<typename AIterT, typename BIterT>
937  inline int operator()(AIterT&, BIterT&) { return 0; }
938 
939  /// Process root and internal nodes.
940  template<typename IterT>
941  inline int operator()(IterT& aIter, IterT& bIter)
942  {
943  ValueT aValue = zeroVal<ValueT>();
944  typename IterT::ChildNodeType* aChild = aIter.probeChild(aValue);
945  if (!aChild && aValue < zeroVal<ValueT>()) {
946  // A is an inside tile. Leave it alone and stop traversing this branch.
947  return STOP;
948  }
949 
950  ValueT bValue = zeroVal<ValueT>();
951  typename IterT::ChildNodeType* bChild = bIter.probeChild(bValue);
952  if (!bChild && bValue < zeroVal<ValueT>()) {
953  // B is an inside tile. Make A an inside tile and stop traversing this branch.
954  aIter.setValue(this->mAInside);
955  aIter.setValueOn(bIter.isValueOn());
956  delete aChild;
957  return STOP;
958  }
959 
960  if (!aChild && aValue > zeroVal<ValueT>()) {
961  // A is an outside tile. If B has a child, transfer it to A,
962  // otherwise leave A alone.
963  if (bChild) {
964  bIter.setValue(this->mBOutside);
965  bIter.setValueOff();
966  bChild->resetBackground(this->mBOutside, this->mAOutside);
967  aIter.setChild(bChild); // transfer child
968  delete aChild;
969  }
970  return STOP;
971  }
972 
973  // If A has a child and B is an outside tile, stop traversing this branch.
974  // Continue traversal only if A and B both have children.
975  return (aChild && bChild) ? 0 : STOP;
976  }
977 
978  /// Process leaf node values.
979  inline int operator()(ChildIterT& aIter, ChildIterT& bIter)
980  {
981  ValueT aValue, bValue;
982  aIter.probeValue(aValue);
983  bIter.probeValue(bValue);
984  if (aValue > bValue) { // a = min(a, b)
985  aIter.setValue(bValue);
986  aIter.setValueOn(bIter.isValueOn());
987  }
988  return 0;
989  }
990 };
991 
992 
993 
994 ////////////////////////////////////////
995 
996 
997 template<typename TreeType>
998 struct CsgIntersectVisitor: public CsgVisitorBase<TreeType>
999 {
1000  typedef TreeType TreeT;
1001  typedef typename TreeT::ValueType ValueT;
1002  typedef typename TreeT::LeafNodeType::ChildAllIter ChildIterT;
1003 
1005 
1007 
1008  /// Don't process nodes that are at different tree levels.
1009  template<typename AIterT, typename BIterT>
1010  inline int operator()(AIterT&, BIterT&) { return 0; }
1011 
1012  /// Process root and internal nodes.
1013  template<typename IterT>
1014  inline int operator()(IterT& aIter, IterT& bIter)
1015  {
1016  ValueT aValue = zeroVal<ValueT>();
1017  typename IterT::ChildNodeType* aChild = aIter.probeChild(aValue);
1018  if (!aChild && !(aValue < zeroVal<ValueT>())) {
1019  // A is an outside tile. Leave it alone and stop traversing this branch.
1020  return STOP;
1021  }
1022 
1023  ValueT bValue = zeroVal<ValueT>();
1024  typename IterT::ChildNodeType* bChild = bIter.probeChild(bValue);
1025  if (!bChild && !(bValue < zeroVal<ValueT>())) {
1026  // B is an outside tile. Make A an outside tile and stop traversing this branch.
1027  aIter.setValue(this->mAOutside);
1028  aIter.setValueOn(bIter.isValueOn());
1029  delete aChild;
1030  return STOP;
1031  }
1032 
1033  if (!aChild && aValue < zeroVal<ValueT>()) {
1034  // A is an inside tile. If B has a child, transfer it to A,
1035  // otherwise leave A alone.
1036  if (bChild) {
1037  bIter.setValue(this->mBOutside);
1038  bIter.setValueOff();
1039  bChild->resetBackground(this->mBOutside, this->mAOutside);
1040  aIter.setChild(bChild); // transfer child
1041  delete aChild;
1042  }
1043  return STOP;
1044  }
1045 
1046  // If A has a child and B is an outside tile, stop traversing this branch.
1047  // Continue traversal only if A and B both have children.
1048  return (aChild && bChild) ? 0 : STOP;
1049  }
1050 
1051  /// Process leaf node values.
1052  inline int operator()(ChildIterT& aIter, ChildIterT& bIter)
1053  {
1054  ValueT aValue, bValue;
1055  aIter.probeValue(aValue);
1056  bIter.probeValue(bValue);
1057  if (aValue < bValue) { // a = max(a, b)
1058  aIter.setValue(bValue);
1059  aIter.setValueOn(bIter.isValueOn());
1060  }
1061  return 0;
1062  }
1063 };
1064 
1065 
1066 ////////////////////////////////////////
1067 
1068 
1069 template<typename TreeType>
1070 struct CsgDiffVisitor: public CsgVisitorBase<TreeType>
1071 {
1072  typedef TreeType TreeT;
1073  typedef typename TreeT::ValueType ValueT;
1074  typedef typename TreeT::LeafNodeType::ChildAllIter ChildIterT;
1075 
1077 
1078  CsgDiffVisitor(const TreeT& a, const TreeT& b): CsgVisitorBase<TreeT>(a, b) {}
1079 
1080  /// Don't process nodes that are at different tree levels.
1081  template<typename AIterT, typename BIterT>
1082  inline int operator()(AIterT&, BIterT&) { return 0; }
1083 
1084  /// Process root and internal nodes.
1085  template<typename IterT>
1086  inline int operator()(IterT& aIter, IterT& bIter)
1087  {
1088  ValueT aValue = zeroVal<ValueT>();
1089  typename IterT::ChildNodeType* aChild = aIter.probeChild(aValue);
1090  if (!aChild && !(aValue < zeroVal<ValueT>())) {
1091  // A is an outside tile. Leave it alone and stop traversing this branch.
1092  return STOP;
1093  }
1094 
1095  ValueT bValue = zeroVal<ValueT>();
1096  typename IterT::ChildNodeType* bChild = bIter.probeChild(bValue);
1097  if (!bChild && bValue < zeroVal<ValueT>()) {
1098  // B is an inside tile. Make A an inside tile and stop traversing this branch.
1099  aIter.setValue(this->mAOutside);
1100  aIter.setValueOn(bIter.isValueOn());
1101  delete aChild;
1102  return STOP;
1103  }
1104 
1105  if (!aChild && aValue < zeroVal<ValueT>()) {
1106  // A is an inside tile. If B has a child, transfer it to A,
1107  // otherwise leave A alone.
1108  if (bChild) {
1109  bIter.setValue(this->mBOutside);
1110  bIter.setValueOff();
1111  bChild->resetBackground(this->mBOutside, this->mAOutside);
1112  aIter.setChild(bChild); // transfer child
1113  bChild->negate();
1114  delete aChild;
1115  }
1116  return STOP;
1117  }
1118 
1119  // If A has a child and B is an outside tile, stop traversing this branch.
1120  // Continue traversal only if A and B both have children.
1121  return (aChild && bChild) ? 0 : STOP;
1122  }
1123 
1124  /// Process leaf node values.
1125  inline int operator()(ChildIterT& aIter, ChildIterT& bIter)
1126  {
1127  ValueT aValue, bValue;
1128  aIter.probeValue(aValue);
1129  bIter.probeValue(bValue);
1130  bValue = math::negative(bValue);
1131  if (aValue < bValue) { // a = max(a, -b)
1132  aIter.setValue(bValue);
1133  aIter.setValueOn(bIter.isValueOn());
1134  }
1135  return 0;
1136  }
1137 };
1138 
1139 
1140 ////////////////////////////////////////
1141 
1142 
1143 template<typename GridOrTreeT>
1145 csgUnion(GridOrTreeT& a, GridOrTreeT& b, bool prune)
1146 {
1147  typedef TreeAdapter<GridOrTreeT> Adapter;
1148  typedef typename Adapter::TreeType TreeT;
1149  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
1150  CsgUnionVisitor<TreeT> visitor(aTree, bTree);
1151  aTree.visit2(bTree, visitor);
1152  if (prune) tools::pruneLevelSet(aTree);
1153 }
1154 
1155 template<typename GridOrTreeT>
1157 csgIntersection(GridOrTreeT& a, GridOrTreeT& b, bool prune)
1158 {
1159  typedef TreeAdapter<GridOrTreeT> Adapter;
1160  typedef typename Adapter::TreeType TreeT;
1161  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
1162  CsgIntersectVisitor<TreeT> visitor(aTree, bTree);
1163  aTree.visit2(bTree, visitor);
1164  if (prune) tools::pruneLevelSet(aTree);
1165 }
1166 
1167 template<typename GridOrTreeT>
1169 csgDifference(GridOrTreeT& a, GridOrTreeT& b, bool prune)
1170 {
1171  typedef TreeAdapter<GridOrTreeT> Adapter;
1172  typedef typename Adapter::TreeType TreeT;
1173  TreeT &aTree = Adapter::tree(a), &bTree = Adapter::tree(b);
1174  CsgDiffVisitor<TreeT> visitor(aTree, bTree);
1175  aTree.visit2(bTree, visitor);
1176  if (prune) tools::pruneLevelSet(aTree);
1177 }
1178 
1179 
1180 template<typename GridOrTreeT>
1181 OPENVDB_STATIC_SPECIALIZATION inline typename GridOrTreeT::Ptr
1182 csgUnionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
1183 {
1184  typedef TreeAdapter<GridOrTreeT> Adapter;
1185  typedef typename Adapter::TreeType::Ptr TreePtrT;
1186 
1187  TreePtrT output = composite::doCSGCopy<composite::CSG_UNION>(
1188  Adapter::tree(a), Adapter::tree(b));
1189 
1191 }
1192 
1193 
1194 template<typename GridOrTreeT>
1195 OPENVDB_STATIC_SPECIALIZATION inline typename GridOrTreeT::Ptr
1196 csgIntersectionCopy(const GridOrTreeT& a, const GridOrTreeT& b)
1197 {
1198  typedef TreeAdapter<GridOrTreeT> Adapter;
1199  typedef typename Adapter::TreeType::Ptr TreePtrT;
1200 
1201  TreePtrT output = composite::doCSGCopy<composite::CSG_INTERSECTION>(
1202  Adapter::tree(a), Adapter::tree(b));
1203 
1205 }
1206 
1207 
1208 template<typename GridOrTreeT>
1209 OPENVDB_STATIC_SPECIALIZATION inline typename GridOrTreeT::Ptr
1210 csgDifferenceCopy(const GridOrTreeT& a, const GridOrTreeT& b)
1211 {
1212  typedef TreeAdapter<GridOrTreeT> Adapter;
1213  typedef typename Adapter::TreeType::Ptr TreePtrT;
1214 
1215  TreePtrT output = composite::doCSGCopy<composite::CSG_DIFFERENCE>(
1216  Adapter::tree(a), Adapter::tree(b));
1217 
1219 }
1220 
1221 ////////////////////////////////////////////////////////
1222 
1223 /// @brief Composite the active values in leaf nodes, i.e. active
1224 /// voxels, of a source tree into a destination tree.
1225 ///
1226 /// @param srcTree source tree from which active voxels are composited.
1227 ///
1228 /// @param dstTree destination tree into which active voxels are composited.
1229 ///
1230 /// @param op a functor of the form <tt>void op(T& dst, const T& src)</tt>,
1231 /// where @c T is the @c ValueType of the tree, that composites
1232 /// a source value into a destination value. By default
1233 /// it copies the value from src to dst.
1234 ///
1235 /// @details All active voxels in the source tree will
1236 /// be active in the destination tree, and their value is
1237 /// determined by a use-defined functor (OpT op) that operates on the
1238 /// source and destination values. The only exception is when
1239 /// the tree type is MaskTree, in which case no functor is
1240 /// needed since by defintion a MaskTree has no values (only topology).
1241 ///
1242 /// @warning This function only operated on leaf node values,
1243 /// i.e. tile values are ignored.
1244 template <typename TreeT, typename OpT = composite::CopyOp<TreeT> >
1245 inline void compActiveLeafVoxels(TreeT &srcTree, TreeT &dstTree, OpT op = composite::CopyOp<TreeT>())
1246 {
1247  composite::doCompActiveLeafVoxels<TreeT, OpT>(srcTree, dstTree, op);
1248 }
1249 
1250 
1251 } // namespace tools
1252 } // namespace OPENVDB_VERSION_NAME
1253 } // namespace openvdb
1254 
1255 #endif // OPENVDB_TOOLS_COMPOSITE_HAS_BEEN_INCLUDED
1256 
1257 // Copyright (c) 2012-2018 DreamWorks Animation LLC
1258 // All rights reserved. This software is distributed under the
1259 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
OPENVDB_STATIC_SPECIALIZATION 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:810
OPENVDB_STATIC_SPECIALIZATION 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:764
CsgIntersectVisitor(const TreeT &a, const TreeT &b)
Definition: Composite.h:1006
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:386
GLenum GLint * range
Definition: glcorearb.h:1924
#define OPENVDB_STATIC_SPECIALIZATION
Macro for determining if there are sufficient C++0x/C++11 features.
Definition: Platform.h:91
BuildSecondarySegment(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:392
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:108
const GLdouble * v
Definition: glcorearb.h:836
png_voidp ptr
Definition: png.h:2145
OPENVDB_STATIC_SPECIALIZATION 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:1182
png_infop png_color_16p * background
Definition: png.h:2326
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:189
int operator()(ChildIterT &aIter, ChildIterT &bIter)
Process leaf node values.
Definition: Composite.h:1125
void operator()(const typename TreeT::ValueOnCIter &iter) const
Definition: Composite.h:834
hboost::mpl::at< NodeChainType, hboost::mpl::int_< 1 > >::type InternalNodeType
Definition: Composite.h:390
int operator()(AIterT &, BIterT &)
Don't process nodes that are at different tree levels.
Definition: Composite.h:1082
TreeT::LeafNodeType::ChildAllIter ChildIterT
Definition: Composite.h:887
png_uint_32 i
Definition: png.h:2877
OPENVDB_STATIC_SPECIALIZATION 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:1210
OPENVDB_STATIC_SPECIALIZATION 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:1157
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:944
int operator()(IterT &aIter, IterT &bIter)
Process root and internal nodes.
Definition: Composite.h:1014
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:1245
const AValueType & a() const
Get the A input value.
Definition: Types.h:426
static GridTypePtr construct(const GridType &grid, TreeTypePtr &tree)
Definition: Composite.h:609
int operator()(AIterT &, BIterT &)
Don't process nodes that are at different tree levels.
Definition: Composite.h:937
OPENVDB_STATIC_SPECIALIZATION 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:795
int operator()(IterT &aIter, IterT &bIter)
Process root and internal nodes.
Definition: Composite.h:1086
GLdouble n
Definition: glcorearb.h:2007
TreeT::LeafNodeType::ChildAllIter ChildIterT
Definition: Composite.h:1074
int operator()(ChildIterT &aIter, ChildIterT &bIter)
Process leaf node values.
Definition: Composite.h:979
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
CsgDiffVisitor(const TreeT &a, const TreeT &b)
Definition: Composite.h:1078
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
int operator()(AIterT &, BIterT &)
Don't process nodes that are at different tree levels.
Definition: Composite.h:1010
const std::enable_if< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:147
Defined various multi-threaded utility functions for trees.
void operator()(const typename TreeT::LeafCIter &leafIter) const
Definition: Composite.h:841
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
const std::enable_if< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:139
hboost::mpl::at< NodeChainType, hboost::mpl::int_< 1 > >::type InternalNodeType
Definition: Composite.h:185
math::Transform & transform()
Return a reference to this grid's transform, which might be shared with other grids.
Definition: Grid.h:347
CsgVisitorBase(const TreeT &aTree, const TreeT &bTree)
Definition: Composite.h:891
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:55
int operator()(IterT &aIter, IterT &bIter)
Process root and internal nodes.
Definition: Composite.h:941
Propagate the signs of distance values from the active voxels in the narrow band to the inactive valu...
OPENVDB_STATIC_SPECIALIZATION 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:1169
GLenum GLenum dst
Definition: glcorearb.h:1792
GLsizei const GLfloat * value
Definition: glcorearb.h:823
int operator()(ChildIterT &aIter, ChildIterT &bIter)
Process leaf node values.
Definition: Composite.h:1052
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...
TreeT::LeafNodeType::ChildAllIter ChildIterT
Definition: Composite.h:929
CsgUnionVisitor(const TreeT &a, const TreeT &b)
Definition: Composite.h:933
OPENVDB_STATIC_SPECIALIZATION 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:748
OPENVDB_STATIC_SPECIALIZATION 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:1145
OPENVDB_STATIC_SPECIALIZATION void compReplace(GridOrTreeT &a, const GridOrTreeT &b)
Copy the active voxels of B into A.
Definition: Composite.h:855
GA_API const UT_StringHolder N
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
static TreeTypePtr construct(const TreeType &, TreeTypePtr &tree)
Definition: Composite.h:598
#define SIZE
Definition: simple.C:40
OPENVDB_STATIC_SPECIALIZATION 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:1196
TreeType::Ptr doCSGCopy(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:571
GLboolean r
Definition: glcorearb.h:1221
const BValueType & b() const
Get the B input value.
Definition: Types.h:428
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:361
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:416
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:135
CombineArgs & setResult(const AValueType &val)
Set the output value.
Definition: Types.h:436
OPENVDB_STATIC_SPECIALIZATION 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:780
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
std::enable_if<!std::is_integral< T >::value, T >::type divide(const T &a, const T &b)
Definition: Composite.h:156
BuildPrimarySegment(const TreeType &lhs, const TreeType &rhs)
Definition: Composite.h:187
GLenum src
Definition: glcorearb.h:1792