Algoritmo para crear esferas?

¿Alguien tiene un algoritmo para crear una esfera de procedimiento con lacantidad de líneas de latitud, locantidad de líneas de longitud y un radio de r? Lo necesito para trabajar con Unity, por lo que las posiciones de los vértices necesitan ser definidas y luego, los triángulos definidos a través de índices ( más información ).

EDITAR

Logré que el código funcionara en unidad. Pero creo que podría haber hecho algo mal. Cuando enciendo detailLevel, Todo lo que hace es agregar más vértices y polígonos sin moverlos. ¿Olvidé algo?

EDITAR 2

Traté de escalar la malla a lo largo de sus niveles normales. Esto es lo que conseguí. Creo que me estoy perdiendo algo. ¿Se supone que debo escalar solo ciertas normales?

Para obtener algo como esto:

Cree un icosaedro (sólido regular de 20 lados) y subdivida las caras para obtener una esfera (vea el código a continuación).

La idea es básicamente:

• Crea un n-hedron regular (un sólido donde cada cara sea del mismo tamaño). Utilizo un icosaedro porque es el sólido con la mayor cantidad de caras donde cada cara es del mismo tamaño. (Hay una prueba de eso en algún lugar. Siéntase libre de Google si tiene curiosidad). Esto le dará una esfera donde casi todas las caras son del mismo tamaño, lo que facilita un poco la textura.

• Subdivida cada cara en cuatro caras del mismo tamaño. Cada vez que haces esto, cuadruplicará el número de caras en el modelo.

  ///      i0
  ///     /  \
  ///    m02-m01
  ///   /  \ /  \
  /// i2---m12---i1
  

i0, i1y i2son los vértices del triángulo original. (En realidad, los índices en el búfer de vértices, pero ese es otro tema). m01es el punto medio del borde (i0,i1), m12 es el punto medio del borde (i1,12)y m02es, obviamente, el punto medio del borde (i0,i2).

Siempre que subdivida una cara, asegúrese de no crear vértices duplicados. Cada punto medio será compartido por otra cara de origen (ya que los bordes se comparten entre caras). El código siguiente lo explica manteniendo un diccionario de puntos medios nombrados que se han creado y devolviendo el índice de un punto medio creado previamente cuando está disponible en lugar de crear uno nuevo.

• Repita hasta que haya alcanzado el número deseado de caras para su cubo.

• Cuando termines, normaliza todos los vértices para suavizar la superficie. Si no haces esto, obtendrás un icosaedro de mayor resolución en lugar de una esfera.

• Voila! Ya terminaste Convertir los tampones de vector y el índice resultante en una VertexBuffery IndexBuffer, y dibujar con Device.DrawIndexedPrimitives().

