COMP 238 Assignment 4

Procedural Shader

[ introduction | cellular automata algorithm | rendering | implementation | results ]

Introduction

The goal of this assignment was to experiment with procedural shading. Because of my interest in real time rendering and simulation I chose to experiment with the NVIDIA Cg shading language. In particular I wanted to use a dynamic fragment shader to perform physical simulation in a texture. I was greatly inspired by Mark Harris' work in this area, especially his submission to the 2002 Cg shader contest, which was a fragment program that implemented the Gray-Scott reaction diffusion system.

The shader that I implemented is based on the cellular automata framework, similar to the game of life, in which each pixel changes state based on the states of its 4 nearest neighbors.

Cellular Automata Simulation

Cellular automata are a well know mechanism for simulating natural phenomena. I've personally encountered the technique as applied to simulating fluid flows, deformable materials, and cracks in material surfaces, although there are many other applications in the literature. My implementation stores the states of the cells as a texture, and updates them using a fragment program.

In my particular cellular automata simulation, the cells can transition between two discrete states, 0 and 1.

Front Propagation

The basic rule of my simulation has the effect of propagating a particular type of front through the material.
The rule is:

A cell in state 0 may transition to state 1 if exactly one of its neighbors is in state 1.

Figure 1: The neighbor relationships necessary for state transition. Cells in state 1 are shown in White, while cells in state 0 are shown in Gray. The center cell, marked with a ? will transition to state 1 in these situations.

The effect of this rule is to produce a pattern similar to a snowflake. We see channels of lit up cells running through the material, separated by channels of unlit cells.

Image 1: The pattern produced by the simple cellular automata rules. Because the texture wraps around at the edges, this simulation has reached an equilibrium in this state.

Noise

While the pattern in the above image is interesting, it can be greatly improved with the addition of some randomness in the simulation. To introduce randomness, I add a second texture ti the simulation which stores a set of random 4 values at each pixel. Before any transition can occur a lookup is done in the random texture and the value is tested against a user provided cutoff. Only if the test passes will the transition take place. This has the effect of breaking up the symmetry of the simulation.

Image 2: The pattern produced using the transition rule with a noise texture to determine the probability of transitions taking places.

Fade Away

To further enhance the simulation I added a fade away term, so that cells which are in state 1, slowly return to state 0. In addition to adding and interesting visual dimensions, this also allows the previously covered portions of the texture to slowly return to an unlit state and so be reused by the simulation.

Image 3: The pattern produced using the transition rule with a noise texture and fading. The center part of the texture shows pixels that were turned on early in the simulation, and so have almost faded back to the zero state over time.

Rendering

I used two methods for rendering the results of my cellular automata simulation. All of them use a texture map to display the data on a square. To better visualize the results I use a view port, and rendered square, that is larger than the resolution of the actual simulation data. Thus a single cell is drawn over several pixels with linear filtering.

Rendering the raw data, in simple black and white.

Rendering using additive blending. To give the illusion of plasma or flames, I rendered the data from the simulation many (50 to 100) times, each time jittering the position of the square on which it is rendered. By setting the color of the square appropriately, and using additive blending, an interesting effect is produced.

Image 4: A rendering of the simulation state using the additive blending technique described above.

Implementation

My cellular automata shader was implemented as a fragment program using the Cg language developed by NVIDIA. The source code is listed below. The inputs to the fragment program are the current state of the cellular automata, a texture of noise, the window dimensions, a vector of probability cutoffs for transitions, and the speed of the fade out.

Complete source code for my shader project has also been provided. The source code is intended as an example of my work not as a working demo. It may contain references to external modules not included in the .zip file.
<source code>

struct v2f : vertex2fragment
{
half4 hPosition : HPOS;
half4 texCoord : TEX0;
half4 texCoord1 : TEX1;
};

