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_VertexCacheStatistics meshopt_analyzeVertexCache(const unsigned int* indices, size_t index_count, size_t vertex_count, unsigned int cache_size, unsigned int warp_size, unsigned int primgroup_size)
8{
9 assert(index_count % 3 == 0);
10 assert(cache_size >= 3);
11 assert(warp_size == 0 || warp_size >= 3);
12
13 meshopt_Allocator allocator;
14
15 meshopt_VertexCacheStatistics result = {};
16
17 unsigned int warp_offset = 0;
18 unsigned int primgroup_offset = 0;
19
20 unsigned int* cache_timestamps = allocator.allocate<unsigned int>(vertex_count);
21 memset(cache_timestamps, 0, vertex_count * sizeof(unsigned int));
22
23 unsigned int timestamp = cache_size + 1;
24
25 for (size_t i = 0; i < index_count; i += 3)
26 {
27 unsigned int a = indices[i + 0], b = indices[i + 1], c = indices[i + 2];
28 assert(a < vertex_count && b < vertex_count && c < vertex_count);
29
30 bool ac = (timestamp - cache_timestamps[a]) > cache_size;
31 bool bc = (timestamp - cache_timestamps[b]) > cache_size;
32 bool cc = (timestamp - cache_timestamps[c]) > cache_size;
33
34 // flush cache if triangle doesn't fit into warp or into the primitive buffer
35 if ((primgroup_size && primgroup_offset == primgroup_size) || (warp_size && warp_offset + ac + bc + cc > warp_size))
36 {
37 result.warps_executed += warp_offset > 0;
38
39 warp_offset = 0;
40 primgroup_offset = 0;
41
42 // reset cache
43 timestamp += cache_size + 1;
44 }
45
46 // update cache and add vertices to warp
47 for (int j = 0; j < 3; ++j)
48 {
49 unsigned int index = indices[i + j];
50
51 if (timestamp - cache_timestamps[index] > cache_size)
52 {
53 cache_timestamps[index] = timestamp++;
54 result.vertices_transformed++;
55 warp_offset++;
56 }
57 }
58
59 primgroup_offset++;
60 }
61
62 size_t unique_vertex_count = 0;
63
64 for (size_t i = 0; i < vertex_count; ++i)
65 unique_vertex_count += cache_timestamps[i] > 0;
66
67 result.warps_executed += warp_offset > 0;
68
69 result.acmr = index_count == 0 ? 0 : float(result.vertices_transformed) / float(index_count / 3);
70 result.atvr = unique_vertex_count == 0 ? 0 : float(result.vertices_transformed) / float(unique_vertex_count);
71
72 return result;
73}
74