OniSplit/Motoko/Quadify.cs

using System;
using System.Collections.Generic;

namespace Oni.Motoko
{
    internal class Quadify
    {
        private readonly Geometry mesh;
        private readonly List<Face> faces;

        public Quadify(Geometry mesh)
        {
            this.mesh = mesh;

            faces = new List<Face>();

            for (int i = 0; i < mesh.Triangles.Length; i += 3)
            {
                var plane = new Plane(
                    mesh.Points[mesh.Triangles[i + 0]],
                    mesh.Points[mesh.Triangles[i + 1]],
                    mesh.Points[mesh.Triangles[i + 2]]);

                faces.Add(new Face(
                    mesh,
                    new[] { mesh.Triangles[i + 0], mesh.Triangles[i + 1], mesh.Triangles[i + 2] },
                    plane.Normal));
            }
        }

        public static List<int[]> Do(Geometry mesh)
        {
            var quadrangulate = new Quadify(mesh);
            return quadrangulate.Execute();
        }

        public List<int[]> Execute()
        {
            GenerateAdjacency();

            var candidates = new List<QuadCandidate>();
            var newFaces = new int[faces.Count][];
            var quadified = new bool[faces.Count];
            int quadCount = 0;

            for (int i = 0; i < faces.Count; i++)
            {
                Face f1 = faces[i];

                if (quadified[i])
                    continue;

                candidates.Clear();

                foreach (Edge e1 in f1.edges)
                {
                    foreach (Edge e2 in e1.adjacency)
                    {
                        if (quadified[faces.IndexOf(e2.face)])
                            continue;

                        candidates.Add(new QuadCandidate(e1, e2));
                    }
                }

                if (candidates.Count > 0)
                {
                    candidates.Sort(new QuadCandidateComparer());
                    newFaces[i] = candidates[0].CreateQuad();

                    int k = faces.IndexOf(candidates[0].e2.face);

                    quadified[i] = true;
                    quadified[k] = true;

                    quadCount++;
                }
            }

            var quadList = new List<int[]>(faces.Count - quadCount);

            for (int i = 0; i < faces.Count; i++)
            {
                if (newFaces[i] != null)
                    quadList.Add(newFaces[i]);
                else if (!quadified[i])
                    quadList.Add(faces[i].indices);
            }

            return quadList;
        }

        private void GenerateAdjacency()
        {
            var points = mesh.Points;
            var pointUseCount = new int[points.Length];
            var pointUsage = new int[points.Length][];

            foreach (Face face in faces)
            {
                foreach (int i in face.indices)
                    pointUseCount[i]++;
            }

            for (int faceIndex = 0; faceIndex < faces.Count; faceIndex++)
            {
                foreach (int pointIndex in faces[faceIndex].indices)
                {
                    int useCount = pointUseCount[pointIndex];
                    int[] usage = pointUsage[pointIndex];

                    if (usage == null)
                    {
                        usage = new int[useCount];
                        pointUsage[pointIndex] = usage;
                    }

                    usage[usage.Length - useCount] = faceIndex;
                    pointUseCount[pointIndex] = useCount - 1;
                }
            }

            var adjacencyBuffer = new List<Edge>();

            foreach (Face f1 in faces)
            {
                foreach (Edge e1 in f1.edges)
                {
                    int[] usage0 = pointUsage[e1.Point0Index];
                    int[] usage1 = pointUsage[e1.Point1Index];

                    if (usage0 == null || usage1 == null)
                        continue;

                    adjacencyBuffer.Clear();

                    foreach (int adjFaceIndex in MatchSortedArrays(usage0, usage1))
                    {
                        Face f2 = faces[adjFaceIndex];

                        if (f2 == f1 || (f2.normal - f1.normal).Length() > 0.01f)
                            continue;

                        foreach (Edge e2 in f2.edges)
                        {
                            if (e1.IsShared(e2))
                                adjacencyBuffer.Add(e2);
                        }
                    }

                    e1.adjacency = adjacencyBuffer.ToArray();
                }
            }
        }

        private static IEnumerable<int> MatchSortedArrays(int[] a1, int[] a2)
        {
            int l1 = a1.Length;
            int l2 = a2.Length;
            int i1 = 0;
            int i2 = 0;

            while (i1 < l1 && i2 < l2)
            {
                int v1 = a1[i1];
                int v2 = a2[i2];

                if (v1 < v2)
                {
                    i1++;
                }
                else if (v1 > v2)
                {
                    i2++;
                }
                else
                {
                    i1++;
                    i2++;

                    yield return v1;
                }
            }
        }

        private class Face
        {
            public readonly Geometry mesh;
            public readonly int[] indices;
            public readonly Edge[] edges;
            public readonly Vector3 normal;

            public Face(Geometry mesh, int[] pointIndices, Vector3 normal)
            {
                this.mesh = mesh;
                this.indices = pointIndices;
                this.normal = normal;

                edges = new Edge[indices.Length];

                for (int i = 0; i < edges.Length; i++)
                    edges[i] = new Edge(this, i);
            }
        }

