----------------------------------------------------------------------------------------------------------------------------------------------------

Copyright (C) 2011 pack-any-shape.com . All Rights Reserved.

Pack-Any-Shape (PAS) is a numerical algorithm that simulates dense random packings of virtual hard particles. The shapes of the particles can be arbitrary. PAS is able to handle spheres and non-spheres, symmetric and asymmetric shapes, convex and concave ones. The virtual packings produced by the PAS algorithm model packed granular materials.

A pilot version of the PAS program is operational. It packs convex particles in 2D. The figure above is an enlarged view of a clip from the 1000-particle packing in the figure below, where the clip boundaries are shown as the smaller rectangle. The pattern of the packing is periodic along both x and y directions and the larger rectangle is the period. The density of the packing, i.e., the fraction of space covered by the particles, is 0.8830. For this assembly, 25 distinct particle shapes have been defined and each shape has been represented by 40 congruent particles. In both figures, if two particles are congruent they are shaded with the same intensity.

How PAS algorithm works

In the beginning, the given virtual particles are proportionally reduced to a very small size and placed randomly in the given virtual container. The condition that no two particles overlap is easily satisfied in such initial state. Then the particles are proportionally expanding while the assembly is imitating a granular flow making sure that no two particles overlap at any time. When no further expansion of the particles is possible a dense random packing is achieved.

Because the size increase occurs concurrently for all the particles, when the boundary is periodic, the resulting packing accurately simulates large granular assemblies. If the particles were positioned sequentially, one-at-a-time, it would have been difficult to maintain both the uniformity of the jamming and the periodicity of the boundary.

The motion, expansion, and interaction of particles are simulated in the PAS algorithm with the highest precision supported by the underlying computing system. For example, the simulation is performed with double precision, if such is the highest precision provided by the compiler. This can be contrasted with the so-called digitizing procedures for the task, where the actions would be represented on a grid of pixels. To compete in precision with the PAS algorithm, a digitizing procedure would have to maintain a non-sustainably fine grid of pixels. It would require an impossibly large memory for representing the space and it would run astronomically slowly. On the other hand, the running time and memory required for the PAS algorithm are realistic. Each example presented here at most took a few days of computing on a 1 GHz uni-processor PC.

Whether or not the high computing resolution assured by the PAS algorithm is indeed required depends on the task in hand. If the accurate pattern of the final packing is important, the high resolution is necessary. For example, it seems unlikely for a digitizing procedure to be able to produce the best packing of 11 congruent squares in a square container, see below.

The following three snapshots depict the views through the window of the clip above at the stages of the particle expansion, while the density was reaching values, successively, 0.10, 0.45, and 0.75.

Density 0.10.

Density 0.45.

Density 0.75

More packing examples

Another packing of 1000 differently shaped particles. Boundary is periodic in both directions. The density is 0.8577. Like in the previous example, an enlarged clip is shown followed by the full packing. In both pictures as in the pictures above, if two particles are congruent they are shaded with the same intensity.

1000 congruent ellipses packed in a rectangle. The major-to-minor diameter ratio of the ellipses is 3:1. Boundary is periodic in both directions. The density is 0.8701

1000 congruent isosceles triangles packed in a rectangle. In the triangles, the ratio of the longest height to the shortest side is (3*sqrt(2)+1)/2 = 2.6213. Boundary is periodic in both directions. The density is 0.8726. In the picture, shading intensities of the particles depend on their orientation.

1000 congruent rectangles packed in a rectangle. The aspect ratio of each particle-rectangle is 2:1. Boundary is periodic in both directions. The density is 0.9293. In the picture, shading intensities of the particles depend on their orientation.

Why we are after random dense packings and not after the maximally dense packings. What a random dense packing is anyway

