« Back to Processing

Tutorial #3: The icosahedron-based geodesic sphere

| 6 Comments | Published on April 17, 2008
The content that follows was originally published on the Don Havey website at http://donhavey.com/blog/tutorials/tutorial-3-the-icosahedron-sphere/

Icosahedron geodesic sphere previewThis quick tutorial will show a more reasonable alternative to the electronsphere, which addressed the problem of distributing points evenly on a sphere. We’ll be creating a geodesic sphere (like at the Epcot center) using a subdivided icosahedron. It’s a relatively simple script and inexpensive in terms of CPU usage. Much more efficient than the electronsphere approach, though not quite as interesting.

Here’s where we’re headed: The final result

And here are the classes you’ll need: Icosahedron classes

About the geodesic sphere

The geodesic dome and sphere are often credited to Buckminster Fuller, although it is generally acknowledged that he did not invent the shape or concept, but rather investigated and expanded upon them. Read more in the Wikipedia article on geodesic spheres.

There is no one standard way to create a geodesic, but in general, the process is as follows:

  1. Create a Platonic solid. We’ll be using the icosahedron.
  2. Subdivide the faces of the Platonic solid to the desired level of resolution.
  3. Project the points of each subdivided face to the surface of a sphere.

Additionally, the term buckyball is used to describe the truncated counterpart to the geodesic sphere. Buckyballs are found frequently in molecular science… and also in soccer. We’ll take a look at how to convert one to the other.

Why create a geodesic sphere?

If you need to create a sphere in Processing just for decoration or whatnot, by all means, use the sphere() command. You do not need this level of complexity.

But let’s say that you need a sphere that can transform itself into a different shape, or warp itself according to some input variable, or behave like a blob… then you’ll probably want to use a geodesic. As I mentioned, its one of the most straightforward ways to create an array of points on a sphere.

Of course, you could also use this script in more physical applications: the coordinates it defines could be used to construct a real-life geodesic structure. You’d probably want to drop the points into Rhino and unfold the thing first.

What you’ll learn

I’ll touch upon the following issues in this tutorial:

  • Subdividing a face to an arbitrary level of resolution.
  • Constraining points to a sphere.
  • Finding the centroid of a face.
  • And of course, more about geodesics.

Still sound interesting?

Without further ado…

A new Face method

Subdividing a triangleThe only functional requirement of our geodesic sphere is this: we’ll need to be able to subdivide the faces of an icosahedron to a variable level of resolution.

Dividing a triangle into four smaller congruent triangles is easy, as shown in the image. But what if we want to divide the triangle into any number of smaller triangles? The solution is a little trickier, but not too bad. We’ll first divide up the edges according to a passed variable, then we’ll divide up the distance between opposite pairs of those edge Points. With those arrays of Points, we’ll be able to create our subfaces.

We’ll be adding the following method to our Face class. Watch out for line breaks that don’t belong in the code below… there are a few wrapped lines:

Face[] subdivide(int $n,Point $p){
  //n must be greater than or equal to two
  Point[] side12 = new Point[$n+1]; side12[0] = p1; side12[$n] = p2;
  Point[] side13 = new Point[$n+1]; side13[0] = p1; side13[$n] = p3;
  Point[][] span = new Point[$n+1][$n];
  //subdivision points
  for(int i=1;i<$n;i++){
    side12[i] = new Point(p1.x+(i/float($n))*(p2.x-p1.x),
                          p1.y+(i/float($n))*(p2.y-p1.y),p1.z+(i/float($n))*(p2.z-p1.z));
    side13[i] = new Point(p1.x+(i/float($n))*(p3.x-p1.x),
                          p1.y+(i/float($n))*(p3.y-p1.y),p1.z+(i/float($n))*(p3.z-p1.z));
  }
  for(int i=0;i<$n+1;i++){
    for(int j=1;j<$n-i;j++){
      span[i][j] = new Point(side12[$n-i].x+(j/float($n-i))*(side13[$n-i].x-side12[$n-i].x),
                             side12[$n-i].y+(j/float($n-i))*(side13[$n-i].y-side12[$n-i].y),
                             side12[$n-i].z+(j/float($n-i))*(side13[$n-i].z-side12[$n-i].z));
    }
  }
  Face[] faces = new Face[int(sq($n))];
  Point[] ps = new Point[3];
  int nfaces = 0;
  //top four subfaces
  ps[0] = side12[0]; ps[1] = side13[1]; ps[2] = side12[1];
  faces[nfaces] = new Face(ps); nfaces++;
  ps[0] = side12[1]; ps[1] = side12[2]; ps[2] = span[$n-2][1];
  faces[nfaces] = new Face(ps); nfaces++;
  ps[0] = side12[1]; ps[1] = span[$n-2][1]; ps[2] = side13[1];
  faces[nfaces] = new Face(ps); nfaces++;
  ps[0] = side13[1]; ps[1] = side13[2]; ps[2] = span[$n-2][1];
  faces[nfaces] = new Face(ps); nfaces++;
  //the rest of the subfaces
  for(int i=2;i<$n;i++){
    //side 2
    ps[0] = side12[i]; ps[1] = side12[i+1]; ps[2] = span[$n-i-1][1];
    faces[nfaces] = new Face(ps); nfaces++;
    ps[0] = side12[i]; ps[1] = span[$n-i][1]; ps[2] = span[$n-i-1][1];
    faces[nfaces] = new Face(ps); nfaces++;
    //center
    for(int j=1;j<$n-i+1;j++){
      ps[0] = span[i-2][j+1]; ps[1] = span[i-2][j]; ps[2] = span[i-1][j];
      faces[nfaces] = new Face(ps); nfaces++;
      if(i>2){
        ps[0] = span[i-2][j+1]; ps[1] = span[i-2][j]; ps[2] = span[i-3][j+1];
        faces[nfaces] = new Face(ps); nfaces++;
      }
    }
    //side 2
    ps[0] = side13[i]; ps[1] = side13[i+1]; ps[2] = span[$n-i-1][i];
    faces[nfaces] = new Face(ps); nfaces++;
    ps[0] = side13[i]; ps[1] = span[$n-i][i-1]; ps[2] = span[$n-i-1][i];
    faces[nfaces] = new Face(ps); nfaces++;
  }
  //orient according to a given point
  for(int i=0;i<nfaces;i++){
    faces[i].orient($p);
  }
  faces = (Face[]) subset(faces,0,nfaces);
  return faces;
}

