OniSplit/Akira/PolygonQuadrangulate.cs

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal class PolygonQuadrangulate
    {
        private readonly PolygonMesh mesh;

        public PolygonQuadrangulate(PolygonMesh mesh)
        {
            this.mesh = mesh;
        }

        public void Execute()
        {
            GenerateAdjacency();

            var candidates = new List<QuadCandidate>();
            var polygons = mesh.Polygons;

            var newPolygons = new Polygon[polygons.Count];
            var marked = new bool[polygons.Count];
            int quadCount = 0;

            for (int i = 0; i < polygons.Count; i++)
            {
                var p1 = polygons[i];

                if (marked[i] || p1.Edges.Length != 3)
                    continue;

                candidates.Clear();

                foreach (PolygonEdge e1 in p1.Edges)
                {
                    foreach (PolygonEdge e2 in e1.Adjancency)
                    {
                        if (marked[polygons.IndexOf(e2.Polygon)])
                            continue;

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

                if (candidates.Count > 0)
                {
                    candidates.Sort();
                    newPolygons[i] = candidates[0].CreateQuad(mesh);

                    int k = polygons.IndexOf(candidates[0].Polygon2);

                    marked[i] = true;
                    marked[k] = true;

                    quadCount++;
                }
            }

            var newPolygonList = new List<Polygon>(polygons.Count - quadCount);

            for (int i = 0; i < polygons.Count; i++)
            {
                if (newPolygons[i] != null)
                    newPolygonList.Add(newPolygons[i]);
                else if (!marked[i])
                    newPolygonList.Add(polygons[i]);
            }

            polygons = newPolygonList;
        }

        #region private class QuadCandidate

        private class QuadCandidate : IComparable<QuadCandidate>
        {
            private PolygonEdge e1;
            private PolygonEdge e2;
            private float l;

            public static bool IsQuadCandidate(PolygonEdge e1, PolygonEdge e2)
            {
                //
                // To merge 2 polygons into one the following must be true:
                // - both must be triangles
                // - they must share the same plane
                // - they must use the same material
                // - TODO: the resulting polygon must be convex!!!
                // - TODO: must have the same texture coordinates
                //

                Polygon p1 = e1.Polygon;
                Polygon p2 = e2.Polygon;

                return (
                       p1.Edges.Length == 3
                    && p2.Edges.Length == 3
                    && p1.Plane == p2.Plane
                    && p1.Material == p2.Material
                    //&& e1.Point0Index == e2.Point0Index
                    //&& e1.Point1Index == e2.Point1Index
                    );
            }

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

                List<Vector3> points = e1.Polygon.Mesh.Points;
                this.l = Vector3.DistanceSquared(points[e1.Point0Index], points[e1.Point1Index]);
            }

            public Polygon Polygon1 => e1.Polygon;
            public Polygon Polygon2 => e2.Polygon;

            public int CompareTo(QuadCandidate other)
            {
                return l.CompareTo(other.l);
            }

            public Polygon CreateQuad(PolygonMesh mesh)
            {
                int[] newPoints = new int[4];
                int[] newTexCoords = new int[4];
                int l = 0;

                newPoints[l] = e1.Polygon.PointIndices[e1.EndIndex];
                newTexCoords[l] = e1.Polygon.TexCoordIndices[e1.EndIndex];
                l++;

                for (int k = 0; k < 3; k++)
                {
                    if (k != e1.Index && k != e1.EndIndex)
                    {
                        newPoints[l] = e1.Polygon.PointIndices[k];
                        newTexCoords[l] = e1.Polygon.TexCoordIndices[k];
                        l++;

                        break;
                    }
                }

                newPoints[l] = e1.Polygon.PointIndices[e1.Index];
                newTexCoords[l] = e1.Polygon.TexCoordIndices[e1.Index];
                l++;

                for (int k = 0; k < 3; k++)
                {
                    if (k != e2.Index && k != e2.EndIndex)
                    {
                        newPoints[l] = e2.Polygon.PointIndices[k];
                        newTexCoords[l] = e2.Polygon.TexCoordIndices[k];
                        l++;

                        break;
                    }
                }

                return new Polygon(mesh, newPoints, e1.Polygon.Plane)
                {
                    TexCoordIndices = newTexCoords,
                    Material = e1.Polygon.Material
                };
            }
        }

        #endregion

        private void GenerateAdjacency()
        {
            var points = mesh.Points;
            var polygons = mesh.Polygons;

            var pointUseCount = new int[points.Count];
            var pointUsage = new int[points.Count][];

            foreach (var polygon in polygons)
            {
                foreach (int i in polygon.PointIndices)
                    pointUseCount[i]++;
            }

            for (int polygon = 0; polygon < polygons.Count; polygon++)
            {
                foreach (int i in polygons[polygon].PointIndices)
                {
                    int useCount = pointUseCount[i];
                    int[] pa = pointUsage[i];

                    if (pa == null)
                    {
                        pa = new int[useCount];
                        pointUsage[i] = pa;
                    }

                    pa[pa.Length - useCount] = polygon;
                    pointUseCount[i] = useCount - 1;
                }
            }

            var adjacencyBuffer = new List<PolygonEdge>();

            foreach (var p1 in polygons)
            {
                foreach (var e1 in p1.Edges)
                {
                    adjacencyBuffer.Clear();

                    int[] a0 = pointUsage[e1.Point0Index];
                    int[] a1 = pointUsage[e1.Point1Index];

                    if (a0 == null || a1 == null)
                        continue;

                    foreach (int pi2 in MatchSortedArrays(a0, a1))
                    {
                        var p2 = polygons[pi2];

                        if (p2 == p1)
                            continue;

                        foreach (var e2 in p2.Edges)
                        {
                            if (e1.Point0Index == e2.Point1Index && e1.Point1Index == e2.Point0Index
                                || e1.Point0Index == e2.Point0Index && e1.Point1Index == e2.Point1Index)
                            {
                                adjacencyBuffer.Add(e2);
                            }
                        }
                    }

                    e1.Adjancency = 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;
                }
            }
        }
    }
}
Revision:	1114
Committed:	Wed Jan 22 14:08:57 2020 UTC (5 years, 8 months ago) by iritscen
File size:	8438 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.Akira
5	{
6	internal class PolygonQuadrangulate
7	{
8	private readonly PolygonMesh mesh;
9
10	public PolygonQuadrangulate(PolygonMesh mesh)
11	{
12	this.mesh = mesh;
13	}
14
15	public void Execute()
16	{
17	GenerateAdjacency();
18
19	var candidates = new List<QuadCandidate>();
20	var polygons = mesh.Polygons;
21
22	var newPolygons = new Polygon[polygons.Count];
23	var marked = new bool[polygons.Count];
24	int quadCount = 0;
25
26	for (int i = 0; i < polygons.Count; i++)
27	{
28	var p1 = polygons[i];
29
30	if (marked[i] \|\| p1.Edges.Length != 3)
31	continue;
32
33	candidates.Clear();
34
35	foreach (PolygonEdge e1 in p1.Edges)
36	{
37	foreach (PolygonEdge e2 in e1.Adjancency)
38	{
39	if (marked[polygons.IndexOf(e2.Polygon)])
40	continue;
41
42	if (QuadCandidate.IsQuadCandidate(e1, e2))
43	candidates.Add(new QuadCandidate(e1, e2));
44	}
45	}
46
47	if (candidates.Count > 0)
48	{
49	candidates.Sort();
50	newPolygons[i] = candidates[0].CreateQuad(mesh);
51
52	int k = polygons.IndexOf(candidates[0].Polygon2);
53
54	marked[i] = true;
55	marked[k] = true;
56
57	quadCount++;
58	}
59	}
60
61	var newPolygonList = new List<Polygon>(polygons.Count - quadCount);
62
63	for (int i = 0; i < polygons.Count; i++)
64	{
65	if (newPolygons[i] != null)
66	newPolygonList.Add(newPolygons[i]);
67	else if (!marked[i])
68	newPolygonList.Add(polygons[i]);
69	}
70
71	polygons = newPolygonList;
72	}
73
74	#region private class QuadCandidate
75
76	private class QuadCandidate : IComparable<QuadCandidate>
77	{
78	private PolygonEdge e1;
79	private PolygonEdge e2;
80	private float l;
81
82	public static bool IsQuadCandidate(PolygonEdge e1, PolygonEdge e2)
83	{
84	//
85	// To merge 2 polygons into one the following must be true:
86	// - both must be triangles
87	// - they must share the same plane
88	// - they must use the same material
89	// - TODO: the resulting polygon must be convex!!!
90	// - TODO: must have the same texture coordinates
91	//
92
93	Polygon p1 = e1.Polygon;
94	Polygon p2 = e2.Polygon;
95
96	return (
97	p1.Edges.Length == 3
98	&& p2.Edges.Length == 3
99	&& p1.Plane == p2.Plane
100	&& p1.Material == p2.Material
101	//&& e1.Point0Index == e2.Point0Index
102	//&& e1.Point1Index == e2.Point1Index
103	);
104	}
105
106	public QuadCandidate(PolygonEdge e1, PolygonEdge e2)
107	{
108	this.e1 = e1;
109	this.e2 = e2;
110
111	List<Vector3> points = e1.Polygon.Mesh.Points;
112	this.l = Vector3.DistanceSquared(points[e1.Point0Index], points[e1.Point1Index]);
113	}
114
115	public Polygon Polygon1 => e1.Polygon;
116	public Polygon Polygon2 => e2.Polygon;
117
118	public int CompareTo(QuadCandidate other)
119	{
120	return l.CompareTo(other.l);
121	}
122
123	public Polygon CreateQuad(PolygonMesh mesh)
124	{
125	int[] newPoints = new int[4];
126	int[] newTexCoords = new int[4];
127	int l = 0;
128
129	newPoints[l] = e1.Polygon.PointIndices[e1.EndIndex];
130	newTexCoords[l] = e1.Polygon.TexCoordIndices[e1.EndIndex];
131	l++;
132
133	for (int k = 0; k < 3; k++)
134	{
135	if (k != e1.Index && k != e1.EndIndex)
136	{
137	newPoints[l] = e1.Polygon.PointIndices[k];
138	newTexCoords[l] = e1.Polygon.TexCoordIndices[k];
139	l++;
140
141	break;
142	}
143	}
144
145	newPoints[l] = e1.Polygon.PointIndices[e1.Index];
146	newTexCoords[l] = e1.Polygon.TexCoordIndices[e1.Index];
147	l++;
148
149	for (int k = 0; k < 3; k++)
150	{
151	if (k != e2.Index && k != e2.EndIndex)
152	{
153	newPoints[l] = e2.Polygon.PointIndices[k];
154	newTexCoords[l] = e2.Polygon.TexCoordIndices[k];
155	l++;
156
157	break;
158	}
159	}
160
161	return new Polygon(mesh, newPoints, e1.Polygon.Plane)
162	{
163	TexCoordIndices = newTexCoords,
164	Material = e1.Polygon.Material
165	};
166	}
167	}
168
169	#endregion
170
171	private void GenerateAdjacency()
172	{
173	var points = mesh.Points;
174	var polygons = mesh.Polygons;
175
176	var pointUseCount = new int[points.Count];
177	var pointUsage = new int[points.Count][];
178
179	foreach (var polygon in polygons)
180	{
181	foreach (int i in polygon.PointIndices)
182	pointUseCount[i]++;
183	}
184
185	for (int polygon = 0; polygon < polygons.Count; polygon++)
186	{
187	foreach (int i in polygons[polygon].PointIndices)
188	{
189	int useCount = pointUseCount[i];
190	int[] pa = pointUsage[i];
191
192	if (pa == null)
193	{
194	pa = new int[useCount];
195	pointUsage[i] = pa;
196	}
197
198	pa[pa.Length - useCount] = polygon;
199	pointUseCount[i] = useCount - 1;
200	}
201	}
202
203	var adjacencyBuffer = new List<PolygonEdge>();
204
205	foreach (var p1 in polygons)
206	{
207	foreach (var e1 in p1.Edges)
208	{
209	adjacencyBuffer.Clear();
210
211	int[] a0 = pointUsage[e1.Point0Index];
212	int[] a1 = pointUsage[e1.Point1Index];
213
214	if (a0 == null \|\| a1 == null)
215	continue;
216
217	foreach (int pi2 in MatchSortedArrays(a0, a1))
218	{
219	var p2 = polygons[pi2];
220
221	if (p2 == p1)
222	continue;
223
224	foreach (var e2 in p2.Edges)
225	{
226	if (e1.Point0Index == e2.Point1Index && e1.Point1Index == e2.Point0Index
227	\|\| e1.Point0Index == e2.Point0Index && e1.Point1Index == e2.Point1Index)
228	{
229	adjacencyBuffer.Add(e2);
230	}
231	}
232	}
233
234	e1.Adjancency = adjacencyBuffer.ToArray();
235	}
236	}
237	}
238
239	private static IEnumerable<int> MatchSortedArrays(int[] a1, int[] a2)
240	{
241	int l1 = a1.Length;
242	int l2 = a2.Length;
243	int i1 = 0;
244	int i2 = 0;
245
246	while (i1 < l1 && i2 < l2)
247	{
248	int v1 = a1[i1];
249	int v2 = a2[i2];
250
251	if (v1 < v2)
252	{
253	i1++;
254	}
255	else if (v1 > v2)
256	{
257	i2++;
258	}
259	else
260	{
261	i1++;
262	i2++;
263
264	yield return v1;
265	}
266	}
267	}
268	}
269	}