source: OniSplit/Akira/PolygonQuadrangulate.cs@ 1114

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;
                }
            }
        }
    }
}