source: OniSplit/Motoko/Stripify.cs@ 1186

Last change on this file since 1186 was 1114, checked in by iritscen, 5 years ago

Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
File size: 10.6 KB
Line 
1using System;
2using System.Collections.Generic;
3
4namespace Oni.Motoko
5{
6 internal class Stripify
7 {
8 private const int BeginStrip = int.MinValue;
9 private int[] tlist;
10 private int[] adjacency;
11 private int[] degree;
12 private List<int> strips;
13 private bool[] used;
14
15 public static int[] FromTriangleList(int[] triangleList)
16 {
17 var triStrips = new Stripify(triangleList);
18 return triStrips.Run();
19 }
20
21 public static int[] ToTriangleList(int[] triangleStrips)
22 {
23 int triangleCount = 0;
24
25 for (int i = 0; i < triangleStrips.Length; i++)
26 {
27 triangleCount++;
28
29 if (triangleStrips[i] < 0)
30 triangleCount -= 2;
31 }
32
33 var triangles = new int[triangleCount * 3];
34 int pos = 0;
35 var face = new int[3];
36 int order = 0;
37
38 for (int i = 0; i < triangleStrips.Length; i++)
39 {
40 if (triangleStrips[i] < 0)
41 {
42 face[0] = triangleStrips[i] & int.MaxValue;
43 i++;
44 face[1] = triangleStrips[i];
45 i++;
46 order = 0;
47 }
48 else
49 {
50 face[order] = face[2];
51 order = (order + 1) % 2;
52 }
53
54 face[2] = triangleStrips[i];
55
56 Array.Copy(face, 0, triangles, pos, 3);
57 pos += 3;
58 }
59
60 return triangles;
61 }
62
63 private Stripify(int[] triangleList)
64 {
65 tlist = triangleList;
66 }
67
68 private int[] Run()
69 {
70 strips = new List<int>();
71
72 GenerateAdjacency();
73
74 while (GenerateStrip())
75 ;
76
77 //
78 // Generate 1 triangle long strips for all triangles that were not included
79 // in triangle strips
80 //
81
82 for (int i = 0; i < degree.Length; i++)
83 {
84 if (!used[i])
85 {
86 int j = i * 3;
87
88 strips.Add(tlist[j + 0] | BeginStrip);
89 strips.Add(tlist[j + 1]);
90 strips.Add(tlist[j + 2]);
91
92 used[i] = true;
93 }
94 }
95
96 return strips.ToArray();
97 }
98
99 private bool GenerateStrip()
100 {
101 int current = -1;
102
103 int minDegree = 4;
104 int minAdjacentDegree = 4;
105
106 //
107 // Find a triangle to start with. The triangle with the lowest degree
108 // is picked as a start triangle. If multiple triangles have the same
109 // degree then the adjacent triangles are checked for lowest degree.
110 //
111
112 for (int t = 0; t < degree.Length; t++)
113 {
114 if (used[t] || degree[t] == 0)
115 continue;
116
117 if (degree[t] < minDegree)
118 {
119 minDegree = degree[t];
120 minAdjacentDegree = 4;
121 current = t;
122 }
123 else if (degree[t] == minDegree)
124 {
125 //
126 // We have 2 candidates for a start triangle with the same degree.
127 // Check their neighbours for lowest degree to decide which candidate to use.
128 //
129
130 for (int k = 0; k < 3; k++)
131 {
132 int a = adjacency[t * 3 + k];
133
134 if (a == -1 || used[a] || degree[a] == 0)
135 continue;
136
137 if (degree[a] < minAdjacentDegree)
138 {
139 minAdjacentDegree = degree[a];
140 current = t;
141 }
142 }
143 }
144 }
145
146 if (current == -1)
147 {
148 //
149 // A start triangle cannot be found. Either there are no more unused triangles left
150 // or all remaining triangles have degree = 0.
151 //
152
153 return false;
154 }
155
156 UseTriangle(current);
157
158 //
159 // Find a triangle adjacent to the start triangle so we can decide
160 // on a vertex order for the start triangle. If there are multiple
161 // adjacent triangles the one with lowest degree is used.
162 //
163
164 int next = -1;
165 int edge = 0;
166
167 minDegree = 4;
168
169 for (int e = 0; e < 3; e++)
170 {
171 int a = adjacency[current * 3 + e];
172
173 if (a == -1 || used[a])
174 continue;
175
176 //
177 // NOTE: Don't check for degree = 0. The previous UseTriangle(current) can make
178 // adjacent triangles have a 0 degree. It works because all we are interested in
179 // is which adjacent triangle has the lowest degree.
180 //
181
182 if (degree[a] < minDegree)
183 {
184 minDegree = degree[a];
185 next = a;
186 edge = e;
187 }
188 }
189
190 //
191 // Begin a new triangle strip
192 //
193
194 var triangle = new int[3];
195
196 triangle[0] = tlist[(current * 3) + (edge + 2) % 3];
197 triangle[1] = tlist[(current * 3) + (edge + 0) % 3];
198 triangle[2] = tlist[(current * 3) + (edge + 1) % 3];
199
200 strips.Add(triangle[0] | BeginStrip);
201 strips.Add(triangle[1]);
202 strips.Add(triangle[2]);
203
204 //
205 // Continue the triangle strip as long as possible
206 //
207
208 int order = 0;
209
210 while (next != -1)
211 {
212 UseTriangle(next);
213
214 triangle[0] = triangle[1 + order];
215
216 //
217 // Search an edge in triangle "next" that matches the "exit" edge of triangle "current"
218 //
219
220 for (int v = 0; v < 3; v++)
221 {
222 int t = next * 3;
223
224 if (tlist[t + v] == triangle[(2 + order) % 3] && tlist[t + (v + 1) % 3] == triangle[order])
225 {
226 edge = (v + 2 - order) % 3;
227 triangle[1 + order] = tlist[t + (v + 2) % 3];
228 break;
229 }
230 }
231
232 strips.Add(triangle[1 + order]);
233
234 //
235 // Replace "current" with "next" and find a "next" triangle that is adjacent with "current"
236 //
237
238 current = next;
239 next = adjacency[current * 3 + edge];
240
241 if (next == -1 || used[next])
242 break;
243
244 UseTriangle(next);
245
246 //
247 // Alternate vertex ordering
248 //
249
250 order = (order + 1) % 2;
251 }
252
253 return true;
254 }
255
256 private void UseTriangle(int t)
257 {
258 degree[t] = 0;
259 used[t] = true;
260
261 //
262 // Decrease the degree of all adjacent triangles by 1.
263 //
264
265 for (int e = 0; e < 3; e++)
266 {
267 int a = adjacency[t * 3 + e];
268
269 if (a != -1 && degree[a] > 0)
270 degree[a]--;
271 }
272 }
273
274 #region private struct Edge
275
276 private struct Edge : IEquatable<Edge>
277 {
278 public readonly int V1;
279 public readonly int V2;
280
281 public Edge(int V1, int V2)
282 {
283 this.V1 = V1;
284 this.V2 = V2;
285 }
286
287 public static bool operator ==(Edge e1, Edge e2) => e1.V1 == e2.V1 && e1.V2 == e2.V2;
288 public static bool operator !=(Edge e1, Edge e2) => e1.V1 != e2.V1 || e1.V2 != e2.V2;
289 public bool Equals(Edge edge) => V1 == edge.V1 && V2 == edge.V2;
290 public override bool Equals(object obj) => obj is Edge && Equals((Edge)obj);
291 public override int GetHashCode() => V1 ^ V2;
292 }
293
294 #endregion
295
296 private void GenerateAdjacency()
297 {
298 adjacency = new int[tlist.Length];
299 degree = new int[tlist.Length / 3];
300 used = new bool[tlist.Length / 3];
301
302 for (int i = 0; i < adjacency.Length; i++)
303 adjacency[i] = -1;
304
305 //
306 // Store all the edges in a dictionary for easier lookup
307 //
308
309 var edges = new Dictionary<Edge, int>();
310
311 for (int t = 0; t < tlist.Length; t += 3)
312 {
313 for (int v = 0; v < 3; v++)
314 {
315 var edge = new Edge(tlist[t + v], tlist[t + (v + 1) % 3]);
316
317 edges[edge] = t / 3;
318 }
319 }
320
321 //
322 // Fill the adjacency array
323 //
324
325 for (int t = 0; t < tlist.Length; t += 3)
326 {
327 for (int e = 0; e < 3; e++)
328 {
329 //
330 // We already have an adjacent triangle for this edge.
331 // This means that there are 3 or more triangles that have a
332 // common edge but this is not very common and we'll just
333 // ignore it.
334 //
335
336 if (adjacency[t + e] != -1)
337 continue;
338
339 //
340 // Notice that the edge must be reversed compared to the
341 // order they were stored in the dictionary to preserve
342 // trinangle vertex ordering.
343 //
344
345 var edge = new Edge(tlist[t + (e + 1) % 3], tlist[t + e]);
346
347 int k;
348
349 //
350 // Note the k != t / 3 check to avoid making degenerate triangles
351 // adjacent to themselfs.
352 //
353
354 if (edges.TryGetValue(edge, out k) && k != t / 3)
355 {
356 adjacency[t + e] = k;
357 degree[t / 3]++;
358 }
359 }
360 }
361 }
362 }
363}
Note: See TracBrowser for help on using the repository browser.