« Back to Processing

Tutorial #1: More than one way to skin a sphere

| 2 Comments | Published on April 7, 2008
The content that follows was originally published on the Don Havey website at http://donhavey.com/blog/tutorials/tutorial-1-more-than-one-way-to-skin-a-sphere/

Electronsphere previewThis first tutorial will address the question of how to evenly distribute points on a sphere. It’s not as simple as it sounds.

I’ll be addressing one method today, which I’ll be calling the electronsphere. The idea is this: treat each point as if it were an electron – repelling all other electrons around it – and limit its maximum distance from a center point. You should end up with a pretty well-distributed sphere of points. The trick will be how to “skin” (triangulate) the sphere. More on that later…

For now, take a look at where we’re going: The final result

And download the classes: Electronsphere classes

When you’re looking at the example, give it about 30-60 seconds to resolve the positions of the electrons (longer on slower computers, waayyy faster within the Processing environment), then you’ll see triangles start to appear between the points on the sphere. Both processes are iterative and random, and therefore quite unpredictable, but they should produce quasi-accurate results.

Why should I distribute points on a sphere?

I’m not really sure. The first time I encountered the problem I was in need of a spherical shape that could be warped or dented. I used a more sensible approach than the electronsphere, which I’ll show in a later tutorial, but the electronsphere is much more exciting. By changing the repulsion between electrons, you could potentially use this to create a sphere of points that reacts to mouse movements or other interactions and warps a mapped image accordingly. That would be worthwhile.

What you’ll be learning

We’ll address all of these issues in this tutorial:

  • Extending classes
  • Node interaction: repulsion forces
  • Using vectors to constrain points and forces
  • Finding the circumcenter of a three-dimensional triangle (face)
  • Back face culling
  • And in general, how to set up an iterative Processing application

Let’s get started…
Without further ado…

The Electron class

Our first class, the Electron, will extend our Point class. Let’s look at the syntax here:

class Electron extends Point{
  //define Electron variables
  //Electron constructor
  Electron(float $x,float $y,float $z){
    //first construct the superclass (Point)
    super($x,$y,$z);
    //now assign any variables that are specific to the Electron class
  }
}

It’s important to note that the “super()” function, which initiates the class we are extending (the “superclass”), must be called first in the extension class’ constructor function. Therefore, if the superclass requires a set of variables be passed to its constructor function, the same variables must be present at the start of the extension class’ constructor function. So we could do something like this:
Electron(float $x,float $y,float $z,float $anyothervariables){
  super($x,$y,$z); //define the super with some or all of this constructor's passed variables
  anyothervariables = $anyothervariables;
}

Or this:
Electron(float $anyothervariables){
  super(5,10,15); //define the super with constant variables
  anyothervariables = $anyothervariables;
}

But not this:
Electron(float $anyothervariables){
  float x = $anyothervariables/2;
  float y = 2*$anyothervariables/3;
  float z = 5*$anyothervariables/4;
  super(x,y,z); //wrong-o
}

That last example is wrong because the super() constructor must be called first.

Moving on. Let’s look at the new methods that the Electron class adds to the Point class.

First, note that the Electron class may override the methods of the Point class, as is the case with the render() function, but otherwise, all of the Point class’ methods are available to the Electron class (such as “move_to()”). Within an override method, such as render(), you’ll notice that you can still call the superclass’ method of that name using the syntax “super.render()”. In that way you can effectively extend methods just like you extend classes.

All of the Electron object’s methods revolve around the “repel()” function:

void repel(Electron[] $electrons){
  //loop through the passed array of neighboring electrons
  for(int i=0;i<$electrons.length;i++){
    //make sure we aren't comparing this electron against itself
    if($electrons[i]!=this){
      //get the distance to the electron in question
      float d = get_distance_to($electrons[i].x,$electrons[i].y,$electrons[i].z);
      if(d>0){
        //get the force of repulsion between the two electrons (note the sq(d) used for falloff)
        float f = force/sq(d);
        //get the components of the distance between the two points
        float dx = $electrons[i].x-x;
        float dy = $electrons[i].y-y;
        float dz = $electrons[i].z-z;
        if(!$electrons[i].locked){
          //add half of the force (negative) to the electron in question
          $electrons[i].add_force((-f/2)*(dx/d),(-f/2)*(dy/d),(-f/2)*(dz/d));
        }
        if(!locked){
          //add half of the force (positive) to this electron
          add_force((f/2)*(dx/d),(f/2)*(dy/d),(f/2)*(dz/d));
        }
      }
    }
  }
}

So what’s happening here? We’re looping through a set of Electrons, getting the distance between them, and forcing them away from each other according to that distance. Nice and simple.

