Close Packing of Spheres

To build a close packing of spheres with disperse sizes within a bunker with flat walls we chose the “rolling” algorithm. The physical idea of this algorithm is formulated as follows. The spheres are generated according to the chosen law of size distribution and are dropped to the bunker either from one point, or from randomly chosen positions. As soon as the dropped sphere encounters an obstacle - the bunker wall or an already packed sphere - it sticks to it (without impact) and begins to slide on its surface in the direction of the minimum of the potential energy to the following obstacle. (This direction is a projection of the free fall direction on the surface of the obstacle.) The movement of the sphere stops, obviously, at a point of intersection of 3 surfaces (3 spheres, 2 spheres and 1 plane and etc.) or on a surface situated perpendicular to the direction of the free fall of the sphere (for example, on the bottom of the bunker).

It should be noticed that the movement of the current packed sphere is completely described by the trajectory of its center. In this case, the sliding of the sphere with center O and radius R on the surface of another sphere with center O1 and radius R1 corresponds to sliding of the center O on the surface of a sphere with center O1 and increased radius R1+R. Similarly, the sliding of the sphere with center O and radius R on the plane

ax = b,

corresponds to sliding of the center O on a shifted plane

ax = b + |a|R.

Thus, it is possible to formulate the following algorithm of movement of the next packed sphere:

1. Choose radius R of the packed sphere and an initial position of its center O. Initialise the set of restrictions: no restrictions.
2. Analyze the current set of restrictions: the system of  0, 1, 2 or 3 inequalities describing positions in the space which are disabled for the center of the packed sphere. Choose the new direction of movement of the sphere center. The movement of the center along this direction must satisfy the restrictions, this direction must form the minimal allowable angle with the direction of the free fall of the sphere (vector (0, 0, –1)), and this angle must be less than /2. In absence of allowable directions, i.e. when all angles more than /2, stop and choose the next sphere for package.
3. Determine the next segment of the movement trajectory of the center. It is a direct line or an arc segment. Perhaps, remove one from the restrictions.
4. Calculate points of intersection of the current segment of the trajectory with all packed spheres (with radii increased by R) or bunker walls (shifted by a normal vector with length R). Select the nearest to the beginning of the seg-ment. Add 1 new restriction: all points inside the sphere or behind the wall (which intersects the current segment at the nearest position) are disabled for the center of the packed sphere. Return to step 2).

It is easy to see that the described algorithm is a square-law of the general number of packed spheres. To convert it to a nearly-linear algorithm, the special technique of grid hashing was used. This technique will be outlined in the following. Let us consider a cubic grid with the cell size comparable with sizes of spheres. For each cell, let us build the list of packed spheres which centers lie in this cell. Then analysis of spheres disposed in several grid cells around the trajectory allows segment to find all intersections of the trajectory segment and the packed spheres. So, when parameters of the grid are customized well, the algorithm becomes almost linear with a multiplier depending from parameters of the whole packing of spheres (such as dispersion of radii of the spheres, etc.).

The results of close packing (1000 particles, Average Radii = 1, Average Square Distortion = 0.2, Distribution Type = 'Gaussian'. ) are shown in Figure 1,   Figure 2.

Figure 1. Close packing (1000 particles, Average Radii = 1, Average Square Distortion = 0.2, Distribution Type = 'Gaussian')

Figure 2. Density distribution from bottom to the top (packing of 1000 particles, Average Radii = 1, Average Square Distortion = 0.2, Distribution Type = 'Gaussian'. ), d - height of the packing