These are 11 congruent squares that are packed in a hard-walled square, and the packing is believed (but apparently not yet proven) to have the maximum attainable density 0.73178.... The corresponding ratio of the sizes (of the enclosing square to that of the square-particle) is equal 3.87708.... (see, e.g. Friedman, E. "Packing Unit Squares in Squares." Elec. J. Combin. DS7, 1-24, Oct. 31, 2005. http://www.combinatorics.org/Surveys/ds7.html ). The PAS program produces this packing in about 20% of randomly initiated runs. The rest 80% of the runs result in packings with lower densities.

What the PAS algoritm is dealing with while trying to pack hard particles, like these 11 congruent squares, is schematically represented in the rendering below.

This 2D diagram represents a set of particle configurations. An individual point represents a configuration with each particle specific position, orientation, and size. The vertical dimension in the diagram linearly scales with the absolute sizes of all particles. The particle-to-particle relative size is fixed. The horizontal dimension is meant to represent the manifold of particle positions and orientations. In non-trivial examples this manifold is multidimensional. For instance, in the case above of 11 squares, the true dimension is 33. The rendering in the diagram, though simplified, can still be used for illustrating the notion of a random dense packing.

The unshaded area represents all feasible configurations. In a feasible configuration, no two particles overlap and, if a hard-wall boundary is present as in the square-packing example above, no particle protrudes the boundary. Point a, for instance, is such a feasible configuration. Configuration a can be changed into any of feasible configurations b, c, d, or e. The change can be made continuous and such that all intermediate configurations are feasible. For example, the straight line segment from a to e represents all the intermediate configurations when sizes of all particles in configuration a gradually reduce to zero. Particle sizes are zero in the final configuration e as well as in all the configurations that are represented by the bottom horizontal line in the figure. It can be reminded that the sizes of particles relative to each other remain unchanged. Also the positions of particle centers and particle orientations do not change while moving from a to e. And a gradual increase of the sizes of all particles in configuration a without changing their positions and orientations corresponds to moving up along the a - c segment.

Unlike interior configuration a which can change in any direction, forward and reverse, without violating feasibility, the change in configuration c is restricted. In particular, no further size increase is possible, if starting from c and if center positions and orientations of the particles are fixed. The set of all such configurations c is represented by the broken line ABCD. This line can be viewed as a function profile. For any set of center positions and orientations of all particles in the packing example, the function returns the maximum particle scale size for which the configuration is feasible. The upward peaks of the broken line are the local maxima of the function. These are points A, C, and D, as well as segment B. Unlike configuration c which can gradually change so that the particle size increases, albeit in a restricted way, no gradual change is possible from configurations A, C, and D unless the particle size decreases. A gradual change is possible from configurations in B, but with no increase in the particle sizes. Such a change means mobility of a subset of particles: the particles would move but the size would stay constant.

A run of the PAS program terminates by arriving at a configuration of some local maximum. To each local maximum, say, A, B, C, or D, corresponds a probability, here p(A), p(B), p(C), or p(D), that this maximum shows up at the run's end. These probabilities sum up to 1, and the number of them is equal to the number of the local maxima. As shown in the diagram, configuration C is the global maximum. It has the largest particle size and hence the largest density. No good estimate for the number of the local maxima in the problem of packing hard particles is provably known. It is believed to be rather large, perhaps it grows exponentially with the number of particles. A "random dense" packing is simply the configuration of a local maximum. The term "random" here relates to the randomly sampled distribution {p(A),p(B),....}, rather than to that such a packing usually looks irregular or "random." In fact, a random dense packing may show a lot of regularity.

The achieved local maximum could turn out to be a global maximum, but usually the hope for that is slim. As a rule, only for a small number of particles the probability of achieving a global maximum becomes substantial, like 20% in the example of 11 squares. In our larger examples of 1000 ellipses, 1000 triangles, and 1000 blocks, the achieved configurations are certainly not the global maxima, because denser configurations exist. In the example of ellipses, a denser configuration is obtained by first arranging congruent circles in the infinite plane in the hexagonal fashion and then proportionally extending a dimension so that the circles turn into the required ellipses. Both configurations, of the circles and of the ellipses, have the same density 0.9068... In both examples of triangles and of blocks, it is obvious that the entire plane can be covered without a void. This corresponds to the maximally achievable density of one. (The dimensions of rectangle-the-period should be appropriately chosen in each example.)

Material scientists are interested in structures and properties of packings achieved under realistic granular flow conditions in real systems of particles. For example, such are sand particles after they are settled under the gravitation and/or if their container is being compressed. The PAS-produced packings are meant to be a model of packed granular materials and those are usually configurations of local maxima. That is why we are content when achieving random dense packings, i.e., local maxima, rather than maximally dense packings, i.e., global maxima.

Comments: packanyshape@aol.com