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())
101 this->min(other.mMin);
102 this->max(other.mMax);
105 const ValueT&
min()
const {
return mMin; }
106 const ValueT&
max()
const {
return mMax; }
107 operator bool()
const {
return mMin <= mMax; }
108 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
111 static constexpr size_t size() {
return 0; }
115template<
typename VecT>
119 using Real =
typename VecT::ValueType;
131 : scalar(v.lengthSqr())
136 bool operator<(
const Pair& rhs)
const {
return scalar < rhs.scalar; }
152 : mMin(
std::numeric_limits<
Real>::max())
153 , mMax(
std::numeric_limits<
Real>::lowest())
187 if (other.mMin < mMin) {
190 if (mMax < other.mMax) {
195 const VecT&
min()
const {
return mMin.vector; }
196 const VecT&
max()
const {
return mMax.vector; }
197 operator bool()
const {
return !(mMax < mMin); }
198 static constexpr bool hasMinMax() {
return !std::is_same<bool, Real>::value; }
201 static constexpr size_t size() {
return 0; }
206template<typename ValueT, int Rank = TensorTraits<ValueT>::Rank>
217template<
typename ValueT>
247 const double delta = double(val) - mAvg;
248 mAvg += delta / double(mSize);
249 mAux += delta * (double(val) - mAvg);
255 const double denom = 1.0 / double(mSize + n);
256 const double delta = double(val) - mAvg;
257 mAvg += denom * delta * double(n);
258 mAux += denom * delta * delta * double(mSize) * double(n);
267 if (other.mSize > 0) {
268 const double denom = 1.0 / double(mSize + other.mSize);
269 const double delta = other.mAvg - mAvg;
270 mAvg += denom * delta * double(other.mSize);
271 mAux += other.mAux + denom * delta * delta * double(mSize) * double(other.mSize);
273 mSize += other.mSize;
278 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
279 static constexpr bool hasAverage() {
return !std::is_same<bool, ValueT>::value; }
280 static constexpr bool hasStdDeviation() {
return !std::is_same<bool, ValueT>::value; }
282 size_t size()
const {
return mSize; }
286 double avg()
const {
return mAvg; }
287 double mean()
const {
return mAvg; }
294 double var()
const {
return mSize < 2 ? 0.0 : mAux / double(mSize); }
301 double std()
const {
return sqrt(this->var()); }
314template<
typename ValueT>
335 typename BaseT::Pair tmp(val);
338 const double delta = tmp.scalar - mAvg;
339 mAvg += delta / double(mSize);
340 mAux += delta * (tmp.scalar - mAvg);
346 typename BaseT::Pair tmp(val);
347 const double denom = 1.0 / double(mSize + n);
348 const double delta = tmp.scalar - mAvg;
349 mAvg += denom * delta * double(n);
350 mAux += denom * delta * delta * double(mSize) * double(n);
359 if (other.mSize > 0) {
360 const double denom = 1.0 / double(mSize + other.mSize);
361 const double delta = other.mAvg - mAvg;
362 mAvg += denom * delta * double(other.mSize);
363 mAux += other.mAux + denom * delta * delta * double(mSize) * double(other.mSize);
365 mSize += other.mSize;
370 static constexpr bool hasMinMax() {
return !std::is_same<bool, ValueT>::value; }
371 static constexpr bool hasAverage() {
return !std::is_same<bool, ValueT>::value; }
372 static constexpr bool hasStdDeviation() {
return !std::is_same<bool, ValueT>::value; }
374 size_t size()
const {
return mSize; }
378 double avg()
const {
return mAvg; }
379 double mean()
const {
return mAvg; }
386 double var()
const {
return mSize < 2 ? 0.0 : mAux / double(mSize); }
393 double std()
const {
return sqrt(this->var()); }
399template<
typename ValueT>
408 static constexpr size_t size() {
return 0; }
417template<
typename Gr
idT,
typename StatsT = Stats<
typename Gr
idT::ValueType>>
421 using TreeT =
typename GridT::TreeType;
422 using ValueT =
typename TreeT::ValueType;
423 using BuildT =
typename TreeT::BuildType;
424 using Node0 =
typename TreeT::Node0;
425 using Node1 =
typename TreeT::Node1;
426 using Node2 =
typename TreeT::Node2;
427 using RootT =
typename TreeT::Node3;
428 static_assert(std::is_same<ValueT, typename StatsT::ValueType>::value,
"Mismatching type");
429 static constexpr bool DO_STATS = StatsT::hasMinMax() || StatsT::hasAverage() || StatsT::hasStdDeviation();
433 void process( GridT& );
434 void process( TreeT& );
435 void process( RootT& );
438 template<
typename NodeT>
441 template<
typename DataT,
int Rank>
443 template<
typename DataT,
int Rank>
445 template<
typename DataT>
448 template<
typename T,
typename FlagT>
449 typename std::enable_if<!std::is_floating_point<T>::value>::type
450 setFlag(
const T&,
const T&, FlagT& flag)
const { flag &= ~FlagT(1); }
452 template<
typename T,
typename FlagT>
453 typename std::enable_if<std::is_floating_point<T>::value>::type
454 setFlag(
const T& min,
const T& max, FlagT& flag)
const;
459 void operator()(GridT& grid, ValueT delta = ValueT(0));
463template<
typename Gr
idT,
typename StatsT>
476 bbox[0].minComponent(other.
bbox[0]);
477 bbox[1].maxComponent(other.
bbox[1]);
484template<
typename Gr
idT,
typename StatsT>
488 this->process( grid );
493template<
typename Gr
idT,
typename StatsT>
494template<
typename DataT,
int Rank>
498 data->setMin(e.min());
499 data->setMax(e.max());
502template<
typename Gr
idT,
typename StatsT>
503template<
typename DataT,
int Rank>
504inline void GridStats<GridT, StatsT>::
505 setStats(DataT* data,
const Stats<ValueT, Rank>& s)
507 data->setMin(s.min());
508 data->setMax(s.max());
509 data->setAvg(s.avg());
510 data->setDev(s.std());
515template<
typename Gr
idT,
typename StatsT>
516template<
typename T,
typename FlagT>
517inline typename std::enable_if<std::is_floating_point<T>::value>::type
518GridStats<GridT, StatsT>::
519 setFlag(
const T& min,
const T& max, FlagT& flag)
const
521 if (mDelta > 0 && (min > mDelta || max < -mDelta)) {
530template<
typename Gr
idT,
typename StatsT>
531void GridStats<GridT, StatsT>::process( GridT &grid )
533 this->process( grid.tree() );
536 auto& data = *grid.data();
537 const auto& indexBBox = grid.tree().root().bbox();
538 if (indexBBox.empty()) {
539 data.mWorldBBox = BBox<Vec3R>();
540 data.setBBoxOn(
false);
550 const Coord
min = indexBBox[0];
551 const Coord
max = indexBBox[1] + Coord(1);
553 auto& worldBBox = data.mWorldBBox;
554 const auto& map = grid.map();
555 worldBBox[0] = worldBBox[1] = map.applyMap(
Vec3d(min[0], min[1], min[2]));
556 worldBBox.expand(map.applyMap(
Vec3d(min[0], min[1], max[2])));
557 worldBBox.expand(map.applyMap(
Vec3d(min[0], max[1], min[2])));
558 worldBBox.expand(map.applyMap(
Vec3d(max[0], min[1], min[2])));
559 worldBBox.expand(map.applyMap(
Vec3d(max[0], max[1], min[2])));
560 worldBBox.expand(map.applyMap(
Vec3d(max[0], min[1], max[2])));
561 worldBBox.expand(map.applyMap(
Vec3d(min[0], max[1], max[2])));
562 worldBBox.expand(map.applyMap(
Vec3d(max[0], max[1], max[2])));
563 data.setBBoxOn(
true);
567 data.setMinMaxOn(StatsT::hasMinMax());
568 data.setAverageOn(StatsT::hasAverage());
569 data.setStdDeviationOn(StatsT::hasStdDeviation());
574template<
typename Gr
idT,
typename StatsT>
575inline void GridStats<GridT, StatsT>::process(
typename GridT::TreeType &tree )
577 this->process( tree.root() );
582template<
typename Gr
idT,
typename StatsT>
583void GridStats<GridT, StatsT>::process(RootT &root)
585 using ChildT = Node2;
586 auto &data = *root.data();
587 if (data.mTableSize == 0) {
588 data.mMinimum = data.mMaximum = data.mBackground;
589 data.mAverage = data.mStdDevi = 0;
594 for (uint32_t i = 0; i < data.mTableSize; ++i) {
595 auto* tile = data.tile(i);
596 if (tile->isChild()) {
597 total.add( this->process( *data.getChild(tile) ) );
598 }
else if (tile->state) {
600 const Coord ijk = tile->origin();
601 total.bbox[0].minComponent(ijk);
602 total.bbox[1].maxComponent(ijk + Coord(ChildT::DIM - 1));
604 total.stats.add(tile->value, ChildT::NUM_VALUES);
608 this->setStats(&data, total.stats);
609 if (total.bbox.empty()) {
610 std::cerr <<
"\nWarning: input tree only contained inactive root tiles!"
611 <<
"\nWhile not strictly an error it's rather suspicious!\n";
614 data.mBBox = total.bbox;
620template<
typename Gr
idT,
typename StatsT>
621template<
typename NodeT>
622typename GridStats<GridT, StatsT>::NodeStats
623GridStats<GridT, StatsT>::process(NodeT &node)
626 using ChildT =
typename NodeT::ChildNodeType;
629 auto* data = node.data();
632 if (
const auto tileCount = data->mValueMask.countOn()) {
634 for (
auto it = data->mValueMask.beginOn(); it; ++it) {
636 total.stats.add( data->mTable[*it].value, ChildT::NUM_VALUES );
638 const Coord ijk = node.offsetToGlobalCoord(*it);
639 total.bbox[0].minComponent(ijk);
640 total.bbox[1].maxComponent(ijk + Coord(int32_t(ChildT::DIM) - 1));
645 if (
const size_t childCount = data->mChildMask.countOn()) {
646#ifndef NANOVDB_USE_TBB
647 for (
auto it = data->mChildMask.beginOn(); it; ++it) {
648 total.add( this->process( *data->getChild(*it) ) );
651 std::unique_ptr<ChildT*[]> childNodes(
new ChildT*[childCount]);
652 ChildT **ptr = childNodes.get();
653 for (
auto it = data->mChildMask.beginOn(); it; ++it) {
654 *ptr++ = data->getChild( *it );
656 using RangeT = tbb::blocked_range<size_t>;
657 total.add( tbb::parallel_reduce(RangeT(0, childCount), NodeStats(),
658 [&](
const RangeT &r, NodeStats local)->NodeStats {
659 for(
size_t i=r.begin(); i!=r.end(); ++i){
660 local.add( this->process( *childNodes[i] ) );
663 [](NodeStats a,
const NodeStats &b)->NodeStats {
return a.add( b ); }
668 data->mBBox = total.bbox;
669 if (total.bbox.empty()) {
670 data->mFlags |= uint32_t(1);
671 data->mFlags &= ~uint32_t(2);
673 data->mFlags |= uint32_t(2);
675 this->setStats(data, total.stats);
676 this->setFlag(data->mMinimum, data->mMaximum, data->mFlags);
684template<
typename Gr
idT,
typename StatsT>
685typename GridStats<GridT, StatsT>::NodeStats
686GridStats<GridT, StatsT>::process(Node0 &leaf)
688 static_assert(Node0::SIZE == 512u,
"Invalid size of leaf nodes");
690 auto *data = leaf.data();
691 if (
auto activeCount = data->mValueMask.countOn()) {
695 local.bbox[0] = local.bbox[1] = data->mBBoxMin;
696 local.bbox[1] += Coord(data->mBBoxDif[0], data->mBBoxDif[1], data->mBBoxDif[2]);
698 for (
auto it = data->mValueMask.beginOn(); it; ++it) {
699 local.stats.add(data->getValue(*it));
701 this->setStats(data, local.stats);
702 this->setFlag(data->getMin(), data->getMax(), data->mFlags);
705 data->mFlags &= ~uint8_t(2);
712template<
typename BuildT>
716 using ValueT =
typename GridT::ValueType;
719 }
else if (mode ==
StatsMode::BBox || std::is_same<bool, ValueT>::value) {
729 throw std::runtime_error(
"gridStats: Unsupported statistics mode.");
739template<
typename NodeT>
740Mask<NodeT::LOG2DIM> getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
742 Mask<NodeT::LOG2DIM> mask;
743 auto b = CoordBBox::createCube(node->origin(), node->dim());
744 assert( bbox.hasOverlap(b) );
745 if ( bbox.isInside(b) ) {
750 b.min() &= NodeT::DIM-1u;
751 b.min() >>= NodeT::ChildNodeType::TOTAL;
752 b.max() &= NodeT::DIM-1u;
753 b.max() >>= NodeT::ChildNodeType::TOTAL;
754 assert( !b.empty() );
756 for (
const Coord& ijk = *it; it; ++it) {
757 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
766template<
typename BuildT>
767Extrema<typename NanoGrid<BuildT>::ValueType>
771 using ValueT =
typename GridT::ValueType;
779 const RootT &root = grid.
tree().root();
780 const auto &bbox3 = root.bbox();
781 if (bbox.isInside(bbox3)) {
782 extrema.
min(root.minimum());
783 extrema.
max(root.maximum());
784 extrema.
add(root.background());
785 }
else if (bbox.hasOverlap(bbox3)) {
786 const auto *data3 = root.data();
787 for (uint32_t i=0; i<data3->mTableSize; ++i) {
788 const auto *tile = data3->tile(i);
789 CoordBBox bbox2 = CoordBBox::createCube(tile->origin(), Node2::dim());
790 if (!bbox.hasOverlap(bbox2))
continue;
791 if (tile->isChild()) {
792 const Node2 *node2 = data3->getChild(tile);
793 if (bbox.isInside(bbox2)) {
794 extrema.
min(node2->minimum());
795 extrema.
max(node2->maximum());
797 auto *data2 = node2->data();
798 const auto bboxMask2 = getBBoxMask(bbox, node2);
799 for (
auto it2 = bboxMask2.beginOn(); it2; ++it2) {
800 if (data2->mChildMask.isOn(*it2)) {
801 const Node1* node1 = data2->getChild(*it2);
802 CoordBBox bbox1 = CoordBBox::createCube(node1->origin(), Node1::dim());
803 if (bbox.isInside(bbox1)) {
804 extrema.
min(node1->minimum());
805 extrema.
max(node1->maximum());
807 auto *data1 = node1->data();
808 const auto bboxMask1 = getBBoxMask(bbox, node1);
809 for (
auto it1 = bboxMask1.beginOn(); it1; ++it1) {
810 if (data1->mChildMask.isOn(*it1)) {
811 const Node0* node0 = data1->getChild(*it1);
812 CoordBBox bbox0 = CoordBBox::createCube(node0->origin(), Node0::dim());
813 if (bbox.isInside(bbox0)) {
814 extrema.
min(node0->minimum());
815 extrema.
max(node0->maximum());
817 auto *data0 = node0->data();
818 const auto bboxMask0 = getBBoxMask(bbox, node0);
819 for (
auto it0 = bboxMask0.beginOn(); it0; ++it0) {
820 extrema.
add(data0->getValue(*it0));
824 extrema.
add(data1->mTable[*it1].value);
829 extrema.
add(data2->mTable[*it2].value);
834 extrema.
add(tile->value);
838 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:111
Extrema & min(const ValueT &v)
Definition: GridStats.h:78
Extrema & add(const ValueT &v, uint64_t)
Definition: GridStats.h:98
Extrema(const ValueT &v)
Definition: GridStats.h:67
Extrema()
Definition: GridStats.h:62
Extrema & operator=(const Extrema &)=default
Extrema & add(const Extrema &other)
Definition: GridStats.h:99
ValueT ValueType
Definition: GridStats.h:61
const ValueT & max() const
Definition: GridStats.h:106
Extrema & max(const ValueT &v)
Definition: GridStats.h:85
ValueT mMax
Definition: GridStats.h:58
Extrema & add(const ValueT &v)
Definition: GridStats.h:92
static constexpr bool hasAverage()
Definition: GridStats.h:109
static constexpr bool hasMinMax()
Definition: GridStats.h:108
Extrema(const ValueT &a, const ValueT &b)
Definition: GridStats.h:72
const ValueT & min() const
Definition: GridStats.h:105
static constexpr bool hasStdDeviation()
Definition: GridStats.h:110
Extrema & min(const VecT &v)
Definition: GridStats.h:167
Extrema & add(const VecT &v, uint64_t)
Definition: GridStats.h:184
static constexpr size_t size()
Definition: GridStats.h:201
Extrema(const VecT &a, const VecT &b)
Definition: GridStats.h:161
Extrema()
Definition: GridStats.h:151
Extrema & add(const Pair &p)
Definition: GridStats.h:138
Extrema & operator=(const Extrema &)=default
Extrema & max(const VecT &v)
Definition: GridStats.h:175
const VecT & min() const
Definition: GridStats.h:195
Extrema & add(const Extrema &other)
Definition: GridStats.h:185
Extrema & add(const VecT &v)
Definition: GridStats.h:183
typename VecT::ValueType Real
Definition: GridStats.h:119
static constexpr bool hasAverage()
Definition: GridStats.h:199
static constexpr bool hasMinMax()
Definition: GridStats.h:198
Extrema(const VecT &v)
Definition: GridStats.h:156
static constexpr bool hasStdDeviation()
Definition: GridStats.h:200
const VecT & max() const
Definition: GridStats.h:196
VecT ValueType
Definition: GridStats.h:150
Definition: GridStats.h:51
Allows for the construction of NanoVDB grids without any dependecy.
Definition: GridStats.h:419
void operator()(GridT &grid, ValueT delta=ValueT(0))
Definition: GridStats.h:485
Highest level of the data structure. Contains a tree and a world->index transform (that currently onl...
Definition: NanoVDB.h:2556
const TreeT & tree() const
Return a const reference to the tree.
Definition: NanoVDB.h:2598
double var() const
Return the population variance.
Definition: GridStats.h:294
size_t size() const
Definition: GridStats.h:282
Stats(const ValueT &val)
Definition: GridStats.h:235
double mean() const
Definition: GridStats.h:287
ValueT ValueType
Definition: GridStats.h:227
size_t mSize
Definition: GridStats.h:223
double RealT
Definition: GridStats.h:222
Stats & add(const ValueT &val, uint64_t n)
Add n samples with constant value val.
Definition: GridStats.h:253
double variance() const
Definition: GridStats.h:295
Stats & add(const ValueT &val)
Add a single sample.
Definition: GridStats.h:243
double stdDev() const
Definition: GridStats.h:302
static constexpr bool hasAverage()
Definition: GridStats.h:279
static constexpr bool hasMinMax()
Definition: GridStats.h:278
Stats & add(const Stats &other)
Add the samples from the other Stats instance.
Definition: GridStats.h:265
double mAux
Definition: GridStats.h:224
double std() const
Return the standard deviation (=Sqrt(variance)) as defined from the (biased) population variance.
Definition: GridStats.h:301
static constexpr bool hasStdDeviation()
Definition: GridStats.h:280
double avg() const
Return the arithmetic mean, i.e. average, value.
Definition: GridStats.h:286
Stats()
Definition: GridStats.h:228
double var() const
Return the population variance.
Definition: GridStats.h:386
size_t size() const
Definition: GridStats.h:374
double mean() const
Definition: GridStats.h:379
ValueT ValueType
Definition: GridStats.h:324
size_t mSize
Definition: GridStats.h:320
double RealT
Definition: GridStats.h:319
Stats & add(const ValueT &val, uint64_t n)
Add n samples with constant value val.
Definition: GridStats.h:344
double variance() const
Definition: GridStats.h:387
Stats & add(const ValueT &val)
Add a single sample.
Definition: GridStats.h:333
double stdDev() const
Definition: GridStats.h:394
static constexpr bool hasAverage()
Definition: GridStats.h:371
static constexpr bool hasMinMax()
Definition: GridStats.h:370
Stats & add(const Stats &other)
Add the samples from the other Stats instance.
Definition: GridStats.h:357
double mAux
Definition: GridStats.h:321
double std() const
Return the standard deviation (=Sqrt(variance)) as defined from the (biased) population variance.
Definition: GridStats.h:393
static constexpr bool hasStdDeviation()
Definition: GridStats.h:372
double avg() const
Return the arithmetic mean, i.e. average, value.
Definition: GridStats.h:378
Stats()
Definition: GridStats.h:325
Definition: GridStats.h:207
void add(double val)
Add a single sample.
Definition: Stats.h:106
double min() const
Return the minimum value.
Definition: Stats.h:125
double max() const
Return the maximum value.
Definition: Stats.h:128
Definition: NanoVDB.h:208
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:768
BBox< Coord > CoordBBox
Definition: NanoVDB.h:1809
StatsMode
Grid flags which indicate what extra information is present in the grid buffer.
Definition: GridStats.h:32
Vec3< double > Vec3d
Definition: NanoVDB.h:1288
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:713
Definition: NanoVDB.h:1655
VecT vector
Definition: GridStats.h:123
Pair(Real s)
Definition: GridStats.h:125
Pair(const VecT &v)
Definition: GridStats.h:130
bool operator<(const Pair &rhs) const
Definition: GridStats.h:136
Real scalar
Definition: GridStats.h:122
Pair & operator=(const Pair &)=default
Definition: GridStats.h:465
NodeStats()
Definition: GridStats.h:470
StatsT stats
Definition: GridStats.h:466
CoordBBox bbox
Definition: GridStats.h:468
NodeStats & add(const NodeStats &other)
Definition: GridStats.h:472
typename GridT::TreeType type
Definition: NanoVDB.h:2785
Struct to derive node type from its level in a given grid, tree or root while preserving constness.
Definition: NanoVDB.h:2343
No-op Stats class.
Definition: GridStats.h:401
NoopStats(const ValueT &)
Definition: GridStats.h:404
static constexpr size_t size()
Definition: GridStats.h:408
NoopStats & add(const ValueT &, uint64_t)
Definition: GridStats.h:406
NoopStats & add(const NoopStats &)
Definition: GridStats.h:407
ValueT ValueType
Definition: GridStats.h:402
NoopStats & add(const ValueT &)
Definition: GridStats.h:405
static constexpr bool hasAverage()
Definition: GridStats.h:410
static constexpr bool hasMinMax()
Definition: GridStats.h:409
NoopStats()
Definition: GridStats.h:403
static constexpr bool hasStdDeviation()
Definition: GridStats.h:411
static constexpr bool value
Definition: NanoVDB.h:358