javascriptalgorithmthree.jsgeometrycircle-pack

Packing irregular circles on the surface of a sphere


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:

Example


Solution

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