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