We’ll have to call this method for every Electron in every frame. That’s a lot of double-looping, but in this case, there’s no way around it. When you’re doing something like object collision detection, you can choose only the relevant objects to test with, but for electron repulsion we’ll have to calculate for the whole set each time.

Now we’ll look at the supporting methods:

void add_force(float $fx,float $fy,float $fz){
  //add force components
  fx += $fx; fy += $fy; fz += $fz; fn++;
}
void average_forces(){
  //average force components
  if(fn==0){ return; }
  fx /= fn; fy /= fn; fz /= fn;
}
void reset_forces(){
  fx = 0; fy = 0; fz = 0; fn = 0;
}
void step(){
  //this will be called each frame after all electrons have been repelled
  average_forces();
  //resize the electron's position vector according to its force components
  v.vx = x+fx; v.vy = y+fy; v.vz = z+fz;
  //then unitize and scale it to match the radius of the sphere (constraining it)
  v.unitize();
  v.scale(radius);
  //now move the electron to match the constrained vector
  move_to(v.vx,v.vy,v.vz);
  reset_forces();
}

Averaging force vectorsSo for every frame before we start adding faces to our sphere, we iterate through the list of Electrons and push them away from one another. It’s important that we call the repel() function on all Electrons before we use the step() function to actually move them. That way, what you’ll end up with before the step() function is a series of forces assigned to each Electron, that can be averaged into a single force, as represented in the image.

The Electronsphere class

I always include a class that controls all of the project-specific classes (such as the Electron class). The Electronsphere class will initialize our group of Electrons, and iterate through them until they reach a relatively stable equilibrium.

You’ll notice that the constructor function generates an array of randomly-placed Electrons within the bounding box of the sphere we’re defining. They will be constrained to the surface of the sphere in the first frame.

The only other Electronsphere method we care about at the moment is the rotate() function, which loops through the array of Electrons and rotates them around the sphere’s central point. Just basic trigonometry, relying on the rotate() function within the Point class.

Variables

The nice part about the electronsphere approach to random distribution is that we can specify any number of Electrons. Here are a few examples of solutions using 12 Electrons, 36 Electrons, and 300 Electrons, in addition to our 100 Electron original. The 12 Electron solution is particularly interesting: it will form an approximation of a icosahedron, which is the jump-off shape for the alternative to an electronsphere approach. As I mentioned before, that’ll be a separate tutorial.

The number of Electrons is only one of a handful of variables that can be set to control the behavior of the applet. By setting the “tiling_start” and “tiling_end” variables (within the _Electronsphere.pde file), we can control how many frames worth of iterations occur before the Electrons are locked into their positions and we try to triangulate the sphere. Additionally, we can change the sphere’s radius and the force with which Electrons repel one another.

Once you’ve played around with the Electrons to your heart’s content, we’ll try approaching the more challenging problem of “skinning” the sphere.

Skinning the sphere

The trick to triangulating our electronsphere is that we do not know where the Electrons will end up, due to the random and iterative nature of the process. So we’ll have to use a similarly random, iterative approach for generating the faces of the sphere.

This is how I structured the solution:

  1. Find a point that represents the circumcenter between any 3 Electrons (the point equidistant to all three).
  2. Project that point to the sphere, using the same vector-scaling approach used to constrain the Electrons.
  3. Find the 3 Electrons closest to that point.
  4. Repeat the above steps until the 3 Electrons whose circumcenter was found match the 3 Electrons closest to that point.
  5. Check that the triangle formed by the 3 Electrons is acute (this will ensure that for any 4 Electrons forming a quadrilateral on the sphere, only 2 Faces are created between them).
  6. Check to make sure that a face does not already exist between those 3 Electrons.
  7. Create the Face and orient it according the the sphere’s central point.
  8. Repeat until the number of Faces matches the number predicted (equal to 2n-4 Electrons).

Testing for acuteness helps prevent overlaps but leads to holesTesting for acuteness helps prevent overlaps but leads to holesThe one caveat is this: due to the fact that we are testing each triangle for acuteness, we may end up with holes in our sphere in special cases. Refer to the diagram. Furthermore, in poorly-distributed solutions, the acuteness test does not prevent all overlaps (in the cases where a quadrilateral contains 3 acute internal angles).

There are ways to fix this. Off the top of my head, I’d suggest either (a) checking for gaps in the sphere using Line-to-Face intersection testing, with a Line created from each Face’s normal, (b) subdividing the sides of each Face and then re-triangulating, or (c) keeping track of the segments between two Electrons and testing to make sure that each borders (only) two Faces. But as I mentioned earlier, the electronsphere approach is definitely not the best way to create a well-skinned sphere… just the more exciting way.

