OniSplit/Motoko/Stripify.cs

using System;
using System.Collections.Generic;

namespace Oni.Motoko
{
    internal class Stripify
    {
        private const int BeginStrip = int.MinValue;
        private int[] tlist;
        private int[] adjacency;
        private int[] degree;
        private List<int> strips;
        private bool[] used;

        public static int[] FromTriangleList(int[] triangleList)
        {
            var triStrips = new Stripify(triangleList);
            return triStrips.Run();
        }

        public static int[] ToTriangleList(int[] triangleStrips)
        {
            int triangleCount = 0;

            for (int i = 0; i < triangleStrips.Length; i++)
            {
                triangleCount++;

                if (triangleStrips[i] < 0)
                    triangleCount -= 2;
            }

            var triangles = new int[triangleCount * 3];
            int pos = 0;
            var face = new int[3];
            int order = 0;

            for (int i = 0; i < triangleStrips.Length; i++)
            {
                if (triangleStrips[i] < 0)
                {
                    face[0] = triangleStrips[i] & int.MaxValue;
                    i++;
                    face[1] = triangleStrips[i];
                    i++;
                    order = 0;
                }
                else
                {
                    face[order] = face[2];
                    order = (order + 1) % 2;
                }

                face[2] = triangleStrips[i];

                Array.Copy(face, 0, triangles, pos, 3);
                pos += 3;
            }

            return triangles;
        }

        private Stripify(int[] triangleList)
        {
            tlist = triangleList;
        }

        private int[] Run()
        {
            strips = new List<int>();

            GenerateAdjacency();

            while (GenerateStrip())
                ;

            //
            // Generate 1 triangle long strips for all triangles that were not included
            // in triangle strips
            //

            for (int i = 0; i < degree.Length; i++)
            {
                if (!used[i])
                {
                    int j = i * 3;

                    strips.Add(tlist[j + 0] | BeginStrip);
                    strips.Add(tlist[j + 1]);
                    strips.Add(tlist[j + 2]);

                    used[i] = true;
                }
            }

            return strips.ToArray();
        }

        private bool GenerateStrip()
        {
            int current = -1;

            int minDegree = 4;
            int minAdjacentDegree = 4;

            //
            // Find a triangle to start with. The triangle with the lowest degree
            // is picked as a start triangle. If multiple triangles have the same 
            // degree then the adjacent triangles are checked for lowest degree.
            //

            for (int t = 0; t < degree.Length; t++)
            {
                if (used[t] || degree[t] == 0)
                    continue;

                if (degree[t] < minDegree)
                {
                    minDegree = degree[t];
                    minAdjacentDegree = 4;
                    current = t;
                }
                else if (degree[t] == minDegree)
                {
                    //
                    // We have 2 candidates for a start triangle with the same degree.
                    // Check their neighbours for lowest degree to decide which candidate to use.
                    //

                    for (int k = 0; k < 3; k++)
                    {
                        int a = adjacency[t * 3 + k];

                        if (a == -1 || used[a] || degree[a] == 0)
                            continue;

                        if (degree[a] < minAdjacentDegree)
                        {
                            minAdjacentDegree = degree[a];
                            current = t;
                        }
                    }
                }
            }

            if (current == -1)
            {
                //
                // A start triangle cannot be found. Either there are no more unused triangles left
                // or all remaining triangles have degree = 0.
                //

                return false;
            }

            UseTriangle(current);

            //
            // Find a triangle adjacent to the start triangle so we can decide
            // on a vertex order for the start triangle. If there are multiple
            // adjacent triangles the one with lowest degree is used.
            //

            int next = -1;
            int edge = 0;

            minDegree = 4;

            for (int e = 0; e < 3; e++)
            {
                int a = adjacency[current * 3 + e];

                if (a == -1 || used[a])
                    continue;

                //
                // NOTE: Don't check for degree = 0. The previous UseTriangle(current) can make 
                // adjacent triangles have a 0 degree. It works because all we are interested in
                // is which adjacent triangle has the lowest degree.
                //

                if (degree[a] < minDegree)
                {
                    minDegree = degree[a];
                    next = a;
                    edge = e;
                }
            }

            //
            // Begin a new triangle strip
            //

            var triangle = new int[3];

            triangle[0] = tlist[(current * 3) + (edge + 2) % 3];
            triangle[1] = tlist[(current * 3) + (edge + 0) % 3];
            triangle[2] = tlist[(current * 3) + (edge + 1) % 3];

            strips.Add(triangle[0] | BeginStrip);
            strips.Add(triangle[1]);
            strips.Add(triangle[2]);

            //
            // Continue the triangle strip as long as possible
            //

            int order = 0;

            while (next != -1)
            {
                UseTriangle(next);

                triangle[0] = triangle[1 + order];

                //
                // Search an edge in triangle "next" that matches the "exit" edge of triangle "current"
                //

                for (int v = 0; v < 3; v++)
                {
                    int t = next * 3;

                    if (tlist[t + v] == triangle[(2 + order) % 3] && tlist[t + (v + 1) % 3] == triangle[order])
                    {
                        edge = (v + 2 - order) % 3;
                        triangle[1 + order] = tlist[t + (v + 2) % 3];
                        break;
                    }
                }

                strips.Add(triangle[1 + order]);

                //
                // Replace "current" with "next" and find a "next" triangle that is adjacent with "current"
                //

                current = next;
                next = adjacency[current * 3 + edge];

                if (next == -1 || used[next])
                    break;

                UseTriangle(next);

                //
                // Alternate vertex ordering
                //

                order = (order + 1) % 2;
            }

            return true;
        }

