Compilation


It is necessary to convert the globally-described shape into a representation that lends itself nicely to amoprhous re-growth. I have implemented a method for describing input shapes in terms of an efficient network of overlapping circles.

Basic Principles of the Circle-Network Representation

Suppose that we construct a network of partially-overlapping circles, in which every circle stores a representation of the relative positions of directly-adjacent circles. In this event, instructing any one of these circles to recursively grow its adjacent circles would result in the emergence of the desired global structure. We can imagine how the process of growing circles at specified locations might be accomplished by cells: first, a particular cell would grow a circle around itself to a specified radius; next, cells in this circle that are destined to become centers of adjacent circles would grow circles around themselves as well. The desired global shape would emerge from this recursive behavior.

Three-Step Compilation

The compilation procedure involves three phases:
I. Finding an efficient circle covering (initial network)
II. Constructing a tightly-linked network of circles by introducing intermediate circles
III. Specifying position information in terms of gradient ratios

I. Finding an Efficient Circle Covering

This first step involves specifying a set of partially-overlapping circles that completely cover the input shape. I have implemented two methods for selecting circles:

Method #1: Tiling

This method first imposes a grid-like structure ("tiling") on the input shape. The tiling algorithm essentially locates the largest squares whose circumscribed circle would fit entirely within the shape, and later produces smaller squares in order to completely cover the shape. The circle network is then comprised of each internal square's corresponding circumscribed circle.

Method #2: Hill Climbing

The second method uses a hill-climbing algorithm to locate circles. Given a random point in shape, the heuristic function is a measure of how much previously-uncovered area that the largest possible circle (centered at this point) will cover.

As expected, the second method is significantly more efficient.

Circles found by method #2.The input shape is
the black circle-square hybrid, and the circles
are outlined in green.



II. Intermediate Circles

The process of amorphous circle growth proceeds outward from a designated center cell. However, in the network generated by the first step, the center of an adjacent circle may not lie in the interior of a previously-grown circle. This introduces difficulties, given the system of triangulation and gradient-messaging among the cells. Therefore, at this stage sequences of intermediate circles are inserted between each pair of circles found in the previous step. The center of each circle in the sequence is constrained to lie within an adjacent circle. We have created, in effect, a bridge between the main circles that facilitates connected growth.


III. Representing Positions of Adjacent Circles

Lastly, we reach the question of encoding the relative positions of adjacent circles in the network. Communication between cells is accomplished via a form of messaging that bears similarities to the spread of chemicals whose concentrations relate distance information during biological growth. Therefore, it is helpful to specify position as a set of gradient values exuded from particular cells ("reference cells") in a circle.

In this step we introduce four reference cells, cells whose primary task is to exude a gradient. These cells essentially provide a coordinate system for each circle, allowing us to specify positions within a circle in terms of distances from each reference cell. The positions of an adjacent circle's center and two reference points are indeed specified in this manner.


Qualities

The circle-network representation exhibits the qualities of scale- and rotation- independence, as all directional and position information is specified in a purely relative manner. In addition, the bi-directional, tightly-connected network promotes the regeneration of missing areas should cell disappearance occur during or after the growth process. As all information necessary for growing the entire shape is encoded within the network, persistent attempts of circles to recursively grow their adjacent circles ensures that the structure will be maintained.



<--back
next-->