This paper describes the design and coding of a program to generate instances of a procedural Lifeform, based on the work of William Latham in the late 1980’s. The sneaky thing is that this tutorial is not really about procedural rendering, it’s more about the realworld experience of designing and writing programs on PS2.
Why choose a procedural model? Nearly all of the early example code that ships with the T10000 development kit is something along the lines of “send this magic lump of precalculated data at this magic bit of VU code”. It does show off the speed of the machine and shows that techniques are possible but it’s not very useful if you want to learn how to produce your own code. By choosing a procedural model to program there are several benefits:
 Very little can be precalculated. The program has to explicitly build up all the data structures, allowing more insights into how things are put together.
 It can generate a lot of polygons quickly. Procedural models are scalable to the point where they can swamp even the fastest graphics system.
 It’s more interesting than yet another Fractal Landscape or Particle System. I just wanted to be a little different. The algorithm is only marginally more complex than a particle system with emitters.
 The algorithm has many ways it can be parallelized. The algorithm has some interesting properties that could allow large parts of it to be run on a VU, taking just the numerical description of a creature as inputs and generating the polygons directly. I have only space to explore one way of producing the models, but there are several other equally good separation points.
 It’s been over ten years. I thought it would be fun to try an old technique with modern hardware. Evolutionary Art was once a painstaking, time consuming search through the genome space, previewing and finally rendering with raytracing. Being able to generate 60 new Lifeforms a second opens up whole new areas of animation and interaction.
This paper will start by assuming you are familiar with the internal structure of the PS2 – EE Core, VIF0, VIF1, GIF, DMAC and Paths 1, 2 and 3. It will also assume you know the formats for GIF, VIF and DMA tags as they have been discussed endlessly in previous tutorials.


Simplified PS2 Block Diagram 
Lifeforms
First, a look at the type of model we’re going to be rendering. The ideas for thesemodels come from the organic artworks of William Latham.
Latham (in the days before his amazing sideburns) was recruited in 1987 from a career lecturing in Fine Art by a team of computer graphics engineers at the IBM UK Scientific Centre at Winchester, UK. He was recruited because of his earlier work in “systems of art” where he generated huge paperbased tree diagrams of forms that followed simple grammars. Basic forms like cubes, spheres and cylinders would have transformations applied to them – “scoop” took a chunk out of a form, “bulge” would add a lobe to the side, etc. These painstaking hand drawn production trees grew to fill enormous sheets of paper and were displayed in the exhibition “The Empire of Form”.
The team at IBM Winchester wanted to use his insights into rule based art to generate computer graphics and so Latham was teamed with programmer Stephen Todd in order to make some demonstrations of his ideas. The resulting programs Form Build and Mutator were used to create images for the exhibitions “The Conquest of Form” and “Mutations”.
The final system was documented in a 1989 IBM Systems Journal paper (vol.28, no.4) and in the book “Evolutionary Art and Computers”, from which all the technical details in this tutorial are taken. (Latham later went on to found the company Computer Artworks who have recently released the game Evolva).
The aim of this tutorial is to render a class of Lifeform that Latham called a “Lobster” as efficiently as possible on the Playstation2. The Lobster is a useful object for exploring procedural rendering as it is a composite object made three parts, head, backbone and ribcage, each of which is a fully parameterized procedural object.


An instance of the Lobster class. 
Definitions
In this talk I shall be using the Renderman standard names for coordinate
spaces:
 Object space – Objects are defined relative to their own origin. For example, a sphere might be defined as having a unit radius and centered around the origin (0,0,0).
 World Space – A modeling transformation is used to position, scaled and orient objects into world space for lighting.
 Camera Space – All objects in the world are transformed so that the camera is sitting at the origin looking down the positive zaxis.
 Screen Space – A 2D space where coordinates range from –1.0..1.0 along the widest axis and takes into consideration the aspect ratio along the smallest axis.
 Raster Space – A integer 2D space where increments of 1 map to single pixel steps.
The
order of spaces is:
object
> world > camera > screen > raster
Defining
A Horn
The basic unit of rendering is the horn, named because of it’s similarity
to the spiral forms of animal horns. A control parameter is swept
from 0.0 to 1.0 along the horn and at fixed intervals along this
line primitives are instanced – a sphere or a torus – according
to an ordered list of parameterized transformation rules.
Here’s an example declaration from the book:
neck
:= horn
ribs (18)
torus (2.1, 0.4)
twist (40, 1)
stack (8.0)
bend (80)
grow (0.9) ;