The Face class

The Face class is primarily for three-dimensional use. It extends the Polygon class, but only contains three Points. Some methods of note:

  • Finding the circumcenter of the triangle: a point equidistant from its three vertices. Not to be confused with the centroid, which is an average of the three vertices. The operation is actually a little complicated, and relies on the Plane class’ three-way intersection function.
  • Finding the incenter of the triangle: a weighted average of its three vertices.
  • Orienting the normal of the Face to point outwards in respect to a given Point. Important in back face culling.
  • Back face culling: determining whether or not to render a face based on which side is showing. More on this in a second…
  • Segment-Face and Line-Face intersection testing for use when determining if a Line hits a Face. Could be useful in 3D object collision detection.

Back face culling is the most exciting item on that list. It’s used to lessen the load on the rendering engine by choosing to render only the Faces whose fronts are shown. OpenGL has built-in back face culling, but I added the method here so that we could use it on transparent faces. Notice how in the example you can see the Points and Vectors on the back side of the sphere, but no Faces. That’s back face culling.

Finishing up

The only thing left to take a look at is the code which implements the sequence I outlined above. It is found within the “generate_face()” method in the Electronsphere class. It is called once a frame until either (a) all Faces have been added, or (b) the frame count hits the limit defined by the “tiling_end” variable. Here’s the commented code:

void generate_face(){
  if(nfaces>=tnfaces){ return; }
  Electron[] ns = {electrons[floor(random(nelectrons-.0001))], electrons[floor(random(nelectrons-.0001))], electrons[floor(random(nelectrons-.0001))]}; //define an array of 3 random electrons
  Electron[] ons = new Electron[3]; //this will contain the previous iteration's 3 electrons
  int tries = 0; //put a limit on the number of attempts to locate a circumcenter
  while(tries<10){
    tries++;
    arraycopy(ns,ons); //store the old points for later comparison
    Face f = new Face(ns);
    Point cp = f.get_circumcenter_point();
    //project circumcenter point to sphere
    float cm = mag(cp.x,cp.y,cp.z);
    if(cm<distance_tolerance){ return; } //avoid division by zero
    cp.x *= radius/cm; cp.y *= radius/cm; cp.z *= radius/cm;
    //now get the closest electrons to the projected point
    ns = get_closest_electrons(cp.x,cp.y,cp.z,3);
    //if the old and new points match, we've found a face
    if((ons[0]==ns[0]||ons[0]==ns[1]||ons[0]==ns[2])&& (ons[1]==ns[0]||ons[1]==ns[1]||ons[1]==ns[2])&& (ons[2]==ns[0]||ons[2]==ns[1]||ons[2]==ns[2])){
      f = new Face(ns);
      if(!f.is_acute()){ return; } //test to make sure we're using acute triangles only
      //test for duplicate faces
      for(int i=0;i<nfaces;i++){
        if((faces[i].p1==ns[0]||faces[i].p1==ns[1]||faces[i].p1==ns[2])&& (faces[i].p2==ns[0]||faces[i].p2==ns[1]||faces[i].p2==ns[2])&& (faces[i].p3==ns[0]||faces[i].p3==ns[1]||faces[i].p3==ns[2])){ return; }
      }
      f.orient(zero_point); //orient the face to point outwards from the sphere's center
      //add the face to our array of faces
      faces[nfaces] = f;
      nfaces++;
      return;
    }
  }
}

That’s about it. The rest of the code in the zip file should be pretty self-explanatory.

Here’s another link to the final result.

As I mentioned, there’s plenty of room for improvement within this example. The best way to accurately triangulate this type of sphere would actually be to project the Electrons to a plane and then use Delauney triangulation to find the Faces. But that’s a whole new level of complexity. For now, hopefully this tutorial has served as a decent introduction to advanced iterative problem solving in Processing.

Let me know if you think of a good way to implement this type of sphere mapping, or find a simple way to patch those holes.

Coming up next… making randomly-generated, three-dimensional trees.

Categories: Processing / Tutorials

Tags: / / / / / / / /

2 Comments

Alberto says:

Dear Don,

I have been trying to generate an electronsphere in Rhino and I came across this tutorial which I think is great. I have ran the elektrosphere classes in Processing and changed the number of points and radius. I would like to use the cooordenates of the points and export them in Rhino. How can I extract the point coordenates from the elektronsphere generation?

Regards,

Alberto

Don says:

Hey Alberto,

Check out the “dxf export” library for Processing. You can find it at processing.org. Actually I think it’s also wrapped into the newer versions. There are examples of how to use it to export shapes to dxf for importing into Rhino.

Leave a Response

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>