// This file is part of meshoptimizer library; see meshoptimizer.h for version/license details #include "meshoptimizer.h" #include <assert.h> #include <string.h> // This work is based on: // Tom Forsyth. Linear-Speed Vertex Cache Optimisation. 2006 // Pedro Sander, Diego Nehab and Joshua Barczak. Fast Triangle Reordering for Vertex Locality and Reduced Overdraw. 2007 namespace meshopt { const size_t kCacheSizeMax = 16; const size_t kValenceMax = 8; struct VertexScoreTable { float cache[1 + kCacheSizeMax]; float live[1 + kValenceMax]; }; // Tuned to minimize the ACMR of a GPU that has a cache profile similar to NVidia and AMD static const VertexScoreTable kVertexScoreTable = { {0.f, 0.779f, 0.791f, 0.789f, 0.981f, 0.843f, 0.726f, 0.847f, 0.882f, 0.867f, 0.799f, 0.642f, 0.613f, 0.600f, 0.568f, 0.372f, 0.234f}, {0.f, 0.995f, 0.713f, 0.450f, 0.404f, 0.059f, 0.005f, 0.147f, 0.006f}, }; // Tuned to minimize the encoded index buffer size static const VertexScoreTable kVertexScoreTableStrip = { {0.f, 1.000f, 1.000f, 1.000f, 0.453f, 0.561f, 0.490f, 0.459f, 0.179f, 0.526f, 0.000f, 0.227f, 0.184f, 0.490f, 0.112f, 0.050f, 0.131f}, {0.f, 0.956f, 0.786f, 0.577f, 0.558f, 0.618f, 0.549f, 0.499f, 0.489f}, }; struct TriangleAdjacency { unsigned int* counts; unsigned int* offsets; unsigned int* data; }; static void buildTriangleAdjacency(TriangleAdjacency& adjacency, const unsigned int* indices, size_t index_count, size_t vertex_count, meshopt_Allocator& allocator) { size_t face_count = index_count / 3; // allocate arrays adjacency.counts = allocator.allocate<unsigned int>(vertex_count); adjacency.offsets = allocator.allocate<unsigned int>(vertex_count); adjacency.data = allocator.allocate<unsigned int>(index_count); // fill triangle counts memset(adjacency.counts, 0, vertex_count * sizeof(unsigned int)); for (size_t i = 0; i < index_count; ++i) { assert(indices[i] < vertex_count); adjacency.counts[indices[i]]++; } // fill offset table unsigned int offset = 0; for (size_t i = 0; i < vertex_count; ++i) { adjacency.offsets[i] = offset; offset += adjacency.counts[i]; } assert(offset == index_count); // fill triangle data for (size_t i = 0; i < face_count; ++i) { unsigned int a = indices[i * 3 + 0], b = indices[i * 3 + 1], c = indices[i * 3 + 2]; adjacency.data[adjacency.offsets[a]++] = unsigned(i); adjacency.data[adjacency.offsets[b]++] = unsigned(i); adjacency.data[adjacency.offsets[c]++] = unsigned(i); } // fix offsets that have been disturbed by the previous pass for (size_t i = 0; i < vertex_count; ++i) { assert(adjacency.offsets[i] >= adjacency.counts[i]); adjacency.offsets[i] -= adjacency.counts[i]; } } static unsigned int getNextVertexDeadEnd(const unsigned int* dead_end, unsigned int& dead_end_top, unsigned int& input_cursor, const unsigned int* live_triangles, size_t vertex_count) { // check dead-end stack while (dead_end_top) { unsigned int vertex = dead_end[--dead_end_top]; if (live_triangles[vertex] > 0) return vertex; } // input order while (input_cursor < vertex_count) { if (live_triangles[input_cursor] > 0) return input_cursor; ++input_cursor; } return ~0u; } static unsigned int getNextVertexNeighbour(const unsigned int* next_candidates_begin, const unsigned int* next_candidates_end, const unsigned int* live_triangles, const unsigned int* cache_timestamps, unsigned int timestamp, unsigned int cache_size) { unsigned int best_candidate = ~0u; int best_priority = -1; for (const unsigned int* next_candidate = next_candidates_begin; next_candidate != next_candidates_end; ++next_candidate) { unsigned int vertex = *next_candidate; // otherwise we don't need to process it if (live_triangles[vertex] > 0) { int priority = 0; // will it be in cache after fanning? if (2 * live_triangles[vertex] + timestamp - cache_timestamps[vertex] <= cache_size) { priority = timestamp - cache_timestamps[vertex]; // position in cache } if (priority > best_priority) { best_candidate = vertex; best_priority = priority; } } } return best_candidate; } static float vertexScore(const VertexScoreTable* table, int cache_position, unsigned int live_triangles) { assert(cache_position >= -1 && cache_position < int(kCacheSizeMax)); unsigned int live_triangles_clamped = live_triangles < kValenceMax ? live_triangles : kValenceMax; return table->cache[1 + cache_position] + table->live[live_triangles_clamped]; } static unsigned int getNextTriangleDeadEnd(unsigned int& input_cursor, const unsigned char* emitted_flags, size_t face_count) { // input order while (input_cursor < face_count) { if (!emitted_flags[input_cursor]) return input_cursor; ++input_cursor; } return ~0u; } } // namespace meshopt void meshopt_optimizeVertexCacheTable(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, const meshopt::VertexScoreTable* table) { using namespace meshopt; assert(index_count % 3 == 0); meshopt_Allocator allocator; // guard for empty meshes if (index_count == 0 || vertex_count == 0) return; // support in-place optimization if (destination == indices) { unsigned int* indices_copy = allocator.allocate<unsigned int>(index_count); memcpy(indices_copy, indices, index_count * sizeof(unsigned int)); indices = indices_copy; } unsigned int cache_size = 16; assert(cache_size <= kCacheSizeMax); size_t face_count = index_count / 3; // build adjacency information TriangleAdjacency adjacency = {}; buildTriangleAdjacency(adjacency, indices, index_count, vertex_count, allocator); // live triangle counts unsigned int* live_triangles = allocator.allocate<unsigned int>(vertex_count); memcpy(live_triangles, adjacency.counts, vertex_count * sizeof(unsigned int)); // emitted flags unsigned char* emitted_flags = allocator.allocate<unsigned char>(face_count); memset(emitted_flags, 0, face_count); // compute initial vertex scores float* vertex_scores = allocator.allocate<float>(vertex_count); for (size_t i = 0; i < vertex_count; ++i) vertex_scores[i] = vertexScore(table, -1, live_triangles[i]); // compute triangle scores float* triangle_scores = allocator.allocate<float>(face_count); for (size_t i = 0; i < face_count; ++i) { unsigned int a = indices[i * 3 + 0]; unsigned int b = indices[i * 3 + 1]; unsigned int c = indices[i * 3 + 2]; triangle_scores[i] = vertex_scores[a] + vertex_scores[b] + vertex_scores[c]; } unsigned int cache_holder[2 * (kCacheSizeMax + 3)]; unsigned int* cache = cache_holder; unsigned int* cache_new = cache_holder + kCacheSizeMax + 3; size_t cache_count = 0; unsigned int current_triangle = 0; unsigned int input_cursor = 1; unsigned int output_triangle = 0; while (current_triangle != ~0u) { assert(output_triangle < face_count); unsigned int a = indices[current_triangle * 3 + 0]; unsigned int b = indices[current_triangle * 3 + 1]; unsigned int c = indices[current_triangle * 3 + 2]; // output indices destination[output_triangle * 3 + 0] = a; destination[output_triangle * 3 + 1] = b; destination[output_triangle * 3 + 2] = c; output_triangle++; // update emitted flags emitted_flags[current_triangle] = true; triangle_scores[current_triangle] = 0; // new triangle size_t cache_write = 0; cache_new[cache_write++] = a; cache_new[cache_write++] = b; cache_new[cache_write++] = c; // old triangles for (size_t i = 0; i < cache_count; ++i) { unsigned int index = cache[i]; if (index != a && index != b && index != c) { cache_new[cache_write++] = index; } } unsigned int* cache_temp = cache; cache = cache_new, cache_new = cache_temp; cache_count = cache_write > cache_size ? cache_size : cache_write; // update live triangle counts live_triangles[a]--; live_triangles[b]--; live_triangles[c]--; // remove emitted triangle from adjacency data // this makes sure that we spend less time traversing these lists on subsequent iterations for (size_t k = 0; k < 3; ++k) { unsigned int index = indices[current_triangle * 3 + k]; unsigned int* neighbours = &adjacency.data[0] + adjacency.offsets[index]; size_t neighbours_size = adjacency.counts[index]; for (size_t i = 0; i < neighbours_size; ++i) { unsigned int tri = neighbours[i]; if (tri == current_triangle) { neighbours[i] = neighbours[neighbours_size - 1]; adjacency.counts[index]--; break; } } } unsigned int best_triangle = ~0u; float best_score = 0; // update cache positions, vertex scores and triangle scores, and find next best triangle for (size_t i = 0; i < cache_write; ++i) { unsigned int index = cache[i]; int cache_position = i >= cache_size ? -1 : int(i); // update vertex score float score = vertexScore(table, cache_position, live_triangles[index]); float score_diff = score - vertex_scores[index]; vertex_scores[index] = score; // update scores of vertex triangles const unsigned int* neighbours_begin = &adjacency.data[0] + adjacency.offsets[index]; const unsigned int* neighbours_end = neighbours_begin + adjacency.counts[index]; for (const unsigned int* it = neighbours_begin; it != neighbours_end; ++it) { unsigned int tri = *it; assert(!emitted_flags[tri]); float tri_score = triangle_scores[tri] + score_diff; assert(tri_score > 0); if (best_score < tri_score) { best_triangle = tri; best_score = tri_score; } triangle_scores[tri] = tri_score; } } // step through input triangles in order if we hit a dead-end current_triangle = best_triangle; if (current_triangle == ~0u) { current_triangle = getNextTriangleDeadEnd(input_cursor, &emitted_flags[0], face_count); } } assert(input_cursor == face_count); assert(output_triangle == face_count); } void meshopt_optimizeVertexCache(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count) { meshopt_optimizeVertexCacheTable(destination, indices, index_count, vertex_count, &meshopt::kVertexScoreTable); } void meshopt_optimizeVertexCacheStrip(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count) { meshopt_optimizeVertexCacheTable(destination, indices, index_count, vertex_count, &meshopt::kVertexScoreTableStrip); } void meshopt_optimizeVertexCacheFifo(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, unsigned int cache_size) { using namespace meshopt; assert(index_count % 3 == 0); assert(cache_size >= 3); meshopt_Allocator allocator; // guard for empty meshes if (index_count == 0 || vertex_count == 0) return; // support in-place optimization if (destination == indices) { unsigned int* indices_copy = allocator.allocate<unsigned int>(index_count); memcpy(indices_copy, indices, index_count * sizeof(unsigned int)); indices = indices_copy; } size_t face_count = index_count / 3; // build adjacency information TriangleAdjacency adjacency = {}; buildTriangleAdjacency(adjacency, indices, index_count, vertex_count, allocator); // live triangle counts unsigned int* live_triangles = allocator.allocate<unsigned int>(vertex_count); memcpy(live_triangles, adjacency.counts, vertex_count * sizeof(unsigned int)); // cache time stamps unsigned int* cache_timestamps = allocator.allocate<unsigned int>(vertex_count); memset(cache_timestamps, 0, vertex_count * sizeof(unsigned int)); // dead-end stack unsigned int* dead_end = allocator.allocate<unsigned int>(index_count); unsigned int dead_end_top = 0; // emitted flags unsigned char* emitted_flags = allocator.allocate<unsigned char>(face_count); memset(emitted_flags, 0, face_count); unsigned int current_vertex = 0; unsigned int timestamp = cache_size + 1; unsigned int input_cursor = 1; // vertex to restart from in case of dead-end unsigned int output_triangle = 0; while (current_vertex != ~0u) { const unsigned int* next_candidates_begin = &dead_end[0] + dead_end_top; // emit all vertex neighbours const unsigned int* neighbours_begin = &adjacency.data[0] + adjacency.offsets[current_vertex]; const unsigned int* neighbours_end = neighbours_begin + adjacency.counts[current_vertex]; for (const unsigned int* it = neighbours_begin; it != neighbours_end; ++it) { unsigned int triangle = *it; if (!emitted_flags[triangle]) { unsigned int a = indices[triangle * 3 + 0], b = indices[triangle * 3 + 1], c = indices[triangle * 3 + 2]; // output indices destination[output_triangle * 3 + 0] = a; destination[output_triangle * 3 + 1] = b; destination[output_triangle * 3 + 2] = c; output_triangle++; // update dead-end stack dead_end[dead_end_top + 0] = a; dead_end[dead_end_top + 1] = b; dead_end[dead_end_top + 2] = c; dead_end_top += 3; // update live triangle counts live_triangles[a]--; live_triangles[b]--; live_triangles[c]--; // update cache info // if vertex is not in cache, put it in cache if (timestamp - cache_timestamps[a] > cache_size) cache_timestamps[a] = timestamp++; if (timestamp - cache_timestamps[b] > cache_size) cache_timestamps[b] = timestamp++; if (timestamp - cache_timestamps[c] > cache_size) cache_timestamps[c] = timestamp++; // update emitted flags emitted_flags[triangle] = true; } } // next candidates are the ones we pushed to dead-end stack just now const unsigned int* next_candidates_end = &dead_end[0] + dead_end_top; // get next vertex current_vertex = getNextVertexNeighbour(next_candidates_begin, next_candidates_end, &live_triangles[0], &cache_timestamps[0], timestamp, cache_size); if (current_vertex == ~0u) { current_vertex = getNextVertexDeadEnd(&dead_end[0], dead_end_top, input_cursor, &live_triangles[0], vertex_count); } } assert(output_triangle == face_count); }