source: OniSplit/Motoko/GeometryDaeReader.cs@ 1117

using System;
using System.Collections.Generic;

namespace Oni.Motoko
{
    internal static class GeometryDaeReader
    {
        #region private struct Vertex

        private struct Vertex : IEquatable<Vertex>
        {
            public readonly int PositionIndex;
            public readonly int TexcoordIndex;
            public readonly int NormalIndex;

            public Vertex(int pointIndex, int uvIndex, int normalIndex)
            {
                PositionIndex = pointIndex;
                TexcoordIndex = uvIndex;
                NormalIndex = normalIndex;
            }

            public static bool operator ==(Vertex v1, Vertex v2) => v1.Equals(v2);

            public static bool operator !=(Vertex v1, Vertex v2) => !v1.Equals(v2);

            public bool Equals(Vertex v) => PositionIndex == v.PositionIndex && TexcoordIndex == v.TexcoordIndex && NormalIndex == v.NormalIndex;

            public override bool Equals(object obj) => obj is Vertex && Equals((Vertex)obj);

            public override int GetHashCode() => PositionIndex ^ TexcoordIndex ^ NormalIndex;
        }

        #endregion

        public static Geometry Read(Dae.Geometry daeGeometry)
        {
            return Read(daeGeometry, false, false, 0.0f);
        }

        public static IEnumerable<Geometry> Read(Dae.Node node, TextureImporter3 textureImporter)
        {
            Dae.FaceConverter.Triangulate(node);

            foreach (var daeGeometryInstance in node.GeometryInstances)
            {
                var daeGeometry = daeGeometryInstance.Target;

                var geometry = Read(daeGeometry, false, false, 0.0f);
                geometry.Name = node.Name;

                if (textureImporter != null && daeGeometryInstance.Materials.Count > 0)
                    geometry.TextureName = textureImporter.AddMaterial(daeGeometryInstance.Materials[0].Target);

                yield return geometry;
            }
        }

        public static Geometry Read(Dae.Geometry daeGeometry, bool generateNormals, bool flatNormals, float shellOffset)
        {
            if (daeGeometry.Primitives.Count > 1)
                throw new NotSupportedException(string.Format("Geometry {0}: Multiple primitive groups per mesh are not supported", daeGeometry.Name));

            var primitives = daeGeometry.Primitives[0];

            if (primitives.PrimitiveType == Dae.MeshPrimitiveType.Lines || primitives.PrimitiveType == Dae.MeshPrimitiveType.LineStrips)
                throw new NotSupportedException(string.Format("Geometry {0}: Line primitives are not supported", daeGeometry.Name));

            var positionIndex = new Dictionary<Vector3, int>();
            var positions = new List<Vector3>();
            int[] positionIndices = null;

            var normalIndex = new Dictionary<Vector3, int>();
            var normals = new List<Vector3>();
            int[] normalIndices = null;

            var texCoordIndex = new Dictionary<Vector2, int>();
            var texCoords = new List<Vector2>();
            int[] texCoordIndices = null;

            foreach (var input in primitives.Inputs)
            {
                switch (input.Semantic)
                {
                    case Dae.Semantic.Position:
                        positionIndices = RemoveDuplicates(input, positions, positionIndex, Dae.Source.ReadVector3);
                        break;

                    case Dae.Semantic.Normal:
                        if (!generateNormals)
                            normalIndices = RemoveDuplicates(input, normals, normalIndex, Dae.Source.ReadVector3);
                        break;

                    case Dae.Semantic.TexCoord:
                        texCoordIndices = RemoveDuplicates(input, texCoords, texCoordIndex, Dae.Source.ReadTexCoord);
                        break;
                }
            }

            if (texCoordIndices == null)
                Console.WriteLine("Geometry {0} does not have texture coordinates", daeGeometry.Name);

            if (normalIndices == null)
                generateNormals = true;

            Vector3[] generatedNormals = null;

            if (generateNormals || shellOffset != 0.0f)
                generatedNormals = GenerateNormals(positions, positionIndices, flatNormals);

            if (generateNormals)
            {
                normals = new List<Vector3>(generatedNormals);
                normalIndices = positionIndices;
            }

            int[] shellIndices = null;

            if (shellOffset != 0.0f)
            {
                var shellNormals = generatedNormals;

                if (flatNormals)
                    shellNormals = GenerateNormals(positions, positionIndices, false);

                shellIndices = GenerateShell(positions, positionIndices, shellNormals, shellOffset);
            }

            var triangles = new int[(shellIndices == null) ? positionIndices.Length : positionIndices.Length + shellIndices.Length];
            var vertices = new List<Vertex>();
            var vertexIndex = new Dictionary<Vertex, int>();

            for (int i = 0; i < positionIndices.Length; i++)
            {
                var vertex = new Vertex(
                    positionIndices[i],
                    (texCoordIndices != null) ? texCoordIndices[i] : -1,
                    (normalIndices != null) ? normalIndices[i] : -1);

                if (!vertexIndex.TryGetValue(vertex, out triangles[i]))
                {
                    triangles[i] = vertices.Count;
                    vertices.Add(vertex);
                    vertexIndex.Add(vertex, triangles[i]);
                }
            }

            if (shellIndices != null)
            {
                for (int i = 0; i < shellIndices.Length; i++)
                {
                    var vertex = new Vertex(shellIndices[i], -1, -1);
                    int j = i + positionIndices.Length;

                    if (!vertexIndex.TryGetValue(vertex, out triangles[j]))
                    {
                        triangles[j] = vertices.Count;
                        vertices.Add(vertex);
                        vertexIndex.Add(vertex, triangles[j]);
                    }
                }
            }

            if (vertices.Count > 2048)
                Console.Error.WriteLine("Warning: Geometry {0} has too many vertices ({1})", daeGeometry.Name, vertices.Count);

            var geometry = new Geometry
            {
                Points = new Vector3[vertices.Count],
                Normals = new Vector3[vertices.Count],
                TexCoords = new Vector2[vertices.Count],
                Triangles = triangles
            };

            for (int i = 0; i < vertices.Count; i++)
            {
                geometry.Points[i] = positions[vertices[i].PositionIndex];

                if (vertices[i].NormalIndex != -1)
                    geometry.Normals[i] = normals[vertices[i].NormalIndex];

                if (vertices[i].TexcoordIndex != -1)
                    geometry.TexCoords[i] = texCoords[vertices[i].TexcoordIndex];
            }

            return geometry;
        }