Esto es lo que usaría en su clase "Esfera" para crear el modelo (tipos de datos XNA y C #, pero debería ser bastante claro):

        var vectors = new List<Vector3>();
        var indices = new List<int>();

        GeometryProvider.Icosahedron(vectors, indices);

        for (var i = 0; i < _detailLevel; i++)
            GeometryProvider.Subdivide(vectors, indices, true);

        /// normalize vectors to "inflate" the icosahedron into a sphere.
        for (var i = 0; i < vectors.Count; i++)
            vectors[i]=Vector3.Normalize(vectors[i]);

Y la GeometryProviderclase

public static class GeometryProvider
{

    private static int GetMidpointIndex(Dictionary<string, int> midpointIndices, List<Vector3> vertices, int i0, int i1)
    {

        var edgeKey = string.Format("{0}_{1}", Math.Min(i0, i1), Math.Max(i0, i1));

        var midpointIndex = -1;

        if (!midpointIndices.TryGetValue(edgeKey, out midpointIndex))
        {
            var v0 = vertices[i0];
            var v1 = vertices[i1];

            var midpoint = (v0 + v1) / 2f;

            if (vertices.Contains(midpoint))
                midpointIndex = vertices.IndexOf(midpoint);
            else
            {
                midpointIndex = vertices.Count;
                vertices.Add(midpoint);
                midpointIndices.Add(edgeKey, midpointIndex);
            }
        }


        return midpointIndex;

    }

    /// <remarks>
    ///      i0
    ///     /  \
    ///    m02-m01
    ///   /  \ /  \
    /// i2---m12---i1
    /// </remarks>
    /// <param name="vectors"></param>
    /// <param name="indices"></param>
    public static void Subdivide(List<Vector3> vectors, List<int> indices, bool removeSourceTriangles)
    {
        var midpointIndices = new Dictionary<string, int>();

        var newIndices = new List<int>(indices.Count * 4);

        if (!removeSourceTriangles)
            newIndices.AddRange(indices);

        for (var i = 0; i < indices.Count - 2; i += 3)
        {
            var i0 = indices[i];
            var i1 = indices[i + 1];
            var i2 = indices[i + 2];

            var m01 = GetMidpointIndex(midpointIndices, vectors, i0, i1);
            var m12 = GetMidpointIndex(midpointIndices, vectors, i1, i2);
            var m02 = GetMidpointIndex(midpointIndices, vectors, i2, i0);

            newIndices.AddRange(
                new[] {
                    i0,m01,m02
                    ,
                    i1,m12,m01
                    ,
                    i2,m02,m12
                    ,
                    m02,m01,m12
                }
                );

        }

        indices.Clear();
        indices.AddRange(newIndices);
    }

    /// <summary>
    /// create a regular icosahedron (20-sided polyhedron)
    /// </summary>
    /// <param name="primitiveType"></param>
    /// <param name="size"></param>
    /// <param name="vertices"></param>
    /// <param name="indices"></param>
    /// <remarks>
    /// You can create this programmatically instead of using the given vertex 
    /// and index list, but it's kind of a pain and rather pointless beyond a 
    /// learning exercise.
    /// </remarks>

    /// note: icosahedron definition may have come from the OpenGL red book. I don't recall where I found it. 
    public static void Icosahedron(List<Vector3> vertices, List<int> indices)
    {

        indices.AddRange(
            new int[]
            {
                0,4,1,
                0,9,4,
                9,5,4,
                4,5,8,
                4,8,1,
                8,10,1,
                8,3,10,
                5,3,8,
                5,2,3,
                2,7,3,
                7,10,3,
                7,6,10,
                7,11,6,
                11,0,6,
                0,1,6,
                6,1,10,
                9,0,11,
                9,11,2,
                9,2,5,
                7,2,11 
            }
            .Select(i => i + vertices.Count)
        );

        var X = 0.525731112119133606f;
        var Z = 0.850650808352039932f;

        vertices.AddRange(
            new[] 
            {
                new Vector3(-X, 0f, Z),
                new Vector3(X, 0f, Z),
                new Vector3(-X, 0f, -Z),
                new Vector3(X, 0f, -Z),
                new Vector3(0f, Z, X),
                new Vector3(0f, Z, -X),
                new Vector3(0f, -Z, X),
                new Vector3(0f, -Z, -X),
                new Vector3(Z, X, 0f),
                new Vector3(-Z, X, 0f),
                new Vector3(Z, -X, 0f),
                new Vector3(-Z, -X, 0f) 
            }
        );


    }



}

Consideremos la definición paramétrica de una esfera:

donde theta y phi son dos ángulos incrementales, a los que nos referiremos como var ty var uy Rx, Ry y Rz son los radios independientes (radios) en las tres direcciones cartesianas, que, en el caso de una esfera, se definirán como una sola radio var rad.

Consideremos ahora el hecho de que el ...símbolo indica una iteración que sugiere el uso de un bucle. El concepto de stacksy rowses "cuántas veces iterará". Como cada iteración agrega el valor de to u, cuanto más iteraciones, menor es el valor, por lo tanto, más precisa es la curvatura de la esfera.

El 'dibujo esfera' condición previa de la función es tener los siguientes parámetros dados: int latitudes, int longitudes, float radius. Las condiciones de publicación (salida) son devolver o aplicar los vértices calculados. Dependiendo de cómo intente usar esto, la función podría devolver una matriz de vector3(vectores tridimensionales) o, si está utilizando algún tipo de OpenGL simple, antes de la versión 2.0, es posible que desee aplicar los vértices directamente al contexto.

NB Aplicar un vértice en openGL es llamar a la siguiente función glVertex3f(x, y, z). En el caso en el que almacenaríamos los vértices, agregaríamos uno nuevo vector3(x, y, z)para facilitar el almacenamiento.

Además, la forma en que solicitó que funcionara el sistema de latitud y longitud necesitaba un ajuste en la definición de la esfera (básicamente cambiando z e y), pero esto solo muestra que la definición es muy maleable y que usted es libre de cambiar Parámetros x, y y z para alterar la dirección en la que se dibuja la esfera (donde están las latitudes y longitudes).

Ahora veamos cómo vamos a hacer las latitudes y longitudes. Las latitudes están representadas por la variable u, iteran de 0 a 2π radianes (360 grados). Por lo tanto, podemos codificar su iteración así:

float latitude_increment = 360.0f / latitudes;

for (float u = 0; u < 360.0f; u += latitude_increment) {
    // further code ...
}

Ahora las longitudes están representadas por la variable te iteran de 0 a π (180 grados). por lo tanto, el siguiente código es similar al anterior:

float latitude_increment = 360.0f / latitudes;
float longitude_increment = 180.0f / longitudes;

for (float u = 0; u <= 360.0f; u += latitude_increment) {
    for (float t = 0; t <= 180.0f; t += longitude_increment) {
        // further code ...
    }
}

(Tenga en cuenta que los bucles son Incluido de ahí condición terminal, ya que el intervalo de integración paramétrica es de 0 a 2p Incluido . Obtendrá una esfera parcial si sus condiciones son no incluido).

Ahora, siguiendo la definición simple de la esfera, podemos derivar la definición variable de la siguiente manera (supongamos float rad = radius;):

float x = (float) (rad * Math.sin(Math.toRadians(t)) * Math.sin(Math.toRadians(u)));
float y = (float) (rad * Math.cos(Math.toRadians(t)));
float z = (float) (rad * Math.sin(Math.toRadians(t)) * Math.cos(Math.toRadians(u)));

¡Una advertencia más importante! En la mayoría de los casos, usará alguna forma de OpenGL, e incluso si no es así, es posible que aún deba hacerlo. Un objeto en tres dimensiones necesita varios vértices para ser definido. Esto generalmente se logra al proporcionar el siguiente vértice que es computable.

Exactamente cómo en la figura de arriba son las diferentes coordenadas x+∂y y+∂, podemos generar fácilmente otros tres vértices para cualquier uso deseado. Los otros vértices son (supongamos float rad = radius;):

float x = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.sin(Math.toRadians(u)));
float y = (float) (rad * Math.cos(Math.toRadians(t + longitude_increment)));
float z = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.cos(Math.toRadians(u)));