        private class Edge
        {
            private static readonly Edge[] emptyEdges = new Edge[0];

            public readonly Face face;
            public readonly int i0;
            public readonly int i1;
            public Edge[] adjacency;

            public Edge(Face polygon, int index)
            {
                this.face = polygon;
                this.i0 = index;
                this.i1 = (index + 1) % face.edges.Length;
                this.adjacency = emptyEdges;
            }

            public int Point0Index
            {
                get { return face.indices[i0]; }
            }

            public int Point1Index
            {
                get { return face.indices[i1]; }
            }

            public bool IsShared(Edge e)
            {
                return (Point0Index == e.Point1Index && Point1Index == e.Point0Index);
            }
        }

        private class QuadCandidateComparer : IComparer<QuadCandidate>
        {
            public int Compare(QuadCandidate x, QuadCandidate y)
            {
                return x.length.CompareTo(y.length);
            }
        }

        private class QuadCandidate
        {
            public readonly Edge e1;
            public readonly Edge e2;
            public readonly float length;

            public QuadCandidate(Edge e1, Edge e2)
            {
                this.e1 = e1;
                this.e2 = e2;

                Vector3[] points = e1.face.mesh.Points;
                this.length = (points[e1.Point0Index] - points[e1.Point1Index]).LengthSquared();
            }

