Optimally filling a 3D sphere with smaller spheres

Question

I'm trying to optimally fill a 3D spherical volume with "particles" (represented by 3D XYZ vectors) that need to maintain a specific distance from each other, while attempting to minimize the amount of free space present in-between them.

There's one catch though- The particles themselves may fall on the boundary of the spherical volume- they just can't exist outside of it. Ideally, I'd like to maximize the number of particles that fall on this boundary (which makes this a kind of spherical packing problem, I suppose) and then fill the rest of the volume inwards.

Are there any kinds of algorithms out there that can solve this sort of thing? It doesn't need to be exact, but the key here is that the density of the final solution needs to be reasonably accurate (+/- ~5% of a "perfect" solution).

Answer 1

There is not a single formula which fills a sphere optimally with n spheres. On this wikipedia page you can see the optimal configurations for n <= 12. For the optimal configurations for n <= 500 you can view this site. As you can see on these sites different numbers of spheres have different optimal symmetry groups.

Answer 2

your constraints are a bit vague so hard to say for sure but I would try field approach for this. First see:

• Computational complexity and shape nesting
• Path generation for non-intersecting disc movement on a plane
• How to implement a constraint solver for 2-D geometry?

and sub-links where you can find some examples of this approach.

Now the algo:

1. place N particles randomly inside sphere

   N should be safely low so it is smaller then your solution particles count.

2. start field simulation

   so use your solution rules to create attractive and repulsive forces and drive your particles via Newton D'Alembert physics. Do not forget to add friction (so movement will stop after time) and sphere volume boundary.

3. stop when your particles stop moving

   so if max(|particles_velocity|)<threshold stop.

4. now check if all particles are correctly placed

   not breaking any of your rules. If yes then remember this placement as solution and try again from #1 with N+1 particles. If not stop and use last correct solution.

   To speed this up you can add more particles instead of using (N+1) similarly to binary search (add 32 particles until you can ... then just 16 ... ). Also you do not need to use random locations in #1 for the other runs. you can let the other particles start positions where they were placed in last run solution.

How to determine accuracy of the solution is entirely different matter. As you did not provide exact rules then we can only guess. I would try to estimate ideal particle density and compute the ideal particle count based on sphere volume. You can use this also for the initial guess of N and then compare with the final N.