OpenVDB  4.0.1
MultiResGrid.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2017 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 //
30 
48 
49 #ifndef OPENVDB_TOOLS_MULTIRESGRID_HAS_BEEN_INCLUDED
50 #define OPENVDB_TOOLS_MULTIRESGRID_HAS_BEEN_INCLUDED
51 
52 #include <openvdb/Grid.h>
54 #include <openvdb/math/Math.h>
55 #include <openvdb/math/Operators.h>
56 #include <openvdb/math/Stencils.h>
57 #include <openvdb/Metadata.h>
60 #include "Interpolation.h"
61 #include "Morphology.h"
62 #include "Prune.h"
63 #include "SignedFloodFill.h"
64 #include "ValueTransformer.h"
65 
66 #include <tbb/enumerable_thread_specific.h>
67 #include <tbb/task_scheduler_init.h>
68 #include <tbb/tbb_thread.h>
69 
70 #include <iostream>
71 #include <sstream>
72 #include <string>
73 #include <vector>
74 
75 namespace openvdb {
77 namespace OPENVDB_VERSION_NAME {
78 namespace tools {
79 
80 template<typename TreeType>
81 class MultiResGrid: public MetaMap
82 {
83 public:
84 
85  typedef boost::shared_ptr<MultiResGrid> Ptr;
86  typedef boost::shared_ptr<const MultiResGrid> ConstPtr;
87 
88  typedef typename TreeType::ValueType ValueType;
89  typedef typename TreeType::ValueOnCIter ValueOnCIter;
90  typedef typename TreeType::ValueOnIter ValueOnIter;
91  typedef typename TreeType::Ptr TreePtr;
92  typedef typename TreeType::ConstPtr ConstTreePtr;
93  typedef typename Grid<TreeType>::Ptr GridPtr;
95 
97 
103  MultiResGrid(size_t levels, ValueType background, double voxelSize = 1.0);
104 
113  MultiResGrid(size_t levels, const Grid<TreeType> &grid, bool useInjection = false);
114 
124  MultiResGrid(size_t levels, GridPtr grid, bool useInjection = false);
125 
127 
131  size_t numLevels() const { return mTrees.size(); }
132 
134  static size_t finestLevel() { return 0; }
135 
137  size_t coarsestLevel() const { return mTrees.size()-1; }
138 
140 
144  TreeType& tree(size_t level);
145 
149  const TreeType& constTree(size_t level) const;
150 
154  TreePtr treePtr(size_t level);
155 
159  ConstTreePtr constTreePtr(size_t level) const;
160 
162  TreeType& finestTree() { return *mTrees.front(); }
163 
165  const TreeType& finestConstTree() const { return *mTrees.front(); }
166 
168  TreePtr finestTreePtr() { return mTrees.front(); }
169 
171  ConstTreePtr finestConstTreePtr() const { return mTrees.front(); }
172 
174  TreeType& coarsestTree() { return *mTrees.back(); }
175 
177  const TreeType& coarsestConstTree() const { return *mTrees.back(); }
178 
180  TreePtr coarsestTreePtr() { return mTrees.back(); }
181 
183  ConstTreePtr coarsestConstTreePtr() const { return mTrees.back(); }
184 
186 
190  GridPtr grid(size_t level);
191 
195  ConstGridPtr grid(size_t level) const;
196 
204  template<Index Order>
205  GridPtr createGrid(float level, size_t grainSize = 1) const;
206 
210  GridPtrVecPtr grids();
211 
215  GridCPtrVecPtr grids() const;
216 
218 
220  math::Transform& transform() { return *mTransform; }
226  const math::Transform& transform() const { return *mTransform; }
227  const math::Transform& constTransform() const { return *mTransform; }
229 
231 
233  static Vec3R xyz(const Coord& in_ijk, size_t in_level, size_t out_level);
236  static Vec3R xyz(const Vec3R& in_xyz, size_t in_level, size_t out_level);
237  static Vec3R xyz(const Vec3R& in_xyz, double in_level, double out_level);
239 
241 
242 
243 
245  template<Index Order>
255  ValueType sampleValue(const Coord& in_ijk, size_t in_level, size_t out_level) const;
256  template<Index Order>
257  ValueType sampleValue(const Vec3R& in_ijk, size_t in_level, size_t out_level) const;
259 
266  template<Index Order>
267  ValueType sampleValue(const Coord& ijk, double level) const;
268 
276  template<Index Order>
277  ValueType sampleValue(const Vec3R& xyz, double level) const;
278 
280 
287  ValueType prolongateVoxel(const Coord& coords, const size_t level) const;
288 
289 
293  void prolongateActiveVoxels(size_t destlevel, size_t grainSize = 1);
294 
296 
301  ValueType restrictVoxel(Coord ijk, const size_t level, bool useInjection = false) const;
302 
309  void restrictActiveVoxels(size_t destlevel, size_t grainSize = 1);
310 
312  void print(std::ostream& = std::cout, int verboseLevel = 1) const;
313 
315  std::string getName() const
316  {
317  if (Metadata::ConstPtr meta = (*this)[GridBase::META_GRID_NAME]) return meta->str();
318  return "";
319  }
320 
322  void setName(const std::string& name)
323  {
324  this->removeMeta(GridBase::META_GRID_NAME);
325  this->insertMeta(GridBase::META_GRID_NAME, StringMetadata(name));
326  }
327 
330  {
331  typename StringMetadata::ConstPtr s =
332  this->getMetadata<StringMetadata>(GridBase::META_GRID_CLASS);
333  return s ? GridBase::stringToGridClass(s->value()) : GRID_UNKNOWN;
334  }
335 
338  {
340  }
341 
343  void clearGridClass() { this->removeMeta(GridBase::META_GRID_CLASS); }
344 
345 private:
346 
347  MultiResGrid(const MultiResGrid& other);//disallow copy construction
348  MultiResGrid& operator=(const MultiResGrid& other);//disallow copy assignment
349 
350  // For optimal performance we disable registration of the ValueAccessor
353 
354  void topDownRestrict(bool useInjection);
355 
356  inline void initMeta();
357 
358  // Private struct that concurrently creates a mask of active voxel
359  // in a coarse tree from the active voxels in a fine tree
360  struct MaskOp;
361 
363  struct RestrictOp;
364 
366  struct ProlongateOp;
367 
368  // Private struct that performs multi-threaded computation of grids a fraction levels
369  template<Index Order>
370  struct FractionOp;
371 
373  template<typename OpType> struct CookOp;
374 
375  // Array of shared pointer to trees, level 0 has the highest resolution.
376  std::vector<TreePtr> mTrees;
377  // Shared point to a transform associated with the finest level grid
378  typename math::Transform::Ptr mTransform;
379 };// MultiResGrid
380 
381 template<typename TreeType>
383 MultiResGrid(size_t levels, ValueType background, double voxelSize)
384  : mTrees(levels)
385  , mTransform(math::Transform::createLinearTransform( voxelSize ))
386 {
387  this->initMeta();
388  for (size_t i=0; i<levels; ++i) mTrees[i] = TreePtr(new TreeType(background));
389 }
390 
391 template<typename TreeType>
393 MultiResGrid(size_t levels, const Grid<TreeType> &grid, bool useInjection)
394  : MetaMap(grid)
395  , mTrees(levels)
396  , mTransform( grid.transform().copy() )
397 {
398  this->initMeta();
399  mTrees[0].reset( new TreeType( grid.tree() ) );// deep copy input tree
400  mTrees[0]->voxelizeActiveTiles();
401  this->topDownRestrict(useInjection);
402 }
403 
404 template<typename TreeType>
406 MultiResGrid(size_t levels, GridPtr grid, bool useInjection)
407  : MetaMap(*grid)
408  , mTrees(levels)
409  , mTransform( grid->transform().copy() )
410 {
411  this->initMeta();
412  mTrees[0] = grid->treePtr();// steal tree from input grid
413  mTrees[0]->voxelizeActiveTiles();
414  grid->newTree();
415  this->topDownRestrict(useInjection);
416 }
417 
418 template<typename TreeType>
419 inline TreeType& MultiResGrid<TreeType>::
420 tree(size_t level)
421 {
422  assert( level < mTrees.size() );
423  return *mTrees[level];
424 }
425 
426 template<typename TreeType>
427 inline const TreeType& MultiResGrid<TreeType>::
428 constTree(size_t level) const
429 {
430  assert( level < mTrees.size() );
431  return *mTrees[level];
432 }
433 
434 template<typename TreeType>
435 inline typename TreeType::Ptr MultiResGrid<TreeType>::
436 treePtr(size_t level)
437 {
438  assert( level < mTrees.size() );
439  return mTrees[level];
440 }
441 
442 template<typename TreeType>
443 inline typename TreeType::ConstPtr MultiResGrid<TreeType>::
444 constTreePtr(size_t level) const
445 {
446  assert( level < mTrees.size() );
447  return mTrees[level];
448 }
449 
450 template<typename TreeType>
452 grid(size_t level)
453 {
454  typename Grid<TreeType>::Ptr grid = Grid<TreeType>::create(this->treePtr(level));
455  math::Transform::Ptr xform = mTransform->copy();
456  if (level>0) xform->preScale( Real(1 << level) );
457  grid->setTransform( xform );
458  grid->insertMeta( *this->copyMeta() );
459  grid->insertMeta( "MultiResGrid_Level", Int64Metadata(level));
460  std::stringstream ss;
461  ss << this->getName() << "_level_" << level;
462  grid->setName( ss.str() );
463  return grid;
464 }
465 
466 template<typename TreeType>
468 grid(size_t level) const
469 {
470  return const_cast<MultiResGrid*>(this)->grid(level);
471 }
472 
473 template<typename TreeType>
474 template<Index Order>
476 createGrid(float level, size_t grainSize) const
477 {
478  assert( level >= 0.0f && level <= float(mTrees.size()-1) );
479 
480  typename Grid<TreeType>::Ptr grid(new Grid<TreeType>(this->constTree(0).background()));
481  math::Transform::Ptr xform = mTransform->copy();
482  xform->preScale( math::Pow(2.0f, level) );
483  grid->setTransform( xform );
484  grid->insertMeta( *(this->copyMeta()) );
485  grid->insertMeta( "MultiResGrid_Level", FloatMetadata(level) );
486  std::stringstream ss;
487  ss << this->getName() << "_level_" << level;
488  grid->setName( ss.str() );
489 
490  if ( size_t(floorf(level)) == size_t(ceilf(level)) ) {
491  grid->setTree( this->constTree( size_t(floorf(level))).copy() );
492  } else {
493  FractionOp<Order> tmp(*this, grid->tree(), level, grainSize);
494  if ( grid->getGridClass() == GRID_LEVEL_SET ) {
495  signedFloodFill( grid->tree() );
496  pruneLevelSet( grid->tree() );//only creates inactive tiles
497  }
498  }
499 
500  return grid;
501 }
502 
503 template<typename TreeType>
506 {
508  for (size_t level=0; level<mTrees.size(); ++level) grids->push_back(this->grid(level));
509  return grids;
510 }
511 
512 template<typename TreeType>
514 grids() const
515 {
517  for (size_t level=0; level<mTrees.size(); ++level) grids->push_back(this->grid(level));
518  return grids;
519 }
520 
521 template<typename TreeType>
523 xyz(const Coord& in_ijk, size_t in_level, size_t out_level)
524 {
525  return Vec3R( in_ijk.data() ) * Real(1 << in_level) / Real(1 << out_level);
526 }
527 
528 template<typename TreeType>
530 xyz(const Vec3R& in_xyz, size_t in_level, size_t out_level)
531 {
532  return in_xyz * Real(1 << in_level) / Real(1 << out_level);
533 }
534 
535 template<typename TreeType>
537 xyz(const Vec3R& in_xyz, double in_level, double out_level)
538 {
539  return in_xyz * math::Pow(2.0, in_level - out_level);
540 
541 }
542 
543 template<typename TreeType>
544 template<Index Order>
545 typename TreeType::ValueType MultiResGrid<TreeType>::
546 sampleValue(const Coord& in_ijk, size_t in_level, size_t out_level) const
547 {
548  assert( in_level >= 0 && in_level < mTrees.size() );
549  assert( out_level >= 0 && out_level < mTrees.size() );
550  const ConstAccessor acc(*mTrees[out_level]);// has disabled registration!
551  return tools::Sampler<Order>::sample( acc, this->xyz(in_ijk, in_level, out_level) );
552 }
553 
554 template<typename TreeType>
555 template<Index Order>
556 typename TreeType::ValueType MultiResGrid<TreeType>::
557 sampleValue(const Vec3R& in_xyz, size_t in_level, size_t out_level) const
558 {
559  assert( in_level >= 0 && in_level < mTrees.size() );
560  assert( out_level >= 0 && out_level < mTrees.size() );
561  const ConstAccessor acc(*mTrees[out_level]);// has disabled registration!
562  return tools::Sampler<Order>::sample( acc, this->xyz(in_xyz, in_level, out_level) );
563 }
564 
565 template<typename TreeType>
566 template<Index Order>
567 typename TreeType::ValueType MultiResGrid<TreeType>::
568 sampleValue(const Coord& ijk, double level) const
569 {
570  assert( level >= 0.0 && level <= double(mTrees.size()-1) );
571  const size_t level0 = size_t(floor(level)), level1 = size_t(ceil(level));
572  const ValueType v0 = this->template sampleValue<Order>( ijk, 0, level0 );
573  if ( level0 == level1 ) return v0;
574  assert( level1 - level0 == 1 );
575  const ValueType v1 = this->template sampleValue<Order>( ijk, 0, level1 );
576  const ValueType a = ValueType(level1 - level);
577  return a * v0 + (ValueType(1) - a) * v1;
578 }
579 
580 template<typename TreeType>
581 template<Index Order>
582 typename TreeType::ValueType MultiResGrid<TreeType>::
583 sampleValue(const Vec3R& xyz, double level) const
584 {
585  assert( level >= 0.0 && level <= double(mTrees.size()-1) );
586  const size_t level0 = size_t(floor(level)), level1 = size_t(ceil(level));
587  const ValueType v0 = this->template sampleValue<Order>( xyz, 0, level0 );
588  if ( level0 == level1 ) return v0;
589  assert( level1 - level0 == 1 );
590  const ValueType v1 = this->template sampleValue<Order>( xyz, 0, level1 );
591  const ValueType a = ValueType(level1 - level);
592  return a * v0 + (ValueType(1) - a) * v1;
593 }
594 
595 template<typename TreeType>
596 typename TreeType::ValueType MultiResGrid<TreeType>::
597 prolongateVoxel(const Coord& ijk, const size_t level) const
598 {
599  assert( level+1 < mTrees.size() );
600  const ConstAccessor acc(*mTrees[level + 1]);// has disabled registration!
601  return ProlongateOp::run(ijk, acc);
602 }
603 
604 template<typename TreeType>
606 prolongateActiveVoxels(size_t destlevel, size_t grainSize)
607 {
608  assert( destlevel < mTrees.size()-1 );
609  TreeType &fineTree = *mTrees[ destlevel ];
610  const TreeType &coarseTree = *mTrees[ destlevel+1 ];
611  CookOp<ProlongateOp> tmp( coarseTree, fineTree, grainSize );
612 }
613 
614 template<typename TreeType>
615 typename TreeType::ValueType MultiResGrid<TreeType>::
616 restrictVoxel(Coord ijk, const size_t destlevel, bool useInjection) const
617 {
618  assert( destlevel > 0 && destlevel < mTrees.size() );
619  const TreeType &fineTree = *mTrees[ destlevel-1 ];
620  if ( useInjection ) return fineTree.getValue(ijk<<1);
621  const ConstAccessor acc( fineTree );// has disabled registration!
622  return RestrictOp::run( ijk, acc);
623 }
624 
625 template<typename TreeType>
627 restrictActiveVoxels(size_t destlevel, size_t grainSize)
628 {
629  assert( destlevel > 0 && destlevel < mTrees.size() );
630  const TreeType &fineTree = *mTrees[ destlevel-1 ];
631  TreeType &coarseTree = *mTrees[ destlevel ];
632  CookOp<RestrictOp> tmp( fineTree, coarseTree, grainSize );
633 }
634 
635 template<typename TreeType>
637 print(std::ostream& os, int verboseLevel) const
638 {
639  os << "MultiResGrid with " << mTrees.size() << " levels\n";
640  for (size_t i=0; i<mTrees.size(); ++i) {
641  os << "Level " << i << ": ";
642  mTrees[i]->print(os, verboseLevel);
643  }
644 
645  if ( MetaMap::metaCount() > 0) {
646  os << "Additional metadata:" << std::endl;
647  for (ConstMetaIterator it = beginMeta(), end = endMeta(); it != end; ++it) {
648  os << " " << it->first;
649  if (it->second) {
650  const std::string value = it->second->str();
651  if (!value.empty()) os << ": " << value;
652  }
653  os << "\n";
654  }
655  }
656 
657  os << "Transform:" << std::endl;
658  transform().print(os, /*indent=*/" ");
659  os << std::endl;
660 }
661 
662 template<typename TreeType>
664 initMeta()
665 {
666  const size_t levels = this->numLevels();
667  if (levels < 2) {
668  OPENVDB_THROW(ValueError, "MultiResGrid: at least two levels are required");
669  }
670  this->insertMeta("MultiResGrid_Levels", Int64Metadata( levels ) );
671 }
672 
673 template<typename TreeType>
675 topDownRestrict(bool useInjection)
676 {
677  const bool isLevelSet = this->getGridClass() == GRID_LEVEL_SET;
678  for (size_t n=1; n<mTrees.size(); ++n) {
679  const TreeType &fineTree = *mTrees[n-1];
680  mTrees[n] = TreePtr(new TreeType( fineTree.background() ) );// empty tree
681  TreeType &coarseTree = *mTrees[n];
682  if (useInjection) {// Restriction by injection
683  for (ValueOnCIter it = fineTree.cbeginValueOn(); it; ++it) {
684  const Coord ijk = it.getCoord();
685  if ( (ijk[0] & 1) || (ijk[1] & 1) || (ijk[2] & 1) ) continue;
686  coarseTree.setValue( ijk >> 1, *it );
687  }
688  } else {// Restriction by full-weighting
689  MaskOp tmp(fineTree, coarseTree, 128);
690  this->restrictActiveVoxels(n, 64);
691  }
692  if ( isLevelSet ) {
693  tools::signedFloodFill( coarseTree );
694  tools::pruneLevelSet( coarseTree );//only creates inactive tiles
695  }
696  }// loop over grid levels
697 }
698 
699 template<typename TreeType>
701 {
702  typedef typename TreeType::template ValueConverter<ValueMask>::Type MaskT;
703  typedef tbb::enumerable_thread_specific<TreeType> PoolType;
705  typedef typename ManagerT::LeafRange RangeT;
706  typedef typename ManagerT::LeafNodeType::ValueOnCIter VoxelIterT;
707 
708  MaskOp(const TreeType& fineTree, TreeType& coarseTree, size_t grainSize = 1)
709  : mPool(new PoolType( coarseTree ) )// empty coarse tree acts as examplar
710  {
711  assert( coarseTree.empty() );
712 
713  // Create Mask of restruction performed on fineTree
714  MaskT mask(fineTree, false, true, TopologyCopy() );
715 
716  // Muli-threaded dilation which also linearizes the tree to leaf nodes
718 
719  // Restriction by injection using thread-local storage of coarse tree masks
720  ManagerT leafs( mask );
721  tbb::parallel_for(leafs.leafRange( grainSize ), *this);
722 
723  // multithreaded union of thread-local coarse tree masks with the coarse tree
724  typedef typename PoolType::const_iterator IterT;
725  for (IterT it=mPool->begin(); it!=mPool->end(); ++it) coarseTree.topologyUnion( *it );
726  delete mPool;
727  }
728  void operator()(const RangeT& range) const
729  {
730  Accessor coarseAcc( mPool->local() );// disabled registration
731  for (typename RangeT::Iterator leafIter = range.begin(); leafIter; ++leafIter) {
732  for (VoxelIterT voxelIter = leafIter->cbeginValueOn(); voxelIter; ++voxelIter) {
733  Coord ijk = voxelIter.getCoord();
734  if ( (ijk[2] & 1) || (ijk[1] & 1) || (ijk[0] & 1) ) continue;//no overlap
735  coarseAcc.setValueOn( ijk >> 1 );//injection from fine to coarse level
736  }//loop over active voxels in the fine tree
737  }// loop over leaf nodes in the fine tree
738  }
739  PoolType* mPool;
740 };// MaskOp
741 
742 template<typename TreeType>
743 template<Index Order>
745 {
746  typedef typename TreeType::template ValueConverter<ValueMask>::Type MaskT;
747  typedef tbb::enumerable_thread_specific<MaskT> PoolType;
748  typedef typename PoolType::iterator PoolIterT;
749  typedef tree::LeafManager<const TreeType> Manager1;
750  typedef tree::LeafManager<TreeType> Manager2;
751  typedef typename Manager1::LeafRange Range1;
752  typedef typename Manager2::LeafRange Range2;
753 
754  FractionOp(const MultiResGrid& parent,
755  TreeType& midTree,
756  float level,
757  size_t grainSize = 1)
758  : mLevel( level )
759  , mPool( NULL )
760  , mTree0( &*(parent.mTrees[size_t(floorf(level))]) )//high-resolution
761  , mTree1( &*(parent.mTrees[size_t(ceilf(level))]) ) //low-resolution
762  {
763  assert( midTree.empty() );
764  assert( mTree0 != mTree1 );
765 
766  // Create a pool of thread-local masks
767  MaskT examplar( false );
768  mPool = new PoolType( examplar );
769 
770  {// create mask from re-mapping coarse tree to mid-level tree
771  tree::LeafManager<const TreeType> manager( *mTree1 );
772  tbb::parallel_for( manager.leafRange(grainSize), *this );
773  }
774 
775  // Multi-threaded dilation of mask
776  tbb::parallel_for(tbb::blocked_range<PoolIterT>(mPool->begin(),mPool->end(),1), *this);
777 
778  // Union thread-local coarse tree masks into the coarse tree
779  for (PoolIterT it=mPool->begin(); it!=mPool->end(); ++it) midTree.topologyUnion( *it );
780  delete mPool;
781 
782  {// Interpolate values into the static mid level tree
783  Manager2 manager( midTree );
784  tbb::parallel_for(manager.leafRange(grainSize), *this);
785  }
786  }
787  void operator()(const Range1& range) const
788  {
789  typedef typename Manager1::LeafNodeType::ValueOnCIter VoxelIter;
790  // Let mLevel = level + frac, where
791  // level is integer part of mLevel and frac is the fractional part
792  // low-res voxel size in world units = dx1 = 2^(level + 1)
793  // mid-res voxel size in world units = dx = 2^(mLevel) = 2^(level + frac)
794  // low-res index -> world: ijk * dx1
795  // world -> mid-res index: world / dx
796  // low-res index -> mid-res index: (ijk * dx1) / dx = ijk * scale where
797  // scale = dx1/dx = 2^(level+1)/2^(level+frac) = 2^(1-frac)
798  const float scale = math::Pow(2.0f, 1.0f - math::FractionalPart(mLevel));
799  tree::ValueAccessor<MaskT, false> acc( mPool->local() );// disabled registration
800  for (typename Range1::Iterator leafIter = range.begin(); leafIter; ++leafIter) {
801  for (VoxelIter voxelIter = leafIter->cbeginValueOn(); voxelIter; ++voxelIter) {
802  Coord ijk = voxelIter.getCoord();
803  ijk[0] = int(math::Round(ijk[0] * scale));
804  ijk[1] = int(math::Round(ijk[1] * scale));
805  ijk[2] = int(math::Round(ijk[2] * scale));
806  acc.setValueOn( ijk );
807  }//loop over active voxels in the fine tree
808  }// loop over leaf nodes in the fine tree
809  }
810  void operator()(const tbb::blocked_range<PoolIterT>& range) const
811  {
812  for (PoolIterT it=range.begin(); it!=range.end(); ++it) {
814  }
815  }
816  void operator()(const Range2 &r) const
817  {
818  typedef typename TreeType::LeafNodeType::ValueOnIter VoxelIter;
819  // Let mLevel = level + frac, where
820  // level is integer part of mLevel and frac is the fractional part
821  // high-res voxel size in world units = dx0 = 2^(level)
822  // low-res voxel size in world units = dx1 = 2^(level+1)
823  // mid-res voxel size in world units = dx = 2^(mLevel) = 2^(level + frac)
824  // mid-res index -> world: ijk * dx
825  // world -> high-res index: world / dx0
826  // world -> low-res index: world / dx1
827  // mid-res index -> high-res index: (ijk * dx) / dx0 = ijk * scale0 where
828  // scale0 = dx/dx0 = 2^(level+frac)/2^(level) = 2^(frac)
829  // mid-res index -> low-res index: (ijk * dx) / dx1 = ijk * scale1 where
830  // scale1 = dx/dx1 = 2^(level+frac)/2^(level+1) = 2^(frac-1)
831  const float b = math::FractionalPart(mLevel), a = 1.0f - b;
832  const float scale0 = math::Pow( 2.0f, b );
833  const float scale1 = math::Pow( 2.0f,-a );
834  ConstAccessor acc0( *mTree0 ), acc1( *mTree1 );
835  for (typename Range2::Iterator leafIter = r.begin(); leafIter; ++leafIter) {
836  for (VoxelIter voxelIter = leafIter->beginValueOn(); voxelIter; ++voxelIter) {
837  const Vec3R xyz = Vec3R( voxelIter.getCoord().data() );// mid level coord
838  const ValueType v0 = tools::Sampler<Order>::sample( acc0, xyz * scale0 );
839  const ValueType v1 = tools::Sampler<Order>::sample( acc1, xyz * scale1 );
840  voxelIter.setValue( ValueType(a*v0 + b*v1) );
841  }
842  }
843  }
844  const float mLevel;
845  PoolType* mPool;
846  const TreeType *mTree0, *mTree1;
847 };// FractionOp
848 
849 
850 template<typename TreeType>
851 template<typename OperatorType>
853 {
855  typedef typename ManagerT::LeafRange RangeT;
856 
857  CookOp(const TreeType& srcTree, TreeType& dstTree, size_t grainSize): acc(srcTree)
858  {
859  ManagerT leafs(dstTree);
860  tbb::parallel_for(leafs.leafRange(grainSize), *this);
861  }
862  CookOp(const CookOp &other): acc(other.acc.tree()) {}
863 
864  void operator()(const RangeT& range) const
865  {
866  for (auto leafIt = range.begin(); leafIt; ++leafIt) {
867  auto& phi = leafIt.buffer(0);
868  for (auto voxelIt = leafIt->beginValueOn(); voxelIt; ++voxelIt) {
869  phi.setValue(voxelIt.pos(), OperatorType::run(voxelIt.getCoord(), acc));
870  }
871  }
872  }
873 
874  const ConstAccessor acc;
875 };// CookOp
876 
877 
878 template<typename TreeType>
880 {
884  static ValueType run(Coord ijk, const ConstAccessor &acc)
885  {
886  ijk <<= 1;
887  // Overlapping grid point
888  ValueType v = 8*acc.getValue(ijk);
889  // neighbors in one axial direction
890  v += 4*(acc.getValue(ijk.offsetBy(-1, 0, 0)) + acc.getValue(ijk.offsetBy( 1, 0, 0)) +// x
891  acc.getValue(ijk.offsetBy( 0,-1, 0)) + acc.getValue(ijk.offsetBy( 0, 1, 0)) +// y
892  acc.getValue(ijk.offsetBy( 0, 0,-1)) + acc.getValue(ijk.offsetBy( 0, 0, 1)));// z
893  // neighbors in two axial directions
894  v += 2*(acc.getValue(ijk.offsetBy(-1,-1, 0)) + acc.getValue(ijk.offsetBy(-1, 1, 0)) +// xy
895  acc.getValue(ijk.offsetBy( 1,-1, 0)) + acc.getValue(ijk.offsetBy( 1, 1, 0)) +// xy
896  acc.getValue(ijk.offsetBy(-1, 0,-1)) + acc.getValue(ijk.offsetBy(-1, 0, 1)) +// xz
897  acc.getValue(ijk.offsetBy( 1, 0,-1)) + acc.getValue(ijk.offsetBy( 1, 0, 1)) +// xz
898  acc.getValue(ijk.offsetBy( 0,-1,-1)) + acc.getValue(ijk.offsetBy( 0,-1, 1)) +// yz
899  acc.getValue(ijk.offsetBy( 0, 1,-1)) + acc.getValue(ijk.offsetBy( 0, 1, 1)));// yz
900  // neighbors in three axial directions
901  for (int i=-1; i<=1; i+=2) {
902  for (int j=-1; j<=1; j+=2) {
903  for (int k=-1; k<=1; k+=2) v += acc.getValue(ijk.offsetBy(i,j,k));// xyz
904  }
905  }
906  v *= ValueType(1.0f/64.0f);
907  return v;
908  }
909 };// RestrictOp
910 
911 template<typename TreeType>
913 {
917  static ValueType run(const Coord& ijk, const ConstAccessor &acc)
918  {
919  switch ( (ijk[0] & 1) | ((ijk[1] & 1) << 1) | ((ijk[2] & 1) << 2) ) {
920  case 0:// all even
921  return acc.getValue(ijk>>1);
922  case 1:// x is odd
923  return ValueType(0.5)*(acc.getValue(ijk.offsetBy(-1,0,0)>>1) +
924  acc.getValue(ijk.offsetBy( 1,0,0)>>1));
925  case 2:// y is odd
926  return ValueType(0.5)*(acc.getValue(ijk.offsetBy(0,-1,0)>>1) +
927  acc.getValue(ijk.offsetBy(0, 1,0)>>1));
928  case 3:// x&y are odd
929  return ValueType(0.25)*(acc.getValue(ijk.offsetBy(-1,-1,0)>>1) +
930  acc.getValue(ijk.offsetBy(-1, 1,0)>>1) +
931  acc.getValue(ijk.offsetBy( 1,-1,0)>>1) +
932  acc.getValue(ijk.offsetBy( 1, 1,0)>>1));
933  case 4:// z is odd
934  return ValueType(0.5)*(acc.getValue(ijk.offsetBy(0,0,-1)>>1) +
935  acc.getValue(ijk.offsetBy(0,0, 1)>>1));
936  case 5:// x&z are odd
937  return ValueType(0.25)*(acc.getValue(ijk.offsetBy(-1,0,-1)>>1) +
938  acc.getValue(ijk.offsetBy(-1,0, 1)>>1) +
939  acc.getValue(ijk.offsetBy( 1,0,-1)>>1) +
940  acc.getValue(ijk.offsetBy( 1,0, 1)>>1));
941  case 6:// y&z are odd
942  return ValueType(0.25)*(acc.getValue(ijk.offsetBy(0,-1,-1)>>1) +
943  acc.getValue(ijk.offsetBy(0,-1, 1)>>1) +
944  acc.getValue(ijk.offsetBy(0, 1,-1)>>1) +
945  acc.getValue(ijk.offsetBy(0, 1, 1)>>1));
946  }
947  // all are odd
948  ValueType v = zeroVal<ValueType>();
949  for (int i=-1; i<=1; i+=2) {
950  for (int j=-1; j<=1; j+=2) {
951  for (int k=-1; k<=1; k+=2) v += acc.getValue(ijk.offsetBy(i,j,k)>>1);// xyz
952  }
953  }
954  return ValueType(0.125) * v;
955  }
956 };// ProlongateOp
957 
958 } // namespace tools
959 } // namespace OPENVDB_VERSION_NAME
960 } // namespace openvdb
961 
962 #endif // OPENVDB_TOOLS_MULTIRESGRID_HAS_BEEN_INCLUDED
963 
964 // Copyright (c) 2012-2017 DreamWorks Animation LLC
965 // All rights reserved. This software is distributed under the
966 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
static size_t finestLevel()
Return the level of the finest grid (always 0)
Definition: MultiResGrid.h:134
SharedPtr< Transform > Ptr
Definition: Transform.h:69
void print(std::ostream &os=std::cout, const std::string &indent="") const
Print a description of this transform.
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:503
static GridClass stringToGridClass(const std::string &)
Return the class of volumetric data specified by the given string.
size_t coarsestLevel() const
Return the level of the coarsest grid, i.e. numLevels()-1.
Definition: MultiResGrid.h:137
SharedPtr< GridCPtrVec > GridCPtrVecPtr
Definition: Grid.h:444
MetadataMap::const_iterator ConstMetaIterator
Definition: MetaMap.h:55
tbb::enumerable_thread_specific< TreeType > PoolType
Definition: MultiResGrid.h:703
TreeType::ValueOnIter ValueOnIter
Definition: MultiResGrid.h:90
Calculate an axis-aligned bounding box in index space from a bounding sphere in world space...
Definition: Transform.h:66
TreeType::template ValueConverter< ValueMask >::Type MaskT
Definition: MultiResGrid.h:702
GridClass getGridClass() const
Return the class of volumetric data (level set, fog volume, etc.) stored in this grid.
Definition: MultiResGrid.h:329
const TreeType & finestConstTree() const
Return a const reference to the tree at the finest level.
Definition: MultiResGrid.h:165
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
ConstTreePtr constTreePtr(size_t level) const
Return a const shared pointer to the tree at the specified level.
Definition: MultiResGrid.h:444
double Real
Definition: Types.h:63
ManagerT::LeafNodeType::ValueOnCIter VoxelIterT
Definition: MultiResGrid.h:706
GridPtr grid(size_t level)
Return a shared pointer to the grid at the specified integer level.
Definition: MultiResGrid.h:452
TreeType::ValueOnCIter ValueOnCIter
Definition: MultiResGrid.h:89
const Int32 * data() const
Definition: Coord.h:163
ValueType sampleValue(const Coord &in_ijk, size_t in_level, size_t out_level) const
Return the value at the specified coordinate position using interpolation of the specified order into...
Definition: ValueAccessor.h:219
TreeType::ConstPtr ConstTreePtr
Definition: MultiResGrid.h:92
const math::Transform & constTransform() const
Return a reference to the finest grid&#39;s transform, which might be shared with other grids...
Definition: MultiResGrid.h:227
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101
tree::LeafManager< const MaskT > ManagerT
Definition: MultiResGrid.h:704
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
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
Container that maps names (strings) to values of arbitrary types.
Definition: MetaMap.h:46
TreePtr finestTreePtr()
Return a shared pointer to the tree at the finest level.
Definition: MultiResGrid.h:168
void setTree(TreeBase::Ptr) override
Associate the given tree with this grid, in place of its existing tree.
Definition: Grid.h:1301
const TreeType & constTree(size_t level) const
Return a const reference to the tree at the specified level.
Definition: MultiResGrid.h:428
void prolongateActiveVoxels(size_t destlevel, size_t grainSize=1)
Definition: MultiResGrid.h:606
ValueType prolongateVoxel(const Coord &coords, const size_t level) const
Return the value at coordinate location in level tree from the coarser tree at level+1 using trilinea...
Definition: MultiResGrid.h:597
Definition: Types.h:263
Definition: Morphology.h:102
static ValueType run(const Coord &ijk, const ConstAccessor &acc)
Interpolate values from a coarse grid (acc) into the index space (ijk) of a fine grid.
Definition: MultiResGrid.h:917
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:115
const TreeType & coarsestConstTree() const
Return a const reference to the tree at the coarsest level.
Definition: MultiResGrid.h:177
TypedMetadata< int64_t > Int64Metadata
Definition: Metadata.h:379
TreeType::ValueType ValueType
Definition: MultiResGrid.h:88
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:48
void setName(const std::string &name)
Set the name of this MultiResGrid.
Definition: MultiResGrid.h:322
MetaIterator endMeta()
Definition: MetaMap.h:112
GridType::Ptr createGrid(const typename GridType::ValueType &background)
Create a new grid of type GridType with a given background value.
Definition: Grid.h:1573
std::vector< GridBase::ConstPtr > GridCPtrVec
Definition: Grid.h:441
void print(std::ostream &=std::cout, int verboseLevel=1) const
Output a human-readable description of this MultiResGrid.
Definition: MultiResGrid.h:637
void setGridClass(GridClass cls)
Specify the class of volumetric data (level set, fog volume, etc.) stored in this grid...
Definition: MultiResGrid.h:337
ConstTreePtr coarsestConstTreePtr() const
Return a const shared pointer to the tree at the coarsest level.
Definition: MultiResGrid.h:183
TreeType & coarsestTree()
Return a reference to the tree at the coarsest level.
Definition: MultiResGrid.h:174
MatType scale(const Vec3< typename MatType::value_type > &s)
Return a matrix that scales by s.
Definition: Mat.h:610
TreeType & tree()
Return a reference to this grid&#39;s tree, which might be shared with other grids.
Definition: Grid.h:796
TypedMetadata< float > FloatMetadata
Definition: Metadata.h:377
ValueType restrictVoxel(Coord ijk, const size_t level, bool useInjection=false) const
Definition: MultiResGrid.h:616
const math::Transform & transform() const
Return a reference to the finest grid&#39;s transform, which might be shared with other grids...
Definition: MultiResGrid.h:226
Definition: MultiResGrid.h:81
Defined various multi-threaded utility functions for trees.
math::Transform & transform()
Return a reference to the finest grid&#39;s transform, which might be shared with other grids...
Definition: MultiResGrid.h:225
MetaMap::Ptr copyMeta() const
Return a copy of this map whose fields are shared with this map.
GridClass getGridClass() const
Return the class of volumetric data (level set, fog volume, etc.) stored in this grid.
TreeType & tree(size_t level)
Return a reference to the tree at the specified level.
Definition: MultiResGrid.h:420
GridClass
Definition: Types.h:262
static Ptr create()
Return a new grid with background value zero.
Definition: Grid.h:1178
#define OPENVDB_VERSION_NAME
Definition: version.h:43
size_t numLevels() const
Return the number of levels, i.e. trees, in this MultiResGrid.
Definition: MultiResGrid.h:131
TreeType & finestTree()
Return a reference to the tree at the finest level.
Definition: MultiResGrid.h:162
boost::shared_ptr< MultiResGrid > Ptr
Definition: MultiResGrid.h:85
TreePtr coarsestTreePtr()
Return a shared pointer to the tree at the coarsest level.
Definition: MultiResGrid.h:180
Type Pow(Type x, int n)
Return .
Definition: Math.h:527
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: ValueAccessor.h:256
ConstTreePtr finestConstTreePtr() const
Return a const shared pointer to the tree at the finest level.
Definition: MultiResGrid.h:171
Propagates the sign of distance values from the active voxels in the narrow band to the inactive valu...
Definition: MultiResGrid.h:700
size_t metaCount() const
Definition: MetaMap.h:118
Implementation of morphological dilation and erosion.
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:391
Definition: Exceptions.h:39
boost::shared_ptr< const MultiResGrid > ConstPtr
Definition: MultiResGrid.h:86
void clearGridClass()
Remove the setting specifying the class of this grid&#39;s volumetric data.
Definition: MultiResGrid.h:343
void insertMeta(const Name &, const Metadata &value)
Insert a new metadata field or overwrite the value of an existing field.
static ValueType run(Coord ijk, const ConstAccessor &acc)
Static method that performs restriction by full weighting.
Definition: MultiResGrid.h:884
std::string getName() const
Return a string with the name of this MultiResGrid.
Definition: MultiResGrid.h:315
void dilateVoxels(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE)
Topologically dilate all leaf-level active voxels in a tree using one of three nearest neighbor conne...
Definition: Morphology.h:854
Definition: Exceptions.h:92
math::Vec3< Real > Vec3R
Definition: Types.h:75
GridPtrVecPtr grids()
Return a shared pointer to a vector of all the base grids in this instance of the MultiResGrid...
Definition: MultiResGrid.h:505
Iterator begin() const
Definition: LeafManager.h:186
SharedPtr< const TypedMetadata< T > > ConstPtr
Definition: Metadata.h:142
void operator()(const RangeT &range) const
Definition: MultiResGrid.h:728
Grid< TreeType >::ConstPtr ConstGridPtr
Definition: MultiResGrid.h:94
float Round(float x)
Return x rounded to the nearest integer.
Definition: Math.h:785
void setTransform(math::Transform::Ptr)
Associate the given transform with this grid, in place of its existing transform. ...
Definition: Grid.h:1104
void setName(const std::string &)
Specify a name for this grid.
void dilateActiveValues(TreeType &tree, int iterations=1, NearestNeighbors nn=NN_FACE, TilePolicy mode=PRESERVE_TILES)
Topologically dilate all active values (i.e. both voxels and tiles) in a tree using one of three near...
Definition: Morphology.h:1073
Defines various finite difference stencils by means of the "curiously recurring template pattern" on ...
std::vector< GridBase::Ptr > GridPtrVec
Definition: Grid.h:436
SharedPtr< const Grid > ConstPtr
Definition: Grid.h:502
GridPtr createGrid(float level, size_t grainSize=1) const
Return a shared pointer to a new grid at the specified floating-point level.
MaskOp(const TreeType &fineTree, TreeType &coarseTree, size_t grainSize=1)
Definition: MultiResGrid.h:708
ManagerT::LeafRange RangeT
Definition: MultiResGrid.h:705
Container class that associates a tree with a transform and metadata.
Definition: Grid.h:54
SharedPtr< const Metadata > ConstPtr
Definition: Metadata.h:52
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
static bool sample(const TreeT &inTree, const Vec3R &inCoord, typename TreeT::ValueType &result)
Sample inTree at the floating-point index coordinate inCoord and store the result in result...
static const char *const META_GRID_CLASS
Definition: Grid.h:290
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
TypedMetadata< std::string > StringMetadata
Definition: Metadata.h:380
static std::string gridClassToString(GridClass)
Return the metadata string value for the given class of volumetric data.
void restrictActiveVoxels(size_t destlevel, size_t grainSize=1)
Definition: MultiResGrid.h:627
MultiResGrid(size_t levels, ValueType background, double voxelSize=1.0)
Constructor of empty grids.
Definition: MultiResGrid.h:383
static const char *const META_GRID_NAME
Definition: Grid.h:292
PoolType * mPool
Definition: MultiResGrid.h:739
MetaIterator beginMeta()
Definition: MetaMap.h:111
static Vec3R xyz(const Coord &in_ijk, size_t in_level, size_t out_level)
Return the floating-point index coordinate at out_level given the index coordinate in_xyz at in_level...
Definition: MultiResGrid.h:523
SharedPtr< Grid > Ptr
Definition: Grid.h:501
Grid< TreeType >::Ptr GridPtr
Definition: MultiResGrid.h:93
TreePtr treePtr(size_t level)
Return a shared pointer to the tree at the specified level.
Definition: MultiResGrid.h:436
SharedPtr< GridPtrVec > GridPtrVecPtr
Definition: Grid.h:439
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition: Coord.h:115
Definition: Types.h:264
TreeType::Ptr TreePtr
Definition: MultiResGrid.h:91
void signedFloodFill(TreeOrLeafManagerT &tree, bool threaded=true, size_t grainSize=1, Index minLevel=0)
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: SignedFloodFill.h:294
Type FractionalPart(Type x)
Return the fractional part of x.
Definition: Math.h:809