Ever since Doom came out, most games have had three things in common: dimensions. Now you could argue that Doom isn't truly 3D¹ and that plenty of games before it were three dimensional, but Doom really started a trend. Almost every popular new game is some kind of 3D shoot-everything-that-moves bloodfest. Bloodfests are fun, but they may come and go: 3D is here to stay. Game players want much more than something that looks real, they want games that behave real -- games that feel real in their motion and physics as well as the way they look.

3D graphics have become ubiquitous outside of games. Even television and movies have been flooded with the new breeds of photorealism that can be attained from new techniques and advanced hardware available today. The power to create impressive three dimensional images and animation now lies jointly in the hands of programmers, artists, and graphic designers. Hardware that has been optimized for graphics speed combined with advanced software tools have made it possible for anyone to create spectacular images. Invest a little time in learning the tools, and you will be able to render fantasy worlds on your screen that are limited only by your imagination.

With graphics hardware becoming faster and cheaper, and specialized visualization tools becoming a commodity, why should we invest our time in learning about the arcane mathematics of graphics? For the same reason we play with dry ice: because it's cool. The simplest things can be done quickly with only a small math background. 3D graphics research is also a growing and very exciting field, and new techniques for improving speed are still being developed². This article is the first in a possible series in which I will explore the basics behind 3D graphics, and endeavor to demonstrate some of the tricks and short cuts that have made it one of the most stimulating fields in computer science.

Let's start with the basics. How does a three dimensional object get onto a two dimensional screen? Think about a shadow. When a light shines on an object the object will cast a projection of itself on a nearby surface. The shadow is a flattening of the three dimensional shape into two dimensions. When the shape moves or rotates, the shadow will also change shape with the changes. If it weren't for the fact that the shadow only shows detail on its edges, we could fool the human eye into thinking that it was a three dimensional object.

Here are some 3D cubes⁴. Since your screen is only two dimensional, you are just seeing a "shadow", but I am able to color them as if they were real three dimensional objects. Go ahead and click on them and drag the mouse to rotate them. Let me step you through the creation of this simple applet.

Here is my simple Vertex class:

public class Vertex {

    public float x, y, z;
    public int   screenX, screenY, screenZ;
 
    public Vertex(float x, float y, float z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

The main component of any three dimensional picture is the vertices. They are the 'control points' for the whole picture. The Vertex class has an x, y, and z coordinate specifying its exact location in space. It also has 3 "screen" coordinates that are filled in when it gets transformed to screen coordinates.

Each side of the cubes is a polygon that is an instance of the Face class:

class Face implements Sortable {

    // the vertices that make up this face.
    private Vertex[]        verts;

    //the color to render this face in.
    private Color           color;

    // here we have to figure out the Z anyway,
    // so we also 
    // prepare the x's and y's for rendering.
    public void preRender() {
        z = 0;
        for (int ii=0; ii < verts.length; ii++) {
            xs[ii] = verts[ii].screenX;
            ys[ii] = verts[ii].screenY;
            z += verts[ii].screenZ;
        }
        z /= verts.length;
    }

    //do the painting thing.
    public void render(Graphics g) {
        g.setColor(color);
        g.fillPolygon(xs, ys, xs.length);
    }
}

The Face class holds references to all the vertices that are a part of it, and can render itself to a Graphics after those vertices have been transformed into screen coordinates. The 3D model is a list of Vertex's and a list of Face's. In this example, the vertices are the corners of each of the cubes.

The vertices get translated from their real coordinates to screen coordinates through a transformation matrix. This matrix is a compilation of all the modifications we want to make to each point. Each face is made up of several line segments, and if each of those is translated to screen coordinates, then the face will have been translated. Similarly, each line segment is simply a joining of two vertices. If each vertex gets translated, then the line segment will have been translated. Therefore, we don't need to translate every possible point on the object being rendered; only the vertices used in the picture.

Here is the transformation and painting code from the Applet.

// reset the transformation matrix
// of the model.
md.mat.unit();

// Translate the model to the origin, so
// that the center of it lies right on the
// origin. Without this our rotations will
// be about the origin, which is bad if
// the model is nowhere near it.
md.mat.translate(-(md.xmin + md.xmax) / 2,
                 -(md.ymin + md.ymax) / 2,
                 -(md.zmin + md.zmax) / 2);

// Multiply the model by the rotation
// matrix
md.mat.mult(amat);

// Expand the size of the model so that
// it is close to the size of the window
md.mat.scale(xfac, -xfac, 16 * xfac / w);

// Translate it away from the origin
// so that we can see it.
md.mat.translate(w / 2, h / 2, 8);

Now we translate each of the points, and then tell the faces to render themselves.

mat.transform(verts);

// render them.
for (int ii=0; ii < faces.length; ii++) {
    faces[ii].render(g); 
}

The procedure is very simple: I compile all of the transformations I want to make to each point into one matrix, so that I can apply all the transformations at once. I multiply every vertex by that matrix to get the screen coordinates, and render each of the faces to the screen in the order of decreasing distance away from the screen, so that the ones in back are covered by the ones in front. This completes the illusion and brings a 3D image to the computer screen!

This example is very primitive -- it is intended only to demonstrate the principles behind 3D rendering. For further understanding, I direct the inquisitive reader to the full source code. In future articles, I hope to cover more advanced issues such as shading and better algorithms for rendering the vertices in back before those in front. While you are not yet ready to program the next Quake, you can fool around with the sample code and master the basics before we move on to other things. 

-- Ray <ray@go2net.com> is a Dreamer of Dreams at go2net. If you told him he was gullible, he'd probably believe you.

Source code for the 3D applet demonstrated in this article:
Face.java, Matrix3D.java, QuickSort.java, Sortable.java, ThreeD.java, Vertex.java