float x = (float) (rad * Math.sin(Math.toRadians(t)) * Math.sin(Math.toRadians(u + latitude_increment)));
float y = (float) (rad * Math.cos(Math.toRadians(t)));
float z = (float) (rad * Math.sin(Math.toRadians(t)) * Math.cos(Math.toRadians(u + latitude_increment)));

float x = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.sin(Math.toRadians(u + latitude_increment)));
float y = (float) (rad * Math.cos(Math.toRadians(t + longitude_increment)));
float z = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.cos(Math.toRadians(u + latitude_increment)));

Finalmente, aquí hay una función completa que devolvería todos los vértices de una esfera, y la segunda muestra una implementación de OpenGL del código (esta es una sintaxis de estilo C y no JavaScript, esto debería funcionar con todos los lenguajes de estilo C, incluido C # cuando se usa Unity).

static Vector3[] generateSphere(float radius, int latitudes, int longitudes) {

    float latitude_increment = 360.0f / latitudes;
    float longitude_increment = 180.0f / longitudes;

    // if this causes an error, consider changing the size to [(latitude + 1)*(longitudes + 1)], but this should work.
    Vector3[] vertices = new Vector3[latitude*longitudes];

    int counter = 0;

    for (float u = 0; u < 360.0f; u += latitude_increment) {
        for (float t = 0; t < 180.0f; t += longitude_increment) {

            float rad = radius;

            float x = (float) (rad * Math.sin(Math.toRadians(t)) * Math.sin(Math.toRadians(u)));
            float y = (float) (rad * Math.cos(Math.toRadians(t)));
            float z = (float) (rad * Math.sin(Math.toRadians(t)) * Math.cos(Math.toRadians(u)));

            vertices[counter++] = new Vector3(x, y, z);

        }
    }

    return vertices;

}

Código OpenGL:

static int createSphereBuffer(float radius, int latitudes, int longitudes) {

    int lst;

    lst = glGenLists(1);

    glNewList(lst, GL_COMPILE);
    {

        float latitude_increment = 360.0f / latitudes;
        float longitude_increment = 180.0f / longitudes;

        for (float u = 0; u < 360.0f; u += latitude_increment) {

            glBegin(GL_TRIANGLE_STRIP);

            for (float t = 0; t < 180.0f; t += longitude_increment) {

                float rad = radius;

                float x = (float) (rad * Math.sin(Math.toRadians(t)) * Math.sin(Math.toRadians(u)));
                float y = (float) (rad * Math.cos(Math.toRadians(t)));
                float z = (float) (rad * Math.sin(Math.toRadians(t)) * Math.cos(Math.toRadians(u)));

                vertex3f(x, y, z);

                float x1 = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.sin(Math.toRadians(u + latitude_increment)));
                float y1 = (float) (rad * Math.cos(Math.toRadians(t + longitude_increment)));
                float z1 = (float) (rad * Math.sin(Math.toRadians(t + longitude_increment)) * Math.cos(Math.toRadians(u + latitude_increment)));

                vertex3f(x1, y1, z1);

            }

            glEnd();

        }

    }
    glEndList()

    return lst;

}

// to render VVVVVVVVV

// external variable in main file
static int sphereList = createSphereBuffer(desired parameters)

// called by the main program
void render() {

    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    glCallList(sphereList);

    // any additional rendering and buffer swapping if not handled already.

}

PD: Puede que hayas notado esta afirmación rad = radius;. Esto permite que el radio se modifique en el bucle, en función de la ubicación o el ángulo. Esto significa que puede aplicar ruido a la esfera para endurecerla, haciendo que parezca más natural si el efecto deseado es similar al de un planeta. P.ejfloat rad = radius * noise[x][y][z];

Claude-Henry.

Creé algo como esto hace un tiempo para hacer una esfera de cubos, por diversión y ciencia. No es muy dificil. Básicamente, tomas una función que crea un círculo de vértices, luego pasas por los incrementos de altura que deseas crear círculos a cada altura en el radio requerido para hacer una esfera. Aquí he modificado el código para que no sea para cubos:

public static void makeSphere(float sphereRadius, Vector3f center, float heightStep, float degreeStep) {
    for (float y = center.y - sphereRadius; y <= center.y + sphereRadius; y+=heightStep) {
        double radius = SphereRadiusAtHeight(sphereRadius, y - center.y); //get the radius of the sphere at this height
        if (radius == 0) {//for the top and bottom points of the sphere add a single point
            addNewPoint((Math.sin(0) * radius) + center.x, y, (Math.cos(0) * radius) + center.z));
        } else { //otherwise step around the circle and add points at the specified degrees
            for (float d = 0; d <= 360; d += degreeStep) {
                addNewPoint((Math.sin(d) * radius) + center.x, y, (Math.cos(d) * radius) + center.z));
            }
        }
    }
}

