zeux / meshoptimizer
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 <limits.h>
6
#include <string.h>
7

8
// This work is based on:
9
// Francine Evans, Steven Skiena and Amitabh Varshney. Optimizing Triangle Strips for Fast Rendering. 1996
10
namespace meshopt
11
{
12

13 3
static unsigned int findStripFirst(const unsigned int buffer[][3], unsigned int buffer_size, const unsigned int* valence)
14
{
15 3
	unsigned int index = 0;
16 3
	unsigned int iv = ~0u;
17

18 3
	for (size_t i = 0; i < buffer_size; ++i)
19
	{
20 3
		unsigned int va = valence[buffer[i][0]], vb = valence[buffer[i][1]], vc = valence[buffer[i][2]];
21 3
		unsigned int v = (va < vb && va < vc) ? va : (vb < vc) ? vb : vc;
22

23 3
		if (v < iv)
24
		{
25 3
			index = unsigned(i);
26 3
			iv = v;
27
		}
28
	}
29

30 3
	return index;
31
}
32

33 3
static int findStripNext(const unsigned int buffer[][3], unsigned int buffer_size, unsigned int e0, unsigned int e1)
34
{
35 3
	for (size_t i = 0; i < buffer_size; ++i)
36
	{
37 3
		unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
38

39 3
		if (e0 == a && e1 == b)
40 3
			return (int(i) << 2) | 2;
41 3
		else if (e0 == b && e1 == c)
42 3
			return (int(i) << 2) | 0;
43 3
		else if (e0 == c && e1 == a)
44 3
			return (int(i) << 2) | 1;
45
	}
46

47 3
	return -1;
48
}
49

50
} // namespace meshopt
51

52 3
size_t meshopt_stripify(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, unsigned int restart_index)
53
{
54 3
	assert(destination != indices);
55 3
	assert(index_count % 3 == 0);
56

57
	using namespace meshopt;
58

59 3
	meshopt_Allocator allocator;
60

61 3
	const size_t buffer_capacity = 8;
62

63 3
	unsigned int buffer[buffer_capacity][3] = {};
64 3
	unsigned int buffer_size = 0;
65

66 3
	size_t index_offset = 0;
67

68 3
	unsigned int strip[2] = {};
69 3
	unsigned int parity = 0;
70

71 3
	size_t strip_size = 0;
72

73
	// compute vertex valence; this is used to prioritize starting triangle for strips
74 3
	unsigned int* valence = allocator.allocate<unsigned int>(vertex_count);
75 3
	memset(valence, 0, vertex_count * sizeof(unsigned int));
76

77 3
	for (size_t i = 0; i < index_count; ++i)
78
	{
79 3
		unsigned int index = indices[i];
80 3
		assert(index < vertex_count);
81

82 3
		valence[index]++;
83
	}
84

85 3
	int next = -1;
86

87 3
	while (buffer_size > 0 || index_offset < index_count)
88
	{
89 3
		assert(next < 0 || (size_t(next >> 2) < buffer_size && (next & 3) < 3));
90

91
		// fill triangle buffer
92 3
		while (buffer_size < buffer_capacity && index_offset < index_count)
93
		{
94 3
			buffer[buffer_size][0] = indices[index_offset + 0];
95 3
			buffer[buffer_size][1] = indices[index_offset + 1];
96 3
			buffer[buffer_size][2] = indices[index_offset + 2];
97

98 3
			buffer_size++;
99 3
			index_offset += 3;
100
		}
101

102 3
		assert(buffer_size > 0);
103

104 3
		if (next >= 0)
105
		{
106 3
			unsigned int i = next >> 2;
107 3
			unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
108 3
			unsigned int v = buffer[i][next & 3];
109

110
			// ordered removal from the buffer
111 3
			memmove(buffer[i], buffer[i + 1], (buffer_size - i - 1) * sizeof(buffer[0]));
112 3
			buffer_size--;
113

114
			// update vertex valences for strip start heuristic
115 3
			valence[a]--;
116 3
			valence[b]--;
117 3
			valence[c]--;
118

119
			// find next triangle (note that edge order flips on every iteration)
120
			// in some cases we need to perform a swap to pick a different outgoing triangle edge
121
			// for [a b c], the default strip edge is [b c], but we might want to use [a c]
122 3
			int cont = findStripNext(buffer, buffer_size, parity ? strip[1] : v, parity ? v : strip[1]);
123 3
			int swap = cont < 0 ? findStripNext(buffer, buffer_size, parity ? v : strip[0], parity ? strip[0] : v) : -1;
124

125 3
			if (cont < 0 && swap >= 0)
126
			{
127
				// [a b c] => [a b a c]
128 3
				destination[strip_size++] = strip[0];
129 3
				destination[strip_size++] = v;
130

131
				// next strip has same winding
132
				// ? a b => b a v
133 3
				strip[1] = v;
134

135 3
				next = swap;
136
			}
137
			else
138
			{
139
				// emit the next vertex in the strip
140 3
				destination[strip_size++] = v;
141

142
				// next strip has flipped winding
143 3
				strip[0] = strip[1];
144 3
				strip[1] = v;
145 3
				parity ^= 1;
146

147 3
				next = cont;
148
			}
149
		}
150
		else
151
		{
152
			// if we didn't find anything, we need to find the next new triangle
153
			// we use a heuristic to maximize the strip length
154 3
			unsigned int i = findStripFirst(buffer, buffer_size, &valence[0]);
155 3
			unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
156

157
			// ordered removal from the buffer
158 3
			memmove(buffer[i], buffer[i + 1], (buffer_size - i - 1) * sizeof(buffer[0]));
159 3
			buffer_size--;
160

161
			// update vertex valences for strip start heuristic
162 3
			valence[a]--;
163 3
			valence[b]--;
164 3
			valence[c]--;
165

166
			// we need to pre-rotate the triangle so that we will find a match in the existing buffer on the next iteration
167 3
			int ea = findStripNext(buffer, buffer_size, c, b);
168 3
			int eb = findStripNext(buffer, buffer_size, a, c);
169 3
			int ec = findStripNext(buffer, buffer_size, b, a);
170

171
			// in some cases we can have several matching edges; since we can pick any edge, we pick the one with the smallest
172
			// triangle index in the buffer. this reduces the effect of stripification on ACMR and additionally - for unclear
173
			// reasons - slightly improves the stripification efficiency
174 3
			int mine = INT_MAX;
175 3
			mine = (ea >= 0 && mine > ea) ? ea : mine;
176 3
			mine = (eb >= 0 && mine > eb) ? eb : mine;
177 3
			mine = (ec >= 0 && mine > ec) ? ec : mine;
178

179 3
			if (ea == mine)
180
			{
181
				// keep abc
182 3
				next = ea;
183
			}
184 3
			else if (eb == mine)
185
			{
186
				// abc -> bca
187 3
				unsigned int t = a;
188 3
				a = b, b = c, c = t;
189

190 3
				next = eb;
191
			}
192 3
			else if (ec == mine)
193
			{
194
				// abc -> cab
195 3
				unsigned int t = c;
196 3
				c = b, b = a, a = t;
197

198 3
				next = ec;
199
			}
200

201 3
			if (restart_index)
202
			{
203 3
				if (strip_size)
204 3
					destination[strip_size++] = restart_index;
205

206 3
				destination[strip_size++] = a;
207 3
				destination[strip_size++] = b;
208 3
				destination[strip_size++] = c;
209

210
				// new strip always starts with the same edge winding
211 3
				strip[0] = b;
212 3
				strip[1] = c;
213 3
				parity = 1;
214
			}
215
			else
216
			{
217 3
				if (strip_size)
218
				{
219
					// connect last strip using degenerate triangles
220 3
					destination[strip_size++] = strip[1];
221 3
					destination[strip_size++] = a;
222
				}
223

224
				// note that we may need to flip the emitted triangle based on parity
225
				// we always end up with outgoing edge "cb" in the end
226 3
				unsigned int e0 = parity ? c : b;
227 3
				unsigned int e1 = parity ? b : c;
228

229 3
				destination[strip_size++] = a;
230 3
				destination[strip_size++] = e0;
231 3
				destination[strip_size++] = e1;
232

233 3
				strip[0] = e0;
234 3
				strip[1] = e1;
235 3
				parity ^= 1;
236
			}
237
		}
238
	}
239

240 3
	return strip_size;
241
}
242

