1// This file is part of meshoptimizer library; see meshoptimizer.h for version/license details
2#include "meshoptimizer.h"
3
4#include <assert.h>
5#include <string.h>
6
7meshopt_VertexFetchStatistics meshopt_analyzeVertexFetch(const unsigned int* indices, size_t index_count, size_t vertex_count, size_t vertex_size)
8{
9 assert(index_count % 3 == 0);
10 assert(vertex_size > 0 && vertex_size <= 256);
11
12 meshopt_Allocator allocator;
13
14 meshopt_VertexFetchStatistics result = {};
15
16 unsigned char* vertex_visited = allocator.allocate<unsigned char>(vertex_count);
17 memset(vertex_visited, 0, vertex_count);
18
19 const size_t kCacheLine = 64;
20 const size_t kCacheSize = 128 * 1024;
21
22 // simple direct mapped cache; on typical mesh data this is close to 4-way cache, and this model is a gross approximation anyway
23 size_t cache[kCacheSize / kCacheLine] = {};
24
25 for (size_t i = 0; i < index_count; ++i)
26 {
27 unsigned int index = indices[i];
28 assert(index < vertex_count);
29
30 vertex_visited[index] = 1;
31
32 size_t start_address = index * vertex_size;
33 size_t end_address = start_address + vertex_size;
34
35 size_t start_tag = start_address / kCacheLine;
36 size_t end_tag = (end_address + kCacheLine - 1) / kCacheLine;
37
38 assert(start_tag < end_tag);
39
40 for (size_t tag = start_tag; tag < end_tag; ++tag)
41 {
42 size_t line = tag % (sizeof(cache) / sizeof(cache[0]));
43
44 // we store +1 since cache is filled with 0 by default
45 result.bytes_fetched += (cache[line] != tag + 1) * kCacheLine;
46 cache[line] = tag + 1;
47 }
48 }
49
50 size_t unique_vertex_count = 0;
51
52 for (size_t i = 0; i < vertex_count; ++i)
53 unique_vertex_count += vertex_visited[i];
54
55 result.overfetch = unique_vertex_count == 0 ? 0 : float(result.bytes_fetched) / float(unique_vertex_count * vertex_size);
56
57 return result;
58}
59