public static double SphereRadiusAtHeight(double SphereRadius, double Height) {
    return Math.sqrt((SphereRadius * SphereRadius) - (Height * Height));
}

Ahora este código solo crearía puntos para la latitud. Sin embargo, casi puede usar el mismo código para hacer las líneas de longitud. Excepto que deberá rotar entre cada iteración y hacer un círculo completo en cada una degreeStep.

Lo sentimos, esta no es una respuesta completa o específica de Unity, pero espero que te ayude a comenzar.

¿No podría simplemente comenzar con una forma simple, podría ser una caja con una distancia de r desde el centro a la esquina? Para hacer una esfera más detallada, subdivida todos los polígonos y luego mueva los vértices a una distancia r del centro, haciendo que el vector pase por su posición actual.

Sigue repitiendo hasta que sea lo suficientemente esférico para tus gustos.

¿Realmente necesitas la geometría 3D o solo la forma?

Puedes hacer una esfera 'falsa' usando un solo quad. Simplemente ponga un círculo sobre él y sombree correctamente. Esto tiene la ventaja de que tendrá exactamente la resolución requerida, independientemente de la distancia a la cámara o la resolución.

Hay un tutorial aquí .

Aquí hay un código para cualquier número de vértices igualmente espaciados de una esfera, es como una cáscara de naranja que enrolla una línea de puntos alrededor de una esfera en espiral. luego, cómo unir los vértices depende de usted. puedes usar puntos vecinos en el bucle como 2 de cada triángulo y luego encontrar que el tercero sería un giro proporcional alrededor de la esfera más arriba o más abajo ... también puedes hacer triángulos por bucle y el vecino más cercano en él, alguien conoce una mejor manera?

var spherevertices = vector3 generic list...

public var numvertices= 1234;
var size = .03;  

function sphere ( N:float){//<--- N is the number of vertices i.e 123

var inc =  Mathf.PI  * (3 - Mathf.Sqrt(5));
var off = 2 / N;
for (var k = 0; k < (N); k++)
{
    var y = k * off - 1 + (off / 2);
    var r = Mathf.Sqrt(1 - y*y);
    var phi = k * inc;
    var pos = Vector3((Mathf.Cos(phi)*r*size), y*size, Mathf.Sin(phi)*r*size); 

    spherevertices   add pos...

}

};

Aunque David es absolutamente correcto en su respuesta, quiero ofrecer una perspectiva diferente.

Para mi tarea de generación de contenido procesal, miré (entre otras cosas) icosaedro versus esferas subdivididas más tradicionales. Mire estas esferas generadas procesalmente:

Ambas parecen esferas perfectamente válidas, ¿verdad? Bueno, echemos un vistazo a sus wireframes:

Wow, ¿qué pasó allí? ¡La versión de estructura metálica de la segunda esfera es tan densa que parece texturizada! Te contaré un secreto: la segunda versión es un icosaedro. Es una esfera casi perfecta, pero tiene un alto precio.

La Esfera 1 usa 31 subdivisiones en el eje xy 31 subdivisiones en el eje z, para un total de 3,844 caras.

La Esfera 2 usa 5 subdivisiones recursivas, para un total de 109,220 caras.

Pero bueno, eso no es realmente justo. Reduzcamos la calidad considerablemente:

La esfera 1 usa 5 subdivisiones en el eje xy 5 subdivisiones en el eje z, para un total de 100 caras.

La Esfera 2 usa 0 subdivisiones recursivas, para un total de 100 caras.

Usan la misma cantidad de caras, pero en mi opinión, la esfera de la izquierda se ve mejor. Se ve menos grumoso y mucho más redondo. Echemos un vistazo a cuántas caras generamos con ambos métodos.

Icosaedro

• Nivel 0 - 100 caras
• Nivel 1 - 420 caras
• Nivel 2 - 1,700 caras
• Nivel 3 - 6.820 caras
• Nivel 4 - 27,300 caras
• Nivel 5 - 109,220 caras

Esfera subdividida:

• YZ: 5-100 caras
• YZ: 10 - 400 caras
• YZ: 15-900 caras
• YZ: 20 - 1,600 caras
• YZ: 25 - 2,500 caras
• YZ: 30 - 3,600 caras

Como puede ver, el icosaedro aumenta en caras a una tasa exponencial, ¡a una tercera potencia! Eso es porque para cada triángulo, debemos subdividirlos en tres triángulos nuevos.

La verdad es que no necesitas la precisión que te dará un icosaedro. Porque ambos esconden un problema mucho más difícil: texturizar un plano 2D en una esfera 3D. Así es como se ve la parte superior:

En la esquina superior izquierda, puede ver la textura que se está utilizando. Casualmente, también se está generando procesalmente. (Oye, fue un curso sobre generación de procedimientos, ¿verdad?)

Se ve terrible, ¿verdad? Bueno, esto es tan bueno como va a ser. Obtuve las mejores calificaciones para mi mapeo de texturas, porque la mayoría de las personas ni siquiera lo hacen bien.

Entonces, por favor, considere usar coseno y seno para generar una esfera. Genera muchas menos caras para la misma cantidad de detalles.

