28
\$\begingroup\$

Does anyone have an algorithm for creating a sphere proceduraly with la amount of latitude lines, lo amount of longitude lines, and a radius of r? I need it to work with Unity, so the vertex positions need to be defined and then, the triangles defined via indexes (more info).


EDIT

enter image description here

I managed to get the code working in unity. But I think I might have done something wrong. When I turn up the detailLevel, All it does is add more vertices and polygons without moving them around. Did I forget something?


EDIT 2

enter image description here

I tried scaling the mesh along its normals. This is what I got. I think I'm missing something. Am I supposed to only scale certain normals?

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Why don't you look at how existing open source implementations do it? have a look at how Three.js does it using meshes, for example. \$\endgroup\$
    – brice
    Jun 28, 2012 at 15:54
  • 3
    \$\begingroup\$ As a small note: unless you have to do latitude/longitude you almost certainly don't want to, because the triangles you get will be much further from uniform than those you get with other methods. (Compare the triangles near the north pole with those near the equator: you're using the same number of triangles to get around one line of latitude in either case, but near the pole that line of latitude has very small circumference whereas at the equator it's the full circumference of your globe.) Techniques like the one in David Lively's answer are generally much better. \$\endgroup\$ Jun 28, 2012 at 20:31
  • 1
    \$\begingroup\$ You're not normalizing the vertex positions after subdividing. I didn't include that part in my example. Normalizing makes them all equidistant from the center, which creates the curve approximation you're looking for. \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 3:37
  • \$\begingroup\$ Think inflating a balloon at the center of the icosahedron. As the balloon pushes the mesh our, it matches the shape of the balloon (sphere). \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 3:45
  • 4
    \$\begingroup\$ "Normalizing" means setting a vector's length to 1. You need to do something like vertices[i] = normalize(vertices[i]). Incidentally, this also gives you your new, correct normals, so you should do normals[i] = vertices[i] afterwards. \$\endgroup\$ Jun 29, 2012 at 14:54

8 Answers 8

31
\$\begingroup\$

To get something like this:

enter image description here

Create an icosahedron (20-sided regular solid) and subdivide the faces to get a sphere (see code below).

The idea is basically:

  • Create a regular n-hedron (a solid where every face is the same size and every edge is the same length). I use an icosahedron because it's the regular solid with the greatest number of faces. (There's a proof for that somewhere out there. Feel free to Google if you're really curious.) This will give you a sphere where nearly every face is the same size, making texturing a little easier.

enter image description here

  • Subdivide each face into four equally-sized faces. Each time you do this, it'll quadruple the number of faces in the model.

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

i0, i1, and i2 are the vertices of the original triangle. (Actually, indices into the vertex buffer, but that's another topic). m01 is the midpoint of the edge (i0,i1), m12 is the midpoint of the edge (i1,12), and m02 is, obviously, the midpoint of the edge (i0,i2).

Whenever you subdivide a face, make sure that you don't create duplicate vertices. Each midpoint will be shared by one other source face (since the edges are shared between faces). The code below accounts for that by maintaining a dictionary of named midpoints that have been created, and returning the index of a previously created midpoint when it's available rather than creating a new one.

  • Repeat until you've reached the desired number of faces for your cube.

  • When you're done, normalize all of the vertices to smooth out the surface. If you don't do this, you'll just get a higher-res icosahedron instead of a sphere.

  • Voila! You're done. Convert the resulting vector and index buffers into a VertexBuffer and IndexBuffer, and draw with Device.DrawIndexedPrimitives().

Here's what you'd use in your "Sphere" class to create the model (XNA datatypes and C#, but it should be pretty clear):

        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]);