I’m afraid I’m going to leave you to interpret the specifics of what’s happening in there. It’s a bit confusing.

Edge points vs. "span" pointsHere’s an image that should help a bit. It describes the relationship between the edge Points and the number of Points that should span between them.

Once we have an array of Points as described above, the subfaces are then created and oriented according to an “inside point” (a three-dimensional Point that lies within the closed geodesic shape). They are returned as an array.

So the number of subfaces returned is equal to the number of subdivisions squared. If you call the method like this:
some_face.subdivide(10,some_point);
You get 100 subfaces from that original Face. In the image above, you’ll notice that each edge is divided into 6 segments, making 36 subfaces. Pretty cool. Now all we need to do is to project all of those subfaces to the sphere.

Icosahedron to sphere

First, we start with a predefined Icosahedron. Here are the coordinates that define it:

float tao = 1.61803399;
float[][] _handles = {{1,tao,0},{-1,tao,0},{1,-tao,0},{-1,-tao,0},
                      {0,1,tao},{0,-1,tao},{0,1,-tao},{0,-1,-tao},
                      {tao,0,1},{-tao,0,1},{tao,0,-1},{-tao,0,-1}};

Notice the tao variable. That’s the golden ratio constant. Nice.

There’s a separate array named “_faces” that defines which of the coordinates in the “_handles” array above create the 20 Faces of our Icosahedron. We’ll scale the entire thing by our “sc” variable and construct the Faces, and it should look like this.

Within our Icosahedron class, we’ve defined a method to call our subdivide() method on each of the Icosahedron’s Faces, then aggregate the new set of Points into an array and constrain them to our “radius” variable. Let’s take a look at it:

void subdivide(int $n){
  //reset all icosahedron variables
  subfaces = new Face[100000]; points = new Point[100000];
  nsubfaces = 0; npoints = 0;
  //subdivide faces
  for(int i=0;i<20;i++){
    Face[] fs = faces[i].subdivide($n,zero_point);
    //add to our array of subfaces
    if(nsubfaces>0){ subfaces = (Face[]) concat(subfaces,fs); }else{ subfaces = fs; }
    nsubfaces += fs.length;
  }
  //add new points to the icosahedron's list of points
  for(int i=0;i<nsubfaces;i++){
    boolean found = false;
    for(int j=0;j<npoints;j++){
      if(points[j]==subfaces[i].p1){ found = true; break; }
    }
    if(!found){
      points[npoints] = subfaces[i].p1;
      npoints++;
    }
    found = false;
    for(int j=0;j<npoints;j++){
      if(points[j]==subfaces[i].p2){ found = true; break; }
    }
    if(!found){
      points[npoints] = subfaces[i].p2;
      npoints++;
    }
    found = false;
    for(int j=0;j<npoints;j++){
      if(points[j]==subfaces[i].p3){ found = true; break; }
    }
    if(!found){
      points[npoints] = subfaces[i].p3;
      npoints++;
    }
  }
  //project each point to the sphere
  for(int i=0;i<npoints;i++){
    //first get the point's magnitude
    float m = mag(points[i].x,points[i].y,points[i].z);
    //now make its magnitude a unit vector then scale it to the radius in one step
    points[i].x *= radius/m; points[i].y *= radius/m; points[i].z *= radius/m;
  }
}

Simple. Now we’ve got a geodesic sphere that can be subdivided 2 times (very faceted), 5 times (decent for web-based apps), or 20 times (danger! 8000 faces!).

Geodesic sphere to buckyball

As promised, here’s how to quickly create a buckyball (think soccer ball) from your shiny new icosahedron-based geodesic: take the centroids of the faces. Well, to be honest, I haven’t checked to make sure that this works out correctly in terms of the mathematics, but it certainly looks like it does.

There’s a method in our Polygon class that our Face class inherits, called get_centroid_point(). All it does is average the three Points that define the Face. That’s the centroid.

Now if we take the centroid of each face on our sphere and render them, we get something like this: viva futbal! That’s based on a 3-subdivisions sphere. Looks like a buckyball to me.

Wrapping up

So that’s how to make a icosahedron-based geodesic sphere. You can use the same methods to create a geodesic from any Platonic solid.

There are a few imperfections in the strategy I used:

  • There are some duplicate points. When each Face of the Icosahedron is subdivided, new Points are created along its shared edges. In a perfect world, those Points should be shared between adjacent Faces of the Icosahedron. The subfaces, on the other hand, correctly share the internal Points.
  • The Faces are not aware of their neighbors. Often times you’ll need to know which Face is next to which. This solution is not optimized for that type of application. In order to achieve that, it would be a good idea to store an array of Segments connecting the subpoints of the Icosahedron. That would allow Faces to find their peers via the shared Segment between them.

Okay. That’s it. Good luck. Let me know if you think of a cool way to use it.

One of the next tutorials will use our geodesic sphere to create a sexy globe.

Until then, have fun with the Icosahedron classes and final result.