summaryrefslogtreecommitdiff
path: root/thirdparty/meshoptimizer/indexgenerator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/meshoptimizer/indexgenerator.cpp')
-rw-r--r--thirdparty/meshoptimizer/indexgenerator.cpp206
1 files changed, 205 insertions, 1 deletions
diff --git a/thirdparty/meshoptimizer/indexgenerator.cpp b/thirdparty/meshoptimizer/indexgenerator.cpp
index aa4a30efa4..f60db0dc4f 100644
--- a/thirdparty/meshoptimizer/indexgenerator.cpp
+++ b/thirdparty/meshoptimizer/indexgenerator.cpp
@@ -4,6 +4,8 @@
#include <assert.h>
#include <string.h>
+// This work is based on:
+// John McDonald, Mark Kilgard. Crack-Free Point-Normal Triangles using Adjacent Edge Normals. 2010
namespace meshopt
{
@@ -83,10 +85,49 @@ struct VertexStreamHasher
}
};
+struct EdgeHasher
+{
+ const unsigned int* remap;
+
+ size_t hash(unsigned long long edge) const
+ {
+ unsigned int e0 = unsigned(edge >> 32);
+ unsigned int e1 = unsigned(edge);
+
+ unsigned int h1 = remap[e0];
+ unsigned int h2 = remap[e1];
+
+ const unsigned int m = 0x5bd1e995;
+
+ // MurmurHash64B finalizer
+ h1 ^= h2 >> 18;
+ h1 *= m;
+ h2 ^= h1 >> 22;
+ h2 *= m;
+ h1 ^= h2 >> 17;
+ h1 *= m;
+ h2 ^= h1 >> 19;
+ h2 *= m;
+
+ return h2;
+ }
+
+ bool equal(unsigned long long lhs, unsigned long long rhs) const
+ {
+ unsigned int l0 = unsigned(lhs >> 32);
+ unsigned int l1 = unsigned(lhs);
+
+ unsigned int r0 = unsigned(rhs >> 32);
+ unsigned int r1 = unsigned(rhs);
+
+ return remap[l0] == remap[r0] && remap[l1] == remap[r1];
+ }
+};
+
static size_t hashBuckets(size_t count)
{
size_t buckets = 1;
- while (buckets < count)
+ while (buckets < count + count / 4)
buckets *= 2;
return buckets;
@@ -119,6 +160,26 @@ static T* hashLookup(T* table, size_t buckets, const Hash& hash, const T& key, c
return 0;
}
+static void buildPositionRemap(unsigned int* remap, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride, meshopt_Allocator& allocator)
+{
+ VertexHasher vertex_hasher = {reinterpret_cast<const unsigned char*>(vertex_positions), 3 * sizeof(float), vertex_positions_stride};
+
+ size_t vertex_table_size = hashBuckets(vertex_count);
+ unsigned int* vertex_table = allocator.allocate<unsigned int>(vertex_table_size);
+ memset(vertex_table, -1, vertex_table_size * sizeof(unsigned int));
+
+ for (size_t i = 0; i < vertex_count; ++i)
+ {
+ unsigned int index = unsigned(i);
+ unsigned int* entry = hashLookup(vertex_table, vertex_table_size, vertex_hasher, index, ~0u);
+
+ if (*entry == ~0u)
+ *entry = index;
+
+ remap[index] = *entry;
+ }
+}
+
} // namespace meshopt
size_t meshopt_generateVertexRemap(unsigned int* destination, const unsigned int* indices, size_t index_count, const void* vertices, size_t vertex_count, size_t vertex_size)
@@ -345,3 +406,146 @@ void meshopt_generateShadowIndexBufferMulti(unsigned int* destination, const uns
destination[i] = remap[index];
}
}
+
+void meshopt_generateAdjacencyIndexBuffer(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride)
+{
+ using namespace meshopt;
+
+ assert(index_count % 3 == 0);
+ assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256);
+ assert(vertex_positions_stride % sizeof(float) == 0);
+
+ meshopt_Allocator allocator;
+
+ static const int next[4] = {1, 2, 0, 1};
+
+ // build position remap: for each vertex, which other (canonical) vertex does it map to?
+ unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
+ buildPositionRemap(remap, vertex_positions, vertex_count, vertex_positions_stride, allocator);
+
+ // build edge set; this stores all triangle edges but we can look these up by any other wedge
+ EdgeHasher edge_hasher = {remap};
+
+ size_t edge_table_size = hashBuckets(index_count);
+ unsigned long long* edge_table = allocator.allocate<unsigned long long>(edge_table_size);
+ unsigned int* edge_vertex_table = allocator.allocate<unsigned int>(edge_table_size);
+
+ memset(edge_table, -1, edge_table_size * sizeof(unsigned long long));
+ memset(edge_vertex_table, -1, edge_table_size * sizeof(unsigned int));
+
+ for (size_t i = 0; i < index_count; i += 3)
+ {
+ for (int e = 0; e < 3; ++e)
+ {
+ unsigned int i0 = indices[i + e];
+ unsigned int i1 = indices[i + next[e]];
+ unsigned int i2 = indices[i + next[e + 1]];
+ assert(i0 < vertex_count && i1 < vertex_count && i2 < vertex_count);
+
+ unsigned long long edge = ((unsigned long long)i0 << 32) | i1;
+ unsigned long long* entry = hashLookup(edge_table, edge_table_size, edge_hasher, edge, ~0ull);
+
+ if (*entry == ~0ull)
+ {
+ *entry = edge;
+
+ // store vertex opposite to the edge
+ edge_vertex_table[entry - edge_table] = i2;
+ }
+ }
+ }
+
+ // build resulting index buffer: 6 indices for each input triangle
+ for (size_t i = 0; i < index_count; i += 3)
+ {
+ unsigned int patch[6];
+
+ for (int e = 0; e < 3; ++e)
+ {
+ unsigned int i0 = indices[i + e];
+ unsigned int i1 = indices[i + next[e]];
+ assert(i0 < vertex_count && i1 < vertex_count);
+
+ // note: this refers to the opposite edge!
+ unsigned long long edge = ((unsigned long long)i1 << 32) | i0;
+ unsigned long long* oppe = hashLookup(edge_table, edge_table_size, edge_hasher, edge, ~0ull);
+
+ patch[e * 2 + 0] = i0;
+ patch[e * 2 + 1] = (*oppe == ~0ull) ? i0 : edge_vertex_table[oppe - edge_table];
+ }
+
+ memcpy(destination + i * 2, patch, sizeof(patch));
+ }
+}
+
+void meshopt_generateTessellationIndexBuffer(unsigned int* destination, const unsigned int* indices, size_t index_count, const float* vertex_positions, size_t vertex_count, size_t vertex_positions_stride)
+{
+ using namespace meshopt;
+
+ assert(index_count % 3 == 0);
+ assert(vertex_positions_stride > 0 && vertex_positions_stride <= 256);
+ assert(vertex_positions_stride % sizeof(float) == 0);
+
+ meshopt_Allocator allocator;
+
+ static const int next[3] = {1, 2, 0};
+
+ // build position remap: for each vertex, which other (canonical) vertex does it map to?
+ unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
+ buildPositionRemap(remap, vertex_positions, vertex_count, vertex_positions_stride, allocator);
+
+ // build edge set; this stores all triangle edges but we can look these up by any other wedge
+ EdgeHasher edge_hasher = {remap};
+
+ size_t edge_table_size = hashBuckets(index_count);
+ unsigned long long* edge_table = allocator.allocate<unsigned long long>(edge_table_size);
+ memset(edge_table, -1, edge_table_size * sizeof(unsigned long long));
+
+ for (size_t i = 0; i < index_count; i += 3)
+ {
+ for (int e = 0; e < 3; ++e)
+ {
+ unsigned int i0 = indices[i + e];
+ unsigned int i1 = indices[i + next[e]];
+ assert(i0 < vertex_count && i1 < vertex_count);
+
+ unsigned long long edge = ((unsigned long long)i0 << 32) | i1;
+ unsigned long long* entry = hashLookup(edge_table, edge_table_size, edge_hasher, edge, ~0ull);
+
+ if (*entry == ~0ull)
+ *entry = edge;
+ }
+ }
+
+ // build resulting index buffer: 12 indices for each input triangle
+ for (size_t i = 0; i < index_count; i += 3)
+ {
+ unsigned int patch[12];
+
+ for (int e = 0; e < 3; ++e)
+ {
+ unsigned int i0 = indices[i + e];
+ unsigned int i1 = indices[i + next[e]];
+ assert(i0 < vertex_count && i1 < vertex_count);
+
+ // note: this refers to the opposite edge!
+ unsigned long long edge = ((unsigned long long)i1 << 32) | i0;
+ unsigned long long oppe = *hashLookup(edge_table, edge_table_size, edge_hasher, edge, ~0ull);
+
+ // use the same edge if opposite edge doesn't exist (border)
+ oppe = (oppe == ~0ull) ? edge : oppe;
+
+ // triangle index (0, 1, 2)
+ patch[e] = i0;
+
+ // opposite edge (3, 4; 5, 6; 7, 8)
+ patch[3 + e * 2 + 0] = unsigned(oppe);
+ patch[3 + e * 2 + 1] = unsigned(oppe >> 32);
+
+ // dominant vertex (9, 10, 11)
+ patch[9 + e] = remap[i0];
+ }
+
+ memcpy(destination + i * 4, patch, sizeof(patch));
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 19:29:41 +0000