CODEWITHSUNDEEP
algorithm3dlanguage-agnosticgeometry
CMPXCHG8B
CMPXCHG8B

Reputation: 497

Optimally filling a 3D sphere with smaller spheres

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

Upvotes: 1

Views: 1687

Answers (2)

Spektre
Spektre

Reputation: 51835

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

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.

Upvotes: 1

user1350184
user1350184

Reputation:

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.

Upvotes: 2

Related Questions