Packing irregular circles on the 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 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

Picture

circlePack Java applet

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

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

Irrelievable

What you are you trying to optimize for? IE: Smallest sphere to fit all circles or maximize the number of circles to fit on a sphere of specific size or what? Relating to that question is what do you mean by "evenly distribute"? – Obstruct

take a look at the source for this page -- might give you an idea or two; engineeringtoolbox.com/… – Willful

Answer 1

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

Gass

Answer 2

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.

Dunedin

Thank you for this explaining this method. The methodology applies beyond just three.js / javascript and is a great example for anyone attempting circle packing – Irrelievable

Answer 3

You can use the same code as in the periodic table of elements. The rectangles there do not touch, so you can get the same effect with circles, virtually by using the same code.

Here is the code they have:

            var vector = new THREE.Vector3();

            for ( var i = 0, l = objects.length; i < l; i ++ ) {

                var phi = Math.acos( -1 + ( 2 * i ) / l );
                var theta = Math.sqrt( l * Math.PI ) * phi;

                var object = new THREE.Object3D();

                object.position.x = 800 * Math.cos( theta ) * Math.sin( phi );
                object.position.y = 800 * Math.sin( theta ) * Math.sin( phi );
                object.position.z = 800 * Math.cos( phi );

                vector.copy( object.position ).multiplyScalar( 2 );

                object.lookAt( vector );

                targets.sphere.push( object );

            }

Swain

I ran a few tests using this method and it breaks down with large discrepancies of vales: ie. circles as little as 10 and as high as 100. – Irrelievable

I added a screenshot in case you wanted to see irregular circles. IMO it doesn't look good and I'm looking for better distribution. – Irrelievable