El siguiente script creará un Icosaedro con n Polígonos ... base 12. También subdividirá los polígonos en mallas separadas y calculará el total de verts-duplicados y polígonos.

No pude encontrar nada similar, así que creé esto. Simplemente adjunte la secuencia de comandos a un GameObject y configure las subdivisiones en el Editor. Trabajando en la modificación de ruido a continuación.

/* Creates an initial Icosahedron with 12 vertices...
 * ...Adapted from https://medium.com/@peter_winslow/creating-procedural-icosahedrons-in-unity-part-1-df83ecb12e91
 * ...And a couple other Icosahedron C# for Unity scripts
 * 
 * Allows an Icosahedron to be created with multiple separate polygon meshes
 * I used a dictionary of Dictionary<int, List<Vector3>> to represent the 
 * Polygon index and the vertice index
 * polygon[0] corresponds to vertice[0]
 * so that all vertices in dictionary vertice[0] will correspond to the polygons in polygon[0]
 * 
 * If you need help understanding Dictionaries
 * https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx
 * 
 * --I used dictionaries because I didn't know what programming instrument to use, so there may be more
 * elegant or efficient ways to go about this.
 * 
 * Essentially int represents the index, and 
 * List<Vector3> represents the actual Vector3 Transforms of the triangle
 * OR List<Vector3> in the polygon dictionary will act as a reference to the indice/index number of the vertices
 * 
 * For example the polygon dictionary at key[0] will contain a list of Vector3's representing polygons
 * ... Vector3.x , Vector3.y, Vector3.z in the polygon list would represent the 3 indexes of the vertice[0] list
 * AKA the three Vector3 transforms that make up the triangle
 *    .
 *  ./_\.
 * 
 * Create a new GameObject and attach this script
 *  -The folders for the material and saving of the mesh data will be created automatically 
 *    -Line 374/448
 * 
 * numOfMainTriangles will represent the individual meshes created
 * numOfSubdivisionsWithinEachTriangle represents the number of subdivisions within each mesh
 * 
 * Before running with Save Icosahedron checked be aware that it can take several minutes to 
 *   generate and save all the meshes depending on the level of divisions
 * 
 * There may be a faster way to save assets - Line 430 - AssetDatabase.CreateAsset(asset,path);
 * */

using System.Collections.Generic;
using UnityEngine;
using UnityEditor;

public class UnityIcosahedronGenerator : MonoBehaviour {
    IcosahedronGenerator icosahedron;
    public const int possibleSubDivisions = 7;
    public static readonly int[] supportedChunkSizes = { 20, 80, 320, 1280, 5120, 20480, 81920};

    [Range(0, possibleSubDivisions - 1)]
    public int numOfMainTriangles = 0;
    [Range(0,possibleSubDivisions - 1)]
    public int numOfSubdivisionsWithinEachTriangle = 0;
    public bool saveIcosahedron = false;

    // Use this for initialization
    void Start() {
        icosahedron = ScriptableObject.CreateInstance<IcosahedronGenerator>();

        // 0 = 12 verts, 20 tris
        icosahedron.GenBaseIcosahedron();
        icosahedron.SeparateAllPolygons();

        // 0 = 12 verts, 20 tris - Already Generated with GenBaseIcosahedron()
        // 1 = 42 verts, 80 tris
        // 2 = 162 verts, 320 tris
        // 3 = 642 verts, 1280 tris
        // 5 = 2562 verts, 5120 tris
        // 5 = 10242 verts, 20480 tris
        // 6 = 40962verts, 81920 tris
        if (numOfMainTriangles > 0) {
            icosahedron.Subdivide(numOfMainTriangles);
        }
        icosahedron.SeparateAllPolygons();

        if (numOfSubdivisionsWithinEachTriangle > 0) {
            icosahedron.Subdivide(numOfSubdivisionsWithinEachTriangle);
        }

        icosahedron.CalculateMesh(this.gameObject, numOfMainTriangles,numOfSubdivisionsWithinEachTriangle, saveIcosahedron);
        icosahedron.DisplayVertAndPolygonCount();
    }
}

public class Vector3Dictionary {
    public List<Vector3> vector3List;
    public Dictionary<int, List<Vector3>> vector3Dictionary;

    public Vector3Dictionary() {
        vector3Dictionary = new Dictionary<int, List<Vector3>>();
        return;
    }

    public void Vector3DictionaryList(int x, int y, int z) {
        vector3List = new List<Vector3>();

        vector3List.Add(new Vector3(x, y, z));
        vector3Dictionary.Add(vector3Dictionary.Count, vector3List);

        return;
    }

    public void Vector3DictionaryList(int index, Vector3 vertice) {
        vector3List = new List<Vector3>();

        if (vector3Dictionary.ContainsKey(index)) {
            vector3List = vector3Dictionary[index];
            vector3List.Add(vertice);
            vector3Dictionary[index] = vector3List;
        } else {
            vector3List.Add(vertice);
            vector3Dictionary.Add(index, vector3List);
        }

        return;
    }

