Java 3D engine

This is a 3D engine in about 1,500 lines of Java, written from scratch: there's no 3D library underneath it, just an array of pixels. It has a scene graph for building shapes out of other shapes, a triangle filler with a z-buffer, and a cartoon effect that finds the outlines from the depth of each pixel.

The scene

There are four shapes: two box frames, a cylinder and a cube. Each one drifts about and grows and shrinks on its own slow sine waves, over a background of leaning rings. Dragging with the mouse turns the whole scene, and holds the animation still until you let go.

Every triangle gets its own flat colour, made from its number. Multiplying the face number by a large odd number gives a jumble of bits, and ORing it with a yellow keeps every colour bright, which is where the pastel stripes on the cylinder come from:

buf.zbufTri(0xFFFFCC00 | (i*0x87638723));

The scene graph

Everything in the scene is either a matrix or an object, and both can be built from others of the same kind.

The matrices are 4x4 transforms with a class for each job: ShiftMat, ScaleMat, and RotateXMat, RotateYMat and RotateZMat, which take their angle in turns rather than radians. A CombineMat holds two other matrices, and works out their product whenever it's updated, so changing the angle in a rotation underneath it changes everything above.

An object, Obj, is a list of points and a list of triangles. A TransformObj is another object seen through a matrix, and a CombineObj is two objects drawn together. From those, the box frames are built in two steps. A "bit" is four cubes squashed into poles and moved out to the corners:

pole1 = new TransformObj
(
  new CubeObj(),
  new CombineMat(new ScaleMat(0.15f, 1.0f, 0.15f), new ShiftMat(-0.85f, 0f, -0.85f))
);

A box frame is three of those bits, one as it is and two turned a quarter turn about X and Z, which gives the twelve edges of a cube. The whole scene is a tree of these, with a scale and a shift above each of the four shapes, and the mouse rotations and a shift away from the camera at the top.

Drawing walks down the tree. Each TransformObj combines its own matrix with the one it was given from above, and passes the result on down to its object:

public void render(RenderBuffer buf, Mat m)
{
  m2.set(mat, m);

  m2.update();

  obj.render(buf, m2);
}

Rendering

Transform and projection

When a basic object is reached, with the combined matrix from all the way up the tree, it transforms its points and projects them onto the screen. The projection is just a divide by z, using the width for both x and y so the pixels come out square, and it keeps 1/z for the depth:

for(i=0; i<numPoints; i++)
{
  x = tpoint[i][0];
  y = tpoint[i][1];
  z = tpoint[i][2];

  spoint[i][0] = buf.w*0.5f + buf.w*0.5f * x / z;
  spoint[i][1] = buf.h*0.5f + buf.w*0.5f * y / z;
  spoint[i][2] = 1.0f / z;
}

1/z is used for depth because, unlike z, it changes evenly across the screen, so it can be stepped along a line of pixels by adding the same amount each time.

Filling triangles

Each triangle is filled a line at a time. The three corners are sorted from top to bottom, and the left and right edges are stepped down the screen in 16.16 fixed point, first from the top corner to the middle one and then on to the bottom. Along each line, 1/z steps across from left to right, and a pixel is only drawn if it's nearer than what's already there:

for(i=xai; i<xbi; i++)
{
  int tempz = (int)(z*0x10000);

  if(tempz > zbuf[oz])
  {
    buf[o] = col;
    zbuf[oz] = tempz;
  }

  o ++;
  oz ++;
  z += dzx;
}

The z-buffer is cleared to 0, which is 1/z for something infinitely far away, so the first triangle to reach a pixel always wins. Because the z-buffer sorts everything out, there's no need to sort the triangles or throw away the ones facing backwards: they're all drawn, and the nearest pixel stays.

Cartoon outlines

The outlines are found from the z-buffer after everything has been drawn. For each pixel, it looks at how the depth changes across and down: the depth to the left and right, minus twice the depth at the pixel. On a flat face that comes to nothing, but it jumps at the edge of a shape and kinks where two faces meet at an angle. The bigger the jump, the darker the pixel is drawn:

int dx = zbuf[i-1] - 2*zbuf[i] + zbuf[i+1];
int dy = zbuf[i-w] - 2*zbuf[i] + zbuf[i+w];

if(dx < 0) dx =- dx;
if(dy < 0) dy =- dy;

if(dx > 40 || dy > 40)
{
  a = dx;
  if(a < dy) a = dy;
  if(a > 255+40) a = 255+40;

  alphaPixel(i, 0, 0, 0, a-40);
}

Blending the black in by how big the change is, rather than just drawing it, keeps the lines soft. The outlines go round the outside of every shape and along the creases inside it, without the engine knowing anything about edges at all. An earlier try, which drew a white halo round the shapes instead, is still in the code, commented out.

Putting a frame together

Each frame draws the rings into the screen buffer, and the shapes into a second buffer of their own, which starts out completely transparent. The outline pass runs on that buffer, and then it's laid over the rings, copying only the pixels the shapes covered:

obj.update();
obj.render(cubes, matFinal);

//- Cartoon effect

cubes.hilightEdges(0xFF000000);

//- Overlay boxes onto screen

screen.layer(cubes);

The pixels get to the browser through TinyPTC, a tiny library by Gaffer that turns an int[] into an image in a Java applet. A loop draws a frame, hands it over and sleeps for 10 milliseconds.

Holding the animation still while you drag is done with the clock. While the mouse is down, the start time is moved along with the real time, so the scene's own time stands still, and it carries on from the same moment when you let go.

Unfinished bits

• The scene was meant to turn by itself as well. The four rotations are set from the time, and then straight away set again from the mouse, so only the mouse turns it.
• The drag doesn't remember where it started. The mouse position is only updated while dragging, so starting a new drag somewhere else makes the scene jump by the distance from where the last one ended.
• Some classes are there for later and not used: Num, Vec, the Im and RenderIm images, and the changed flag on every piece of data.