Regular circle packing in 2-dimensions is a long-solved problem that has been approached from several points of view.
For example, in 1773 Joseph Louis Lagrange proved that hexagonal packing is the optimal arrangement.
More recently, random polygon packing - of which circle packing is a special case - has become
popular among professionals, and hobbyists such as myself who enjoy creating mathematical art.
While the math is interesting, the intent here is to use random circle packing as a model problem to investigate approaches to parallel processing.
Generally, the procedure is to create a circle with random location and properties (e.g. color and size).
If it is created in a location where it collides with another circle it may be moved a number of times to different locations to
see if it can fit somewhere else. If not, it is simply destroyed. Fast collision detection is the heart of the problem.
If no place can be found for circles of a certain size, a smaller size is used for subsequent trials.
Software I use controls for color, size, growth, and filled vs hollow, and speed.
Color of the circles can be based on the following:
Uniform color (all circles the same)
Random color
Sequence in the frame
Frame number in the animation
Horizontal location where created
Vertical location where created
Radial location where created
Trigonometric function based on location
The color method used can be altered at runtime for a variety of effects.
Size of the circles can be based on the following:
Uniform size (all circles the same)
Random size
Horizontal location where created
Radial location where created
Trigonometric function based on location
The size method used can be altered at runtime for a variety of effects.
Growth can be controlled in two ways:
Growth to fill maximum space - that is, a circle was created with radius 10 pixels, but after being placed it is able to grow to 20 pixels without colliding with its neighbor
Growth as animation - the size has been determined, but the circle appears to grow to make animations look better
Growth visible in videos and images is only for aesthetic purposes (the latter option). Growth to fill maximum space (the former option) happens silently on the GPU and is not visible.
Circles may be drawn as filled or hollow. It's more interesting to grow them hollow (like expending bubbles) and then fill them when the growth animation has completed.
Maximizing Speed is the main reason for this project. So tradeoffs are driven towards keping framerates "interactive", such as 10-30 per second. It amazes me that personal computers can generate 256 circles and test them against hundreds of thousands of existing circles to determine placement at such speeds.
There are also more technical considerations, such as:
Circle Size - how much should test circles shrink when the current size doesn't fit
Concurrency - How many circles should the algorithm place simultaneously (256 are tested concurrently here)
Capacity - How many circles should the program consider in total (1 million easily fill the screen)
Movement - How many times should a circle move to a new location if it doesn't fit (2000 used here)
Growth - Should a placed circle grow to fill all available space (optional at runtime)
Data - How should the data structures that hold circle information be organized managed
Algorithm Design - Which parts of the algorithm can be parallelized
CPU/GPU split - How should processing tasks be allocated to mnake best use of CPU and GPU capabilities (all work except circle growth animation done on GPU)
There are several other types of random spece-filling algorithms. Here are some examples:
Circle packing - simple and computationally inexpensive, but perhaps a little boring
Regular convex polygons (triangle, square, hexagon, etc.) packing - similar to circle packing but collision detection is a little more expensive
Polygon - similar to regular polygons, but with more expensive collision detection
Arbitrary shape / bitmap (with transparent areas) - much more complex and generally requires a different and more computationally expensive bitmap-based method for collision detection
Other - hollow shapes, multidimensional (3D), etc.
Circle packing with size and color gradients
Parallel circle-packing computation, with growth
Recursive circle packing with animation