And the GeometryProvider class

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


    }



}
\$\endgroup\$
8
  • \$\begingroup\$ Great answer. Thanks. I can't tell but is this unity code? Oh, and the lat/long doesn't matter, as long as I can set the resolution. \$\endgroup\$
    – Daniel
    Jun 28, 2012 at 16:02
  • \$\begingroup\$ It's not Unity (XNA) but it'll give you the vertex coordinates and index list. Replace Vector3 with whatever the Unity equivalent is. You set the resolution by adjusting the number of Subdivide iterations. Each loop multiplies the number of faces by 4. 2 or 3 iterations will give a nice sphere. \$\endgroup\$
    – 3Dave
    Jun 28, 2012 at 16:09
  • \$\begingroup\$ Ah I see. It's almost identical to Unity C#. Just a few questions... Why when the indices are defined, you put them inside of an int array? And what does the .Select(i => i + vertices.Count) do? \$\endgroup\$
    – Daniel
    Jun 29, 2012 at 0:23
  • \$\begingroup\$ The .Select(i => i + vertices.Count) doesn't work for me at all. Is it a XNA only feature? \$\endgroup\$
    – Daniel
    Jun 29, 2012 at 2:30
  • 1
    \$\begingroup\$ Make sure you're including 'using System.Linq' as it defines.Select, etc. \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 3:37
6
\$\begingroup\$

Let us consider the parametric definition of a sphere:

parametric definition of a sphere

where theta and phi are two incrementing angles, that we will refer to as var t and var u and Rx, Ry and Rz are the independent radii (radiuses) in all three cartesian directions, which, in the case of a sphere, will be defined as one single radius var rad.

Let us now consider the fact that the ... symbol indicates an iteration which hints the use of a loop. The concept of stacks and rows is "how many times will you iterate". Since each iteration adds the the value of t or u, the more iterations, the smaller the value is, therefore the more precise the curvature of the sphere is.

The 'sphere drawing' function's precondition is to have the following given parameters: int latitudes, int longitudes, float radius. The post conditions (output) is to return, or apply the calculated vertices. Depending on how you intend to use this, the function could return an array of vector3 (three dimensional vectors) or, if you are using some sort of simple OpenGL, prior to version 2.0, you might want to apply the vertices to the context directly.

N.B. Applying a vertex in openGL is calling the following function glVertex3f(x, y, z). In the case where we would store the vertices, we would add an new vector3(x, y, z) for easy storage.

Also, the way you requested the latitude and longitude system to work needed an adjustment to the definition of the sphere (basically switching z and y), but this just shows that the definition is very malleable, and that you are free to switch around the x, y and z parameters to alter the direction in which the sphere is drawn (where the latitudes and longitudes are).

Now let us look at how we are going to do the latitudes and longitudes. Latitudes are represented by the variable u, they iterate from 0 to 2π radians (360 degrees). We can therefore code its iteration like so:

float latitude_increment = 360.0f / latitudes;

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

Now the longitudes are represented by the variable t and iterates for 0 to π (180 degrees). therefore the following code looks similar to the previous one:

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

(Note that loops are Inclusive of there terminal condition, because the interval for parametric integration is from 0 to 2π Inclusive. you will get a partial sphere if your conditions are non-inclusive.)

Now, following the simple definition of the sphere we can derive the variable definition as follows (assume 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)));

One more important warning! In most cases you will be using some form of OpenGL, and even if not so, the you might still need to do this. An object in three dimensional needs several vertices to be defined. This is generally achieved by providing the next vertex that is computable.

how multiple vertices are used to define a (primitive) shape

Just how in the figure above the different coordinates are x+∂ and y+∂, we can easily generate three other vertices for any desired use. The other vertices are (assume 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)));

Finally, here is a working full function that would return all vertices of a sphere, and the second one shows a working OpenGL implementation of the code (this is C-style syntax and not JavaScript, this should work with all C-style languages, including C# when using 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;

}

OpenGL code:

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.

}

P.S. You may have noticed this statement rad = radius;. This allows the radius to be modified in the loop, based on the location or the angle. This means that you can apply noise to the sphere to roughen it, making it look more natural if the desired effect is a planet-like one. E.g. float rad = radius * noise[x][y][z];

Claude-Henry.

\$\endgroup\$
3
  • \$\begingroup\$ The line ` float z = (float) (rad * Math.sin(Math.toRadians(t)) * Math.cos(Math.toRadians(u)));` is incorrect. You've already calculated an X,Y with a hypotenuse of rad. Now you're making that one leg of a triangle, and implying that the hypotenuse of said triangle is also rad. This effectively gives you a radius of rad * sqrt(2). \$\endgroup\$
    – 3Dave
    Nov 10, 2016 at 21:38
  • \$\begingroup\$ @DavidLively thanks for pointing it out, i wrote this a while back so I'm not surprised if its bad or even outright wrong. \$\endgroup\$ Nov 11, 2016 at 18:19
  • \$\begingroup\$ it's always fun when I find a mistake in one of MY posts from years ago. It happens. :) \$\endgroup\$
    – 3Dave
    Nov 14, 2016 at 14:19
