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
7 namespace meshopt
8 {
9
hashUpdate4(unsigned int h,const unsigned char * key,size_t len)10 static unsigned int hashUpdate4(unsigned int h, const unsigned char* key, size_t len)
11 {
12 // MurmurHash2
13 const unsigned int m = 0x5bd1e995;
14 const int r = 24;
15
16 while (len >= 4)
17 {
18 unsigned int k = *reinterpret_cast<const unsigned int*>(key);
19
20 k *= m;
21 k ^= k >> r;
22 k *= m;
23
24 h *= m;
25 h ^= k;
26
27 key += 4;
28 len -= 4;
29 }
30
31 return h;
32 }
33
34 struct VertexHasher
35 {
36 const unsigned char* vertices;
37 size_t vertex_size;
38 size_t vertex_stride;
39
hashmeshopt::VertexHasher40 size_t hash(unsigned int index) const
41 {
42 return hashUpdate4(0, vertices + index * vertex_stride, vertex_size);
43 }
44
equalmeshopt::VertexHasher45 bool equal(unsigned int lhs, unsigned int rhs) const
46 {
47 return memcmp(vertices + lhs * vertex_stride, vertices + rhs * vertex_stride, vertex_size) == 0;
48 }
49 };
50
51 struct VertexStreamHasher
52 {
53 const meshopt_Stream* streams;
54 size_t stream_count;
55
hashmeshopt::VertexStreamHasher56 size_t hash(unsigned int index) const
57 {
58 unsigned int h = 0;
59
60 for (size_t i = 0; i < stream_count; ++i)
61 {
62 const meshopt_Stream& s = streams[i];
63 const unsigned char* data = static_cast<const unsigned char*>(s.data);
64
65 h = hashUpdate4(h, data + index * s.stride, s.size);
66 }
67
68 return h;
69 }
70
equalmeshopt::VertexStreamHasher71 bool equal(unsigned int lhs, unsigned int rhs) const
72 {
73 for (size_t i = 0; i < stream_count; ++i)
74 {
75 const meshopt_Stream& s = streams[i];
76 const unsigned char* data = static_cast<const unsigned char*>(s.data);
77
78 if (memcmp(data + lhs * s.stride, data + rhs * s.stride, s.size) != 0)
79 return false;
80 }
81
82 return true;
83 }
84 };
85
hashBuckets(size_t count)86 static size_t hashBuckets(size_t count)
87 {
88 size_t buckets = 1;
89 while (buckets < count)
90 buckets *= 2;
91
92 return buckets;
93 }
94
95 template <typename T, typename Hash>
hashLookup(T * table,size_t buckets,const Hash & hash,const T & key,const T & empty)96 static T* hashLookup(T* table, size_t buckets, const Hash& hash, const T& key, const T& empty)
97 {
98 assert(buckets > 0);
99 assert((buckets & (buckets - 1)) == 0);
100
101 size_t hashmod = buckets - 1;
102 size_t bucket = hash.hash(key) & hashmod;
103
104 for (size_t probe = 0; probe <= hashmod; ++probe)
105 {
106 T& item = table[bucket];
107
108 if (item == empty)
109 return &item;
110
111 if (hash.equal(item, key))
112 return &item;
113
114 // hash collision, quadratic probing
115 bucket = (bucket + probe + 1) & hashmod;
116 }
117
118 assert(false && "Hash table is full"); // unreachable
119 return 0;
120 }
121
122 } // namespace meshopt
123
meshopt_generateVertexRemap(unsigned int * destination,const unsigned int * indices,size_t index_count,const void * vertices,size_t vertex_count,size_t vertex_size)124 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)
125 {
126 using namespace meshopt;
127
128 assert(indices || index_count == vertex_count);
129 assert(index_count % 3 == 0);
130 assert(vertex_size > 0 && vertex_size <= 256);
131
132 meshopt_Allocator allocator;
133
134 memset(destination, -1, vertex_count * sizeof(unsigned int));
135
136 VertexHasher hasher = {static_cast<const unsigned char*>(vertices), vertex_size, vertex_size};
137
138 size_t table_size = hashBuckets(vertex_count);
139 unsigned int* table = allocator.allocate<unsigned int>(table_size);
140 memset(table, -1, table_size * sizeof(unsigned int));
141
142 unsigned int next_vertex = 0;
143
144 for (size_t i = 0; i < index_count; ++i)
145 {
146 unsigned int index = indices ? indices[i] : unsigned(i);
147 assert(index < vertex_count);
148
149 if (destination[index] == ~0u)
150 {
151 unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
152
153 if (*entry == ~0u)
154 {
155 *entry = index;
156
157 destination[index] = next_vertex++;
158 }
159 else
160 {
161 assert(destination[*entry] != ~0u);
162
163 destination[index] = destination[*entry];
164 }
165 }
166 }
167
168 assert(next_vertex <= vertex_count);
169
170 return next_vertex;
171 }
172
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)173 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)
174 {
175 using namespace meshopt;
176
177 assert(indices || index_count == vertex_count);
178 assert(index_count % 3 == 0);
179 assert(stream_count > 0 && stream_count <= 16);
180
181 for (size_t i = 0; i < stream_count; ++i)
182 {
183 assert(streams[i].size > 0 && streams[i].size <= 256);
184 assert(streams[i].size <= streams[i].stride);
185 }
186
187 meshopt_Allocator allocator;
188
189 memset(destination, -1, vertex_count * sizeof(unsigned int));
190
191 VertexStreamHasher hasher = {streams, stream_count};
192
193 size_t table_size = hashBuckets(vertex_count);
194 unsigned int* table = allocator.allocate<unsigned int>(table_size);
195 memset(table, -1, table_size * sizeof(unsigned int));
196
197 unsigned int next_vertex = 0;
198
199 for (size_t i = 0; i < index_count; ++i)
200 {
201 unsigned int index = indices ? indices[i] : unsigned(i);
202 assert(index < vertex_count);
203
204 if (destination[index] == ~0u)
205 {
206 unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
207
208 if (*entry == ~0u)
209 {
210 *entry = index;
211
212 destination[index] = next_vertex++;
213 }
214 else
215 {
216 assert(destination[*entry] != ~0u);
217
218 destination[index] = destination[*entry];
219 }
220 }
221 }
222
223 assert(next_vertex <= vertex_count);
224
225 return next_vertex;
226 }
227
meshopt_remapVertexBuffer(void * destination,const void * vertices,size_t vertex_count,size_t vertex_size,const unsigned int * remap)228 void meshopt_remapVertexBuffer(void* destination, const void* vertices, size_t vertex_count, size_t vertex_size, const unsigned int* remap)
229 {
230 assert(vertex_size > 0 && vertex_size <= 256);
231
232 meshopt_Allocator allocator;
233
234 // support in-place remap
235 if (destination == vertices)
236 {
237 unsigned char* vertices_copy = allocator.allocate<unsigned char>(vertex_count * vertex_size);
238 memcpy(vertices_copy, vertices, vertex_count * vertex_size);
239 vertices = vertices_copy;
240 }
241
242 for (size_t i = 0; i < vertex_count; ++i)
243 {
244 if (remap[i] != ~0u)
245 {
246 assert(remap[i] < vertex_count);
247
248 memcpy(static_cast<unsigned char*>(destination) + remap[i] * vertex_size, static_cast<const unsigned char*>(vertices) + i * vertex_size, vertex_size);
249 }
250 }
251 }
252
meshopt_remapIndexBuffer(unsigned int * destination,const unsigned int * indices,size_t index_count,const unsigned int * remap)253 void meshopt_remapIndexBuffer(unsigned int* destination, const unsigned int* indices, size_t index_count, const unsigned int* remap)
254 {
255 assert(index_count % 3 == 0);
256
257 for (size_t i = 0; i < index_count; ++i)
258 {
259 unsigned int index = indices ? indices[i] : unsigned(i);
260 assert(remap[index] != ~0u);
261
262 destination[i] = remap[index];
263 }
264 }
265
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)266 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)
267 {
268 using namespace meshopt;
269
270 assert(indices);
271 assert(index_count % 3 == 0);
272 assert(vertex_size > 0 && vertex_size <= 256);
273 assert(vertex_size <= vertex_stride);
274
275 meshopt_Allocator allocator;
276
277 unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
278 memset(remap, -1, vertex_count * sizeof(unsigned int));
279
280 VertexHasher hasher = {static_cast<const unsigned char*>(vertices), vertex_size, vertex_stride};
281
282 size_t table_size = hashBuckets(vertex_count);
283 unsigned int* table = allocator.allocate<unsigned int>(table_size);
284 memset(table, -1, table_size * sizeof(unsigned int));
285
286 for (size_t i = 0; i < index_count; ++i)
287 {
288 unsigned int index = indices[i];
289 assert(index < vertex_count);
290
291 if (remap[index] == ~0u)
292 {
293 unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
294
295 if (*entry == ~0u)
296 *entry = index;
297
298 remap[index] = *entry;
299 }
300
301 destination[i] = remap[index];
302 }
303 }
304
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)305 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)
306 {
307 using namespace meshopt;
308
309 assert(indices);
310 assert(index_count % 3 == 0);
311 assert(stream_count > 0 && stream_count <= 16);
312
313 for (size_t i = 0; i < stream_count; ++i)
314 {
315 assert(streams[i].size > 0 && streams[i].size <= 256);
316 assert(streams[i].size <= streams[i].stride);
317 }
318
319 meshopt_Allocator allocator;
320
321 unsigned int* remap = allocator.allocate<unsigned int>(vertex_count);
322 memset(remap, -1, vertex_count * sizeof(unsigned int));
323
324 VertexStreamHasher hasher = {streams, stream_count};
325
326 size_t table_size = hashBuckets(vertex_count);
327 unsigned int* table = allocator.allocate<unsigned int>(table_size);
328 memset(table, -1, table_size * sizeof(unsigned int));
329
330 for (size_t i = 0; i < index_count; ++i)
331 {
332 unsigned int index = indices[i];
333 assert(index < vertex_count);
334
335 if (remap[index] == ~0u)
336 {
337 unsigned int* entry = hashLookup(table, table_size, hasher, index, ~0u);
338
339 if (*entry == ~0u)
340 *entry = index;
341
342 remap[index] = *entry;
343 }
344
345 destination[i] = remap[index];
346 }
347 }
348