fragout main(v2f IN,                                     // input from vertex program
             uniform samplerRECT cellularAutomataState, // state of the cellular automata
             uniform samplerRECT noiseTexture,           // a texture of noise values
             uniform half4       windowDims,             // dimensions of the window
             uniform half4       turnOnProbability,      // transition probabilities
             uniform half        fadeOutSpeed            // speed of fade out
            )
{
fragout OUT;

// Setup the texture coordinate pairs and sample the center and its 4 nearest
// neighbors. Note that since the texture rectangles required for float
// textures do not support texture repeat wrapping, we have to detect the
// edge fragments and do wrapping on our own. The conditional expressions
// below take care of this.
half2 uv = IN.texCoord.xy;
half4 centerState = h4texRECT(cellularAutomataState, uv);

half4 neighborStates;
// left neighbor
uv.x = (IN.texCoord.x <= 1.0h) ? windowDims.x - 0.5h : IN.texCoord.x - 1.0h;
neighborStates.x = h1texRECT(cellularAutomataState, uv);

// top neighbor
uv.x = IN.texCoord.x;
uv.y = (IN.texCoord.y > windowDims.y - 1.0h) ? 0.5h : IN.texCoord.y + 1.0h;
neighborStates.y = h1texRECT(cellularAutomataState, uv);

// right neighbor
uv.x = (IN.texCoord.x > windowDims.x - 1.0h) ? 0.5h : IN.texCoord.x + 1.0h;
uv.y = IN.texCoord.y;
neighborStates.z = h1texRECT(cellularAutomataState, uv);

// bottom neighbor
uv.x = IN.texCoord.x;
uv.y = (IN.texCoord.y <= 1.0h) ? windowDims.y - 0.5h : IN.texCoord.y - 1.0h;
neighborStates.w = h1texRECT(cellularAutomataState, uv);

// set the default result to be the same as the input.
OUT.col = centerState;

// state transition
if(centerState.x == 0.0h)
{
    // test neighbor states and transition prababilities
    half4 p = h4texRECT(noiseTexture, IN.texCoord.xy);
    bool4 neighborsValid;
    neighborsValid = neighborStates == half4(1, 0, 0, 0);
    if(all(neighborsValid) && p.x < turnOnProbability.x)
    {
      OUT.col = 1.0.xxxx;
    }
    neighborsValid = neighborStates == half4(0, 1, 0, 0);
    if(all(neighborsValid) && p.y < turnOnProbability.y)
    {
      OUT.col = 1.0.xxxx;
    }
    neighborsValid = neighborStates == half4(0, 0, 1, 0);
    if(all(neighborsValid) && p.z < turnOnProbability.z)
    {
      OUT.col = 1.0.xxxx;
    }
    neighborsValid = neighborStates == half4(0, 0, 0, 1);
    if(all(neighborsValid) && p.w < turnOnProbability.w)
    {
      OUT.col = 1.0.xxxx;
    }
}
else
{
    // fade away
    OUT.col.xyzw = max(0.0.xxxx, centerState - fadeOutSpeed.xxxx);
}
return OUT;
}

Figure 2: The source code for my cellular automata fragment program..

Results

The simulations I show below were all produced by varying the parameters of the shader (transition probabilities and fade out time) and the base color for the additive blending quad. They all ran at approximately one frame per second on a 933MHz Pentium 3, with an NVIDIA GeForce4 graphics card running the NV30 emulator. These should all run in real time on the NV30 hardware that will be released shortly. The videos were produced using frame capture. They show the simulation at 23 frames per second, a reasonable rate on the NV30 hardware.


Video 1: The evolution of the symmetric pattern shown above. This was produced using the transition rules, without the use of any randomness, or fade away. <mpeg video 2.0MB>	Video 2: The pattern producedby the transition rules using a constant 0.7 probability for all transitions. The effect of the randomness is to break up the symmetry of evolution. <mpeg video 1.1MB>

Video 3: A simulation that uses both probabilistic transition and fade away. The fade away parameter is set very low, 0.01 units per frame, so the simulation runs out of empty space and dies out. This was rendered using the additive blending technique. <mpeg video 2.7MB>	Video 4: A simulation using both probabilistic transition and fade away. The fade away speed was increased to 0.1 units per frame, so that the front can evolve forever by continuously moving into areas vacated by faded cells. <mpeg video 2.3MB>

Video 4: A simulation using both probabilistic transition and fade away. The fade away speed was increased even further, to 0.2 units per frame, and the probability of transitions was lowered to 0.6. This makes the simulation difficult to maintain as the front may die out if not enough transitions occur. The result is a much sparser set of trails. <mpeg video 4.7MB>