15#ifndef NANOVDB_GRIDSTATS_H_HAS_BEEN_INCLUDED
16#define NANOVDB_GRIDSTATS_H_HAS_BEEN_INCLUDED
18#include "../NanoVDB.h"
23#include <tbb/parallel_reduce.h>
45template<
typename BuildT>
50template<typename ValueT, int Rank = TensorTraits<ValueT>::Rank>
54template<
typename ValueT>
63 : mMin(
std::numeric_limits<ValueT>::max())
64 , mMax(
std::numeric_limits<ValueT>::lowest())
100 this->min(other.mMin);
101 this->max(other.mMax);
104 const ValueT&
min()
const {
return mMin; }
105 const ValueT&
max()
const {
return mMax; }
106 operator bool()
const {
return mMin <= mMax; }
107 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
110 static constexpr size_t size() {
return 0; }
114template<
typename VecT>
118 using Real =
typename VecT::ValueType;
130 : scalar(v.lengthSqr())
134 bool operator<(
const Pair& rhs)
const {
return scalar < rhs.scalar; }
150 : mMin(
std::numeric_limits<
Real>::max())
151 , mMax(
std::numeric_limits<
Real>::lowest())
184 if (other.mMin < mMin) {
187 if (mMax < other.mMax) {
192 const VecT&
min()
const {
return mMin.vector; }
193 const VecT&
max()
const {
return mMax.vector; }
194 operator bool()
const {
return !(mMax < mMin); }
195 static constexpr bool hasMinMax() {
return !std::is_same<bool, Real>::value; }
198 static constexpr size_t size() {
return 0; }
203template<typename ValueT, int Rank = TensorTraits<ValueT>::Rank>
214template<
typename ValueT>
244 const double delta = double(val) - mAvg;
245 mAvg += delta / double(mSize);
246 mAux += delta * (double(val) - mAvg);
252 const double denom = 1.0 / double(mSize + n);
253 const double delta = double(val) - mAvg;
254 mAvg += denom * delta * double(n);
255 mAux += denom * delta * delta * double(mSize) * double(n);
264 if (other.mSize > 0) {
265 const double denom = 1.0 / double(mSize + other.mSize);
266 const double delta = other.mAvg - mAvg;
267 mAvg += denom * delta * double(other.mSize);
268 mAux += other.mAux + denom * delta * delta * double(mSize) * double(other.mSize);
270 mSize += other.mSize;
275 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
276 static constexpr bool hasAverage() {
return !std::is_same<bool, ValueT>::value; }
277 static constexpr bool hasStdDeviation() {
return !std::is_same<bool, ValueT>::value; }
279 size_t size()
const {
return mSize; }
283 double avg()
const {
return mAvg; }
284 double mean()
const {
return mAvg; }
291 double var()
const {
return mSize < 2 ? 0.0 : mAux / double(mSize); }
298 double std()
const {
return sqrt(this->var()); }
311template<
typename ValueT>
332 typename BaseT::Pair tmp(val);
335 const double delta = tmp.scalar - mAvg;
336 mAvg += delta / double(mSize);
337 mAux += delta * (tmp.scalar - mAvg);
343 typename BaseT::Pair tmp(val);
344 const double denom = 1.0 / double(mSize + n);
345 const double delta = tmp.scalar - mAvg;
346 mAvg += denom * delta * double(n);
347 mAux += denom * delta * delta * double(mSize) * double(n);
356 if (other.mSize > 0) {
357 const double denom = 1.0 / double(mSize + other.mSize);
358 const double delta = other.mAvg - mAvg;
359 mAvg += denom * delta * double(other.mSize);
360 mAux += other.mAux + denom * delta * delta * double(mSize) * double(other.mSize);
362 mSize += other.mSize;
367 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
368 static constexpr bool hasAverage() {
return !std::is_same<bool, ValueT>::value; }
369 static constexpr bool hasStdDeviation() {
return !std::is_same<bool, ValueT>::value; }
371 size_t size()
const {
return mSize; }
375 double avg()
const {
return mAvg; }
376 double mean()
const {
return mAvg; }
383 double var()
const {
return mSize < 2 ? 0.0 : mAux / double(mSize); }
390 double std()
const {
return sqrt(this->var()); }
396template<
typename ValueT>
405 static constexpr size_t size() {
return 0; }
414template<
typename Gr
idT,
typename StatsT = Stats<
typename Gr
idT::ValueType>>
418 using TreeT =
typename GridT::TreeType;
419 using ValueT =
typename TreeT::ValueType;
420 using BuildT =
typename TreeT::BuildType;
421 using Node0 =
typename TreeT::Node0;
422 using Node1 =
typename TreeT::Node1;
423 using Node2 =
typename TreeT::Node2;
424 using RootT =
typename TreeT::Node3;
425 static_assert(std::is_same<ValueT, typename StatsT::ValueType>::value,
"Mismatching type");
426 static constexpr bool DO_STATS = StatsT::hasMinMax() || StatsT::hasAverage() || StatsT::hasStdDeviation();
430 void process( GridT& );
431 void process( TreeT& );
432 void process( RootT& );
435 template<
typename NodeT>
438 template<
typename DataT,
int Rank>
440 template<
typename DataT,
int Rank>
442 template<
typename DataT>
445 template<
typename T,
typename FlagT>
446 typename std::enable_if<!std::is_floating_point<T>::value>::type
447 setFlag(
const T&,
const T&, FlagT& flag)
const { flag &= ~FlagT(1); }
449 template<
typename T,
typename FlagT>
450 typename std::enable_if<std::is_floating_point<T>::value>::type
451 setFlag(
const T& min,
const T& max, FlagT& flag)
const;
456 void operator()(GridT& grid, ValueT delta = ValueT(0));
460template<
typename Gr
idT,
typename StatsT>
473 bbox[0].minComponent(other.
bbox[0]);
474 bbox[1].maxComponent(other.
bbox[1]);
481template<
typename Gr
idT,
typename StatsT>
485 this->process( grid );
490template<
typename Gr
idT,
typename StatsT>
491template<
typename DataT,
int Rank>
495 data->setMin(e.min());
496 data->setMax(e.max());
499template<
typename Gr
idT,
typename StatsT>
500template<
typename DataT,
int Rank>
501inline void GridStats<GridT, StatsT>::
502 setStats(DataT* data,
const Stats<ValueT, Rank>& s)
504 data->setMin(s.min());
505 data->setMax(s.max());
506 data->setAvg(s.avg());
507 data->setDev(s.std());
512template<
typename Gr
idT,
typename StatsT>
513template<
typename T,
typename FlagT>
514inline typename std::enable_if<std::is_floating_point<T>::value>::type
515GridStats<GridT, StatsT>::
516 setFlag(
const T& min,
const T& max, FlagT& flag)
const
518 if (mDelta > 0 && (min > mDelta || max < -mDelta)) {
527template<
typename Gr
idT,
typename StatsT>
528void GridStats<GridT, StatsT>::process( GridT &grid )
530 this->process( grid.tree() );
533 auto& data = *grid.data();
534 const auto& indexBBox = grid.tree().root().bbox();
535 if (indexBBox.empty()) {
536 data.mWorldBBox = BBox<Vec3R>();
537 data.setBBoxOn(
false);
547 const Coord
min = indexBBox[0];
548 const Coord
max = indexBBox[1] + Coord(1);
550 auto& worldBBox = data.mWorldBBox;
551 const auto& map = grid.map();
552 worldBBox[0] = worldBBox[1] = map.applyMap(
Vec3d(min[0], min[1], min[2]));
553 worldBBox.expand(map.applyMap(
Vec3d(min[0], min[1], max[2])));
554 worldBBox.expand(map.applyMap(
Vec3d(min[0], max[1], min[2])));
555 worldBBox.expand(map.applyMap(
Vec3d(max[0], min[1], min[2])));
556 worldBBox.expand(map.applyMap(
Vec3d(max[0], max[1], min[2])));
557 worldBBox.expand(map.applyMap(
Vec3d(max[0], min[1], max[2])));
558 worldBBox.expand(map.applyMap(
Vec3d(min[0], max[1], max[2])));
559 worldBBox.expand(map.applyMap(
Vec3d(max[0], max[1], max[2])));
560 data.setBBoxOn(
true);
564 data.setMinMaxOn(StatsT::hasMinMax());
565 data.setAverageOn(StatsT::hasAverage());
566 data.setStdDeviationOn(StatsT::hasStdDeviation());
571template<
typename Gr
idT,
typename StatsT>
572inline void GridStats<GridT, StatsT>::process(
typename GridT::TreeType &tree )
574 this->process( tree.root() );
579template<
typename Gr
idT,
typename StatsT>
580void GridStats<GridT, StatsT>::process(RootT &root)
582 using ChildT = Node2;
583 auto &data = *root.data();
584 if (data.mTableSize == 0) {
585 data.mMinimum = data.mMaximum = data.mBackground;
586 data.mAverage = data.mStdDevi = 0;
591 for (uint32_t i = 0; i < data.mTableSize; ++i) {
592 auto* tile = data.tile(i);
593 if (tile->isChild()) {
594 total.add( this->process( *data.getChild(tile) ) );
595 }
else if (tile->state) {
597 const Coord ijk = tile->origin();
598 total.bbox[0].minComponent(ijk);
599 total.bbox[1].maxComponent(ijk + Coord(ChildT::DIM - 1));
601 total.stats.add(tile->value, ChildT::NUM_VALUES);
605 this->setStats(&data, total.stats);
606 if (total.bbox.empty()) {
607 std::cerr <<
"\nWarning: input tree only contained inactive root tiles!"
608 <<
"\nWhile not strictly an error it's rather suspicious!\n";
611 data.mBBox = total.bbox;
617template<
typename Gr
idT,
typename StatsT>
618template<
typename NodeT>
619typename GridStats<GridT, StatsT>::NodeStats
620GridStats<GridT, StatsT>::process(NodeT &node)
623 using ChildT =
typename NodeT::ChildNodeType;
626 auto* data = node.data();
629 if (
const auto tileCount = data->mValueMask.countOn()) {
631 for (
auto it = data->mValueMask.beginOn(); it; ++it) {
633 total.stats.add( data->mTable[*it].value, ChildT::NUM_VALUES );
635 const Coord ijk = node.offsetToGlobalCoord(*it);
636 total.bbox[0].minComponent(ijk);
637 total.bbox[1].maxComponent(ijk + Coord(int32_t(ChildT::DIM) - 1));
642 if (
const size_t childCount = data->mChildMask.countOn()) {
643#ifndef NANOVDB_USE_TBB
644 for (
auto it = data->mChildMask.beginOn(); it; ++it) {
645 total.add( this->process( *data->getChild(*it) ) );
648 std::unique_ptr<ChildT*[]> childNodes(
new ChildT*[childCount]);
649 ChildT **ptr = childNodes.get();
650 for (
auto it = data->mChildMask.beginOn(); it; ++it) {
651 *ptr++ = data->getChild( *it );
653 using RangeT = tbb::blocked_range<size_t>;
654 total.add( tbb::parallel_reduce(RangeT(0, childCount), NodeStats(),
655 [&](
const RangeT &r, NodeStats local)->NodeStats {
656 for(
size_t i=r.begin(); i!=r.end(); ++i){
657 local.add( this->process( *childNodes[i] ) );
660 [](NodeStats a,
const NodeStats &b)->NodeStats {
return a.add( b ); }
665 data->mBBox = total.bbox;
666 if (total.bbox.empty()) {
667 data->mFlags |= uint32_t(1);
668 data->mFlags &= ~uint32_t(2);
670 data->mFlags |= uint32_t(2);
672 this->setStats(data, total.stats);
673 this->setFlag(data->mMinimum, data->mMaximum, data->mFlags);
681template<
typename Gr
idT,
typename StatsT>
682typename GridStats<GridT, StatsT>::NodeStats
683GridStats<GridT, StatsT>::process(Node0 &leaf)
685 static_assert(Node0::SIZE == 512u,
"Invalid size of leaf nodes");
687 auto *data = leaf.data();
688 if (
auto activeCount = data->mValueMask.countOn()) {
692 local.bbox[0] = local.bbox[1] = data->mBBoxMin;
693 local.bbox[1] += Coord(data->mBBoxDif[0], data->mBBoxDif[1], data->mBBoxDif[2]);
695 for (
auto it = data->mValueMask.beginOn(); it; ++it) {
696 local.stats.add(data->getValue(*it));
698 this->setStats(data, local.stats);
699 this->setFlag(data->getMin(), data->getMax(), data->mFlags);
702 data->mFlags &= ~uint8_t(2);
709template<
typename BuildT>
713 using ValueT =
typename GridT::ValueType;
716 }
else if (mode ==
StatsMode::BBox || std::is_same<bool, ValueT>::value) {
726 throw std::runtime_error(
"gridStats: Unsupported statistics mode.");
736template<
typename NodeT>
737Mask<NodeT::LOG2DIM> getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
739 Mask<NodeT::LOG2DIM> mask;
740 auto b = CoordBBox::createCube(node->origin(), node->dim());
741 assert( bbox.hasOverlap(b) );
742 if ( bbox.isInside(b) ) {
747 b.min() &= NodeT::DIM-1u;
748 b.min() >>= NodeT::ChildNodeType::TOTAL;
749 b.max() &= NodeT::DIM-1u;
750 b.max() >>= NodeT::ChildNodeType::TOTAL;
751 assert( !b.empty() );
753 for (
const Coord& ijk = *it; it; ++it) {
754 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
763template<
typename BuildT>
764Extrema<typename NanoGrid<BuildT>::ValueType>
768 using ValueT =
typename GridT::ValueType;
776 const RootT &root = grid.
tree().root();
777 const auto &bbox3 = root.bbox();
778 if (bbox.isInside(bbox3)) {
779 extrema.
min(root.minimum());
780 extrema.
max(root.maximum());
781 extrema.
add(root.background());
782 }
else if (bbox.hasOverlap(bbox3)) {
783 const auto *data3 = root.data();
784 for (uint32_t i=0; i<data3->mTableSize; ++i) {
785 const auto *tile = data3->tile(i);
786 CoordBBox bbox2 = CoordBBox::createCube(tile->origin(), Node2::dim());
787 if (!bbox.hasOverlap(bbox2))
continue;
788 if (tile->isChild()) {
789 const Node2 *node2 = data3->getChild(tile);
790 if (bbox.isInside(bbox2)) {
791 extrema.
min(node2->minimum());
792 extrema.
max(node2->maximum());
794 auto *data2 = node2->data();
795 const auto bboxMask2 = getBBoxMask(bbox, node2);
796 for (
auto it2 = bboxMask2.beginOn(); it2; ++it2) {
797 if (data2->mChildMask.isOn(*it2)) {
798 const Node1* node1 = data2->getChild(*it2);
799 CoordBBox bbox1 = CoordBBox::createCube(node1->origin(), Node1::dim());
800 if (bbox.isInside(bbox1)) {
801 extrema.
min(node1->minimum());
802 extrema.
max(node1->maximum());
804 auto *data1 = node1->data();
805 const auto bboxMask1 = getBBoxMask(bbox, node1);
806 for (
auto it1 = bboxMask1.beginOn(); it1; ++it1) {
807 if (data1->mChildMask.isOn(*it1)) {
808 const Node0* node0 = data1->getChild(*it1);
809 CoordBBox bbox0 = CoordBBox::createCube(node0->origin(), Node0::dim());
810 if (bbox.isInside(bbox0)) {
811 extrema.
min(node0->minimum());
812 extrema.
max(node0->maximum());
814 auto *data0 = node0->data();
815 const auto bboxMask0 = getBBoxMask(bbox, node0);
816 for (
auto it0 = bboxMask0.beginOn(); it0; ++it0) {
817 extrema.
add(data0->getValue(*it0));
821 extrema.
add(data1->mTable[*it1].value);
826 extrema.
add(data2->mTable[*it2].value);
831 extrema.
add(tile->value);
835 extrema.
add(root.background());
A unified wrapper for tbb::parallel_for and a naive std::thread fallback.
Custom Range class that is compatible with the tbb::blocked_range classes.
Template specialization of Extrema on scalar value types, i.e. rank = 0.
Definition GridStats.h:56
static constexpr size_t size()
Definition GridStats.h:110
Extrema & min(const ValueT &v)
Definition GridStats.h:77
Extrema & add(const ValueT &v, uint64_t)
Definition GridStats.h:97
Extrema(const ValueT &v)
Definition GridStats.h:67
Extrema()
Definition GridStats.h:62
Extrema & add(const Extrema &other)
Definition GridStats.h:98
ValueT ValueType
Definition GridStats.h:61
const ValueT & max() const
Definition GridStats.h:105
Extrema & max(const ValueT &v)
Definition GridStats.h:84
ValueT mMax
Definition GridStats.h:58
Extrema & add(const ValueT &v)
Definition GridStats.h:91
static constexpr bool hasAverage()
Definition GridStats.h:108
static constexpr bool hasMinMax()
Definition GridStats.h:107
Extrema(const ValueT &a, const ValueT &b)
Definition GridStats.h:72
const ValueT & min() const
Definition GridStats.h:104
static constexpr bool hasStdDeviation()
Definition GridStats.h:109
Extrema & min(const VecT &v)
Definition GridStats.h:164
Extrema & add(const VecT &v, uint64_t)
Definition GridStats.h:181
static constexpr size_t size()
Definition GridStats.h:198
Extrema(const VecT &a, const VecT &b)
Definition GridStats.h:159
Extrema()
Definition GridStats.h:149
Extrema & add(const Pair &p)
Definition GridStats.h:136
Extrema & max(const VecT &v)
Definition GridStats.h:172
const VecT & min() const
Definition GridStats.h:192
Extrema & add(const Extrema &other)
Definition GridStats.h:182
Extrema & add(const VecT &v)
Definition GridStats.h:180
typename VecT::ValueType Real
Definition GridStats.h:118
static constexpr bool hasAverage()
Definition GridStats.h:196
static constexpr bool hasMinMax()
Definition GridStats.h:195
Extrema(const VecT &v)
Definition GridStats.h:154
static constexpr bool hasStdDeviation()
Definition GridStats.h:197
const VecT & max() const
Definition GridStats.h:193
VecT ValueType
Definition GridStats.h:148
Definition GridStats.h:51
Allows for the construction of NanoVDB grids without any dependecy.
Definition GridStats.h:416
void operator()(GridT &grid, ValueT delta=ValueT(0))
Definition GridStats.h:482
Highest level of the data structure. Contains a tree and a world->index transform (that currently onl...
Definition NanoVDB.h:2558
const TreeT & tree() const
Return a const reference to the tree.
Definition NanoVDB.h:2600
double var() const
Return the population variance.
Definition GridStats.h:291
size_t size() const
Definition GridStats.h:279
Stats(const ValueT &val)
Definition GridStats.h:232
double mean() const
Definition GridStats.h:284
ValueT ValueType
Definition GridStats.h:224
size_t mSize
Definition GridStats.h:220
double RealT
Definition GridStats.h:219
Stats & add(const ValueT &val, uint64_t n)
Add n samples with constant value val.
Definition GridStats.h:250
double variance() const
Definition GridStats.h:292
Stats & add(const ValueT &val)
Add a single sample.
Definition GridStats.h:240
double stdDev() const
Definition GridStats.h:299
static constexpr bool hasAverage()
Definition GridStats.h:276
static constexpr bool hasMinMax()
Definition GridStats.h:275
Stats & add(const Stats &other)
Add the samples from the other Stats instance.
Definition GridStats.h:262
double mAux
Definition GridStats.h:221
double std() const
Return the standard deviation (=Sqrt(variance)) as defined from the (biased) population variance.
Definition GridStats.h:298
static constexpr bool hasStdDeviation()
Definition GridStats.h:277
double avg() const
Return the arithmetic mean, i.e. average, value.
Definition GridStats.h:283
Stats()
Definition GridStats.h:225
double var() const
Return the population variance.
Definition GridStats.h:383
size_t size() const
Definition GridStats.h:371
double mean() const
Definition GridStats.h:376
ValueT ValueType
Definition GridStats.h:321
size_t mSize
Definition GridStats.h:317
double RealT
Definition GridStats.h:316
Stats & add(const ValueT &val, uint64_t n)
Add n samples with constant value val.
Definition GridStats.h:341
double variance() const
Definition GridStats.h:384
Stats & add(const ValueT &val)
Add a single sample.
Definition GridStats.h:330
double stdDev() const
Definition GridStats.h:391
static constexpr bool hasAverage()
Definition GridStats.h:368
static constexpr bool hasMinMax()
Definition GridStats.h:367
Stats & add(const Stats &other)
Add the samples from the other Stats instance.
Definition GridStats.h:354
double mAux
Definition GridStats.h:318
double std() const
Return the standard deviation (=Sqrt(variance)) as defined from the (biased) population variance.
Definition GridStats.h:390
static constexpr bool hasStdDeviation()
Definition GridStats.h:369
double avg() const
Return the arithmetic mean, i.e. average, value.
Definition GridStats.h:375
Stats()
Definition GridStats.h:322
Definition GridStats.h:204
void add(double val)
Add a single sample.
Definition Stats.h:102
double min() const
Return the minimum value.
Definition Stats.h:121
double max() const
Return the maximum value.
Definition Stats.h:124
Extrema< typename NanoGrid< BuildT >::ValueType > getExtrema(const NanoGrid< BuildT > &grid, const CoordBBox &bbox)
return the extrema of all the values in a grid that intersects the specified bounding box.
Definition GridStats.h:765
BBox< Coord > CoordBBox
Definition NanoVDB.h:1811
StatsMode
Grid flags which indicate what extra information is present in the grid buffer.
Definition GridStats.h:32
Vec3< double > Vec3d
Definition NanoVDB.h:1290
void gridStats(NanoGrid< BuildT > &grid, StatsMode mode=StatsMode::Default)
Re-computes the min/max, stats and bbox information for an existing NanoVDB Grid.
Definition GridStats.h:710
Definition NanoVDB.h:1657
VecT vector
Definition GridStats.h:122
Pair(Real s)
Definition GridStats.h:124
Pair(const VecT &v)
Definition GridStats.h:129
bool operator<(const Pair &rhs) const
Definition GridStats.h:134
Real scalar
Definition GridStats.h:121
Definition GridStats.h:462
NodeStats()
Definition GridStats.h:467
StatsT stats
Definition GridStats.h:463
CoordBBox bbox
Definition GridStats.h:465
NodeStats & add(const NodeStats &other)
Definition GridStats.h:469
typename GridT::TreeType type
Definition NanoVDB.h:2787
Struct to derive node type from its level in a given grid, tree or root while preserving constness.
Definition NanoVDB.h:2345
No-op Stats class.
Definition GridStats.h:398
NoopStats(const ValueT &)
Definition GridStats.h:401
static constexpr size_t size()
Definition GridStats.h:405
NoopStats & add(const ValueT &, uint64_t)
Definition GridStats.h:403
NoopStats & add(const NoopStats &)
Definition GridStats.h:404
ValueT ValueType
Definition GridStats.h:399
NoopStats & add(const ValueT &)
Definition GridStats.h:402
static constexpr bool hasAverage()
Definition GridStats.h:407
static constexpr bool hasMinMax()
Definition GridStats.h:406
NoopStats()
Definition GridStats.h:400
static constexpr bool hasStdDeviation()
Definition GridStats.h:408
static constexpr bool value
Definition NanoVDB.h:358