            public int[] CreateQuad()
            {
                int[] newPoints = new int[4];
                int l = 0;

                newPoints[l] = e1.face.indices[e1.i1];
                l++;

                for (int k = 0; k < 3; k++)
                {
                    if (k != e1.i0 && k != e1.i1)
                    {
                        newPoints[l] = e1.face.indices[k];
                        l++;

                        break;
                    }
                }

                newPoints[l] = e1.face.indices[e1.i0];
                l++;

                for (int k = 0; k < 3; k++)
                {
                    if (k != e2.i0 && k != e2.i1)
                    {
                        newPoints[l] = e2.face.indices[k];
                        l++;

                        break;
                    }
                }

                return newPoints;
            }
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 8 months ago) by iritscen
File size:	8757 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 Quadify
7	{
8	private readonly Geometry mesh;
9	private readonly List<Face> faces;
10
11	public Quadify(Geometry mesh)
12	{
13	this.mesh = mesh;
14
15	faces = new List<Face>();
16
17	for (int i = 0; i < mesh.Triangles.Length; i += 3)
18	{
19	var plane = new Plane(
20	mesh.Points[mesh.Triangles[i + 0]],
21	mesh.Points[mesh.Triangles[i + 1]],
22	mesh.Points[mesh.Triangles[i + 2]]);
23
24	faces.Add(new Face(
25	mesh,
26	new[] { mesh.Triangles[i + 0], mesh.Triangles[i + 1], mesh.Triangles[i + 2] },
27	plane.Normal));
28	}
29	}
30
31	public static List<int[]> Do(Geometry mesh)
32	{
33	var quadrangulate = new Quadify(mesh);
34	return quadrangulate.Execute();
35	}
36
37	public List<int[]> Execute()
38	{
39	GenerateAdjacency();
40
41	var candidates = new List<QuadCandidate>();
42	var newFaces = new int[faces.Count][];
43	var quadified = new bool[faces.Count];
44	int quadCount = 0;
45
46	for (int i = 0; i < faces.Count; i++)
47	{
48	Face f1 = faces[i];
49
50	if (quadified[i])
51	continue;
52
53	candidates.Clear();
54
55	foreach (Edge e1 in f1.edges)
56	{
57	foreach (Edge e2 in e1.adjacency)
58	{
59	if (quadified[faces.IndexOf(e2.face)])
60	continue;
61
62	candidates.Add(new QuadCandidate(e1, e2));
63	}
64	}
65
66	if (candidates.Count > 0)
67	{
68	candidates.Sort(new QuadCandidateComparer());
69	newFaces[i] = candidates[0].CreateQuad();
70
71	int k = faces.IndexOf(candidates[0].e2.face);
72
73	quadified[i] = true;
74	quadified[k] = true;
75
76	quadCount++;
77	}
78	}
79
80	var quadList = new List<int[]>(faces.Count - quadCount);
81
82	for (int i = 0; i < faces.Count; i++)
83	{
84	if (newFaces[i] != null)
85	quadList.Add(newFaces[i]);
86	else if (!quadified[i])
87	quadList.Add(faces[i].indices);
88	}
89
90	return quadList;
91	}
92
93	private void GenerateAdjacency()
94	{
95	var points = mesh.Points;
96	var pointUseCount = new int[points.Length];
97	var pointUsage = new int[points.Length][];
98
99	foreach (Face face in faces)
100	{
101	foreach (int i in face.indices)
102	pointUseCount[i]++;
103	}
104
105	for (int faceIndex = 0; faceIndex < faces.Count; faceIndex++)
106	{
107	foreach (int pointIndex in faces[faceIndex].indices)
108	{
109	int useCount = pointUseCount[pointIndex];
110	int[] usage = pointUsage[pointIndex];
111
112	if (usage == null)
113	{
114	usage = new int[useCount];
115	pointUsage[pointIndex] = usage;
116	}
117
118	usage[usage.Length - useCount] = faceIndex;
119	pointUseCount[pointIndex] = useCount - 1;
120	}
121	}
122
123	var adjacencyBuffer = new List<Edge>();
124
125	foreach (Face f1 in faces)
126	{
127	foreach (Edge e1 in f1.edges)
128	{
129	int[] usage0 = pointUsage[e1.Point0Index];
130	int[] usage1 = pointUsage[e1.Point1Index];
131
132	if (usage0 == null \|\| usage1 == null)
133	continue;
134
135	adjacencyBuffer.Clear();
136
137	foreach (int adjFaceIndex in MatchSortedArrays(usage0, usage1))
138	{
139	Face f2 = faces[adjFaceIndex];
140
141	if (f2 == f1 \|\| (f2.normal - f1.normal).Length() > 0.01f)
142	continue;
143
144	foreach (Edge e2 in f2.edges)
145	{
146	if (e1.IsShared(e2))
147	adjacencyBuffer.Add(e2);
148	}
149	}
150
151	e1.adjacency = adjacencyBuffer.ToArray();
152	}
153	}
154	}
155
156	private static IEnumerable<int> MatchSortedArrays(int[] a1, int[] a2)
157	{
158	int l1 = a1.Length;
159	int l2 = a2.Length;
160	int i1 = 0;
161	int i2 = 0;
162
163	while (i1 < l1 && i2 < l2)
164	{
165	int v1 = a1[i1];
166	int v2 = a2[i2];
167
168	if (v1 < v2)
169	{
170	i1++;
171	}
172	else if (v1 > v2)
173	{
174	i2++;
175	}
176	else
177	{
178	i1++;
179	i2++;
180
181	yield return v1;
182	}
183	}
184	}
185
186	private class Face
187	{
188	public readonly Geometry mesh;
189	public readonly int[] indices;
190	public readonly Edge[] edges;
191	public readonly Vector3 normal;
192
193	public Face(Geometry mesh, int[] pointIndices, Vector3 normal)
194	{
195	this.mesh = mesh;
196	this.indices = pointIndices;
197	this.normal = normal;
198
199	edges = new Edge[indices.Length];
200
201	for (int i = 0; i < edges.Length; i++)
202	edges[i] = new Edge(this, i);
203	}
204	}
205
206	private class Edge
207	{
208	private static readonly Edge[] emptyEdges = new Edge[0];
209
210	public readonly Face face;
211	public readonly int i0;
212	public readonly int i1;
213	public Edge[] adjacency;
214
215	public Edge(Face polygon, int index)
216	{
217	this.face = polygon;
218	this.i0 = index;
219	this.i1 = (index + 1) % face.edges.Length;
220	this.adjacency = emptyEdges;
221	}
222
223	public int Point0Index
224	{
225	get { return face.indices[i0]; }
226	}
227
228	public int Point1Index
229	{
230	get { return face.indices[i1]; }
231	}
232
233	public bool IsShared(Edge e)
234	{
235	return (Point0Index == e.Point1Index && Point1Index == e.Point0Index);
236	}
237	}
238
239	private class QuadCandidateComparer : IComparer<QuadCandidate>
240	{
241	public int Compare(QuadCandidate x, QuadCandidate y)
242	{
243	return x.length.CompareTo(y.length);
244	}
245	}
246
247	private class QuadCandidate
248	{
249	public readonly Edge e1;
250	public readonly Edge e2;
251	public readonly float length;
252
253	public QuadCandidate(Edge e1, Edge e2)
254	{
255	this.e1 = e1;
256	this.e2 = e2;
257
258	Vector3[] points = e1.face.mesh.Points;
259	this.length = (points[e1.Point0Index] - points[e1.Point1Index]).LengthSquared();
260	}
261
262	public int[] CreateQuad()
263	{
264	int[] newPoints = new int[4];
265	int l = 0;
266
267	newPoints[l] = e1.face.indices[e1.i1];
268	l++;
269
270	for (int k = 0; k < 3; k++)
271	{
272	if (k != e1.i0 && k != e1.i1)
273	{
274	newPoints[l] = e1.face.indices[k];
275	l++;
276
277	break;
278	}
279	}
280
281	newPoints[l] = e1.face.indices[e1.i0];
282	l++;
283
284	for (int k = 0; k < 3; k++)
285	{
286	if (k != e2.i0 && k != e2.i1)
287	{
288	newPoints[l] = e2.face.indices[k];
289	l++;
290
291	break;
292	}
293	}
294
295	return newPoints;
296	}
297	}
298	}
299	}