packing irregular circles on surface of a sphere

Question

I'm using THREE.js to create points on a sphere, similar to the periodic table of elements example

My data set is a circles of irregular size, and I wish to evenly distribute them around the surface of a sphere. After numerous hours searching the web, I realize that is much harder than it sounds.

Here are examples of this idea in action:

vimeo

pic

circlePack java applet

Can anyone help point me in the direction for finding an algorithm that will allow me to do this? The packing ratio doesn't need to be super high and it'd ideally be something quick and easy to calculate in javascript for rendering in THREE.js (Cartesian or Coordinate system). Efficiency is key here.

Edit: circle radii can vary widely. Here's an example using the periodic table code:

Answer 1

Here's a method to try: an iterative search using a simulated repulsive force.

Algorithm

First initialize the data set by arranging the circles across the surface in any kind of algorithm. This is just for initialization, so it doesn't have to be great. The periodic table code will do nicely. Also, assign each circle a "mass" using its radius as its mass value.

Now begin the iteration to converge on a solution. For each pass through the main loop, do the following:

1. Compute repulsive forces for each circle. Model your repulsive force after the formula for gravitational force, with two adjustments: (a) objects should be pushed away from each other, not attracted toward each other, and (b) you'll need to tweak the "force constant" value to fit the scale of your model. Depending on your math ability you may be able to calculate a good constant value during planning; other wise just experiment a little at first and you'll find a good value.

2. After computing the total forces on each circle (please look up the n-body problem if you're not sure how to do this), move each circle along the vector of its total calculated force, using the length of the vector as the distance to move. This is where you may find that you have to tweak the force constant value. At first you'll want movements with lengths that are less than 5% of the radius of the sphere.

3. The movements in step 2 will have pushed the circles off the surface of the sphere (because they are repelling each other). Now move each circle back to the surface of the sphere, in the direction toward the center of the sphere.

4. For each circle, calculate the distance from the circle's old position to its new position. The largest distance moved is the movement length for this iteration in the main loop.

Continue iterating through the main loop for a while. Over time the movement length should become smaller and smaller as the relative positions of the circles stabilize into an arrangement that meets your criteria. Exit the loop when the movement legth drops below some very small value.

Tweaking

You may find that you have to tweak the force calculation to get the algorithm to converge on a solution. How you tweak depends on the type of result you're looking for. Start by tweaking the force constant. If that doesn't work, you may have to change the mass values up or down. Or maybe change the exponent of the radius in the force calculation. For example, instead of this:

f = ( k * m[i] * m[j] ) / ( r * r );

You might try this:

f = ( k * m[i] * m[j] ) / pow( r, p );

Then you can experiment with different values of p.

You can also experiment with different algorithms for the initial distribution.

The amount of trial-and-error will depend on your design goals.

Answer 2

Here is something you can build on perhaps. It will randomly distribute your spheres along a sphere. Later we will iterate over this starting point to get an even distribution.

//random point on sphere of radius R
var sphereCenters = []
var numSpheres = 100;
for(var i = 0; i < numSpheres; i++) {
    var R = 1.0;
    var vec = new THREE.Vector3(Math.random(), Math.random(), Math.random()).normalize();
    var sphereCenter = new THREE.Vector3().copy(vec).multiplyScalar(R);
    sphereCenter.radius = Math.random() * 5; // RANDOM SPHERE SIZE, plug in your sizes here
    sphereCenters.push(sphereCenter);
    //Create a THREE.js sphere at sphereCenter
    ...

}

Then run the below code a few times to pack the spheres efficiently:

for(var i = 0; i < sphereCenters.length; i++) {
    for(var j = 0; j < sphereCenters.length; j++) {
        if(i === j) continue;
        //calculate the distance between sphereCenters[i] and sphereCenters[j]
        var dist = new THREE.Vector3().copy(sphereCenters[i]).sub(sphereCenters[j]);
        if(dist.length() < sphereSize) {
             //move the center of this sphere to to compensate
             //how far do we have to move?
             var mDist = sphereSize - dist.length();
             //perturb the sphere in direction of dist magnitude mDist
             var mVec = new THREE.Vector3().copy(dist).normalize();
             mVec.multiplyScalar(mDist);
             //offset the actual sphere
             sphereCenters[i].add(mVec).normalize().multiplyScalar(R);

        }
    }
}

Running the second section a number of times will "converge" on the solution you are looking for. You have to choose how many times it should be run in order to find the best trade off between speed, and accuracy.

Updated for accuracy