An example horn. 
The above declaration, exactly as it appears in the book, is written in a high level functional scripting language the IBM team used to define objects. We will have to translate this language into a form we can program in C++, so let’s start by analyzing the declaration line by line:
neck := horn
The symbol “neck” is defined by this horn. Symbols come into play later when we start creating linear lists of horns or use a horn as the input primitive for other production rules like “branch” or “ribcage”. At this point in the declaration the horn object is initialized to zero values.
ribs (18)
This horn has 18 ribs along it’s length. To generate the horn, an iterator will begin at the start position (see later, initially 0.0) and count up to 1.0, taking 18 steps along the way. At each step a copy of the current inform (input form) is generated. Internally, this interpolator value is known as m. The number of ribs need not be an integral number – in this implementation the first rib is always at the start position, then a fractional rib is generated, followed by the integer ribs. In effect, the horn grows from the root.
torus (2.1, 0.4)
This horn will use for it’s inform a torus of major radius 2.1 units and minor radius 0.4 units (remember that these values are just the radii, the bounding box size of the object is twice these values). In the original Form Build program this declaration can be any list of horns, composite forms or primitives which are instanced along the horn in the order they are declared (e.g. sphere, cube, torus, sphere, cube, torus, etc.), but for our purposes we will allow only a single primitive here. Extending the program to use generalized primitive lists is quite simple. Primitives are assumed to be positioned at the origin sitting on the xz plane, right handed coordinate system.
twist (40, 1)
Now we begin the list of transformations that each primitive will undergo. These declarations specify the transform at the far end of the horn, so intermediate ribs will have to interpolate this transform along the horn using the iterator value m.
twist(angle,offset) is a compound transform that works like this:
 translate the rib offset units along the xaxis.
 rotate the result m*angle degrees around the yaxis.
 translate that result –offset units along the xaxis.
The end result, at this stage, produces a spiral shaped horn sitting on the xz plane with as yet no elevation.
stack (8.0)
This translates the rib upwards along the +yaxis. Note that although we have 18 ribs that are 0.8 units high (18 * 0.8 = 14.4), we’re packing them into a space 8.0 units high. Primitives will therefore overlap making a solid, space filling form.
bend (80)
This rotates each rib some fraction of 80 degrees around the zaxis as it grows. This introduces a bend to the left if you were looking down the –zaxis (right handed system).
grow (0.9)
This scales the rib by a factor of 0.9, shrinking each primitive by 10 percent. This is not to say that each rib will be 90 percent of the size of the previous rib, the 0.9 scale factor is for the whole horn transformation. In order to interpolate the scale factor correctly we need to calculate powf(0.9,m) where m is our interpolator.
At the end of this horn declaration we have defined three areas of information:
 The horn’s attributes (18 ribs, start counting at zero)
 The ordered list of input forms (in this case a single torus).
 The ordered list of transformations (twist, stack, bend, grow).
The order of declarations inside each area is important e.g. twist comes before stack, but between areas order is unimportant e.g. ribs(18) can be declared anywhere and overrides the previous declaration. This leads us to a design for a horn object, using the C++ STL, something like this:


The
Transformation List
To render a single rib we need to know where to render the inform,
at what size and at what orientation. To use this information we
need to be able to generate a 4x4 matrix at any point along the
parametric line.
Remembering that matrices concatenate right to left, the horn we defined earlier generates this list of operations:
T
= bend * (stack * (twist (grow * identity)))
= bend * stack * twist * grow
* identity
(As a side note, one oddity of the horn generation algorithm presented in the book “Evolutionary Art” is that it seems the programmers have altered the order of scale operations to always prepend the transformation queue. Every other transformation is appended to the left hand end of a transformation queue, e.g.
M = rotate * M
whereas all scale operations (the grow function) are prepended on the right hand side:
M = M * scale
This detail is never discussed in the book but turns out to be necessary to get the diagrams to match the declarations in the book.)
For simplicity’s sake we’ll leave off the identity matrix from the far right and just assume it’s there. If we parameterize this list of transforms w.r.t. the iterator m, the equation expands to this:
T(m) = bend(80*m) * stack(8.0*m) * twist(40*m, 1) * grow(0.9^m)
Each of the transforms has to generate a 4x4 matrix which again expands the equation into the more familiar matrix form (ignoring details of the coefficients):
T(m) = B * S * T * G
=
c s 0 0 s c 0 0 0 0 1 0 0 0 0 1 
1
0 0 0 * 0 1 0 0 0 0 1 0 0 t 0 1 
c
0 s 0 * 0 1 0 0 s 0 c 0 t 0 t 1 
s
0 0 0 * 0 s 0 0 0 0 s 0 0 0 0 1 
We are going to be wanting to move and orient the whole horn to some position in world space to allow us to construct composite objects, so we will have to prepend a modeling transformation we shall call the “root” transform (positioned after the identity):
T(m) = B * S * T * G * root
And finally we will have to transform the objects from world to screen space to generate the final rendering matrix M:
M = world_to_screen * T(m) * root
This description is slightly simplified as we have to take into consideration transforming lighting normals for the primitives. Normals are direction vectors transformed by the transpose of the inverse of a matrix, but as every matrix in this list is simple rotation, translation or scale then this matrix is the same as the modeling matrix T(m) except for a scale factor. We can use the transpose of the adjoint (the inverse not yet divided by the determinant) and renormalize each normal vector after transformation or build a special lighting matrix that ignores translations and scales, retaining only the orthogonal operations that change orientation (i.e. record only rotations and reflections).
void
Horn::render(const Matrix &root,
const
Matrix &world_to_screen);
Chaining
Horns and Build
One operation we’re going to want to do is to chain horns together
to allow us to generate long strings of primitives to model the
backbones and tentacles.