243 3
size_t meshopt_stripifyBound(size_t index_count)
244
{
245 3
	assert(index_count % 3 == 0);
246

247
	// worst case without restarts is 2 degenerate indices and 3 indices per triangle
248
	// worst case with restarts is 1 restart index and 3 indices per triangle
249 3
	return (index_count / 3) * 5;
250
}
251

252 3
size_t meshopt_unstripify(unsigned int* destination, const unsigned int* indices, size_t index_count, unsigned int restart_index)
253
{
254 3
	assert(destination != indices);
255

256 3
	size_t offset = 0;
257 3
	size_t start = 0;
258

259 3
	for (size_t i = 0; i < index_count; ++i)
260
	{
261 3
		if (restart_index && indices[i] == restart_index)
262
		{
263 3
			start = i + 1;
264
		}
265 3
		else if (i - start >= 2)
266
		{
267 3
			unsigned int a = indices[i - 2], b = indices[i - 1], c = indices[i];
268

269
			// flip winding for odd triangles
270 3
			if ((i - start) & 1)
271
			{
272 3
				unsigned int t = a;
273 3
				a = b, b = t;
274
			}
275

276
			// although we use restart indices, strip swaps still produce degenerate triangles, so skip them
277 3
			if (a != b && a != c && b != c)
278
			{
279 3
				destination[offset + 0] = a;
280 3
				destination[offset + 1] = b;
281 3
				destination[offset + 2] = c;
282 3
				offset += 3;
283
			}
284
		}
285
	}
286

287 3
	return offset;
288
}
289

290 3
size_t meshopt_unstripifyBound(size_t index_count)
291
{
292 3
	assert(index_count == 0 || index_count >= 3);
293

294 3
	return (index_count == 0) ? 0 : (index_count - 2) * 3;
295
}

Read our documentation on viewing source code .

Loading