    public void Vector3DictionaryList(int index, List<Vector3> vertice, bool list) {
        vector3List = new List<Vector3>();

        if (vector3Dictionary.ContainsKey(index)) {
            vector3List = vector3Dictionary[index];
            for (int a = 0; a < vertice.Count; a++) {
                vector3List.Add(vertice[a]);
            }
            vector3Dictionary[index] = vector3List;
        } else {
            for (int a = 0; a < vertice.Count; a++) {
                vector3List.Add(vertice[a]);
            }
            vector3Dictionary.Add(index, vector3List);
        }

        return;
    }

    public void Vector3DictionaryList(int index, int x, int y, int z) {
        vector3List = new List<Vector3>();

        if (vector3Dictionary.ContainsKey(index)) {
            vector3List = vector3Dictionary[index];
            vector3List.Add(new Vector3(x, y, z));
            vector3Dictionary[index] = vector3List;
        } else {
            vector3List.Add(new Vector3(x, y, z));
            vector3Dictionary.Add(index, vector3List);
        }

        return;
    }

    public void Vector3DictionaryList(int index, float x, float y, float z, bool replace) {
        if (replace) {
            vector3List = new List<Vector3>();

            vector3List.Add(new Vector3(x, y, z));
            vector3Dictionary[index] = vector3List;
        }

        return;
    }
}

public class IcosahedronGenerator : ScriptableObject {
    public Vector3Dictionary icosahedronPolygonDict;
    public Vector3Dictionary icosahedronVerticeDict;
    public bool firstRun = true;

    public void GenBaseIcosahedron() {
        icosahedronPolygonDict = new Vector3Dictionary();
        icosahedronVerticeDict = new Vector3Dictionary();

        // An icosahedron has 12 vertices, and
        // since it's completely symmetrical the
        // formula for calculating them is kind of
        // symmetrical too:

        float t = (1.0f + Mathf.Sqrt(5.0f)) / 2.0f;

        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(-1, t, 0).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(1, t, 0).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(-1, -t, 0).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(1, -t, 0).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(0, -1, t).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(0, 1, t).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(0, -1, -t).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(0, 1, -t).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(t, 0, -1).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(t, 0, 1).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(-t, 0, -1).normalized);
        icosahedronVerticeDict.Vector3DictionaryList(0, new Vector3(-t, 0, 1).normalized);

        // And here's the formula for the 20 sides,
        // referencing the 12 vertices we just created.
        // Each side will be placed in it's own dictionary key.
        // The first number is the key/index, and the next 3 numbers reference the vertice index
        icosahedronPolygonDict.Vector3DictionaryList(0, 0, 11, 5);
        icosahedronPolygonDict.Vector3DictionaryList(1, 0, 5, 1);
        icosahedronPolygonDict.Vector3DictionaryList(2, 0, 1, 7);
        icosahedronPolygonDict.Vector3DictionaryList(3, 0, 7, 10);
        icosahedronPolygonDict.Vector3DictionaryList(4, 0, 10, 11);
        icosahedronPolygonDict.Vector3DictionaryList(5, 1, 5, 9);
        icosahedronPolygonDict.Vector3DictionaryList(6, 5, 11, 4);
        icosahedronPolygonDict.Vector3DictionaryList(7, 11, 10, 2);
        icosahedronPolygonDict.Vector3DictionaryList(8, 10, 7, 6);
        icosahedronPolygonDict.Vector3DictionaryList(9, 7, 1, 8);
        icosahedronPolygonDict.Vector3DictionaryList(10, 3, 9, 4);
        icosahedronPolygonDict.Vector3DictionaryList(11, 3, 4, 2);
        icosahedronPolygonDict.Vector3DictionaryList(12, 3, 2, 6);
        icosahedronPolygonDict.Vector3DictionaryList(13, 3, 6, 8);
        icosahedronPolygonDict.Vector3DictionaryList(14, 3, 8, 9);
        icosahedronPolygonDict.Vector3DictionaryList(15, 4, 9, 5);
        icosahedronPolygonDict.Vector3DictionaryList(16, 2, 4, 11);
        icosahedronPolygonDict.Vector3DictionaryList(17, 6, 2, 10);
        icosahedronPolygonDict.Vector3DictionaryList(18, 8, 6, 7);
        icosahedronPolygonDict.Vector3DictionaryList(19, 9, 8, 1);