4
\$\begingroup\$

I created something like this a while back to make a sphere of cubes, for fun and science. It's not too hard. Basically, you take a function that creates a circle of vertices, then step through the height increments you want creating circles at each height at the radius required to make a sphere. Here I've modified the code to not be for cubes:

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

Now this code would just create points for the latitude. However, you can almost use the same code to make the longitude lines. Except you'll need to rotate between each iteration and make a full circle at each degreeStep.

Sorry this is not a complete answer or Unity specific, but hopefully it'll get you started.

\$\endgroup\$
2
  • \$\begingroup\$ This is pretty good if you need a lat/long sphere, but you could simplify it a little by working in spherical coordinates until the last step. \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 21:39
  • 1
    \$\begingroup\$ Thanks @David. I agree, if I get around to writing up a version using spherical coords, I'll post it here. \$\endgroup\$
    – House
    Jun 29, 2012 at 22:17
3
\$\begingroup\$

Couldn't you just start with a simple shape, could be a box with r distance from center to corner. To make a more detailed sphere, subdivide all the polygons and then move the vertices out to r distance from the center, having the vector going through their current position.

Keep repeating until spherical enough for your tastes.

\$\endgroup\$
4
  • \$\begingroup\$ This is essentially the same as the icosahedral approach, only with a different starting shape. One advantage of starting with a cube that I don't think has been mentioned: it's substantially easier to build decent UV maps for because you can use a cubemap and know that your texture seams will align perfectly with edges in your sphere mesh. \$\endgroup\$ Jun 29, 2012 at 16:27
  • \$\begingroup\$ @StevenStadnicki the only issue I have with cubes is that the faces tend to wind up being very different sizes after a few subdivisons. \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 19:47
  • \$\begingroup\$ @DavidLively That depends a lot on how you subdivide - if you chop the square faces of your cube into an even grid and then project outward/normalize then that's true, but if you grid up your faces non-uniformly then you can actually make the projection be evenly spaced along the arcs of the edges; that turns out to work pretty well. \$\endgroup\$ Jun 29, 2012 at 20:50
  • \$\begingroup\$ @StevenStadnicki nifty! \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 21:31
2
\$\begingroup\$

Do you actually need the 3D geometry or just the shape?

You can make a 'fake' sphere using a single quad. Just put a circle on it and shade it correctly. This has the advantage that it will have exactly the resolution required regardless of the distance to the camera or resolution.

There's a tutorial here.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice hack, but fails if you need to texture it. \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 21:40
  • \$\begingroup\$ @DavidLively It should be possible to calculate the texture coordinates per-pixel based on it's rotation unless you need to texture polygons individually. \$\endgroup\$ Jul 1, 2012 at 2:02
  • \$\begingroup\$ @DavidCBishop You'd have to account for the "lensing" of the surface - texel coords are squeezed close to the circle border due to perspective - at which point you're faking rotation. Also, that involves moving a lot more work into the pixel shader that could be performed in the vertex shader (and we all know that VS's are a lot cheaper!). \$\endgroup\$
    – 3Dave
    Aug 6, 2012 at 21:53
0
\$\begingroup\$

here is some code for any number of equally spaced vertices of a sphere, its like an orange peel it winds a line of dots around a sphere in a spiral. afterwards, how you join the vertices is up to you. you can use neighbour dots in the loop as 2 of each triangle and then find the third would be a proportional one twist around the sphere higher up or lower down... you can also do triangles by loop and nearest neighbour on it, does someone know a better way?

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...

}

};

\$\endgroup\$
-1
\$\begingroup\$

Although David is absolutely correct in his answer, I want to offer a different perspective.

For my assignment for procedural content generation, I looked at (among other things) icosahedron versus more traditional subdivided spheres. Look at these procedurally generated spheres:

Awesome spheres

Both look like perfectly valid spheres, right? Well, let's look at their wireframes:

Wow that's dense

Wow, what happened there? The wireframe version of the second sphere is so dense that it looks textured! I'll let you in on a secret: the second version is an icosahedron. It's an almost perfect sphere, but it comes at a high price.