        private static int[] RemoveDuplicates<T>(
            Dae.IndexedInput input,
            List<T> list,
            Dictionary<T, int> index,
            Func<Dae.Source, int, T> elementReader)
        {
            var indices = new int[input.Indices.Count];

            for (int i = 0; i < indices.Length; i++)
            {
                var v = elementReader(input.Source, input.Indices[i]);

                if (!index.TryGetValue(v, out indices[i]))
                {
                    indices[i] = list.Count;
                    list.Add(v);
                    index.Add(v, indices[i]);
                }
            }

            return indices;
        }

        private static Vector3[] GenerateNormals(List<Vector3> positions, int[] triangleList, bool flatNormals)
        {
            var autoNormals = new Vector3[positions.Count];

            if (!flatNormals)
            {
                for (int i = 0; i < triangleList.Length; i += 3)
                {
                    Vector3 p0 = positions[triangleList[i + 0]];
                    Vector3 p1 = positions[triangleList[i + 1]];
                    Vector3 p2 = positions[triangleList[i + 2]];

                    Vector3 e1 = p1 - p0;
                    Vector3 e2 = p2 - p0;

                    Vector3 faceNormal = Vector3.Cross(e1, e2);
                    float weight = FMath.Atan2(faceNormal.Length(), Vector3.Dot(e1, e2));
                    faceNormal = Vector3.Normalize(faceNormal) * weight;

                    for (int j = 0; j < 3; j++)
                        autoNormals[triangleList[i + j]] += faceNormal;
                }

                for (int i = 0; i < autoNormals.Length; i++)
                    autoNormals[i].Normalize();
            }

            return autoNormals;
        }

        private static int[] GenerateShell(List<Vector3> positions, int[] positionIndices, Vector3[] normals, float offset)
        {
            int positionCount = positions.Count;

            for (int i = 0; i < positionCount; i++)
                positions.Add(positions[i] + normals[i] * offset);

            var shellIndices = new int[positionIndices.Length];

            for (int i = 0; i < positionIndices.Length; i += 3)
            {
                shellIndices[i + 0] = positionIndices[i + 2] + positionCount;
                shellIndices[i + 1] = positionIndices[i + 1] + positionCount;
                shellIndices[i + 2] = positionIndices[i + 0] + positionCount;
            }

            return shellIndices;
        }
    }
}