        return;
    }

    public void SeparateAllPolygons(){
        // Separates all polygons and vertex keys/indicies into their own key/index
        // For example if the numOfMainTriangles is set to 2,
        // This function will separate each polygon/triangle into it's own index
        // By looping through all polygons in each dictionary key/index

        List<Vector3> originalPolygons = new List<Vector3>();
        List<Vector3> originalVertices = new List<Vector3>();
        List<Vector3> newVertices = new List<Vector3>();
        Vector3Dictionary tempIcosahedronPolygonDict = new Vector3Dictionary();
        Vector3Dictionary tempIcosahedronVerticeDict = new Vector3Dictionary();

        // Cycles through the polygon list
        for (int i = 0; i < icosahedronPolygonDict.vector3Dictionary.Count; i++) {
            originalPolygons = new List<Vector3>();
            originalVertices = new List<Vector3>();

            // Loads all the polygons in a certain index/key
            originalPolygons = icosahedronPolygonDict.vector3Dictionary[i];

            // Since the original script was set up without a dictionary index
            // It was easier to loop all the original triangle vertices into index 0
            // Thus the first time this function runs, all initial vertices will be 
            // redistributed to the correct indicies/index/key

            if (firstRun) {
                originalVertices = icosahedronVerticeDict.vector3Dictionary[0];
            } else {
                // i - 1 to account for the first iteration of pre-set vertices
                originalVertices = icosahedronVerticeDict.vector3Dictionary[i];
            }

            // Loops through all the polygons in a specific Dictionary key/index
            for (int a = 0; a < originalPolygons.Count; a++){
                newVertices = new List<Vector3>();

                int x = (int)originalPolygons[a].x;
                int y = (int)originalPolygons[a].y;
                int z = (int)originalPolygons[a].z;

                // Adds three vertices/transforms for each polygon in the list
                newVertices.Add(originalVertices[x]);
                newVertices.Add(originalVertices[y]);
                newVertices.Add(originalVertices[z]);

                // Overwrites the Polygon indices from their original locations
                // index (20,11,5) for example would become (0,1,2) to correspond to the
                // three new Vector3's added to the list.
                // In the case of this function there will only be 3 Vector3's associated to each dictionary key
                tempIcosahedronPolygonDict.Vector3DictionaryList(0, 1, 2);

                // sets the index to the size of the temp dictionary list
                int tempIndex = tempIcosahedronPolygonDict.vector3Dictionary.Count;
                // adds the new vertices to the corresponding same key in the vertice index
                // which corresponds to the same key/index as the polygon dictionary
                tempIcosahedronVerticeDict.Vector3DictionaryList(tempIndex - 1, newVertices, true);
            }
        }
        firstRun = !firstRun;

        // Sets the temp dictionarys as the main dictionaries
        icosahedronVerticeDict = tempIcosahedronVerticeDict;
        icosahedronPolygonDict = tempIcosahedronPolygonDict;
    }

    public void Subdivide(int recursions) {
        // Divides each triangle into 4 triangles, and replaces the Dictionary entry

        var midPointCache = new Dictionary<int, int>();
        int polyDictIndex = 0;
        List<Vector3> originalPolygons = new List<Vector3>();
        List<Vector3> newPolygons;

        for (int x = 0; x < recursions; x++) {
            polyDictIndex = icosahedronPolygonDict.vector3Dictionary.Count;
            for (int i = 0; i < polyDictIndex; i++) {
                newPolygons = new List<Vector3>();
                midPointCache = new Dictionary<int, int>();
                originalPolygons = icosahedronPolygonDict.vector3Dictionary[i];

                for (int z = 0; z < originalPolygons.Count; z++) {
                    int a = (int)originalPolygons[z].x;
                    int b = (int)originalPolygons[z].y;
                    int c = (int)originalPolygons[z].z;

                    // Use GetMidPointIndex to either create a
                    // new vertex between two old vertices, or
                    // find the one that was already created.
                    int ab = GetMidPointIndex(i,midPointCache, a, b);
                    int bc = GetMidPointIndex(i,midPointCache, b, c);
                    int ca = GetMidPointIndex(i,midPointCache, c, a);

                    // Create the four new polygons using our original
                    // three vertices, and the three new midpoints.
                    newPolygons.Add(new Vector3(a, ab, ca));
                    newPolygons.Add(new Vector3(b, bc, ab));
                    newPolygons.Add(new Vector3(c, ca, bc));
                    newPolygons.Add(new Vector3(ab, bc, ca));
                }
                // Replace all our old polygons with the new set of
                // subdivided ones.
                icosahedronPolygonDict.vector3Dictionary[i] = newPolygons;
            }
        }
        return;
    }

    int GetMidPointIndex(int polyIndex, Dictionary<int, int> cache, int indexA, int indexB) {
        // We create a key out of the two original indices
        // by storing the smaller index in the upper two bytes
        // of an integer, and the larger index in the lower two
        // bytes. By sorting them according to whichever is smaller
        // we ensure that this function returns the same result
        // whether you call
        // GetMidPointIndex(cache, 5, 9)
        // or...
        // GetMidPointIndex(cache, 9, 5)

        int smallerIndex = Mathf.Min(indexA, indexB);
        int greaterIndex = Mathf.Max(indexA, indexB);
        int key = (smallerIndex << 16) + greaterIndex;

        // If a midpoint is already defined, just return it.
        int ret;
        if (cache.TryGetValue(key, out ret))
            return ret;

        // If we're here, it's because a midpoint for these two
        // vertices hasn't been created yet. Let's do that now!
        List<Vector3> tempVertList = icosahedronVerticeDict.vector3Dictionary[polyIndex];

        Vector3 p1 = tempVertList[indexA];
        Vector3 p2 = tempVertList[indexB];
        Vector3 middle = Vector3.Lerp(p1, p2, 0.5f).normalized;

        ret = tempVertList.Count;
        tempVertList.Add(middle);
        icosahedronVerticeDict.vector3Dictionary[polyIndex] = tempVertList;

        cache.Add(key, ret);
        return ret;
    }

    public void CalculateMesh(GameObject icosahedron, int numOfMainTriangles, int numOfSubdivisionsWithinEachTriangle, bool saveIcosahedron) {
        GameObject meshChunk;
        List<Vector3> meshPolyList;
        List<Vector3> meshVertList;
        List<int> triList;

        CreateFolders(numOfMainTriangles, numOfSubdivisionsWithinEachTriangle);
        CreateMaterial();

        // Loads a material from the Assets/Resources/ folder so that it can be saved with the prefab later
        Material material = Resources.Load("BlankSphere", typeof(Material)) as Material;

        int polyDictIndex = icosahedronPolygonDict.vector3Dictionary.Count;

        // Used to assign the child objects as well as to be saved as the .prefab
        // Sets the name
        icosahedron.gameObject.name = "Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle;

        for (int i = 0; i < polyDictIndex; i++) {
            meshPolyList = new List<Vector3>();
            meshVertList = new List<Vector3>();
            triList = new List<int>();
            // Assigns the polygon and vertex indices
            meshPolyList = icosahedronPolygonDict.vector3Dictionary[i];
            meshVertList = icosahedronVerticeDict.vector3Dictionary[i];

            // Sets the child gameobject parameters
            meshChunk = new GameObject("MeshChunk");
            meshChunk.transform.parent = icosahedron.gameObject.transform;
            meshChunk.transform.localPosition = new Vector3(0, 0, 0);
            meshChunk.AddComponent<MeshFilter>();
            meshChunk.AddComponent<MeshRenderer>();
            meshChunk.GetComponent<MeshRenderer>().material = material;
            meshChunk.AddComponent<MeshCollider>();
            Mesh mesh = meshChunk.GetComponent<MeshFilter>().mesh;

            // Adds the triangles to the list
            for (int z = 0; z < meshPolyList.Count; z++) {
                triList.Add((int)meshPolyList[z].x);
                triList.Add((int)meshPolyList[z].y);
                triList.Add((int)meshPolyList[z].z);
            }

            mesh.vertices = meshVertList.ToArray();
            mesh.triangles = triList.ToArray();
            mesh.uv = new Vector2[meshVertList.Count];

            /*
            //Not Needed because all normals have been calculated already
            Vector3[] _normals = new Vector3[meshVertList.Count];
            for (int d = 0; d < _normals.Length; d++){
                _normals[d] = meshVertList[d].normalized;
            }
            mesh.normals = _normals;
            */

            mesh.normals = meshVertList.ToArray();

            mesh.RecalculateBounds();

            // Saves each chunk mesh to a specified folder
            // The folder must exist
            if (saveIcosahedron) {
                string sphereAssetName = "icosahedronChunk" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle + "_" + i + ".asset";
                AssetDatabase.CreateAsset(mesh, "Assets/Icosahedrons/Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle + "/" + sphereAssetName);
                AssetDatabase.SaveAssets();
            }
        }

        // Removes the script for the prefab save
        // Saves the prefab to a specified folder
        // The folder must exist
        if (saveIcosahedron) {
            DestroyImmediate(icosahedron.GetComponent<UnityIcosahedronGenerator>());
            PrefabUtility.CreatePrefab("Assets/Icosahedrons/Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle + "/Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle + ".prefab", icosahedron);
        }

        return;
    }

    void CreateFolders(int numOfMainTriangles, int numOfSubdivisionsWithinEachTriangle){
        // Creates the folders if they don't exist
        if (!AssetDatabase.IsValidFolder("Assets/Icosahedrons")) {
            AssetDatabase.CreateFolder("Assets", "Icosahedrons");
        }
        if (!AssetDatabase.IsValidFolder("Assets/Icosahedrons/Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle)) {
            AssetDatabase.CreateFolder("Assets/Icosahedrons", "Icosahedron" + numOfMainTriangles + "Recursion" + numOfSubdivisionsWithinEachTriangle);
        }
        if (!AssetDatabase.IsValidFolder("Assets/Resources")) {
            AssetDatabase.CreateFolder("Assets", "Resources");
        }

        return;
    }

    static void CreateMaterial() {
        if (Resources.Load("BlankSphere", typeof(Material)) == null) {
            // Create a simple material asset if one does not exist
            Material material = new Material(Shader.Find("Standard"));
            material.color = Color.blue;
            AssetDatabase.CreateAsset(material, "Assets/Resources/BlankSphere.mat");
        }

        return;
    }

    // Displays the Total Polygon/Triangle and Vertice Count
    public void DisplayVertAndPolygonCount(){
        List<Vector3> tempVertices;
        HashSet<Vector3> verticeHash = new HashSet<Vector3>();

        int polygonCount = 0;
        List<Vector3> tempPolygons;

        // Saves Vertices to a hashset to ensure no duplicate vertices are counted
        for (int a = 0; a < icosahedronVerticeDict.vector3Dictionary.Count; a++) {
            tempVertices = new List<Vector3>();
            tempVertices = icosahedronVerticeDict.vector3Dictionary[a];
            for (int b = 0; b < tempVertices.Count; b++) {
                verticeHash.Add(tempVertices[b]);
            }
        }

        for (int a = 0; a < icosahedronPolygonDict.vector3Dictionary.Count; a++) {
            tempPolygons = new List<Vector3>();
            tempPolygons = icosahedronPolygonDict.vector3Dictionary[a];
            for (int b = 0; b < tempPolygons.Count; b++) {
                polygonCount++;
            }
        }

        Debug.Log("Vertice Count: " + verticeHash.Count);
        Debug.Log("Polygon Count: " + polygonCount);

        return;
    }
}