1 // Copyright (c) 2017-2021, Lawrence Livermore National Security, LLC and
2 // other Axom Project Developers. See the top-level LICENSE file for details.
3 //
4 // SPDX-License-Identifier: (BSD-3-Clause)
5 
6 /**
7  * \file InOutOctreeStats.hpp
8  *
9  * \brief Defines helper class to generate statistics about an InOutOctree.
10  */
11 
12 #ifndef AXOM_QUEST_INOUT_OCTREE_STATS__HPP_
13 #define AXOM_QUEST_INOUT_OCTREE_STATS__HPP_
14 
15 #include "axom/core.hpp"
16 #include "axom/slic.hpp"
17 #include "axom/slam.hpp"
18 #include "axom/primal.hpp"
19 
20 #include "BlockData.hpp"
21 #include "MeshWrapper.hpp"
22 
23 #include "axom/fmt.hpp"
24 
25 namespace axom
26 {
27 namespace quest
28 {
29 // Predeclare InOutOctree class
30 template <int DIM>
31 class InOutOctree;
32 
33 namespace detail
34 {
35 template <int DIM>
36 class InOutOctreeStats
37 {
38 public:
39   using InOutOctreeType = InOutOctree<DIM>;
40   using CellIndexSet = typename InOutOctreeType::CellIndexSet;
41 
42   using OctreeBaseType = typename InOutOctreeType::OctreeBaseType;
43   using OctreeLevels = typename OctreeBaseType::OctreeLevels;
44   using BlockIndex = typename OctreeBaseType::BlockIndex;
45 
46   using LeafCountMap = slam::Map<slam::Set<>, int>;
47   using CellCountMap = slam::Map<slam::Set<>, int>;
48   using CardinalityVCMap = slam::Map<slam::Set<>, int>;
49 
50   using LogHistogram = std::map<int, int>;
51   using MinMaxRange = primal::BoundingBox<double, 1>;
52   using LengthType = MinMaxRange::PointType;
53   using LogRangeMap = std::map<int, MinMaxRange>;
54 
55   /** A simple struct to track totals within the octree levels */
56   struct Totals
57   {
58     int blocks {0};
59     int leaves {0};
60     int leavesWithVert {0};
61     int cellRefCount {0};
62     int whiteBlocks {0};
63     int blackBlocks {0};
64     int grayBlocks {0};
65   };
66 
67 public:
InOutOctreeStats(const InOutOctreeType & octree)68   InOutOctreeStats(const InOutOctreeType& octree)
69     : m_octree(octree)
70     , m_generationState(m_octree.m_generationState)
71     , m_levelBlocks(&m_octree.m_levels)
72     , m_levelLeaves(&m_octree.m_levels)
73     , m_levelLeavesWithVert(&m_octree.m_levels)
74     , m_levelCellRefCount(&m_octree.m_levels)
75     , m_levelWhiteBlockCount(&m_octree.m_levels)
76     , m_levelBlackBlockCount(&m_octree.m_levels)
77     , m_levelGrayBlockCount(&m_octree.m_levels)
78   {
79     if(m_generationState >= InOutOctreeType::INOUTOCTREE_ELEMENTS_INSERTED)
80     {
81       m_cellCount = CellCountMap(&m_octree.m_meshWrapper.elementSet());
82     }
83 
84     // Iterate through blocks -- count the numbers of internal and leaf blocks
85     for(int lev = 0; lev < m_octree.m_levels.size(); ++lev)
86     {
87       const auto& levelLeafMap = m_octree.getOctreeLevel(lev);
88 
89       m_levelBlocks[lev] = levelLeafMap.numBlocks();
90       m_levelLeaves[lev] = levelLeafMap.numLeafBlocks();
91       m_levelLeavesWithVert[lev] = 0;
92       m_levelCellRefCount[lev] = 0;
93       m_levelWhiteBlockCount[lev] = 0;
94       m_levelBlackBlockCount[lev] = 0;
95       m_levelGrayBlockCount[lev] = 0;
96 
97       auto itEnd = levelLeafMap.end();
98       for(auto it = levelLeafMap.begin(); it != itEnd; ++it)
99       {
100         const InOutBlockData& blockData = *it;
101         BlockIndex block(it.pt(), lev);
102 
103         if(blockData.isLeaf())
104         {
105           if(blockData.hasData())
106           {
107             ++m_levelLeavesWithVert[lev];
108 
109             if(m_generationState >= InOutOctreeType::INOUTOCTREE_ELEMENTS_INSERTED)
110             {
111               m_levelCellRefCount[lev] +=
112                 m_octree.leafCells(block, blockData).size();
113 
114               BlockIndex blk(it.pt(), lev);
115               CellIndexSet cells = m_octree.leafCells(blk, blockData);
116               for(int i = 0; i < cells.size(); ++i)
117               {
118                 ++m_cellCount[cells[i]];
119               }
120             }
121           }
122 
123           if(m_generationState >= InOutOctreeType::INOUTOCTREE_LEAVES_COLORED)
124           {
125             switch(blockData.color())
126             {
127             case InOutBlockData::Black:
128               ++m_levelBlackBlockCount[lev];
129               break;
130             case InOutBlockData::White:
131               ++m_levelWhiteBlockCount[lev];
132               break;
133             case InOutBlockData::Gray:
134               ++m_levelGrayBlockCount[lev];
135               break;
136             case InOutBlockData::Undetermined:
137               break;
138             }
139           }
140         }
141       }
142 
143       m_totals.blocks += m_levelBlocks[lev];
144       m_totals.leaves += m_levelLeaves[lev];
145       m_totals.leavesWithVert += m_levelLeavesWithVert[lev];
146       m_totals.cellRefCount += m_levelCellRefCount[lev];
147       m_totals.whiteBlocks += m_levelWhiteBlockCount[lev];
148       m_totals.blackBlocks += m_levelBlackBlockCount[lev];
149       m_totals.grayBlocks += m_levelGrayBlockCount[lev];
150     }
151   }
152 
153   /// Generates a string summarizing information about the leaves and blocks of the octree
blockDataStats() const154   std::string blockDataStats() const
155   {
156     std::stringstream sstr;
157 
158     for(int lev = 0; lev < m_octree.m_levels.size(); ++lev)
159     {
160       if(m_levelBlocks[lev] > 0)
161       {
162         sstr << fmt::format(
163           "\t Level {} has {} blocks -- {} internal; {} leaves ({}% w/ vert);",
164           lev,
165           m_levelBlocks[lev],
166           m_levelBlocks[lev] - m_levelLeaves[lev],
167           m_levelLeaves[lev],
168           integerPercentage(m_levelLeavesWithVert[lev], m_levelLeaves[lev]));
169 
170         if(m_generationState >= InOutOctreeType::INOUTOCTREE_LEAVES_COLORED)
171         {
172           sstr << fmt::format(
173             " Leaf counts: {} Black, {} White, {} Gray w/ {} cell refs.",
174             m_levelBlackBlockCount[lev],
175             m_levelWhiteBlockCount[lev],
176             m_levelGrayBlockCount[lev],
177             m_levelCellRefCount[lev]);
178         }
179         //sstr <<"Hash load factor: "
180         //     << this->m_leavesLevelMap[ lev ].load_factor()
181         //     << " -- max lf: " << this->m_leavesLevelMap[ lev
182         // ].max_load_factor();
183         sstr << "\n";
184       }
185     }
186 
187     return sstr.str();
188   }
189 
190   /// Generates a string summarizing information about the mesh elements indexed by the octree
meshDataStats() const191   std::string meshDataStats() const
192   {
193     std::stringstream sstr;
194 
195     double meshNumCells = m_octree.m_meshWrapper.numMeshCells();
196 
197     sstr << fmt::format(
198       "  Mesh has {} vertices."
199       "\n  Octree has {} blocks; {} internal; {} leaves ({}% w/ vert); ",
200       meshNumCells,
201       m_totals.blocks,
202       m_totals.blocks - m_totals.leaves,
203       m_totals.leaves,
204       integerPercentage(m_totals.leavesWithVert, m_totals.leaves));
205 
206     if(m_generationState >= InOutOctreeType::INOUTOCTREE_ELEMENTS_INSERTED)
207     {
208       sstr << fmt::format(
209         " \n\t There were {} cell references "
210         " (avg. {} refs per cell).",
211         m_totals.cellRefCount,
212         (m_totals.cellRefCount / meshNumCells));
213     }
214 
215     return sstr.str();
216   }
217 
cellCountHistogram() const218   std::string cellCountHistogram() const
219   {
220     std::stringstream sstr;
221 
222     // Generate and output a histogram of the bucket counts on a lg-scale
223     LogHistogram cellCountHist;  // Create histogram of edge lengths (log scale)
224     LogRangeMap cellCountRange;
225 
226     int numCells = m_octree.m_meshWrapper.numMeshCells();
227 
228     for(int i = 0; i < numCells; ++i)
229     {
230       LengthType count(m_cellCount[i]);
231       int expBase2;
232       std::frexp(m_cellCount[i], &expBase2);
233       cellCountHist[expBase2]++;
234       cellCountRange[expBase2].addPoint(count);
235     }
236 
237     std::stringstream cellCountStr;
238     cellCountStr << "\tCell index count "
239                  << "(lg-arithmic bins for number of references per cell):";
240     for(auto it = cellCountHist.begin(); it != cellCountHist.end(); ++it)
241     {
242       cellCountStr << fmt::format("\n\t exp: {}\t count: {}\tRange: {}",
243                                   it->first,
244                                   it->second,
245                                   cellCountRange[it->first]);
246     }
247 
248     return cellCountStr.str();
249   }
250 
vertexCardinalityHistogram() const251   std::string vertexCardinalityHistogram() const
252   {
253     std::stringstream sstr;
254 
255     using CellVertIndices = typename MeshWrapper<DIM>::CellVertIndices;
256 
257     // Generate and output histogram of VT relation
258     CardinalityVCMap cardVC(&m_octree.m_meshWrapper.vertexSet());
259 
260     int numCells = m_octree.m_meshWrapper.numMeshCells();
261     for(int i = 0; i < numCells; ++i)
262     {
263       CellVertIndices cvRel = m_octree.m_meshWrapper.cellVertexIndices(i);
264       for(int j = 0; j < cvRel.size(); ++j)
265       {
266         cardVC[cvRel[j]]++;
267       }
268     }
269 
270     using LinHistogram = std::map<int, int>;
271     LinHistogram vtCardHist;
272     int numVerts = m_octree.m_meshWrapper.numMeshVertices();
273     for(int i = 0; i < numVerts; ++i)
274     {
275       LengthType count(cardVC[i]);
276       vtCardHist[cardVC[i]]++;
277     }
278 
279     sstr << "\tCardinality VT relation histogram (linear): ";
280     for(auto it = vtCardHist.begin(); it != vtCardHist.end(); ++it)
281     {
282       sstr << fmt::format("\n\t exp: {}\t count: {}", it->first, it->second);
283     }
284 
285     return sstr.str();
286   }
287 
summaryStats() const288   std::string summaryStats() const
289   {
290     std::stringstream octreeStatsStr;
291 
292     octreeStatsStr << fmt::format(
293       "*** {} octree summary *** \n",
294       (m_generationState >= InOutOctreeType::INOUTOCTREE_ELEMENTS_INSERTED
295          ? "PM"
296          : "PR"));
297 
298     octreeStatsStr << blockDataStats() << "\n" << meshDataStats();
299 
300     if(m_generationState >= InOutOctreeType::INOUTOCTREE_LEAVES_COLORED)
301     {
302       octreeStatsStr << fmt::format("\n\tColors: {} Black, {} White, {} Gray",
303                                     m_totals.blackBlocks,
304                                     m_totals.whiteBlocks,
305                                     m_totals.grayBlocks);
306     }
307 
308     if(m_generationState >= InOutOctreeType::INOUTOCTREE_ELEMENTS_INSERTED)
309     {
310       octreeStatsStr << "\n"
311                      << cellCountHistogram() << "\n"
312                      << vertexCardinalityHistogram();
313     }
314 
315     return octreeStatsStr.str();
316   }
317 
318 private:
integerPercentage(double val,double size) const319   int integerPercentage(double val, double size) const
320   {
321     return (size > 0) ? static_cast<int>((100. * val) / size) : 0;
322   }
323 
324 private:
325   const InOutOctreeType& m_octree;
326   typename InOutOctreeType::GenerationState m_generationState;
327 
328   LeafCountMap m_levelBlocks;
329   LeafCountMap m_levelLeaves;
330   LeafCountMap m_levelLeavesWithVert;
331   LeafCountMap m_levelCellRefCount;
332 
333   LeafCountMap m_levelWhiteBlockCount;
334   LeafCountMap m_levelBlackBlockCount;
335   LeafCountMap m_levelGrayBlockCount;
336 
337   CellCountMap m_cellCount;
338 
339   Totals m_totals;
340 };
341 
342 }  // namespace detail
343 }  // namespace quest
344 }  // namespace axom
345 
346 #endif  // AXOM_QUEST_INOUT_OCTREE_STATS__HPP_
347