OpenVDB  8.1.1
LevelSetMeasure.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
7 
8 #ifndef OPENVDB_TOOLS_LEVELSETMEASURE_HAS_BEEN_INCLUDED
9 #define OPENVDB_TOOLS_LEVELSETMEASURE_HAS_BEEN_INCLUDED
10 
11 #include <openvdb/math/Math.h>
12 #include <openvdb/Types.h>
13 #include <openvdb/Grid.h>
17 #include <openvdb/math/Operators.h>
18 #include <openvdb/math/Stencils.h>
20 #include <tbb/parallel_for.h>
21 #include <tbb/parallel_sort.h>
22 #include <tbb/parallel_invoke.h>
23 #include <type_traits>
24 
25 namespace openvdb {
27 namespace OPENVDB_VERSION_NAME {
28 namespace tools {
29 
38 template<class GridType>
39 inline Real
40 levelSetArea(const GridType& grid, bool useWorldSpace = true);
41 
50 template<class GridType>
51 inline Real
52 levelSetVolume(const GridType& grid, bool useWorldSpace = true);
53 
60 template<class GridType>
61 inline int
62 levelSetEulerCharacteristic(const GridType& grid);
63 
71 template<class GridType>
72 inline int
73 levelSetGenus(const GridType& grid);
74 
76 
78 template<typename RealT>
80 {
81 public:
82  // eps is the half-width of the dirac delta function in units of phi
83  DiracDelta(RealT eps) : mC(0.5/eps), mD(2*math::pi<RealT>()*mC), mE(eps) {}
84  // values of the dirac delta function are in units of one over the units of phi
85  inline RealT operator()(RealT phi) const { return math::Abs(phi) > mE ? 0 : mC*(1+cos(mD*phi)); }
86 private:
87  const RealT mC, mD, mE;
88 };// DiracDelta functor
89 
90 
98 template<typename GridT, typename InterruptT = util::NullInterrupter>
100 {
101 public:
102  using GridType = GridT;
103  using TreeType = typename GridType::TreeType;
104  using ValueType = typename TreeType::ValueType;
106 
107  static_assert(std::is_floating_point<ValueType>::value,
108  "level set measure is supported only for scalar, floating-point grids");
109 
114  LevelSetMeasure(const GridType& grid, InterruptT* interrupt = nullptr);
115 
119  void init(const GridType& grid);
120 
122  virtual ~LevelSetMeasure() {}
123 
125  int getGrainSize() const { return mGrainSize; }
126 
129  void setGrainSize(int grainsize) { mGrainSize = grainsize; }
130 
134  Real area(bool useWorldUnits = true);
135 
139  Real volume(bool useWorldUnits = true);
140 
144  Real totMeanCurvature(bool useWorldUnits = true);
145 
149  Real totGaussianCurvature(bool useWorldUnits = true);
150 
154  Real avgMeanCurvature(bool useWorldUnits = true) {return this->totMeanCurvature(useWorldUnits) / this->area(useWorldUnits);}
155 
159  Real avgGaussianCurvature(bool useWorldUnits = true) {return this->totGaussianCurvature(useWorldUnits) / this->area(useWorldUnits); }
160 
163  int eulerCharacteristic();
164 
168  int genus() { return 1 - this->eulerCharacteristic()/2;}
169 
170 private:
171 
172  using LeafT = typename TreeType::LeafNodeType;
173  using VoxelCIterT = typename LeafT::ValueOnCIter;
174  using LeafRange = typename ManagerType::LeafRange;
175  using LeafIterT = typename LeafRange::Iterator;
176  using ManagerPtr = std::unique_ptr<ManagerType>;
177  using BufferPtr = std::unique_ptr<double[]>;
178 
179  // disallow copy construction and copy by assignment!
180  LevelSetMeasure(const LevelSetMeasure&);// not implemented
181  LevelSetMeasure& operator=(const LevelSetMeasure&);// not implemented
182 
183  const GridType *mGrid;
184  ManagerPtr mLeafs;
185  BufferPtr mBuffer;
186  InterruptT *mInterrupter;
187  double mDx, mArea, mVolume, mTotMeanCurvature, mTotGausCurvature;
188  int mGrainSize;
189  bool mUpdateArea, mUpdateCurvature;
190 
191  // @brief Return false if the process was interrupted
192  bool checkInterrupter();
193 
194  struct MeasureArea
195  {
196  MeasureArea(LevelSetMeasure* parent) : mParent(parent), mStencil(*mParent->mGrid)
197  {
198  if (parent->mInterrupter) parent->mInterrupter->start("Measuring area and volume of level set");
199  if (parent->mGrainSize>0) {
200  tbb::parallel_for(parent->mLeafs->leafRange(parent->mGrainSize), *this);
201  } else {
202  (*this)(parent->mLeafs->leafRange());
203  }
204  tbb::parallel_invoke([&](){parent->mArea = parent->reduce(0);},
205  [&](){parent->mVolume = parent->reduce(1)/3.0;});
206  parent->mUpdateArea = false;
207  if (parent->mInterrupter) parent->mInterrupter->end();
208  }
209  MeasureArea(const MeasureArea& other) : mParent(other.mParent), mStencil(*mParent->mGrid) {}
210  void operator()(const LeafRange& range) const;
211  LevelSetMeasure* mParent;
212  mutable math::GradStencil<GridT, false> mStencil;
213  };// MeasureArea
214 
215  struct MeasureCurvatures
216  {
217  MeasureCurvatures(LevelSetMeasure* parent) : mParent(parent), mStencil(*mParent->mGrid)
218  {
219  if (parent->mInterrupter) parent->mInterrupter->start("Measuring curvatures of level set");
220  if (parent->mGrainSize>0) {
221  tbb::parallel_for(parent->mLeafs->leafRange(parent->mGrainSize), *this);
222  } else {
223  (*this)(parent->mLeafs->leafRange());
224  }
225  tbb::parallel_invoke([&](){parent->mTotMeanCurvature = parent->reduce(0);},
226  [&](){parent->mTotGausCurvature = parent->reduce(1);});
227  parent->mUpdateCurvature = false;
228  if (parent->mInterrupter) parent->mInterrupter->end();
229  }
230  MeasureCurvatures(const MeasureCurvatures& other) : mParent(other.mParent), mStencil(*mParent->mGrid) {}
231  void operator()(const LeafRange& range) const;
232  LevelSetMeasure* mParent;
233  mutable math::CurvatureStencil<GridT, false> mStencil;
234  };// MeasureCurvatures
235 
236  double reduce(int offset)
237  {
238  double *first = mBuffer.get() + offset*mLeafs->leafCount(), *last = first + mLeafs->leafCount();
239  tbb::parallel_sort(first, last);// mitigates catastrophic cancellation
240  Real sum = 0.0;
241  while(first != last) sum += *first++;
242  return sum;
243  }
244 
245 }; // end of LevelSetMeasure class
246 
247 
248 template<typename GridT, typename InterruptT>
249 inline
251  : mInterrupter(interrupt)
252  , mGrainSize(1)
253 {
254  this->init(grid);
255 }
256 
257 template<typename GridT, typename InterruptT>
258 inline void
260 {
261  if (!grid.hasUniformVoxels()) {
263  "The transform must have uniform scale for the LevelSetMeasure to function");
264  }
265  if (grid.getGridClass() != GRID_LEVEL_SET) {
267  "LevelSetMeasure only supports level sets;"
268  " try setting the grid class to \"level set\"");
269  }
270  if (grid.empty()) {
272  "LevelSetMeasure does not support empty grids;");
273  }
274  mGrid = &grid;
275  mDx = grid.voxelSize()[0];
276  mLeafs = std::make_unique<ManagerType>(mGrid->tree());
277  mBuffer = std::make_unique<double[]>(2*mLeafs->leafCount());
278  mUpdateArea = mUpdateCurvature = true;
279 }
280 
281 template<typename GridT, typename InterruptT>
282 inline Real
284 {
285  if (mUpdateArea) {MeasureArea m(this);};
286  double area = mArea;
287  if (useWorldUnits) area *= math::Pow2(mDx);
288  return area;
289 }
290 
291 template<typename GridT, typename InterruptT>
292 inline Real
294 {
295  if (mUpdateArea) {MeasureArea m(this);};
296  double volume = mVolume;
297  if (useWorldUnits) volume *= math::Pow3(mDx) ;
298  return volume;
299 }
300 
301 template<typename GridT, typename InterruptT>
302 inline Real
304 {
305  if (mUpdateCurvature) {MeasureCurvatures m(this);};
306  return mTotMeanCurvature * (useWorldUnits ? mDx : 1);
307 }
308 
309 template<typename GridT, typename InterruptT>
310 inline Real
312 {
313  if (mUpdateCurvature) {MeasureCurvatures m(this);};
314  return mTotGausCurvature;
315 }
316 
317 template<typename GridT, typename InterruptT>
318 inline int
320 {
321  const Real x = this->totGaussianCurvature(true) / (2.0*math::pi<Real>());
322  return int(math::Round( x ));
323 }
324 
326 
327 template<typename GridT, typename InterruptT>
328 inline bool
330 {
331  if (util::wasInterrupted(mInterrupter)) {
332  tbb::task::self().cancel_group_execution();
333  return false;
334  }
335  return true;
336 }
337 
338 template<typename GridT, typename InterruptT>
339 inline void
341 MeasureArea::operator()(const LeafRange& range) const
342 {
343  using Vec3T = math::Vec3<ValueType>;
344  // computations are performed in index space where dV = 1
345  mParent->checkInterrupter();
346  const Real invDx = 1.0/mParent->mDx;
347  const DiracDelta<Real> DD(1.5);// dirac delta function is 3 voxel units wide
348  const size_t leafCount = mParent->mLeafs->leafCount();
349  for (LeafIterT leafIter=range.begin(); leafIter; ++leafIter) {
350  Real sumA = 0, sumV = 0;//reduce risk of catastrophic cancellation
351  for (VoxelCIterT voxelIter = leafIter->cbeginValueOn(); voxelIter; ++voxelIter) {
352  const Real dd = DD(invDx * (*voxelIter));
353  if (dd > 0.0) {
354  mStencil.moveTo(voxelIter);
355  const Coord& p = mStencil.getCenterCoord();// in voxel units
356  const Vec3T g = mStencil.gradient();// in world units
357  sumA += dd*g.length();// \delta(\phi)*|\nabla\phi|
358  sumV += dd*(g[0]*Real(p[0]) + g[1]*Real(p[1]) + g[2]*Real(p[2]));// \delta(\phi)\vec{x}\cdot\nabla\phi
359  }
360  }
361  double* ptr = mParent->mBuffer.get() + leafIter.pos();
362  *ptr = sumA;
363  ptr += leafCount;
364  *ptr = sumV;
365  }
366 }
367 
368 template<typename GridT, typename InterruptT>
369 inline void
371 MeasureCurvatures::operator()(const LeafRange& range) const
372 {
373  using Vec3T = math::Vec3<ValueType>;
374  // computations are performed in index space where dV = 1
375  mParent->checkInterrupter();
376  const Real dx = mParent->mDx, dx2=dx*dx, invDx = 1.0/dx;
377  const DiracDelta<Real> DD(1.5);// dirac delta function is 3 voxel units wide
378  ValueType mean, gauss;
379  const size_t leafCount = mParent->mLeafs->leafCount();
380  for (LeafIterT leafIter=range.begin(); leafIter; ++leafIter) {
381  Real sumM = 0, sumG = 0;//reduce risk of catastrophic cancellation
382  for (VoxelCIterT voxelIter = leafIter->cbeginValueOn(); voxelIter; ++voxelIter) {
383  const Real dd = DD(invDx * (*voxelIter));
384  if (dd > 0.0) {
385  mStencil.moveTo(voxelIter);
386  const Vec3T g = mStencil.gradient();
387  const Real dA = dd*g.length();// \delta(\phi)*\delta(\phi)
388  mStencil.curvatures(mean, gauss);
389  sumM += dA*mean*dx;// \delta(\phi)*\delta(\phi)*MeanCurvature
390  sumG += dA*gauss*dx2;// \delta(\phi)*\delta(\phi)*GaussCurvature
391  }
392  }
393  double* ptr = mParent->mBuffer.get() + leafIter.pos();
394  *ptr = sumM;
395  ptr += leafCount;
396  *ptr = sumG;
397  }
398 }
399 
401 
402 //{
404 
405 template<class GridT>
406 inline
407 typename std::enable_if<std::is_floating_point<typename GridT::ValueType>::value, Real>::type
408 doLevelSetArea(const GridT& grid, bool useWorldUnits)
409 {
410  LevelSetMeasure<GridT> m(grid);
411  return m.area(useWorldUnits);
412 }
413 
414 template<class GridT>
415 inline
416 typename std::enable_if<!std::is_floating_point<typename GridT::ValueType>::value, Real>::type
417 doLevelSetArea(const GridT&, bool)
418 {
420  "level set area is supported only for scalar, floating-point grids");
421 }
422 
424 //}
425 
426 template<class GridT>
427 inline Real
428 levelSetArea(const GridT& grid, bool useWorldUnits)
429 {
430  return doLevelSetArea<GridT>(grid, useWorldUnits);
431 }
432 
434 
435 //{
437 
438 template<class GridT>
439 inline
440 typename std::enable_if<std::is_floating_point<typename GridT::ValueType>::value, Real>::type
441 doLevelSetVolume(const GridT& grid, bool useWorldUnits)
442 {
443  LevelSetMeasure<GridT> m(grid);
444  return m.volume(useWorldUnits);
445 }
446 
447 template<class GridT>
448 inline
449 typename std::enable_if<!std::is_floating_point<typename GridT::ValueType>::value, Real>::type
450 doLevelSetVolume(const GridT&, bool)
451 {
453  "level set volume is supported only for scalar, floating-point grids");
454 }
455 
457 //}
458 
459 template<class GridT>
460 inline Real
461 levelSetVolume(const GridT& grid, bool useWorldUnits)
462 {
463  return doLevelSetVolume<GridT>(grid, useWorldUnits);
464 }
465 
467 
468 //{
470 
471 template<class GridT>
472 inline
473 typename std::enable_if<std::is_floating_point<typename GridT::ValueType>::value, int>::type
474 doLevelSetEulerCharacteristic(const GridT& grid)
475 {
476  LevelSetMeasure<GridT> m(grid);
477  return m.eulerCharacteristic();
478 }
479 
480 template<class GridT>
481 inline
482 typename std::enable_if<!std::is_floating_point<typename GridT::ValueType>::value, int>::type
483 doLevelSetEulerCharacteristic(const GridT&)
484 {
486  "level set euler characteristic is supported only for scalar, floating-point grids");
487 }
488 
490 //}
491 
492 
493 template<class GridT>
494 inline int
495 levelSetEulerCharacteristic(const GridT& grid)
496 {
497  return doLevelSetEulerCharacteristic(grid);
498 }
499 
501 
502 //{
504 
505 template<class GridT>
506 inline
507 typename std::enable_if<std::is_floating_point<typename GridT::ValueType>::value, int>::type
508 doLevelSetEuler(const GridT& grid)
509 {
510  LevelSetMeasure<GridT> m(grid);
511  return m.eulerCharacteristics();
512 
513 }
514 
515 template<class GridT>
516 inline
517 typename std::enable_if<std::is_floating_point<typename GridT::ValueType>::value, int>::type
518 doLevelSetGenus(const GridT& grid)
519 {
520  LevelSetMeasure<GridT> m(grid);
521  return m.genus();
522 }
523 
524 template<class GridT>
525 inline
526 typename std::enable_if<!std::is_floating_point<typename GridT::ValueType>::value, int>::type
527 doLevelSetGenus(const GridT&)
528 {
530  "level set genus is supported only for scalar, floating-point grids");
531 }
532 
534 //}
535 
536 template<class GridT>
537 inline int
538 levelSetGenus(const GridT& grid)
539 {
540  return doLevelSetGenus(grid);
541 }
542 
543 } // namespace tools
544 } // namespace OPENVDB_VERSION_NAME
545 } // namespace openvdb
546 
547 #endif // OPENVDB_TOOLS_LEVELSETMEASURE_HAS_BEEN_INCLUDED
typename TreeType::ValueType ValueType
Definition: LevelSetMeasure.h:104
typename tree::LeafManager< const TreeType > ManagerType
Definition: LevelSetMeasure.h:105
GridT GridType
Definition: LevelSetMeasure.h:102
#define OPENVDB_THROW(exception, message)
Definition: openvdb/Exceptions.h:74
Coord Abs(const Coord &xyz)
Definition: Coord.h:515
typename GridType::TreeType TreeType
Definition: LevelSetMeasure.h:103
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Real avgGaussianCurvature(bool useWorldUnits=true)
Compute the average gaussian curvature of the level set surface.
Definition: LevelSetMeasure.h:159
int genus()
Compute the genus of the level set surface.
Definition: LevelSetMeasure.h:168
void setGrainSize(int grainsize)
Set the grain-size used for multi-threading.
Definition: LevelSetMeasure.h:129
Real levelSetVolume(const GridType &grid, bool useWorldSpace=true)
Return the volume of a narrow-band level set surface.
int eulerCharacteristic()
Compute the Euler characteristic of the level set surface.
Definition: LevelSetMeasure.h:319
RealT operator()(RealT phi) const
Definition: LevelSetMeasure.h:85
Real levelSetArea(const GridT &grid, bool useWorldUnits)
Definition: LevelSetMeasure.h:428
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:84
Real avgMeanCurvature(bool useWorldUnits=true)
Compute the average mean curvature of the level set surface.
Definition: LevelSetMeasure.h:154
Real levelSetVolume(const GridT &grid, bool useWorldUnits)
Definition: LevelSetMeasure.h:461
bool wasInterrupted(T *i, int percent=-1)
Definition: NullInterrupter.h:49
int levelSetGenus(const GridType &grid)
Return the genus of a narrow-band level set surface.
Definition: Mat.h:187
Real area(bool useWorldUnits=true)
Compute the surface area of the level set.
Definition: LevelSetMeasure.h:283
Definition: openvdb/Exceptions.h:63
Definition: openvdb/Exceptions.h:13
Type Pow2(Type x)
Return x2.
Definition: Math.h:551
int levelSetEulerCharacteristic(const GridType &grid)
Return the Euler Characteristics of a narrow-band level set surface (possibly disconnected).
Type Pow3(Type x)
Return x3.
Definition: Math.h:555
Definition: openvdb/Exceptions.h:64
double Real
Definition: openvdb/Types.h:56
DiracDelta(RealT eps)
Definition: LevelSetMeasure.h:83
Smeared-out and continuous Dirac Delta function.
Definition: LevelSetMeasure.h:79
Definition: openvdb/Types.h:333
Real totMeanCurvature(bool useWorldUnits=true)
Compute the total mean curvature of the level set surface.
Definition: LevelSetMeasure.h:303
Real totGaussianCurvature(bool useWorldUnits=true)
Compute the total gaussian curvature of the level set surface.
Definition: LevelSetMeasure.h:311
int levelSetEulerCharacteristic(const GridT &grid)
Definition: LevelSetMeasure.h:495
Defines various finite difference stencils by means of the "curiously recurring template pattern" on ...
float Round(float x)
Return x rounded to the nearest integer.
Definition: Math.h:822
int getGrainSize() const
Definition: LevelSetMeasure.h:125
virtual ~LevelSetMeasure()
Destructor.
Definition: LevelSetMeasure.h:122
int levelSetGenus(const GridT &grid)
Definition: LevelSetMeasure.h:538
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
void init(const GridType &grid)
Re-initialize using the specified grid.
Definition: LevelSetMeasure.h:259
constexpr T pi()
Pi constant taken from Boost to match old behaviour.
Definition: Math.h:118
Real volume(bool useWorldUnits=true)
Compute the volume of the level set surface.
Definition: LevelSetMeasure.h:293
Real levelSetArea(const GridType &grid, bool useWorldSpace=true)
Return the surface area of a narrow-band level set.
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:178
Multi-threaded computation of surface area, volume and average mean-curvature for narrow band level s...
Definition: LevelSetMeasure.h:99