OpenVDB  7.0.0
DenseSparseTools.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 #ifndef OPENVDB_TOOLS_DENSESPARSETOOLS_HAS_BEEN_INCLUDED
5 #define OPENVDB_TOOLS_DENSESPARSETOOLS_HAS_BEEN_INCLUDED
6 
7 #include <tbb/parallel_reduce.h>
8 #include <tbb/blocked_range3d.h>
9 #include <tbb/blocked_range2d.h>
10 #include <tbb/blocked_range.h>
11 #include <openvdb/Types.h>
13 #include "Dense.h"
14 #include <algorithm> // for std::min()
15 #include <vector>
16 
17 
18 namespace openvdb {
20 namespace OPENVDB_VERSION_NAME {
21 namespace tools {
22 
89 template<typename OpType, typename DenseType>
90 typename OpType::ResultTreeType::Ptr
91 extractSparseTree(const DenseType& dense, const OpType& functor,
92  const typename OpType::ResultValueType& background,
93  bool threaded = true);
94 
98 template<typename DenseType, typename TreeType>
100 {
101  using ValueType = typename DenseType::ValueType;
102  using Type = typename TreeType::template ValueConverter<ValueType>::Type;
103 };
104 
105 
115 template<typename DenseType, typename MaskTreeType>
117 extractSparseTreeWithMask(const DenseType& dense,
118  const MaskTreeType& mask,
119  const typename DenseType::ValueType& background,
120  bool threaded = true);
121 
122 
143 template<typename ValueT, typename OpType>
145  const openvdb::CoordBBox& bbox, const OpType& op, bool parallel=true);
146 
151 };
152 
160 template<DSCompositeOp, typename TreeT>
162  const TreeT& source,
163  const TreeT& alpha,
164  const typename TreeT::ValueType beta,
165  const typename TreeT::ValueType strength,
166  bool threaded = true);
167 
168 
172 template<typename OpType, typename DenseType>
174 {
175 public:
176  using Index = openvdb::math::Coord::ValueType;
177 
178  using DenseValueType = typename DenseType::ValueType;
179  using ResultTreeType = typename OpType::ResultTreeType;
180  using ResultValueType = typename ResultTreeType::ValueType;
181  using ResultLeafNodeType = typename ResultTreeType::LeafNodeType;
182  using MaskTree = typename ResultTreeType::template ValueConverter<ValueMask>::Type;
183 
184  using Range3d = tbb::blocked_range3d<Index, Index, Index>;
185 
186 private:
187  const DenseType& mDense;
188  const OpType& mFunctor;
189  const ResultValueType mBackground;
190  const openvdb::math::CoordBBox mBBox;
191  const Index mWidth;
192  typename ResultTreeType::Ptr mMask;
193  openvdb::math::Coord mMin;
194 
195 public:
196  SparseExtractor(const DenseType& dense, const OpType& functor,
197  const ResultValueType background) :
198  mDense(dense), mFunctor(functor),
199  mBackground(background),
200  mBBox(dense.bbox()),
201  mWidth(ResultLeafNodeType::DIM),
202  mMask( new ResultTreeType(mBackground))
203  {}
204 
205  SparseExtractor(const DenseType& dense,
206  const openvdb::math::CoordBBox& bbox,
207  const OpType& functor,
208  const ResultValueType background) :
209  mDense(dense), mFunctor(functor),
210  mBackground(background),
211  mBBox(bbox),
212  mWidth(ResultLeafNodeType::DIM),
213  mMask( new ResultTreeType(mBackground))
214  {
215  // mBBox must be inside the coordinate rage of the dense grid
216  if (!dense.bbox().isInside(mBBox)) {
217  OPENVDB_THROW(ValueError, "Data extraction window out of bound");
218  }
219  }
220 
221  SparseExtractor(SparseExtractor& other, tbb::split):
222  mDense(other.mDense), mFunctor(other.mFunctor),
223  mBackground(other.mBackground), mBBox(other.mBBox),
224  mWidth(other.mWidth),
225  mMask(new ResultTreeType(mBackground)),
226  mMin(other.mMin)
227  {}
228 
229  typename ResultTreeType::Ptr extract(bool threaded = true)
230  {
231  // Construct 3D range of leaf nodes that
232  // intersect mBBox.
233 
234  // Snap the bbox to nearest leaf nodes min and max
235 
236  openvdb::math::Coord padded_min = mBBox.min();
237  openvdb::math::Coord padded_max = mBBox.max();
238 
239 
240  padded_min &= ~(mWidth - 1);
241  padded_max &= ~(mWidth - 1);
242 
243  padded_max[0] += mWidth - 1;
244  padded_max[1] += mWidth - 1;
245  padded_max[2] += mWidth - 1;
246 
247 
248  // number of leaf nodes in each direction
249  // division by leaf width, e.g. 8 in most cases
250 
251  const Index xleafCount = ( padded_max.x() - padded_min.x() + 1 ) / mWidth;
252  const Index yleafCount = ( padded_max.y() - padded_min.y() + 1 ) / mWidth;
253  const Index zleafCount = ( padded_max.z() - padded_min.z() + 1 ) / mWidth;
254 
255  mMin = padded_min;
256 
257  Range3d leafRange(0, xleafCount, 1,
258  0, yleafCount, 1,
259  0, zleafCount, 1);
260 
261  // Iterate over the leafnodes applying *this as a functor.
262  if (threaded) {
263  tbb::parallel_reduce(leafRange, *this);
264  } else {
265  (*this)(leafRange);
266  }
267 
268  return mMask;
269  }
270 
271  void operator()(const Range3d& range)
272  {
273  ResultLeafNodeType* leaf = nullptr;
274 
275  // Unpack the range3d item.
276  const Index imin = range.pages().begin();
277  const Index imax = range.pages().end();
278 
279  const Index jmin = range.rows().begin();
280  const Index jmax = range.rows().end();
281 
282  const Index kmin = range.cols().begin();
283  const Index kmax = range.cols().end();
284 
285 
286  // loop over all the candidate leafs. Adding only those with 'true' values
287  // to the tree
288 
289  for (Index i = imin; i < imax; ++i) {
290  for (Index j = jmin; j < jmax; ++j) {
291  for (Index k = kmin; k < kmax; ++k) {
292 
293  // Calculate the origin of candidate leaf
294  const openvdb::math::Coord origin =
295  mMin + openvdb::math::Coord(mWidth * i,
296  mWidth * j,
297  mWidth * k );
298 
299  if (leaf == nullptr) {
300  leaf = new ResultLeafNodeType(origin, mBackground);
301  } else {
302  leaf->setOrigin(origin);
303  leaf->fill(mBackground);
304  leaf->setValuesOff();
305  }
306 
307  // The bounding box for this leaf
308 
309  openvdb::math::CoordBBox localBBox = leaf->getNodeBoundingBox();
310 
311  // Shrink to the intersection with mBBox (i.e. the dense
312  // volume)
313 
314  localBBox.intersect(mBBox);
315 
316  // Early out for non-intersecting leafs
317 
318  if (localBBox.empty()) continue;
319 
320 
321  const openvdb::math::Coord start = localBBox.getStart();
322  const openvdb::math::Coord end = localBBox.getEnd();
323 
324  // Order the looping to respect the memory layout in
325  // the Dense source
326 
327  if (mDense.memoryLayout() == openvdb::tools::LayoutZYX) {
328 
329  openvdb::math::Coord ijk;
330  Index offset;
331  const DenseValueType* dp;
332  for (ijk[0] = start.x(); ijk[0] < end.x(); ++ijk[0] ) {
333  for (ijk[1] = start.y(); ijk[1] < end.y(); ++ijk[1] ) {
334  for (ijk[2] = start.z(),
335  offset = ResultLeafNodeType::coordToOffset(ijk),
336  dp = &mDense.getValue(ijk);
337  ijk[2] < end.z(); ++ijk[2], ++offset, ++dp) {
338 
339  mFunctor(*dp, offset, leaf);
340  }
341  }
342  }
343 
344  } else {
345 
346  openvdb::math::Coord ijk;
347  const DenseValueType* dp;
348  for (ijk[2] = start.z(); ijk[2] < end.z(); ++ijk[2]) {
349  for (ijk[1] = start.y(); ijk[1] < end.y(); ++ijk[1]) {
350  for (ijk[0] = start.x(),
351  dp = &mDense.getValue(ijk);
352  ijk[0] < end.x(); ++ijk[0], ++dp) {
353 
354  mFunctor(*dp, ijk, leaf);
355 
356  }
357  }
358  }
359  }
360 
361  // Only add non-empty leafs (empty is defined as all inactive)
362 
363  if (!leaf->isEmpty()) {
364  mMask->addLeaf(leaf);
365  leaf = nullptr;
366  }
367 
368  }
369  }
370  }
371 
372  // Clean up an unused leaf.
373 
374  if (leaf != nullptr) delete leaf;
375  }
376 
377  void join(SparseExtractor& rhs) {
378  mMask->merge(*rhs.mMask);
379  }
380 }; // class SparseExtractor
381 
382 
383 template<typename OpType, typename DenseType>
384 typename OpType::ResultTreeType::Ptr
385 extractSparseTree(const DenseType& dense, const OpType& functor,
386  const typename OpType::ResultValueType& background,
387  bool threaded)
388 {
389  // Construct the mask using a parallel reduce pattern.
390  // Each thread computes disjoint mask-trees. The join merges
391  // into a single tree.
392 
393  SparseExtractor<OpType, DenseType> extractor(dense, functor, background);
394 
395  return extractor.extract(threaded);
396 }
397 
398 
402 template<typename DenseType, typename MaskTreeType>
404 {
405 public:
408  using ResultLeafNodeType = typename ResultTreeType::LeafNodeType;
409  using ResultValueType = typename ResultTreeType::ValueType;
411 
412  using MaskTree = typename ResultTreeType::template ValueConverter<ValueMask>::Type;
414  using MaskLeafVec = std::vector<const typename MaskTree::LeafNodeType*>;
415 
416 
417  SparseMaskedExtractor(const DenseType& dense,
418  const ResultValueType& background,
419  const MaskLeafVec& leafVec
420  ):
421  mDense(dense), mBackground(background), mBBox(dense.bbox()),
422  mLeafVec(leafVec),
423  mResult(new ResultTreeType(mBackground))
424  {}
425 
426  SparseMaskedExtractor(const SparseMaskedExtractor& other, tbb::split):
427  mDense(other.mDense), mBackground(other.mBackground), mBBox(other.mBBox),
428  mLeafVec(other.mLeafVec), mResult( new ResultTreeType(mBackground))
429  {}
430 
431  typename ResultTreeType::Ptr extract(bool threaded = true)
432  {
433  tbb::blocked_range<size_t> range(0, mLeafVec.size());
434 
435  if (threaded) {
436  tbb::parallel_reduce(range, *this);
437  } else {
438  (*this)(range);
439  }
440 
441  return mResult;
442  }
443 
444  // Used in looping over leaf nodes in the masked grid
445  // and using the active mask to select data to
446  void operator()(const tbb::blocked_range<size_t>& range)
447  {
448  ResultLeafNodeType* leaf = nullptr;
449 
450  // loop over all the candidate leafs. Adding only those with 'true' values
451  // to the tree
452 
453  for (size_t idx = range.begin(); idx < range.end(); ++ idx) {
454 
455  const typename MaskTree::LeafNodeType* maskLeaf = mLeafVec[idx];
456 
457  // The bounding box for this leaf
458 
459  openvdb::math::CoordBBox localBBox = maskLeaf->getNodeBoundingBox();
460 
461  // Shrink to the intersection with the dense volume
462 
463  localBBox.intersect(mBBox);
464 
465  // Early out if there was no intersection
466 
467  if (localBBox.empty()) continue;
468 
469  // Reset or allocate the target leaf
470 
471  if (leaf == nullptr) {
472  leaf = new ResultLeafNodeType(maskLeaf->origin(), mBackground);
473  } else {
474  leaf->setOrigin(maskLeaf->origin());
475  leaf->fill(mBackground);
476  leaf->setValuesOff();
477  }
478 
479  // Iterate over the intersecting bounding box
480  // copying active values to the result tree
481 
482  const openvdb::math::Coord start = localBBox.getStart();
483  const openvdb::math::Coord end = localBBox.getEnd();
484 
485  openvdb::math::Coord ijk;
486 
487  if (mDense.memoryLayout() == openvdb::tools::LayoutZYX
488  && maskLeaf->isDense()) {
489 
490  Index offset;
491  const DenseValueType* src;
492  for (ijk[0] = start.x(); ijk[0] < end.x(); ++ijk[0] ) {
493  for (ijk[1] = start.y(); ijk[1] < end.y(); ++ijk[1] ) {
494  for (ijk[2] = start.z(),
495  offset = ResultLeafNodeType::coordToOffset(ijk),
496  src = &mDense.getValue(ijk);
497  ijk[2] < end.z(); ++ijk[2], ++offset, ++src) {
498 
499  // copy into leaf
500  leaf->setValueOn(offset, *src);
501  }
502 
503  }
504  }
505 
506  } else {
507 
508  Index offset;
509  for (ijk[0] = start.x(); ijk[0] < end.x(); ++ijk[0] ) {
510  for (ijk[1] = start.y(); ijk[1] < end.y(); ++ijk[1] ) {
511  for (ijk[2] = start.z(),
512  offset = ResultLeafNodeType::coordToOffset(ijk);
513  ijk[2] < end.z(); ++ijk[2], ++offset) {
514 
515  if (maskLeaf->isValueOn(offset)) {
516  const ResultValueType denseValue = mDense.getValue(ijk);
517  leaf->setValueOn(offset, denseValue);
518  }
519  }
520  }
521  }
522  }
523  // Only add non-empty leafs (empty is defined as all inactive)
524 
525  if (!leaf->isEmpty()) {
526  mResult->addLeaf(leaf);
527  leaf = nullptr;
528  }
529  }
530 
531  // Clean up an unused leaf.
532 
533  if (leaf != nullptr) delete leaf;
534  }
535 
537  mResult->merge(*rhs.mResult);
538  }
539 
540 
541 private:
542  const DenseType& mDense;
543  const ResultValueType mBackground;
544  const openvdb::math::CoordBBox& mBBox;
545  const MaskLeafVec& mLeafVec;
546 
547  typename ResultTreeType::Ptr mResult;
548 
549 }; // class SparseMaskedExtractor
550 
551 
553 template<typename _ResultTreeType, typename DenseValueType>
555 {
556  using ResultTreeType = _ResultTreeType;
557  using ResultLeafNodeType = typename ResultTreeType::LeafNodeType;
558 
559  template<typename CoordOrIndex> inline void
560  operator()(const DenseValueType& a, const CoordOrIndex& offset, ResultLeafNodeType* leaf) const
561  {
562  leaf->setValueOn(offset, a);
563  }
564 };
565 
566 
567 template<typename DenseType, typename MaskTreeType>
569 extractSparseTreeWithMask(const DenseType& dense,
570  const MaskTreeType& maskProxy,
571  const typename DenseType::ValueType& background,
572  bool threaded)
573 {
575  using DenseValueType = typename LeafExtractor::DenseValueType;
576  using ResultTreeType = typename LeafExtractor::ResultTreeType;
577  using MaskLeafVec = typename LeafExtractor::MaskLeafVec;
578  using MaskTree = typename LeafExtractor::MaskTree;
579  using MaskLeafCIter = typename LeafExtractor::MaskLeafCIter;
580  using ExtractionRule = ExtractAll<ResultTreeType, DenseValueType>;
581 
582  // Use Mask tree to hold the topology
583 
584  MaskTree maskTree(maskProxy, false, TopologyCopy());
585 
586  // Construct an array of pointers to the mask leafs.
587 
588  const size_t leafCount = maskTree.leafCount();
589  MaskLeafVec leafarray(leafCount);
590  MaskLeafCIter leafiter = maskTree.cbeginLeaf();
591  for (size_t n = 0; n != leafCount; ++n, ++leafiter) {
592  leafarray[n] = leafiter.getLeaf();
593  }
594 
595 
596  // Extract the data that is masked leaf nodes in the mask.
597 
598  LeafExtractor leafextractor(dense, background, leafarray);
599  typename ResultTreeType::Ptr resultTree = leafextractor.extract(threaded);
600 
601 
602  // Extract data that is masked by tiles in the mask.
603 
604 
605  // Loop over the mask tiles, extracting the data into new trees.
606  // These trees will be leaf-orthogonal to the leafTree (i.e. no leaf
607  // nodes will overlap). Merge these trees into the result.
608 
609  typename MaskTreeType::ValueOnCIter tileIter(maskProxy);
610  tileIter.setMaxDepth(MaskTreeType::ValueOnCIter::LEAF_DEPTH - 1);
611 
612  // Return the leaf tree if the mask had no tiles
613 
614  if (!tileIter) return resultTree;
615 
616  ExtractionRule allrule;
617 
618  // Loop over the tiles in series, but the actual data extraction
619  // is in parallel.
620 
621  CoordBBox bbox;
622  for ( ; tileIter; ++tileIter) {
623 
624  // Find the intersection of the tile with the dense grid.
625 
626  tileIter.getBoundingBox(bbox);
627  bbox.intersect(dense.bbox());
628 
629  if (bbox.empty()) continue;
630 
631  SparseExtractor<ExtractionRule, DenseType> copyData(dense, bbox, allrule, background);
632  typename ResultTreeType::Ptr fromTileTree = copyData.extract(threaded);
633  resultTree->merge(*fromTileTree);
634  }
635 
636  return resultTree;
637 }
638 
639 
643 template<typename _ValueT, typename OpType>
645 {
646 public:
647  using ValueT = _ValueT;
649  using IntType = openvdb::math::Coord::ValueType;
650  using RangeType = tbb::blocked_range2d<IntType, IntType>;
651 
652 private:
653  DenseT& mDense;
654  const OpType& mOp;
655  openvdb::math::CoordBBox mBBox;
656 
657 public:
658  DenseTransformer(DenseT& dense, const openvdb::math::CoordBBox& bbox, const OpType& functor):
659  mDense(dense), mOp(functor), mBBox(dense.bbox())
660  {
661  // The iteration space is the intersection of the
662  // input bbox and the index-space covered by the dense grid
663  mBBox.intersect(bbox);
664  }
665 
667  mDense(other.mDense), mOp(other.mOp), mBBox(other.mBBox) {}
668 
669  void apply(bool threaded = true) {
670 
671  // Early out if the iteration space is empty
672 
673  if (mBBox.empty()) return;
674 
675 
676  const openvdb::math::Coord start = mBBox.getStart();
677  const openvdb::math::Coord end = mBBox.getEnd();
678 
679  // The iteration range only the slower two directions.
680  const RangeType range(start.x(), end.x(), 1,
681  start.y(), end.y(), 1);
682 
683  if (threaded) {
684  tbb::parallel_for(range, *this);
685  } else {
686  (*this)(range);
687  }
688  }
689 
690  void operator()(const RangeType& range) const {
691 
692  // The stride in the z-direction.
693  // Note: the bbox is [inclusive, inclusive]
694 
695  const size_t zlength = size_t(mBBox.max().z() - mBBox.min().z() + 1);
696 
697  const IntType imin = range.rows().begin();
698  const IntType imax = range.rows().end();
699  const IntType jmin = range.cols().begin();
700  const IntType jmax = range.cols().end();
701 
702 
703  openvdb::math::Coord xyz(imin, jmin, mBBox.min().z());
704  for (xyz[0] = imin; xyz[0] != imax; ++xyz[0]) {
705  for (xyz[1] = jmin; xyz[1] != jmax; ++xyz[1]) {
706 
707  mOp.transform(mDense, xyz, zlength);
708  }
709  }
710  }
711 }; // class DenseTransformer
712 
713 
717 template<typename ValueT, typename PointWiseOp>
719 {
720  ContiguousOp(const PointWiseOp& op) : mOp(op){}
721 
723  inline void transform(DenseT& dense, openvdb::math::Coord& ijk, size_t size) const
724  {
725  ValueT* dp = const_cast<ValueT*>(&dense.getValue(ijk));
726 
727  for (size_t offset = 0; offset < size; ++offset) {
728  dp[offset] = mOp(dp[offset]);
729  }
730  }
731 
732  const PointWiseOp mOp;
733 };
734 
735 
737 template<typename ValueT, typename PointwiseOpT>
738 void
740  const openvdb::CoordBBox& bbox,
741  const PointwiseOpT& functor, bool parallel)
742 {
744 
745  // Convert the Op so it operates on a contiguous line in memory
746 
747  OpT op(functor);
748 
749  // Apply to the index space intersection in the dense grid
750  DenseTransformer<ValueT, OpT> transformer(dense, bbox, op);
751  transformer.apply(parallel);
752 }
753 
754 
755 template<typename CompositeMethod, typename _TreeT>
757 {
758 public:
759  using TreeT = _TreeT;
760  using ValueT = typename TreeT::ValueType;
761  using LeafT = typename TreeT::LeafNodeType;
762  using MaskTreeT = typename TreeT::template ValueConverter<ValueMask>::Type;
763  using MaskLeafT = typename MaskTreeT::LeafNodeType;
765  using Index = openvdb::math::Coord::ValueType;
766  using Range3d = tbb::blocked_range3d<Index, Index, Index>;
767 
768  SparseToDenseCompositor(DenseT& dense, const TreeT& source, const TreeT& alpha,
769  const ValueT beta, const ValueT strength) :
770  mDense(dense), mSource(source), mAlpha(alpha), mBeta(beta), mStrength(strength)
771  {}
772 
774  mDense(other.mDense), mSource(other.mSource), mAlpha(other.mAlpha),
775  mBeta(other.mBeta), mStrength(other.mStrength) {}
776 
777 
778  void sparseComposite(bool threaded)
779  {
780  const ValueT beta = mBeta;
781  const ValueT strength = mStrength;
782 
783  // construct a tree that defines the iteration space
784 
785  MaskTreeT maskTree(mSource, false /*background*/, openvdb::TopologyCopy());
786  maskTree.topologyUnion(mAlpha);
787 
788  // Composite regions that are represented by leafnodes in either mAlpha or mSource
789  // Parallelize over bool-leafs
790 
791  openvdb::tree::LeafManager<const MaskTreeT> maskLeafs(maskTree);
792  maskLeafs.foreach(*this, threaded);
793 
794  // Composite regions that are represented by tiles
795  // Parallelize within each tile.
796 
797  typename MaskTreeT::ValueOnCIter citer = maskTree.cbeginValueOn();
798  citer.setMaxDepth(MaskTreeT::ValueOnCIter::LEAF_DEPTH - 1);
799 
800  if (!citer) return;
801 
802  typename tree::ValueAccessor<const TreeT> alphaAccessor(mAlpha);
803  typename tree::ValueAccessor<const TreeT> sourceAccessor(mSource);
804 
805  for (; citer; ++citer) {
806 
807  const openvdb::math::Coord org = citer.getCoord();
808 
809  // Early out if both alpha and source are zero in this tile.
810 
811  const ValueT alphaValue = alphaAccessor.getValue(org);
812  const ValueT sourceValue = sourceAccessor.getValue(org);
813 
814  if (openvdb::math::isZero(alphaValue) &&
815  openvdb::math::isZero(sourceValue)) continue;
816 
817  // Compute overlap of tile with the dense grid
818 
819  openvdb::math::CoordBBox localBBox = citer.getBoundingBox();
820  localBBox.intersect(mDense.bbox());
821 
822  // Early out if there is no intersection
823 
824  if (localBBox.empty()) continue;
825 
826  // Composite the tile-uniform values into the dense grid.
827  compositeFromTile(mDense, localBBox, sourceValue,
828  alphaValue, beta, strength, threaded);
829  }
830  }
831 
832  // Composites leaf values where the alpha values are active.
833  // Used in sparseComposite
834  void inline operator()(const MaskLeafT& maskLeaf, size_t /*i*/) const
835  {
836  using ULeaf = UniformLeaf;
837  openvdb::math::CoordBBox localBBox = maskLeaf.getNodeBoundingBox();
838  localBBox.intersect(mDense.bbox());
839 
840  // Early out for non-overlapping leafs
841 
842  if (localBBox.empty()) return;
843 
844  const openvdb::math::Coord org = maskLeaf.origin();
845  const LeafT* alphaLeaf = mAlpha.probeLeaf(org);
846  const LeafT* sourceLeaf = mSource.probeLeaf(org);
847 
848  if (!sourceLeaf) {
849 
850  // Create a source leaf proxy with the correct value
851  ULeaf uniformSource(mSource.getValue(org));
852 
853  if (!alphaLeaf) {
854 
855  // Create an alpha leaf proxy with the correct value
856  ULeaf uniformAlpha(mAlpha.getValue(org));
857 
858  compositeFromLeaf(mDense, localBBox, uniformSource, uniformAlpha,
859  mBeta, mStrength);
860  } else {
861 
862  compositeFromLeaf(mDense, localBBox, uniformSource, *alphaLeaf,
863  mBeta, mStrength);
864  }
865  } else {
866  if (!alphaLeaf) {
867 
868  // Create an alpha leaf proxy with the correct value
869  ULeaf uniformAlpha(mAlpha.getValue(org));
870 
871  compositeFromLeaf(mDense, localBBox, *sourceLeaf, uniformAlpha,
872  mBeta, mStrength);
873  } else {
874 
875  compositeFromLeaf(mDense, localBBox, *sourceLeaf, *alphaLeaf,
876  mBeta, mStrength);
877  }
878  }
879  }
880  // i.e. it assumes that all valueOff Alpha voxels have value 0.
881 
882  template<typename LeafT1, typename LeafT2>
883  inline static void compositeFromLeaf(DenseT& dense, const openvdb::math::CoordBBox& bbox,
884  const LeafT1& source, const LeafT2& alpha,
885  const ValueT beta, const ValueT strength)
886  {
887  using IntType = openvdb::math::Coord::ValueType;
888 
889  const ValueT sbeta = strength * beta;
890  openvdb::math::Coord ijk = bbox.min();
891 
892 
893  if (alpha.isDense() /*all active values*/) {
894 
895  // Optimal path for dense alphaLeaf
896  const IntType size = bbox.max().z() + 1 - bbox.min().z();
897 
898  for (ijk[0] = bbox.min().x(); ijk[0] < bbox.max().x() + 1; ++ijk[0]) {
899  for (ijk[1] = bbox.min().y(); ijk[1] < bbox.max().y() + 1; ++ijk[1]) {
900 
901  ValueT* d = const_cast<ValueT*>(&dense.getValue(ijk));
902  const ValueT* a = &alpha.getValue(ijk);
903  const ValueT* s = &source.getValue(ijk);
904 
905  for (IntType idx = 0; idx < size; ++idx) {
906  d[idx] = CompositeMethod::apply(d[idx], a[idx], s[idx],
907  strength, beta, sbeta);
908  }
909  }
910  }
911  } else {
912 
913  // AlphaLeaf has non-active cells.
914 
915  for (ijk[0] = bbox.min().x(); ijk[0] < bbox.max().x() + 1; ++ijk[0]) {
916  for (ijk[1] = bbox.min().y(); ijk[1] < bbox.max().y() + 1; ++ijk[1]) {
917  for (ijk[2] = bbox.min().z(); ijk[2] < bbox.max().z() + 1; ++ijk[2]) {
918 
919  if (alpha.isValueOn(ijk)) {
920  dense.setValue(ijk, CompositeMethod::apply(dense.getValue(ijk),
921  alpha.getValue(ijk), source.getValue(ijk), strength, beta, sbeta));
922  }
923  }
924  }
925  }
926  }
927  }
928 
929  inline static void compositeFromTile(DenseT& dense, openvdb::math::CoordBBox& bbox,
930  const ValueT& sourceValue, const ValueT& alphaValue,
931  const ValueT& beta, const ValueT& strength,
932  bool threaded)
933  {
934  using TileTransformer = UniformTransformer;
935  TileTransformer functor(sourceValue, alphaValue, beta, strength);
936 
937  // Transform the data inside the bbox according to the TileTranformer.
938 
939  transformDense(dense, bbox, functor, threaded);
940  }
941 
942  void denseComposite(bool threaded)
943  {
946  const openvdb::math::CoordBBox& bbox = mDense.bbox();
947 
948  Range3d range(bbox.min().x(), bbox.max().x(), LeafT::DIM,
949  bbox.min().y(), bbox.max().y(), LeafT::DIM,
950  bbox.min().z(), bbox.max().z(), LeafT::DIM);
951 
952  // Iterate over the range, compositing into
953  // the dense grid using value accessors for
954  // sparse the grids.
955  if (threaded) {
956  tbb::parallel_for(range, *this);
957  } else {
958  (*this)(range);
959  }
960  }
961 
962  // Composites a dense region using value accessors
963  // into a dense grid
964  void operator()(const Range3d& range) const
965  {
966  // Use value accessors to alpha and source
967 
968  typename tree::ValueAccessor<const TreeT> alphaAccessor(mAlpha);
969  typename tree::ValueAccessor<const TreeT> sourceAccessor(mSource);
970 
971  const ValueT strength = mStrength;
972  const ValueT beta = mBeta;
973  const ValueT sbeta = strength * beta;
974 
975  // Unpack the range3d item.
976  const Index imin = range.pages().begin();
977  const Index imax = range.pages().end();
978 
979  const Index jmin = range.rows().begin();
980  const Index jmax = range.rows().end();
981 
982  const Index kmin = range.cols().begin();
983  const Index kmax = range.cols().end();
984 
985  openvdb::Coord ijk;
986  for (ijk[0] = imin; ijk[0] < imax; ++ijk[0]) {
987  for (ijk[1] = jmin; ijk[1] < jmax; ++ijk[1]) {
988  for (ijk[2] = kmin; ijk[2] < kmax; ++ijk[2]) {
989  const ValueT d_old = mDense.getValue(ijk);
990  const ValueT& alpha = alphaAccessor.getValue(ijk);
991  const ValueT& src = sourceAccessor.getValue(ijk);
992 
993  mDense.setValue(ijk,
994  CompositeMethod::apply(d_old, alpha, src, strength, beta, sbeta));
995  }
996  }
997  }
998  }
999 
1000 private:
1001  // Internal class that wraps the templated composite method
1002  // for use when both alpha and source are uniform over
1003  // a prescribed bbox (e.g. a tile).
1004  class UniformTransformer
1005  {
1006  public:
1007  UniformTransformer(const ValueT& source, const ValueT& alpha, const ValueT& _beta,
1008  const ValueT& _strength) :
1009  mSource(source), mAlpha(alpha), mBeta(_beta),
1010  mStrength(_strength), mSBeta(_strength * _beta)
1011  {}
1012 
1013  ValueT operator()(const ValueT& input) const
1014  {
1015  return CompositeMethod::apply(input, mAlpha, mSource, mStrength, mBeta, mSBeta);
1016  }
1017 
1018  private:
1019  const ValueT mSource;
1020  const ValueT mAlpha;
1021  const ValueT mBeta;
1022  const ValueT mStrength;
1023  const ValueT mSBeta;
1024  };
1025 
1026 
1027  // Simple Class structure that mimics a leaf
1028  // with uniform values. Holds LeafT::DIM copies
1029  // of a value in an array.
1030  struct Line { ValueT mValues[LeafT::DIM]; };
1031  class UniformLeaf : private Line
1032  {
1033  public:
1034  using ValueT = typename LeafT::ValueType;
1035 
1036  using BaseT = Line;
1037  UniformLeaf(const ValueT& value) : BaseT(init(value)) {}
1038 
1039  static const BaseT init(const ValueT& value) {
1040  BaseT tmp;
1041  for (openvdb::Index i = 0; i < LeafT::DIM; ++i) {
1042  tmp.mValues[i] = value;
1043  }
1044  return tmp;
1045  }
1046 
1047  bool isDense() const { return true; }
1048  bool isValueOn(openvdb::math::Coord&) const { return true; }
1049 
1050  const ValueT& getValue(const openvdb::math::Coord&) const { return BaseT::mValues[0]; }
1051  };
1052 
1053 private:
1054  DenseT& mDense;
1055  const TreeT& mSource;
1056  const TreeT& mAlpha;
1057  ValueT mBeta;
1058  ValueT mStrength;
1059 }; // class SparseToDenseCompositor
1060 
1061 
1062 namespace ds
1063 {
1065  template<typename ValueT>
1067  struct OpOver
1068  {
1069  static inline ValueT apply(const ValueT u, const ValueT alpha,
1070  const ValueT v,
1071  const ValueT strength,
1072  const ValueT beta,
1073  const ValueT /*sbeta*/)
1074  { return (u + strength * alpha * (beta * v - u)); }
1075  };
1076 
1077  template<typename ValueT>
1078  struct OpAdd
1079  {
1080  static inline ValueT apply(const ValueT u, const ValueT alpha,
1081  const ValueT v,
1082  const ValueT /*strength*/,
1083  const ValueT /*beta*/,
1084  const ValueT sbeta)
1085  { return (u + sbeta * alpha * v); }
1086  };
1087 
1088  template<typename ValueT>
1089  struct OpSub
1090  {
1091  static inline ValueT apply(const ValueT u, const ValueT alpha,
1092  const ValueT v,
1093  const ValueT /*strength*/,
1094  const ValueT /*beta*/,
1095  const ValueT sbeta)
1096  { return (u - sbeta * alpha * v); }
1097  };
1098 
1099  template<typename ValueT>
1100  struct OpMin
1101  {
1102  static inline ValueT apply(const ValueT u, const ValueT alpha,
1103  const ValueT v,
1104  const ValueT s /*trength*/,
1105  const ValueT beta,
1106  const ValueT /*sbeta*/)
1107  { return ( ( 1 - s * alpha) * u + s * alpha * std::min(u, beta * v) ); }
1108  };
1109 
1110  template<typename ValueT>
1111  struct OpMax
1112  {
1113  static inline ValueT apply(const ValueT u, const ValueT alpha,
1114  const ValueT v,
1115  const ValueT s/*trength*/,
1116  const ValueT beta,
1117  const ValueT /*sbeta*/)
1118  { return ( ( 1 - s * alpha ) * u + s * alpha * std::min(u, beta * v) ); }
1119  };
1120 
1121  template<typename ValueT>
1122  struct OpMult
1123  {
1124  static inline ValueT apply(const ValueT u, const ValueT alpha,
1125  const ValueT v,
1126  const ValueT s/*trength*/,
1127  const ValueT /*beta*/,
1128  const ValueT sbeta)
1129  { return ( ( 1 + alpha * (sbeta * v - s)) * u ); }
1130  };
1132 
1134  template<DSCompositeOp OP, typename ValueT>
1137 
1138  template<typename ValueT>
1140 
1141  template<typename ValueT>
1143 
1144  template<typename ValueT>
1146 
1147  template<typename ValueT>
1149 
1150  template<typename ValueT>
1152 
1153  template<typename ValueT>
1156 
1157 } // namespace ds
1158 
1159 
1160 template<DSCompositeOp OpT, typename TreeT>
1161 inline void
1164  const TreeT& source, const TreeT& alpha,
1165  const typename TreeT::ValueType beta,
1166  const typename TreeT::ValueType strength,
1167  bool threaded)
1168 {
1169  using ValueT = typename TreeT::ValueType;
1171  using Method = typename Translator::OpT;
1172 
1173  if (openvdb::math::isZero(strength)) return;
1174 
1175  SparseToDenseCompositor<Method, TreeT> tool(dense, source, alpha, beta, strength);
1176 
1177  if (openvdb::math::isZero(alpha.background()) &&
1178  openvdb::math::isZero(source.background()))
1179  {
1180  // Use the sparsity of (alpha U source) as the iteration space.
1181  tool.sparseComposite(threaded);
1182  } else {
1183  // Use the bounding box of dense as the iteration space.
1184  tool.denseComposite(threaded);
1185  }
1186 }
1187 
1188 } // namespace tools
1189 } // namespace OPENVDB_VERSION_NAME
1190 } // namespace openvdb
1191 
1192 #endif //OPENVDB_TOOLS_DENSESPARSETOOLS_HAS_BEEN_INCLUDED
SparseExtractor(const DenseType &dense, const openvdb::math::CoordBBox &bbox, const OpType &functor, const ResultValueType background)
Definition: DenseSparseTools.h:205
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT, const ValueT, const ValueT sbeta)
Definition: DenseSparseTools.h:1091
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT s, const ValueT beta, const ValueT)
Definition: DenseSparseTools.h:1113
SparseMaskedExtractor(const DenseType &dense, const ResultValueType &background, const MaskLeafVec &leafVec)
Definition: DenseSparseTools.h:417
typename DenseType::ValueType ValueType
Definition: DenseSparseTools.h:101
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:281
Translator that converts an enum to compositing functor types.
Definition: DenseSparseTools.h:1136
typename OpType::ResultTreeType ResultTreeType
Definition: DenseSparseTools.h:179
_ResultTreeType ResultTreeType
Definition: DenseSparseTools.h:556
typename ResultTreeType::template ValueConverter< ValueMask >::Type MaskTree
Definition: DenseSparseTools.h:412
tbb::blocked_range2d< IntType, IntType > RangeType
Definition: DenseSparseTools.h:650
ResultTreeType::Ptr extract(bool threaded=true)
Definition: DenseSparseTools.h:431
a simple utility class used by extractSparseTreeWithMask
Definition: DenseSparseTools.h:554
typename MaskTree::LeafCIter MaskLeafCIter
Definition: DenseSparseTools.h:413
typename TreeT::LeafNodeType LeafT
Definition: DenseSparseTools.h:761
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
void setValue(size_t offset, const ValueT &value)
Set the value of the voxel at the given array offset.
Definition: Dense.h:260
Dense is a simple dense grid API used by the CopyToDense and CopyFromDense classes defined below...
Definition: Dense.h:182
typename TreeT::ValueType ValueT
Definition: DenseSparseTools.h:760
Definition: DenseSparseTools.h:150
typename DSConverter< DenseType, MaskTreeType >::Type _ResultTreeType
Definition: DenseSparseTools.h:406
Definition: DenseSparseTools.h:150
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:230
ContiguousOp(const PointWiseOp &op)
Definition: DenseSparseTools.h:720
openvdb::math::Coord::ValueType Index
Definition: DenseSparseTools.h:765
typename ResultTreeType::LeafNodeType ResultLeafNodeType
Definition: DenseSparseTools.h:408
DSCompositeOp
Definition: DenseSparseTools.h:149
ResultTreeType::Ptr extract(bool threaded=true)
Definition: DenseSparseTools.h:229
void join(SparseMaskedExtractor &rhs)
Definition: DenseSparseTools.h:536
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1143
This file defines a simple dense grid and efficient converters to and from VDB grids.
_ValueT ValueT
Definition: DenseSparseTools.h:647
typename ResultTreeType::template ValueConverter< ValueMask >::Type MaskTree
Definition: DenseSparseTools.h:182
typename ResultTreeType::ValueType ResultValueType
Definition: DenseSparseTools.h:180
typename TreeType::template ValueConverter< ValueType >::Type Type
Definition: DenseSparseTools.h:102
openvdb::math::Coord::ValueType IntType
Definition: DenseSparseTools.h:649
DenseTransformer(const DenseTransformer &other)
Definition: DenseSparseTools.h:666
void operator()(const RangeType &range) const
Definition: DenseSparseTools.h:690
Functor-based class used to extract data from a dense grid, at the index-space intersection with a su...
Definition: DenseSparseTools.h:403
typename TreeT::template ValueConverter< ValueMask >::Type MaskTreeT
Definition: DenseSparseTools.h:762
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT s, const ValueT beta, const ValueT)
Definition: DenseSparseTools.h:1102
void apply(bool threaded=true)
Definition: DenseSparseTools.h:669
_ResultTreeType ResultTreeType
Definition: DenseSparseTools.h:407
SparseToDenseCompositor(const SparseToDenseCompositor &other)
Definition: DenseSparseTools.h:773
SparseExtractor(const DenseType &dense, const OpType &functor, const ResultValueType background)
Definition: DenseSparseTools.h:196
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1157
typename ResultTreeType::LeafNodeType ResultLeafNodeType
Definition: DenseSparseTools.h:557
void compositeToDense(Dense< typename TreeT::ValueType, LayoutZYX > &dense, const TreeT &source, const TreeT &alpha, const typename TreeT::ValueType beta, const typename TreeT::ValueType strength, bool threaded=true)
Composite data from a sparse tree into a dense array of the same value type.
Definition: DenseSparseTools.h:1162
Definition: DenseSparseTools.h:150
Definition: Exceptions.h:65
void operator()(const tbb::blocked_range< size_t > &range)
Definition: DenseSparseTools.h:446
OpType::ResultTreeType::Ptr extractSparseTree(const DenseType &dense, const OpType &functor, const typename OpType::ResultValueType &background, bool threaded=true)
Selectively extract and transform data from a dense grid, producing a sparse tree with leaf nodes onl...
Definition: DenseSparseTools.h:385
void transform(DenseT &dense, openvdb::math::Coord &ijk, size_t size) const
Definition: DenseSparseTools.h:723
Definition: DenseSparseTools.h:1089
void operator()(const Range3d &range)
Definition: DenseSparseTools.h:271
Definition: DenseSparseTools.h:1078
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
tbb::blocked_range3d< Index, Index, Index > Range3d
Definition: DenseSparseTools.h:766
Class that applies a functor to the index space intersection of a prescribed bounding box and the den...
Definition: DenseSparseTools.h:644
void denseComposite(bool threaded)
Definition: DenseSparseTools.h:942
SparseMaskedExtractor(const SparseMaskedExtractor &other, tbb::split)
Definition: DenseSparseTools.h:426
Definition: DenseSparseTools.h:150
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT strength, const ValueT beta, const ValueT)
Definition: DenseSparseTools.h:1069
void operator()(const Range3d &range) const
Definition: DenseSparseTools.h:964
Definition: Exceptions.h:13
SparseExtractor(SparseExtractor &other, tbb::split)
Definition: DenseSparseTools.h:221
ResultValueType DenseValueType
Definition: DenseSparseTools.h:410
typename ResultTreeType::LeafNodeType ResultLeafNodeType
Definition: DenseSparseTools.h:181
Definition: DenseSparseTools.h:99
LeafNodeT * getLeaf() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1234
_TreeT TreeT
Definition: DenseSparseTools.h:759
typename DenseType::ValueType DenseValueType
Definition: DenseSparseTools.h:178
Definition: DenseSparseTools.h:1111
openvdb::math::Coord::ValueType Index
Definition: DenseSparseTools.h:176
Definition: DenseSparseTools.h:150
const PointWiseOp mOp
Definition: DenseSparseTools.h:732
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:681
void transformDense(Dense< ValueT, openvdb::tools::LayoutZYX > &dense, const openvdb::CoordBBox &bbox, const PointwiseOpT &functor, bool parallel)
Apply a point-wise functor to the intersection of a dense grid and a given bounding box...
Definition: DenseSparseTools.h:739
void sparseComposite(bool threaded)
Definition: DenseSparseTools.h:778
void operator()(const MaskLeafT &maskLeaf, size_t) const
Definition: DenseSparseTools.h:834
DSConverter< DenseType, MaskTreeType >::Type::Ptr extractSparseTreeWithMask(const DenseType &dense, const MaskTreeType &mask, const typename DenseType::ValueType &background, bool threaded=true)
Copy data from the intersection of a sparse tree and a dense input grid. The resulting tree has the s...
Definition: DenseSparseTools.h:569
static void compositeFromTile(DenseT &dense, openvdb::math::CoordBBox &bbox, const ValueT &sourceValue, const ValueT &alphaValue, const ValueT &beta, const ValueT &strength, bool threaded)
Definition: DenseSparseTools.h:929
a wrapper struct used to avoid unnecessary computation of memory access from Coord when all offsets a...
Definition: DenseSparseTools.h:718
typename MaskTreeT::LeafNodeType MaskLeafT
Definition: DenseSparseTools.h:763
typename RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:185
Index32 Index
Definition: Types.h:31
const ValueT & getValue(size_t offset) const
Return a const reference to the value of the voxel at the given array offset.
Definition: Dense.h:263
Definition: DenseSparseTools.h:150
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT s, const ValueT, const ValueT sbeta)
Definition: DenseSparseTools.h:1124
Functor-based class used to extract data that satisfies some criteria defined by the embedded OpType ...
Definition: DenseSparseTools.h:173
Point wise methods used to apply various compositing operations.
Definition: DenseSparseTools.h:1067
tbb::blocked_range3d< Index, Index, Index > Range3d
Definition: DenseSparseTools.h:184
std::vector< const typename MaskTree::LeafNodeType * > MaskLeafVec
Definition: DenseSparseTools.h:414
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:102
tree::Tree4< ValueMask, 5, 4, 3 >::Type MaskTree
Definition: openvdb.h:27
Definition: Tree.h:176
static void compositeFromLeaf(DenseT &dense, const openvdb::math::CoordBBox &bbox, const LeafT1 &source, const LeafT2 &alpha, const ValueT beta, const ValueT strength)
Definition: DenseSparseTools.h:883
Definition: Dense.h:68
DenseTransformer(DenseT &dense, const openvdb::math::CoordBBox &bbox, const OpType &functor)
Definition: DenseSparseTools.h:658
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
typename ResultTreeType::ValueType ResultValueType
Definition: DenseSparseTools.h:409
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
Definition: DenseSparseTools.h:1122
void join(SparseExtractor &rhs)
Definition: DenseSparseTools.h:377
Definition: DenseSparseTools.h:150
static ValueT apply(const ValueT u, const ValueT alpha, const ValueT v, const ValueT, const ValueT, const ValueT sbeta)
Definition: DenseSparseTools.h:1080
Definition: DenseSparseTools.h:1100
Index32 leafCount() const override
Return the number of leaf nodes.
Definition: Tree.h:339
SparseToDenseCompositor(DenseT &dense, const TreeT &source, const TreeT &alpha, const ValueT beta, const ValueT strength)
Definition: DenseSparseTools.h:768
Definition: DenseSparseTools.h:756
void operator()(const DenseValueType &a, const CoordOrIndex &offset, ResultLeafNodeType *leaf) const
Definition: DenseSparseTools.h:560