        private void UseTriangle(int t)
        {
            degree[t] = 0;
            used[t] = true;

            //
            // Decrease the degree of all adjacent triangles by 1.
            //

            for (int e = 0; e < 3; e++)
            {
                int a = adjacency[t * 3 + e];

                if (a != -1 && degree[a] > 0)
                    degree[a]--;
            }
        }

        #region private struct Edge

        private struct Edge : IEquatable<Edge>
        {
            public readonly int V1;
            public readonly int V2;

            public Edge(int V1, int V2)
            {
                this.V1 = V1;
                this.V2 = V2;
            }

            public static bool operator ==(Edge e1, Edge e2) => e1.V1 == e2.V1 && e1.V2 == e2.V2;
            public static bool operator !=(Edge e1, Edge e2) => e1.V1 != e2.V1 || e1.V2 != e2.V2;
            public bool Equals(Edge edge) => V1 == edge.V1 && V2 == edge.V2;
            public override bool Equals(object obj) => obj is Edge && Equals((Edge)obj);
            public override int GetHashCode() => V1 ^ V2;
        }

        #endregion

        private void GenerateAdjacency()
        {
            adjacency = new int[tlist.Length];
            degree = new int[tlist.Length / 3];
            used = new bool[tlist.Length / 3];

            for (int i = 0; i < adjacency.Length; i++)
                adjacency[i] = -1;

            //
            // Store all the edges in a dictionary for easier lookup
            //

            var edges = new Dictionary<Edge, int>();

            for (int t = 0; t < tlist.Length; t += 3)
            {
                for (int v = 0; v < 3; v++)
                {
                    var edge = new Edge(tlist[t + v], tlist[t + (v + 1) % 3]);

                    edges[edge] = t / 3;
                }
            }

            //
            // Fill the adjacency array
            //

            for (int t = 0; t < tlist.Length; t += 3)
            {
                for (int e = 0; e < 3; e++)
                {
                    //
                    // We already have an adjacent triangle for this edge.
                    // This means that there are 3 or more triangles that have a 
                    // common edge but this is not very common and we'll just 
                    // ignore it.
                    //

                    if (adjacency[t + e] != -1)
                        continue;

                    //
                    // Notice that the edge must be reversed compared to the
                    // order they were stored in the dictionary to preserve
                    // trinangle vertex ordering.
                    //

                    var edge = new Edge(tlist[t + (e + 1) % 3], tlist[t + e]);

                    int k;

                    //
                    // Note the k != t / 3 check to avoid making degenerate triangles
                    // adjacent to themselfs.
                    //

                    if (edges.TryGetValue(edge, out k) && k != t / 3)
                    {
                        adjacency[t + e] = k;
                        degree[t / 3]++;
                    }
                }
            }
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 9 months ago) by iritscen
File size:	10842 byte(s)
Log Message:	Adding OniSplit source code (v0.9.99.0). Many thanks to Neo for all his work over the years.
#	Content
1	using System;
2	using System.Collections.Generic;
3
4	namespace 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	}