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
10namespace meshopt
11{
12
13static unsigned int findStripFirst(const unsigned int buffer[][3], unsigned int buffer_size, const unsigned int* valence)
14{
15 unsigned int index = 0;
16 unsigned int iv = ~0u;
17
18 for (size_t i = 0; i < buffer_size; ++i)
19 {
20 unsigned int va = valence[buffer[i][0]], vb = valence[buffer[i][1]], vc = valence[buffer[i][2]];
21 unsigned int v = (va < vb && va < vc) ? va : (vb < vc) ? vb : vc;
22
23 if (v < iv)
24 {
25 index = unsigned(i);
26 iv = v;
27 }
28 }
29
30 return index;
31}
32
33static int findStripNext(const unsigned int buffer[][3], unsigned int buffer_size, unsigned int e0, unsigned int e1)
34{
35 for (size_t i = 0; i < buffer_size; ++i)
36 {
37 unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
38
39 if (e0 == a && e1 == b)
40 return (int(i) << 2) | 2;
41 else if (e0 == b && e1 == c)
42 return (int(i) << 2) | 0;
43 else if (e0 == c && e1 == a)
44 return (int(i) << 2) | 1;
45 }
46
47 return -1;
48}
49
50} // namespace meshopt
51
52size_t meshopt_stripify(unsigned int* destination, const unsigned int* indices, size_t index_count, size_t vertex_count, unsigned int restart_index)
53{
54 assert(destination != indices);
55 assert(index_count % 3 == 0);
56
57 using namespace meshopt;
58
59 meshopt_Allocator allocator;
60
61 const size_t buffer_capacity = 8;
62
63 unsigned int buffer[buffer_capacity][3] = {};
64 unsigned int buffer_size = 0;
65
66 size_t index_offset = 0;
67
68 unsigned int strip[2] = {};
69 unsigned int parity = 0;
70
71 size_t strip_size = 0;
72
73 // compute vertex valence; this is used to prioritize starting triangle for strips
74 unsigned int* valence = allocator.allocate<unsigned int>(vertex_count);
75 memset(valence, 0, vertex_count * sizeof(unsigned int));
76
77 for (size_t i = 0; i < index_count; ++i)
78 {
79 unsigned int index = indices[i];
80 assert(index < vertex_count);
81
82 valence[index]++;
83 }
84
85 int next = -1;
86
87 while (buffer_size > 0 || index_offset < index_count)
88 {
89 assert(next < 0 || (size_t(next >> 2) < buffer_size && (next & 3) < 3));
90
91 // fill triangle buffer
92 while (buffer_size < buffer_capacity && index_offset < index_count)
93 {
94 buffer[buffer_size][0] = indices[index_offset + 0];
95 buffer[buffer_size][1] = indices[index_offset + 1];
96 buffer[buffer_size][2] = indices[index_offset + 2];
97
98 buffer_size++;
99 index_offset += 3;
100 }
101
102 assert(buffer_size > 0);
103
104 if (next >= 0)
105 {
106 unsigned int i = next >> 2;
107 unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
108 unsigned int v = buffer[i][next & 3];
109
110 // ordered removal from the buffer
111 memmove(buffer[i], buffer[i + 1], (buffer_size - i - 1) * sizeof(buffer[0]));
112 buffer_size--;
113
114 // update vertex valences for strip start heuristic
115 valence[a]--;
116 valence[b]--;
117 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 int cont = findStripNext(buffer, buffer_size, parity ? strip[1] : v, parity ? v : strip[1]);
123 int swap = cont < 0 ? findStripNext(buffer, buffer_size, parity ? v : strip[0], parity ? strip[0] : v) : -1;
124
125 if (cont < 0 && swap >= 0)
126 {
127 // [a b c] => [a b a c]
128 destination[strip_size++] = strip[0];
129 destination[strip_size++] = v;
130
131 // next strip has same winding
132 // ? a b => b a v
133 strip[1] = v;
134
135 next = swap;
136 }
137 else
138 {
139 // emit the next vertex in the strip
140 destination[strip_size++] = v;
141
142 // next strip has flipped winding
143 strip[0] = strip[1];
144 strip[1] = v;
145 parity ^= 1;
146
147 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 unsigned int i = findStripFirst(buffer, buffer_size, &valence[0]);
155 unsigned int a = buffer[i][0], b = buffer[i][1], c = buffer[i][2];
156
157 // ordered removal from the buffer
158 memmove(buffer[i], buffer[i + 1], (buffer_size - i - 1) * sizeof(buffer[0]));
159 buffer_size--;
160
161 // update vertex valences for strip start heuristic
162 valence[a]--;
163 valence[b]--;
164 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 int ea = findStripNext(buffer, buffer_size, c, b);
168 int eb = findStripNext(buffer, buffer_size, a, c);
169 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 int mine = INT_MAX;
175 mine = (ea >= 0 && mine > ea) ? ea : mine;
176 mine = (eb >= 0 && mine > eb) ? eb : mine;
177 mine = (ec >= 0 && mine > ec) ? ec : mine;
178
179 if (ea == mine)
180 {
181 // keep abc
182 next = ea;
183 }
184 else if (eb == mine)
185 {
186 // abc -> bca
187 unsigned int t = a;
188 a = b, b = c, c = t;
189
190 next = eb;
191 }
192 else if (ec == mine)
193 {
194 // abc -> cab
195 unsigned int t = c;
196 c = b, b = a, a = t;
197
198 next = ec;
199 }
200
201 if (restart_index)
202 {
203 if (strip_size)
204 destination[strip_size++] = restart_index;
205
206 destination[strip_size++] = a;
207 destination[strip_size++] = b;
208 destination[strip_size++] = c;
209
210 // new strip always starts with the same edge winding
211 strip[0] = b;
212 strip[1] = c;
213 parity = 1;
214 }
215 else
216 {
217 if (strip_size)
218 {
219 // connect last strip using degenerate triangles
220 destination[strip_size++] = strip[1];
221 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 unsigned int e0 = parity ? c : b;
227 unsigned int e1 = parity ? b : c;
228
229 destination[strip_size++] = a;
230 destination[strip_size++] = e0;
231 destination[strip_size++] = e1;
232
233 strip[0] = e0;
234 strip[1] = e1;
235 parity ^= 1;
236 }
237 }
238 }
239
240 return strip_size;
241}
242
243size_t meshopt_stripifyBound(size_t index_count)
244{
245 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 return (index_count / 3) * 5;
250}
251
252size_t meshopt_unstripify(unsigned int* destination, const unsigned int* indices, size_t index_count, unsigned int restart_index)
253{
254 assert(destination != indices);
255
256 size_t offset = 0;
257 size_t start = 0;
258
259 for (size_t i = 0; i < index_count; ++i)
260 {
261 if (restart_index && indices[i] == restart_index)
262 {
263 start = i + 1;
264 }
265 else if (i - start >= 2)
266 {
267 unsigned int a = indices[i - 2], b = indices[i - 1], c = indices[i];
268
269 // flip winding for odd triangles
270 if ((i - start) & 1)
271 {
272 unsigned int t = a;
273 a = b, b = t;
274 }
275
276 // although we use restart indices, strip swaps still produce degenerate triangles, so skip them
277 if (a != b && a != c && b != c)
278 {
279 destination[offset + 0] = a;
280 destination[offset + 1] = b;
281 destination[offset + 2] = c;
282 offset += 3;
283 }
284 }
285 }
286
287 return offset;
288}
289
290size_t meshopt_unstripifyBound(size_t index_count)
291{
292 assert(index_count == 0 || index_count >= 3);
293
294 return (index_count == 0) ? 0 : (index_count - 2) * 3;
295}
296