A backbone made from chained horns. 
This is where the root transformation comes into play. To chain horns together we need to transform the root of a horn N+1 by the end transformation of the previous horn N. We do this by getting the horn generation function to return the final matrix of the current horn for use later:
void
Horn::render(Matrix &newroot,
const
Matrix &root,
const
Matrix &world_to_screen);
Another detail of horn generation arises in animations. As the number of ribs increases all that happens is that ribs become more closely packed – if you want the horn to appear to grow in length by adding horns you will have to respecify the stack command in the transformation list to correctly extend your horn for more ribs. The way around this problem is to tell the iterator how many ribs this list of transforms was designed for, allowing it to generate the correct transformations for more ribs. This is done using the build command:
myhorn
:= horn
ribs (9)
build (5)
torus (2.1, 0.4)
stack (11);
This declaration declares a horn where the first 5 ribs are stacked 11 units high, but the horn is designed to transform 9 ribs the remaining four ribs will be generated with interpolation values greater than 1.0.
Initially the horn has a build member variable set to 0.0, telling the interpolator to generate interpolation values of 0..1 using ribs steps. If the build variable is not equal to 0.0, the interpolator will map 0..1 using build steps, allowing requests for fewer or greater ribs to work with the correct spacing:
Matrix T;
float base = (build == 0.0) ? ribs : build;
for(int i=0; i
float m = i / base;
calc_matrix(T, m);
...
}
Branch
and Ribcage
In order to construct the Lobster there are two more structures
to generate – the head and the ribcage.
The head is an instance of a branch object – horns are transformed so that their near end is at the origin and their far ends spread out over the surface of a sphere using a spiral pattern along the sphere’s surface. You can control the pitch and angles of the spiral to produce a wide range of interesting patterns.


Examples of a branch structure. 
The branch algorithm just produces a bunch of root transformations by:
 Generate a point on a unit sphere.
 Calculating the vector from the origin of the sphere to that point on the surface.
 Return a 4x4 transform matrix that rotates the Object space yaxis to point in that direction.
To correctly orient horns twist could be taken into consideration by rotating horns so that the xaxis lies along the tangent to the spiral, but this is unimportant for the look of most Lifeforms. (To do branches correctly we could use a quaternion slerp along the spiral, but we’ll leave that as an exercise). The function declaration looks like this:
branch(const Matrix &root,
const Horn &horn, // inform to instance
const int number, // number of informs to instance
const float angle, // solid angle of the sphere to use
const float pitch); // pitch of the spiral
The ribcage algorithm takes two inputs – a horn for the shape of the rib and a second horn to use as the backbone. To place a horn on the ribcage the ribcage algorithm queries the backbone horn for transformations at specific points along it’s length and uses those transforms as the root for instancing each ribcage horn.
Assuming for the moment that the backbone is a simple stack up the yaxis. Ribs must stick out at 90 degrees from the backbone so we introduce a 90 degree rotation about the zaxis, followed by a 90 degree rotation about the yaxis. Also ribs come in pairs so the second rib must be a reflection of the first about the yz plane. This can all be done by adding in a single reflection matrix. Think of the resulting composite transform as repositioning the rib flat onto the xz plane pointing in the correct direction before moving it along the backbone:
rootrib(m) = Tbackbone(m) * reflection * root
where
reflection =  1
0 0 0  0 0 –1 0  0 –1 0 0   0 0 0 1  
1
0 0 0  and 0 0 –1 0   0 1 0 0   0 0 0 1  
Note that this reflection must be applied to the shading normals too otherwise lighting for the ribcage will be wrong.


Examples of a ribcage (with backbone). 
To help this process we must be able to randomly access transformations along a horn, hence the generalised calc_transform() member function in the Horn class.
The Basic Rendering Process Here, finally, is an outline of the basic rendering process for a Lobster. We will take this as the starting point for our investigation of procedural rendering and start focussing on how to implement this process more efficiently on the Playstation 2 using the EECore, vector units and GS together.
ribcage(const
Matrix &root,
const
Horn &horn, // inform to use as ribs
const
Horn &backbone, // inform to query as the backbone
const
int number); // number of pairs of ribs to generate
The
Basic Rendering Process
Here, finally, is an outline of the basic rendering process for
a Lobster. We will take this as the starting point for our investigation
of procedural rendering and start focussing on how to implement
this process more efficiently on the Playstation 2 using the EECore,
vector units and GS together.


TenThings Nobody Told You About PS2
Before we start translating this Lifeform algorithm into a PS2 friendly design, I’d like to cover some more about the PS2. Later we’ll use these insights to reorder and tweak the algorithm to get some speed out of the machine.
1.
You must design before coding.
Lots of people have said this about PS2 – you cannot just sit down
and code away and expect high speed programs as a result. You have
to plan and design your code around the hardware and that requires
insight into how the machine works. Where do you get this insight
from? This is where this paper comes in. The aim later is to present
some of the boilerplate designs you can use as a starting point.
2.
The compiler doesn’t make things easy for you.
Many of the problems with programming PS2 come from the limitations
of the compiler. Each General Purpose Register in the Emotion Engine