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.cpp347
1 files changed, 347 insertions, 0 deletions
diff --git a/thirdparty/meshoptimizer/indexgenerator.cpp b/thirdparty/meshoptimizer/indexgenerator.cpp
new file mode 100644
index 0000000000..aa4a30efa4
--- /dev/null
+++ b/thirdparty/meshoptimizer/indexgenerator.cpp
@@ -0,0 +1,347 @@
+// This file is part of meshoptimizer library; see meshoptimizer.h for version/license details
+#include "meshoptimizer.h"
+
+#include <assert.h>
+#include <string.h>
+
+namespace meshopt
+{
+
+static unsigned int hashUpdate4(unsigned int h, const unsigned char* key, size_t len)
+{
+ // MurmurHash2
+ const unsigned int m = 0x5bd1e995;
+ const int r = 24;
+
+ while (len >= 4)
+ {
+ unsigned int k = *reinterpret_cast<const unsigned int*>(key);
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h *= m;
+ h ^= k;
+
+ key += 4;
+ len -= 4;
+ }
+
+ return h;
+}
+
+struct VertexHasher
+{
+ const unsigned char* vertices;
+ size_t vertex_size;
+ size_t vertex_stride;
+
+ size_t hash(unsigned int index) const
+ {
+ return hashUpdate4(0, vertices + index * vertex_stride, vertex_size);
+ }
+
+ bool equal(unsigned int lhs, unsigned int rhs) const
+ {
+ return memcmp(vertices + lhs * vertex_stride, vertices + rhs * vertex_stride, vertex_size) == 0;
+ }
+};
+
+struct VertexStreamHasher
+{
+ const meshopt_Stream* streams;
+ size_t stream_count;
+
+ size_t hash(unsigned int index) const
+ {
+ unsigned int h = 0;
+
+ for (size_t i = 0; i < stream_count; ++i)
+ {
+ const meshopt_Stream& s = streams[i];
+ const unsigned char* data = static_cast<const unsigned char*>(s.data);
+
+ h = hashUpdate4(h, data + index * s.stride, s.size);
+ }
+
+ return h;
+ }
+
+ bool equal(unsigned int lhs, unsigned int rhs) const
+ {
+ for (size_t i = 0; i < stream_count; ++i)
+ {
+ const meshopt_Stream& s = streams[i];
+ const unsigned char* data = static_cast<const unsigned char*>(s.data);
+
+ if (memcmp(data + lhs * s.stride, data + rhs * s.stride, s.size) != 0)
+ return false;
+ }
+
+ return true;
+ }
+};
+
+static size_t hashBuckets(size_t count)
+{
+ size_t buckets = 1;
+ while (buckets < count)
+ buckets *= 2;
+
+ return buckets;
+}
+
+template <typename T, typename Hash>
+static T* hashLookup(T* table, size_t buckets, const Hash& hash, const T& key, const T& empty)
+{
+ assert(buckets > 0);
+ assert((buckets & (buckets - 1)) == 0);
+
+ size_t hashmod = buckets - 1;
+ size_t bucket = hash.hash(key) & hashmod;
+
+ for (size_t probe = 0; probe <= hashmod; ++probe)
+ {
+ T& item = table[bucket];
+
+ if (item == empty)
+ return &item;
+
+ if (hash.equal(item, key))
+ return &item;
+
+ // hash collision, quadratic probing
+ bucket = (bucket + probe + 1) & hashmod;
+ }
+
+ assert(false && "Hash table is full"); // unreachable
+ return 0;
+}
+
+} // 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)
+{
+ using namespace meshopt;
+
+ assert(indices || index_count == vertex_count);
+ assert(index_count % 3 == 0);
+ assert(vertex_size > 0 && vertex_size <= 256);
+
+ meshopt_Allocator allocator;
+
+ memset(destination, -1, vertex_count * sizeof(unsigned int));
+
+ VertexHasher hasher = {static_cast<const unsigned char*>(vertices), vertex_size, vertex_size};
+
+ size_t table_size = hashBuckets(vertex_count);
+ unsigned int* table = allocator.allocate<unsigned int>(table_size);
+ memset(table, -1, table_size * sizeof(unsigned int));
+
+ unsigned int next_vertex = 0;
+
+ for (size_t i = 0; i < index_count; ++i)
+ {
+ unsigned int index = indices ? indices[i] : unsigned(i);
+ assert(index < vertex_count);
+
+ if (destination[index] == ~0u)
+ {
+ unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
+
+ if (*entry == ~0u)
+ {
+ *entry = index;
+
+ destination[index] = next_vertex++;
+ }
+ else
+ {
+ assert(destination[*entry] != ~0u);
+
+ destination[index] = destination[*entry];
+ }
+ }
+ }
+
+ assert(next_vertex <= vertex_count);
+
+ return next_vertex;
+}
+
+size_t meshopt_generateVertexRemapMulti(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, const struct meshopt_Stream* streams, size_t stream_count)
+{
+ using namespace meshopt;
+
+ assert(indices || index_count == vertex_count);
+ assert(index_count % 3 == 0);
+ assert(stream_count > 0 && stream_count <= 16);
+
+ for (size_t i = 0; i < stream_count; ++i)
+ {
+ assert(streams[i].size > 0 && streams[i].size <= 256);
+ assert(streams[i].size <= streams[i].stride);
+ }
+
+ meshopt_Allocator allocator;
+
+ memset(destination, -1, vertex_count * sizeof(unsigned int));
+
+ VertexStreamHasher hasher = {streams, stream_count};
+
+ size_t table_size = hashBuckets(vertex_count);
+ unsigned int* table = allocator.allocate<unsigned int>(table_size);
+ memset(table, -1, table_size * sizeof(unsigned int));
+
+ unsigned int next_vertex = 0;
+
+ for (size_t i = 0; i < index_count; ++i)
+ {
+ unsigned int index = indices ? indices[i] : unsigned(i);
+ assert(index < vertex_count);
+
+ if (destination[index] == ~0u)
+ {
+ unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
+
+ if (*entry == ~0u)
+ {
+ *entry = index;
+
+ destination[index] = next_vertex++;
+ }
+ else
+ {
+ assert(destination[*entry] != ~0u);
+
+ destination[index] = destination[*entry];
+ }
+ }
+ }
+
+ assert(next_vertex <= vertex_count);
+
+ return next_vertex;
+}
+
+void meshopt_remapVertexBuffer(void* destination, const void* vertices, size_t vertex_count, size_t vertex_size, const unsigned int* remap)
+{
+ assert(vertex_size > 0 && vertex_size <= 256);
+
+ meshopt_Allocator allocator;
+
+ // support in-place remap
+ if (destination == vertices)
+ {
+ unsigned char* vertices_copy = allocator.allocate<unsigned char>(vertex_count * vertex_size);
+ memcpy(vertices_copy, vertices, vertex_count * vertex_size);
+ vertices = vertices_copy;
+ }
+
+ for (size_t i = 0; i < vertex_count; ++i)
+ {
+ if (remap[i] != ~0u)
+ {
+ assert(remap[i] < vertex_count);
+
+ memcpy(static_cast<unsigned char*>(destination) + remap[i] * vertex_size, static_cast<const unsigned char*>(vertices) + i * vertex_size, vertex_size);
+ }
+ }
+}
+
+void meshopt_remapIndexBuffer(unsigned int* destination, const unsigned int* indices, size_t index_count, const unsigned int* remap)
+{
+ assert(index_count % 3 == 0);
+
+ for (size_t i = 0; i < index_count; ++i)
+ {
+ unsigned int index = indices ? indices[i] : unsigned(i);
+ assert(remap[index] != ~0u);
+
+ destination[i] = remap[index];
+ }
+}
+
+void meshopt_generateShadowIndexBuffer(unsigned int* destination, const unsigned int* indices, size_t index_count, const void* vertices, size_t vertex_count, size_t vertex_size, size_t vertex_stride)
+{
+ using namespace meshopt;
+
+ assert(indices);
+ assert(index_count % 3 == 0);
+ assert(vertex_size > 0 && vertex_size <= 256);
+ assert(vertex_size <= vertex_stride);
+
+ meshopt_Allocator allocator;
+
+ unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
+ memset(remap, -1, vertex_count * sizeof(unsigned int));
+
+ VertexHasher hasher = {static_cast<const unsigned char*>(vertices), vertex_size, vertex_stride};
+
+ size_t table_size = hashBuckets(vertex_count);
+ unsigned int* table = allocator.allocate<unsigned int>(table_size);
+ memset(table, -1, table_size * sizeof(unsigned int));
+
+ for (size_t i = 0; i < index_count; ++i)
+ {
+ unsigned int index = indices[i];
+ assert(index < vertex_count);
+
+ if (remap[index] == ~0u)
+ {
+ unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
+
+ if (*entry == ~0u)
+ *entry = index;
+
+ remap[index] = *entry;
+ }
+
+ destination[i] = remap[index];
+ }
+}
+
+void meshopt_generateShadowIndexBufferMulti(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, const struct meshopt_Stream* streams, size_t stream_count)
+{
+ using namespace meshopt;
+
+ assert(indices);
+ assert(index_count % 3 == 0);
+ assert(stream_count > 0 && stream_count <= 16);
+
+ for (size_t i = 0; i < stream_count; ++i)
+ {
+ assert(streams[i].size > 0 && streams[i].size <= 256);
+ assert(streams[i].size <= streams[i].stride);
+ }
+
+ meshopt_Allocator allocator;
+
+ unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
+ memset(remap, -1, vertex_count * sizeof(unsigned int));
+
+ VertexStreamHasher hasher = {streams, stream_count};
+
+ size_t table_size = hashBuckets(vertex_count);
+ unsigned int* table = allocator.allocate<unsigned int>(table_size);
+ memset(table, -1, table_size * sizeof(unsigned int));
+
+ for (size_t i = 0; i < index_count; ++i)
+ {
+ unsigned int index = indices[i];
+ assert(index < vertex_count);
+
+ if (remap[index] == ~0u)
+ {
+ unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
+
+ if (*entry == ~0u)
+ *entry = index;
+
+ remap[index] = *entry;
+ }
+
+ destination[i] = remap[index];
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-17 04:29:07 +0000