Subdivided Octahedron Sphere (with Seam Fix)

//Copyright (C) 2012 Carsten Jørgensen
//Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
//associated documentation files (the "Software"), to deal in the Software without restriction, including
//without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to
//the following conditions:

//The above copyright notice and this permission notice shall be included in all copies or substantial
//portions of the Software.

//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
//LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
//NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
//WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
//SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace MyGame
{
    /// <summary>
    /// Generates a unit sphere, by subdividing an octahedron
    /// </summary>
    public class OctahedronSphere
    {
        /// <summary>
        /// The triangle class. A collection of 3 indices that represent a triangle.
        /// Could simply be replaced by int[] in its use, but it clarifies/prettifies the code a bit.
        /// </summary>
        private class Triangle
        {
            private int[] indices;
            public int this[int triIndex]
            {
                get { return indices[triIndex]; }
                set { indices[triIndex] = value; }
            }

            public Triangle(int v0, int v1, int v2)
            {
                indices = new int[] { v0, v1, v2 };
            }
        }

        #region Properties and Fields

        public int Tesselation { get; set; }

        protected VertexBuffer VertexBuffer { get; set; }
        protected IndexBuffer IndexBuffer { get; set; }
        protected VertexPositionTexture[] Vertices { get; set; }
        protected int[] Indices { get; set; }

        private List<Triangle> triangles;
        private List<Vector3> points;

        #endregion

        #region Constructors

        public OctahedronSphere() { }
        public OctahedronSphere(int tesselation)
        {
            Tesselation = tesselation;
        }

        #endregion

        /// <summary>
        /// Creates vertices and indices for a unit sphere by subdividing an octahedron
        /// </summary>
        public void Create(GraphicsDevice graphicsDevice)
        {
            //Create the points and triangles for the initial base octahedron
            CreateOctahedron();

            //Divide each triangle 4 times, each iteration (Tesselation = Iterations)
            for (int i = 0; i < Tesselation; i++)
            {
                List<Triangle> newtriangles = new List<Triangle>();
                foreach (Triangle triangle in triangles)
                {
                    //Adds 4 new triangles to the new collection:
                    newtriangles.AddRange(DivideTriangle(triangle));
                }
                triangles.Clear();
                triangles = newtriangles;
            }

            //2nd pass sets the Vertices and Indices for the primitive:
            SetMesh(graphicsDevice);
        }

        /// <summary>
        /// The 2nd pass. Runs through all triangles and adds the Vertices and Indices.
        /// </summary>
        private void SetMesh(GraphicsDevice graphicsDevice)
        {
            //Add the vertices based on the list of triangles:
            int cloneCount = (int)(1.0 / 2.0 * (Math.Pow(2, Tesselation + 2) - 2));
            Vertices = new VertexPositionTexture[points.Count + cloneCount];
            for (int i = 0; i < triangles.Count; i++)
            {
                //Adds vertices, and tacles seam issue:
                AddTriangleVertices(triangles[i]);
            }

            VertexBuffer = new VertexBuffer(graphicsDevice, typeof(VertexPositionTexture), Vertices.Length, BufferUsage.WriteOnly);
            VertexBuffer.SetData(Vertices);

            //Creates an array of indices based on the list of triangles:
            Indices = new int[triangles.Count * 3];
            for (int i = 0; i < triangles.Count; i++)
            {
                Indices[i * 3 + 0] = triangles[i][0];
                Indices[i * 3 + 1] = triangles[i][1];
                Indices[i * 3 + 2] = triangles[i][2];
            }

            IndexBuffer = new IndexBuffer(graphicsDevice, typeof(int), Indices.Length, BufferUsage.WriteOnly);
            IndexBuffer.SetData(Indices);
        }

        /// <summary>
        /// Draws the octahedron sphere immediately
        /// </summary>
        public void Draw(GraphicsDevice graphicsDevice, Effect effect)
        {
            //Set the Vertex and Index buffers created by SetMesh()
            graphicsDevice.SetVertexBuffer(VertexBuffer);
            graphicsDevice.Indices = IndexBuffer;
            graphicsDevice.RasterizerState = RasterizerState.CullNone;

            //Apply effect and draw:
            effect.CurrentTechnique.Passes[0].Apply();
            graphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, Vertices.Length, 0, Indices.Length / 3);
        }
        public void Draw(GraphicsDevice graphicsDevice, BasicEffect effect,
            Matrix world, Matrix view, Matrix projection)
        {
            effect.World = world;
            effect.View = view;
            effect.Projection = projection;

            Draw(graphicsDevice, effect);
        }

        #region Helpers

        /// <summary>
        /// Sets the starting points and triangles for the base octahedron
        /// </summary>
        private void CreateOctahedron()
        {
            //The 6 Octahedron vertices:
            points = new List<Vector3>() {
                new Vector3(0, 1, 0),
                new Vector3(1, 0, 0),
                new Vector3(0, 0, -1),
                new Vector3(-1, 0, 0),
                new Vector3(0, 0, 1),
                new Vector3(0,-1, 0)
            };

            //The 8 Octahedron triangles (indexed triangles)
            triangles = new List<Triangle>()
            {
                new Triangle(0,1,2),new Triangle(0,2,3),new Triangle(0,3,4),new Triangle(0,4,1),
                new Triangle(5,1,2),new Triangle(5,2,3),new Triangle(5,3,4),new Triangle(5,4,1)
            };
        }

        /// <summary>
        /// Divides a triangle in 4 smaller triangles, by connecting the centers of each edge.
        /// </summary>
        private Triangle[] DivideTriangle(Triangle triangle)
        {
            //Calculate the new points that's needed for creating additional triangles:
            Vector3[] newPoints = new Vector3[] {
                NormalizedEdgeCentroid(points[triangle[0]], points[triangle[1]]),
                NormalizedEdgeCentroid(points[triangle[1]], points[triangle[2]]),
                NormalizedEdgeCentroid(points[triangle[2]], points[triangle[0]])
            };

            //Runs through the new points to retrieve indices:
            int[] newIndices = new int[3];
            for (int i = 0; i < 3; i++)
            {
                //Finds index for this point:
                newIndices[i] = points.FindIndex(v => v == newPoints[i]);

                //If point does not exists, it will be added to the collection:
                if (newIndices[i] < 0)
                {
                    //The index is set to last point (last index = count - 1):
                    newIndices[i] = points.Count;
                    points.Add(newPoints[i]);
                }
            }

            //Return 4 subdivided triangles:
            return new Triangle[] {
                new Triangle(newIndices[0], newIndices[1], newIndices[2]),
                new Triangle(triangle[0], newIndices[0], newIndices[2]),
                new Triangle(triangle[1], newIndices[0], newIndices[1]),
                new Triangle(triangle[2], newIndices[1], newIndices[2])
            };
        }

        /// <summary>
        /// Adds vertices to the collection based on a triangle. Also corrects seam issue.
        /// </summary>
        private void AddTriangleVertices(Triangle triangle)
        {
            //Calculate texture coordinates for each vertex of this triangle:
            Vector2[] texCoord = new Vector2[] {
                MapUv(points[triangle[0]]),
                MapUv(points[triangle[1]]),
                MapUv(points[triangle[2]])
            };

            //Get the indices which is on the seam:
            int[] seamIndices = GetSeamIndices(texCoord);
            if (seamIndices != null)
            {
                for (int i = 0; i < seamIndices.Length; i++)
                {
                    int triangleIndex = seamIndices[i];
                    int currentIndex = triangle[triangleIndex];
                    Vector3 clone = points[currentIndex];

                    //Checks if duplicate allready exists (begins search after the current index):
                    int cloneIndex = points.FindIndex(currentIndex + 1, x => x == clone);
                    if (cloneIndex == -1)
                    {
                        points.Add(clone);
                        cloneIndex = points.Count - 1;
                    }

                    //Change the triangle, to use the new index, and adjust texture U value to 1:
                    triangle[triangleIndex] = cloneIndex;
                    texCoord[triangleIndex].X = 1;
                }
            }

            //Adds the vertices:
            for (int i = 0; i < 3; i++)
            {
                Vertices[triangle[i]] = new VertexPositionTexture()
                {
                    Position = points[triangle[i]],
                    TextureCoordinate = texCoord[i]
                };
            }
        }

        /// <summary>
        /// Returns how many (if any) of the provided coords are located on the seam (U = 0),
        /// while the remainding of the coords are closer to 1 than 0.
        /// </summary>
        private int[] GetSeamIndices(Vector2[] texCoords)
        {
            List<int> seamIndices = new List<int>();

            //Loop through the coords
            for (int i = 0; i < 3; i++)
            {
                //Add index if U has a value of 0:
                if (texCoords[i].X == 0)
                    seamIndices.Add(i);

                //If at any point, a texcoord is on the first half of the sphere, this is not a seam triangle:
                else if (texCoords[i].X < 0.5f)
                    return null;
            }

            return seamIndices.Count > 0 ? seamIndices.ToArray() : null;
        }

        /// <summary>
        /// Returns the normalized center of a line
        /// </summary>
        private Vector3 NormalizedEdgeCentroid(Vector3 p0, Vector3 p1)
        {
            return Vector3.Normalize(new Vector3(
                (p0.X + p1.X) / 2,
                (p0.Y + p1.Y) / 2,
                (p0.Z + p1.Z) / 2));
        }

        /// <summary>
        /// UV maps a normalized Vector3.
        /// </summary>
        private Vector2 MapUv(Vector3 p)
        {
            float u = 0.5f - ((float)Math.Atan2(p.Z, p.X) / MathHelper.TwoPi);
            float v = 0.5f - 2.0f * ((float)Math.Asin(p.Y) / MathHelper.TwoPi);

            return new Vector2(u, v);
        }

        #endregion
    }
}