Introduction
This tutorial presents the code for a shader that generates an animated pattern based on the principles of Conways Game of Life, so-called 2D cellular automata (CA). A full, or even a partial, discussion of cellular automata is beyond the scope of this tutorial. It is, therefore, assumed the reader has at least some familiarity with the basic concepts of CA. A static image of cellular automata is of little visual interest, only when animated does their complex behavior become apparent - figure 1.
Figure 1 (1.8 MB)
Cellular automata are generally displayed as a pattern of cells. The cells seen above are represented by the micropolygons into which prman has diced a surface. The 2 by 2 polygon shown above had a ShadingRate of 62 and was rendered using orthographic projection - listing 1. The shading rate yielded a pattern of 32 by 32 cells ie. micropolygons.
Listing 1 - celluar.rib
Option "searchpath" "shader" "@:PATH_TO_USERS_SHADERS"
DisplayChannel "float _cellLife"
Display "cellular" "it" "rgb"
Format 240 240 1
Projection "orthographic"
ShadingRate 62
Translate 0 0 3
Rotate -90 1 0 0
Rotate 0 0 1 0
Scale 1 1 -1
WorldBegin
Attribute "dice" "rasterorient" 0 # view-independent dicing
Surface "cellular"
"float init" 1
"float count" 32
"string oldcell" ["./old.ptc"] # note "./"
"string newcell" ["./new.ptc"]
AttributeBegin
Scale 2 2 2
Polygon "P" [-0.5 0 -0.5 -0.5 0 0.5 0.5 0 0.5 0.5 0 -0.5]
"st" [0 0 0 1 1 1 1 0]
AttributeEnd
WorldEnd
System "cp new.ptc old.ptc"
System "rm ./new.ptc"
|
The Rules of the Game of Life
Each cell (ie. micropolygon) can be in one of two states, either alive or dead. White cells are those considered to be alive; black cells are those that are dead. The state of a cell, say at frame 10, depends on the state of the cells that surrounded it on frame 9. In short, a cell lives, dies or a dead cell becomes alive depending on how many of its neighbors, in the previous frame of animation, were alive (possible overpopulation) or dead (possible underpopulation). These are the rules of the game of life.
Shading Issues
Because the renderer cannot be queried about the "previous" condition of a micropolygon it is impossible, without some trickery, to implement a shader that mimics the behavior of cellular automata. However, point clouds provide an opportunity to record the condition of a micropolygon so that it can be queried in a subsequent frame of animation. The technique presented here relies on the use of two point clouds. From one point cloud, "old.ptc", it reads data that was baked during the previous frame of an animation. Into the other point cloud, "new.ptc", it writes data that will be used in the next frame of animation.
Algorithm
On the first frame of an animation the shader, for each micropolygon,
- randomly assigns it a state - black (dead) or white (alive),
- writes the state to "new.ptc".
On all subsequent frames, again for each micropolygon, the shader,
- reads "old.ptc" to query the state of a neighborhood of micropolygons,
- sets a new state according to the rules of the game of life,
- writes the state to "new.ptc".
After each frame of animation the data in "old.ptc" is overwritten by
"new.ptc".
Data written to a point cloud is "bound" to the shading point
P and the surface normal
N of a micropolygon. Reading a point
cloud consists of referencing the baked data via P
and N. To determine the state of a cell
(micropolygon) a shader must query those cells (micropolygons) that were
adjacent to it on the previous frame of animation. Since
P is a (3D) point it is uncertain what
values should be used to define the 8 vectors that will provide offsets by which
the adjacent cells (micropolygons) can be referenced in the point cloud. To overcome
this difficulty the shader presented here does not use
P but instead, constructs a proxy point
based on 's' and 't'.
Because the size of a micropolygon varies across a surface when viewed by a
perspective camera a limitation of this approach is that an orthographic camera
must be used to render a planar square polygon. Only in this way can a shader
ensure it is accurately sampling a point cloud. Adaptive sampling was tried ie.
float stepSize = sqrt(area(P));
but it gave poor results.
