Ink Dispersion Simulation

I've been experimenting with using cellular automata to "simulate" the visual effect of ink dispersing in wet paper.[ I use the term "simulation" for lack of a better word; only the "look" is simulated; not the actual physics. ] You can see more images generated by the simulation on it's Art page and you can play with the simulation itself in this applet.

The inspiration for this was John Haddon's paper, "Sketchy Rendering" and the short animation it describes. Haddon states that "a very simple cellular automata rule was developed to provide the effect of ink on a wet page" but goes into no detail. As it turns out, producing this effect is quite simple, but very general. As seen in the example images, a wide variety of realistic and nonrealistic effects can be achieved.

The method I used was simply the first that came to mind: run a cellular automata in the background, using the values of "living" cells to modify the corresponding pixels on the "canvas" (which is what the user sees). The cells can contain any integer from 0 to 255; 0 is considered "dead", while all other values are "alive". The only restriction on the CA rules applied is that all cells must eventually die. This is trivially satisfied by ending the rules by decrementing the cell value. The simplest canvas modification is subtractive blending: the value of the cell (scaled, perhaps) is subtracted from each of the red, green, and blue components of the corresponding pixel. Whereas Haddon's implementation was a post-process, with the automata being "stimulated" by the edges of an animation frame, mine is interactive. The user "draws" on the canvas with the mouse, with the ink bleeding away from the "pen" in real-time.

Note: In the discussion that follows, the current value of the cell is v. Neighboring cells are refered to using compass directions: n, se, etc. choose(...) is a function that returns one of its arguments chosen at random. max(...) returns the maximum of its arguments, similarly min() and avg().

The basic structure of the simulation is something like this: For every cell

Growth Run the CA rule on the cell.
Test Test the new value of the cell. If the test succeeds, then
- Plot Plot the corresponding pixel on the canvas.
Decay Decrement the cell, clamping its value at 0, and save this value back into the cell.

Each stage can be modified to change the final effect. The simplest implementation that still provides a good result is probably
Growth: cell = max(cell, choose(n,s,e,w))
Test: true (The test always succeeds.)
Plot: Subtractive blending.
Decay: cell = cell - 1
(The decay stage is at the end, rather than directly after the growth stage purely out of tradition; my first implementation worked this way. This order means that both Test and Plot use the un-decayed value of the current cell. In practice, it turns out that a useful test is whether the cell has increased in value; if the decay were performed before the test, no cell would ever be seen as increasing in value.)

These next sections will describe some variations on the stages of the algorithm.

Growth

The Growth stage is the heart of the algorithm; it implements the cellular automata rule that determines the "shape" of the dispersion. My implementation only uses a 3x3 neighborhood; larger neighborhoods could be used but performance would suffer. I've found using all eight neighbors (the "von Neumann neighborhood") allows for much more complex effects.

A useful value that can be computed from the neighborhood is its count. The count is simply the number of neighbors that have values greater than some test value. The test value can be a constant, the value of the center cell, or any other value available. If the test value is 0, then the count is the number of living neighbors. If the test value is the current (center) cell's value, then the count is the number of cells living, relative to the "health" of the current cell (i.e., the current cell is taken as the dividing line between death and life).

Test

The test stages allows the algorithm to avoid plotting certain cells. The simplest test is true, which always succeeds. The next simplest test is new_cell > cell, where new_cell is the value computed by the growth stage. For many growth stages, cells only increase in value once in their lifetime, when they first come to life; thus, testing for increasing value results in most cells being plotted only once.

Another useful test is low < cell < high, where low and high are some limits. Setting low = 0 and high == 127 highlights the edges, producing a watercolor-like effect.

The test can compare the cell's value against one of its neighbors: cell > se will produce a bump-map effect.

Plot

The basic subtractive blending method works well enough (with a white canvas) that I haven't experimented much with other blending modes. Additive blending can be used to lighten the images, sometimes producing a backrun effect. The over compositing operator can be used (with the cell value as opacity), however, the multiplication and division used in over result in a lot of roundoff errors. Because each pixel may be plotted hundreds of times, these built up and tend to produce a greyish smear.

Haddon mentions using a color gradient; the cell value could be used as an index to a color lookup table.

Decay

The basic deacy is simply decrementation by a constant. Larger values result in smaller "flows" of ink. A random value can produce a more noisy effect. Using the scaled value of a neighbor tends to make the ink flow in that direction.

Other variations

Each stage has access to the original cell value and all the neighbors. All stages after Growth have access to the new (post-growth) cell value. Depending on the implementation, the stages may have access to the value of the current cell during the previous cycle. It is also useful to provide a "texture" value, supplied by a greyscale image. This value varies from cell to cell, but for a given cell is constant from cycle to cycle. Finally, the number of cycles computed thus far is sometimes useful.

The limited range of cell values (one byte) does not allow for cells to be divided into subfields. I experimented with running two CAs at the same time, allowing them to interact with each other. However, the result was very slow, and did not produce any interesting effects. You can see an image produced by this implementation here.

I have experimented with allowing the Plot stage to access the neighborhood of pixels in the canvas. For example, the Plot stage could blur the neighboring pixels. However, this complicates the implementation, and I could not find any interesting effects using this method.

Links of interest

Sketchy Rendering: The original "Sketchy Rendering" paper on which this is based.
Modeling Watercolor by Simulating Diffusion, Pigment, and Paper Fibers: Possibly the first instance of this technique, Small uses cellular automata to simulate watercolors. Small's implementation ran on a Connection Machine, which allowed each pixel to be managed by a separate processor.
Wet and Sticky: Cockshott's disertation on using CA to simulate paint, courtesy of Bill Baxter.
Computer Generated Watercolor: Curtis, et al's work in non-realtime watercolor simulation.
MoXi: MoXi is a real-time ink (and now watercolor) simulation program.
Real Time Simulation of Thin Paint: Work by Van Laerhoven, et al, on a distributed simulation of watercolors.