source: OniSplit/Dae/Converters/FaceConverter.cs@ 1144

using System;
using System.Collections.Generic;
using Oni.Collections;

namespace Oni.Dae
{
    internal class FaceConverter
    {
        private Node root;
        private int maxEdges = 3;

        public static void Triangulate(Node root)
        {
            var converter = new FaceConverter {
                root = root
            };

            converter.Convert();
        }

        private void Convert()
        {
            ConvertNode(root);
        }

        private void ConvertNode(Node node)
        {
            foreach (var instance in node.Instances)
                ConvertInstance(instance);

            foreach (var child in node.Nodes)
                ConvertNode(child);
        }

        private void ConvertInstance(Instance instance)
        {
            var geometryInstance = instance as GeometryInstance;

            if (geometryInstance != null)
            {
                ConvertGeometry(geometryInstance.Target);
                return;
            }
        }

        private void ConvertGeometry(Geometry geometry)
        {
            foreach (var primitives in geometry.Primitives)
            {
                if (primitives.PrimitiveType != MeshPrimitiveType.Polygons)
                    continue;

                if (primitives.VertexCounts.All(c => c == 3))
                    continue;

                ConvertPolygons(geometry, primitives);
            }
        }

        private void ConvertPolygons(Geometry geometry, MeshPrimitives primitives)
        {
            var positionInput = primitives.Inputs.FirstOrDefault(i => i.Semantic == Semantic.Position);

            if (positionInput == null)
            {
                Console.Error.WriteLine("{0}: cannot find position input", geometry.Name);
                return;
            }

            var newFaces = new List<int>(primitives.VertexCounts.Count * 2);
            var newVertexCounts = new List<int>(primitives.VertexCounts.Count * 2);
            int voffset = 0;

            foreach (int vcount in primitives.VertexCounts)
            {
                if (vcount < 3)
                {
                    Console.Error.WriteLine("{0}: skipping bad face (line)", geometry.Name);
                }
                else if (vcount <= maxEdges)
                {
                    for (int i = 0; i < vcount; i++)
                        newFaces.Add(voffset + i);

                    newVertexCounts.Add(vcount);
                }
                else
                {
                    ConvertPolygon(geometry, positionInput, voffset, vcount, newFaces, newVertexCounts);
                }

                voffset += vcount;
            }

            primitives.VertexCounts.Clear();
            primitives.VertexCounts.AddRange(newVertexCounts);

            var oldIndices = new int[primitives.Inputs.Count][];

            for (int i = 0; i < primitives.Inputs.Count; i++)
            {
                var input = primitives.Inputs[i];
                oldIndices[i] = input.Indices.ToArray();
                input.Indices.Clear();
            }

            for (int i = 0; i < primitives.Inputs.Count; i++)
            {
                var ni = primitives.Inputs[i].Indices;
                var oi = oldIndices[i];

                foreach (int v in newFaces)
                    ni.Add(oi[v]);
            }
        }

        private void ConvertPolygon(Geometry geometry, IndexedInput input, int offset, int vcount, List<int> newFaces, List<int> newVertexCounts)
        {
            var points = new Vector3[vcount];

            for (int i = 0; i < vcount; i++)
                points[i] = Dae.Source.ReadVector3(input.Source, input.Indices[offset + i]);

            int concave = -1;

            for (int i = 0; i < vcount; i++)
            {
                Vector3 p0 = points[i];
                Vector3 p1 = points[(i + 1) % vcount];

                if (Vector3.Dot(p0, p1) < 0.0f)
                {
                    concave = i;
                    break;
                }
            }

            if (concave == -1)
            {
                for (int i = 0; i < vcount - 2; i++)
                {
                    newFaces.Add(offset + 0);
                    newFaces.Add(offset + 1 + i);
                    newFaces.Add(offset + 2 + i);
                    newVertexCounts.Add(3);
                }

                return;
            }

            if (vcount == 4)
            {
                newFaces.Add(offset + concave);
                newFaces.Add(offset + (concave + 1) % vcount);
                newFaces.Add(offset + (concave + 2) % vcount);
                newVertexCounts.Add(3);

                newFaces.Add(offset + (concave + vcount - 1) % vcount);
                newFaces.Add(offset + (concave + vcount - 2) % vcount);
                newFaces.Add(offset + concave);
                newVertexCounts.Add(3);

                return;
            }

            Console.Error.WriteLine("{0}: skipping bad face (concave {1}-gon)", geometry.Name, vcount);
        }
    }
}