Sphere 1 uses 31 subdivisions on the x-axis and 31 subdivisions on the z-axis, for a total of 3,844 faces.

Sphere 2 uses 5 recursive subdivisions, for a total of 109,220 faces.

But okay, that's not really fair. Let's scale down the quality considerably:

Lumpy

Sphere 1 uses 5 subdivisions on the x-axis and 5 subdivisions on the z-axis, for a total of 100 faces.

Sphere 2 uses 0 recursive subdivisions, for a total of 100 faces.

They use the same amount of faces, but in my opinion, the sphere on the left looks better. It looks less lumpy and a lot more round. Let's take a look at how many faces we generate with both methods.

Icosahedron:

  • Level 0 - 100 faces
  • Level 1 - 420 faces
  • Level 2 - 1,700 faces
  • Level 3 - 6,820 faces
  • Level 4 - 27,300 faces
  • Level 5 - 109,220 faces

Subdivided sphere:

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

As you can see, the icosahedron increases in faces at an exponential rate, to a third power! That is because for every triangle, we must subdivide them into three new triangles.

The truth is: you don't need the precision an icosahedron will give you. Because they both hide a much harder problem: texturing a 2D plane on a 3D sphere. Here's what the top looks like:

Top sucks

On the top-left, you can see the texture being used. Coincidentally, it's also being generated procedurally. (Hey, it was a course on procedural generation, right?)

It looks terrible, right? Well, this is as good as it's going to get. I got top marks for my texture mapping, because most people don't even get it this right.

So please, consider using cosine and sine to generate a sphere. It generates a lot less faces for the same amount of detail.

\$\endgroup\$
7
  • 6
    \$\begingroup\$ I'm afraid I can only downvote this. The icosphere scales exponentially? That’s only because you decided yours should scale exponentially. An UV sphere generates fewer faces than an icosphere for the same amount of detail? That is wrong, absolutely wrong, totally backwards. \$\endgroup\$ Jun 29, 2012 at 7:20
  • 5
    \$\begingroup\$ Subdivision does not need to be recursive. You can divide a triangle's edge into as many equal parts as you wish. Using N parts will give you N*N new triangles, which is quadratic, exactly like what you do with the UV-sphere. \$\endgroup\$ Jun 29, 2012 at 10:04
  • 6
    \$\begingroup\$ I must also add that the sphere you say looks "less lumpy and a lot more round" is viewed from the best angle, making that claim dishonest too. Just do the same screenshot with the spheres viewed from above to see what I mean. \$\endgroup\$ Jun 29, 2012 at 10:08
  • 4
    \$\begingroup\$ Also, your icosahedron numbers don't look correct. Level 0 is 20 faces (by definition), then 80, 320, 1280, etc. You can subdivide in any number and any pattern that you want. The smoothness of the model is ultimately going to be determined by the number and distribution of faces in the final result (regardless of the method used to generate them), and we want to keep the size of each face as uniform as possible (no polar squeezing) to maintain a consistent profile regardless of view angle. Add to that the fact that the subdivision code is a lot simpler (imho)... \$\endgroup\$
    – 3Dave
    Jun 29, 2012 at 19:55
  • 2
    \$\begingroup\$ Some work has been put into this answer, which makes me feel slightly bad about downvoting it. But it is completely and utterly wrong, so I have to. A perfectly round-looking Icosphere that fills the entire screen in FullHD needs 5 subdivisions, with a basic icosahedron having no subdivisions. An icosahedron without subdivisions doesn't have 100 faces, it has 20. Icosa = 20. It's the name! Each subdivision multiplies the number of faces by 4, so 1->80, 2->320, 3->1280, 4->5120, 5->20,480. With a geosphere we need at least 40'000 faces to get an equally round sphere. \$\endgroup\$
    – Peter
    Dec 20, 2015 at 12:16
-1
\$\begingroup\$

The below script will create an Icosahedron with n Polygons...base 12. It will also subdivide the polygons into separate meshes, and calculate the total verts-duplicates and polygons.

I couldn't find anything similar so I created this. Just attach the script to a GameObject, and set the subdivisions in the Editor. Working on noise modification next.


/* 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;
    }
}
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .