Java 3D pillars

This is a small software 3D engine in Java: a scene graph, a triangle filler with a z-buffer, and a post-processing pass, all drawing into an array of pixels. It shows five pillars standing in a ring on a chequered floor, each with a little object spinning on top.

There are two versions. The first has a reflective floor, which is done without any real reflection: there's a second ring of pillars underneath the floor, and the floor is drawn half see-through over it. The second draws everything plain white and finds the outlines afterwards from the z-buffer, so it looks like a pencil drawing.

The applet is called Site3D, and it was the start of a 3D front page for the Zero-Now website, which is where its page gets the title "Zero-Now 3D Web site v0.01". [CHECK: was each pillar meant to lead to a section of the site, as in the mock-up with a "Contact" panel over each one?]

Pillars with reflective floor

The pillars and their reflections on a black background. The objects on top spin by themselves, and dragging turns the whole scene.

White outline (cartoon shading)

The same scene with every face drawn white on a white background, so all the lines come from the outline pass, which looks for jumps in the z-buffer. This version turns by itself, and it's the one at the top of the page.

The code in the rest of this article is from this version. The reflective floor version is built from the same code, with these differences:

The scene

The scene is a tree of shapes. At the top is MainShape, which holds the floor, the five pillars and the five objects on top of them, and each of those is made of smaller shapes, all the way down to cubes.

The pillars

A pillar is three cubes. The cube runs from -1 to 1 on each axis, and it's squashed into a slab for the base and the top and stretched into a tall shaft for the middle:

    Shape s;

    s = new Cube(sc, 0x336699);
    s.trans.scale(1.0, 0.2, 1.0);
    s.trans.translate(0.0, -2.0, 0.0);
    addShape(s);

    s = new Cube(sc, 0x003366);
    s.trans.scale(0.6, 1.8, 0.6);
    addShape(s);

    s = new Cube(sc, 0x336699);
    s.trans.scale(1.0, 0.2, 1.0);
    s.trans.translate(0.0, 2.0, 0.0);
    addShape(s);

That makes a pillar 4.4 units tall, from -2.2 to 2.2, 2 units across at the slabs and 1.2 across the shaft. Its top and bottom are the same, which comes in handy for the reflections.

Five pillars stand in a ring. Each is moved 4.5 units out along x and then turned about the vertical axis by a fifth of a turn more than the last, and the object for each pillar goes through the same moves after being shrunk to half size, then up onto the top:

    for(i=0; i<5; i++)
    {
      s = new Pillar(sc);
      s.trans.translate(-4.5, 0.0, 0.0);
      s.trans.rotateY(3.14159*2.0*i/5.0);
      addShape(s);

      st[i].trans.scale(0.5, 0.5, 0.5);
      st[i].trans.translate(-4.5, 0.0, 0.0);
      st[i].trans.rotateY(3.14159*2.0*i/5.0);
      st[i].trans.translate(0.0, 2.95, 0.0);
      addShape(st[i]);
    }

The floor

The floor is four Checks shapes. Each one is a grid of 4x4 squares, two triangles per square, coloured white or black by whether the square's x and y numbers are odd or even ((i^j)&1). They're scaled up by 2 and put side by side, so the floor is 16 units across with 8 squares a side:

      s = new Checks(sc, col1, col2);
      s.trans.scale(2, 1, 2);
      s.trans.translate(8*i-4, -2.2, 8*j-4);
      addShape(s);

The floor is at -2.2, exactly the bottom of the pillars.

The objects on top

Each pillar has its own object, made from cubes or, for the star, from three-sided pyramids:

The colours of LinkShape4 come straight from the bits of the cube's number, which also give its position:

      s = new Cube(sc, b0*0xFF0000 + b1*0x00FF00 + b2*0x0000FF);
      s.trans.scale(0.4, 0.4, 0.4);
      s.trans.translate(b0*1.2-0.6, b1*1.2-0.6, b2*1.2-0.6);

All together that's 50 cubes of 12 triangles, 24 triangles in the star and 128 in the floor: 752 triangles a frame, and another 180 for the reflected pillars.

Shapes and transforms

A Shape holds up to 64 points, with lines and triangular faces between them, a list of child shapes, and a Transform that places it inside its parent. A shape with only points is drawn as dots, one with only lines as lines, and one with faces as filled triangles. Everything in this scene has faces. A face added without a colour gets one made up from its corner numbers.

Transforms

A Transform wraps a 4x4 matrix from a general matrix package by Doug Palmer, which has had its package and exceptions taken out so it builds on its own. Each call makes a new matrix for the move and multiplies it on the left:

  public void translate(double x, double y, double z)
  {
    m = Matrix.translate(x, y, z).multiply(m);
  }

Multiplying on the left means the moves happen to a point in the order they're written. In the pillar above, the cube is squashed first and then moved down, so it's moved by 2 units and not by 2 squashed ones.

The transform stack

The scene keeps a stack of up to 32 transforms. The bottom one is the camera, which moves everything 11 units away. Drawing a shape pushes its own transform combined with the one below:

  public void transform(Transform t)
  {
    trans[numTransforms] = new Transform(trans[numTransforms-1]);
    trans[numTransforms].transform(t);
    numTransforms ++;
  }

Then a shape draws its children, which push their own, transforms its points with whatever is on top of the stack, draws its faces and pops its transform off again:

    scene.transform(trans);
...
    for(i=0; i<shapes.size(); i++) ((Shape)shapes.elementAt(i)).render();

    //  Transform points

    for(i=0; i<numPoints; i++) scene.transformPoint(p[i], t[i], s[i]);

    //  Render this shape

    if(numLines+numFaces == 0) for(i=0; i<numPoints; i++) scene.plotPoint(s[i][0], s[i][1]);
    if(numFaces == 0)          for(i=0; i<numLines ; i++) scene.drawLine (s[lp1[i]][0], s[lp1[i]][1], s[lp2[i]][0], s[lp2[i]][1]);
                               for(i=0; i<numFaces ; i++) drawFace (s[fp1[i]], s[fp2[i]], s[fp3[i]], col[i]);

    //  Revert transformation

    scene.untransform();

So a cube in a pillar is moved by the cube's transform, then the pillar's, then MainShape's turn and tilt, then the camera's, all in one matrix.

Projection

Each transformed point is projected onto the screen with a divide by z, with 250 pixels as the distance to the screen:

      s[0] = w*0.5 + 250.0*t[0]/(t[2]);
      s[1] = h*0.5 - 250.0*t[1]/(t[2]);
      s[2] = t[2];

At the middle of the scene, 11 units away, one unit comes out at about 23 pixels. A face is skipped if any of its corners is nearer than 0.1, which is all the clipping there is in depth.

Each shape also works out a fog amount from how far away its centre is, and mixes its colour towards the background by it. The fog only starts at 100 units, and nothing in this scene is more than about 23 away, so it never shows.

Filling triangles

A face is drawn by the Poly class. It keeps two tables with an entry for every row of the screen: where the triangle starts and ends on that row, and the depth at each end. Each of the three edges is walked down a row at a time, and which table it goes in depends only on which way it goes. An edge that goes down the screen is on the right-hand side:

    if(y2>y1) {

      // line going down - right hand side

      iy1 = (int)(y1)+1;
      iy2 = (int)(y2)+1;
...
      for(y=iy1; y<iy2; y++)
      {
        x = (int) (x1 + (x2-x1)*(y-y1)/(y2-y1));
        z = (int)(4*4096*65536/ ( ( z1 + (z2-z1) * (y-y1) / (y2-y1) )) );
        if(x > w) { x = w; }  //  TODO:  Clip z to edge of screen too
        if(x < 0) { x = 0; }  //  TODO:  Clip z to edge of screen too
        poly_xmax[y] =  x;
        poly_zmax[y] =  z;
      }

An edge going up is swapped round and fills in the left-hand ends instead. That only works if the corners of every triangle go round the same way on the screen, and that's the trick: a triangle facing away from the camera has its corners going round the other way, so every row ends up with its left end to the right of its right end, and nothing gets drawn. Back faces are thrown away without any test for them. (In the cube's list of faces, each one has a comment with its corners in order, and a "!" where they're listed the other way round so that it faces outwards.)

The depth isn't stored as z but as 1/z, scaled up by 2³⁰ to make it a whole number. A point 11 units away, in the middle of the scene, is stored as 97,612,893. A bigger number is nearer, so the z-buffer is cleared to 0 and a pixel is drawn only if it's bigger than what's there:

      for(y=poly_ymin; y<poly_ymax; y++, oo += w)
      {
        z = poly_zmin[y]; if(poly_xmax[y] > poly_xmin[y]) zd = (poly_zmax[y]-z)/(poly_xmax[y]-poly_xmin[y]);
        for(x=poly_xmin[y], o = oo + poly_xmin[y]; x<poly_xmax[y]; x++, o++, z += zd) if(z > zbuf[o]) { buf[o] = c; zbuf[o] = z; }
      }

1/z changes evenly across a flat face on the screen, so it can be stepped along a row by adding the same amount each pixel. Down the edges it's z that's stepped evenly, and then turned into 1/z, which isn't quite right in perspective.

The ends of each row are clipped to the sides of the screen, but the depth at the end isn't moved to match, as the TODO comment says. On a triangle that hangs off the side of the screen, the depth is stepped across the part of each row that's on screen as if it were the whole row.

The reflective floor

A reflection in the floor is the scene mirrored in the floor's plane. The floor is at -2.2, so a point at height y has its reflection at -4.4 - y. A pillar runs from -2.2 to 2.2 and is the same top and bottom, so its mirror image is exactly the same pillar, just moved down by 4.4. There's no need to flip anything:

So MainShape starts with a second ring of pillars, 4.4 lower than the real ones, and gives the floor's two colours a flag in their top byte:

    if(reflections)
    {
      for(i=0; i<5; i++)
      {
        s = new Pillar(sc);
        s.trans.translate(-4.5, -4.4, 0.0);
        s.trans.rotateY(3.14159*2.0*i/5.0);
        addShape(s);
      }
    }

    //- Floor

    int col1 = 0xFFFFFF;
    int col2 = 0x000000;

    if(reflections) { col1 += 0x80000000; }
    if(reflections) { col2 += 0x80000000; }

In the white outline version reflections is false. The reflective floor version draws them.

The order matters. The reflected pillars are added first, so they're drawn first, under where the floor will be. Then the floor is drawn, and a colour with anything in its top byte is drawn half see-through: where something has already been drawn, the new colour and the old one are averaged, by halving each and adding them:

        for(x=poly_xmin[y], o = oo + poly_xmin[y]; x<poly_xmax[y]; x++, o++, z += zd) if(z > zbuf[o])
        {
          if(zbuf[o] > 0) buf[o] = ((buf[o]>>1)&0x7F7F7F)+((c>>1)&0x7F7F7F);
                     else buf[o] = c;
          zbuf[o] = z;
        }

Shifting the whole pixel right by one halves all three colour channels at once, and the mask clears the bit that each channel would otherwise pass down into the top of the one below. Where there's no reflection underneath, the z-buffer is still 0 and the floor is drawn at full strength, so the black and white checks stay crisp and the pillars show through at half strength.

Where the floor is drawn at full strength the flag stays in the top byte of the pixel, but the colour model the pixels are shown with has no alpha, so it's ignored. Last come the real pillars, which are nearer than the floor and draw over it as usual.

Only the pillars are reflected, not the objects on top of them. It's the same idea as the mirrors in Box & reflective tetrahedron: rather than working out reflections, draw a mirrored copy of the thing behind the mirror.

Outlines from the z-buffer

In the white outline version, the triangle filler ignores the colour it's given and fills every face with white:

    ////////
    c = 0x00FFFFFF;
    ////////

The background is white too, so after the shapes are drawn the picture is completely white, and everything you see comes from the z-buffer. For each pixel, the outline pass adds up a quarter of the 1/z of each of its four neighbours, and takes away its own:

    for(j=rad; j<h-rad; j++) for(i=rad, o=j*w+i; i<w-rad; i++, o++)
    {
      //  Calculate difference

      d  = (zbuf[o-1]>>2) + (zbuf[o+1]>>2) + (zbuf[o-w]>>2) + (zbuf[o+w]>>2);

      d -= zbuf[o];
      if(d < 0) d = 0;

      d = (d)>>15;
      if(d > 256) d = 256;

      d = 256-d;
...
      if(d < 256)
      {
        r = (buf[o]>>16)&255;
        g = (buf[o]>> 8)&255;
        b = (buf[o]    )&255;

        r = (r*d)>>8;
        g = (g*d)>>8;
        b = (b*d)>>8;

        buf[o] = (r<<16)+(g<<8)+b;
      }
    }

On a flat face 1/z changes evenly, so the average of the four neighbours is the pixel's own value and the difference is nothing. Next to the edge of something nearer, one or two of the neighbours are on the nearer thing, the average comes out nearer than the pixel, and the pixel is darkened by how much. Only the pixels on the far side of an edge are darkened, so each edge gets a line one pixel wide, just outside it.

Here is a pixel just outside the edge of a pillar 11 units away, with one neighbour on the pillar, and different things behind it:

The bigger the jump in depth, the darker the line, and anything from 11 units with something more than about 17 units behind it, or nothing at all, gets solid black. That's why the edges of the floor against the background are hard black lines, and the pillars against the floor are soft grey ones.

The pass skips a border of 4 pixels all round the screen (rad). That's as far out as the wider of two other versions of the test, which are still in the code, commented out: one that also looks two pixels away and one that looks out to four. There's also a 5x5 Gaussian table that nothing uses.

Each frame

The applet, Site3D, is built on TinyPTC by Gaffer, a small class that makes an applet its own image source, so a program can draw into an int[] of pixels and hand the whole array over to be shown. Its main is just a loop:

    while (true)
    {
      scene.render();
      update(buf);
    }

update passes the pixels to the image with setPixels, tells it the frame is finished, and draws the image on the applet. The pixels are 0x00RRGGBB, which is the colour model TinyPTC sets up.

There's no sleep in the loop, so it runs as fast as it can. Time is counted in frames instead, with each one moving the clock on by 0.05, which is right at 20 frames a second:

    time += 0.05;  //  Assume 20 fps

On a faster machine everything just moves faster.

Turning the scene

In the white outline version, the whole scene turns and tilts from the clock:

    rx = -0.45 + 0.15 * Math.sin(time*3.14159/7.391);
    ry = 0.257 * time;
    rz = 0.157 * time;
...
    t.rotateY(ry);
    t.rotateX(rx);
    s.setTransform(t);

At 20 frames a second it goes all the way round every 24 seconds, while the tilt rocks between 0.3 and 0.6 radians, looking down at the floor from between about 17° and 34°, and back every 15 seconds. rz is worked out but not used, and some tumbling rotations about all three axes are still there, commented out.

In the reflective floor version the scene starts tilted by 0.6 and only turns when you drag. Each pixel of drag turns it by 0.01 radians, and the tilt is kept between 0.1 and 1.2:

    scene.ry += (x-mouse_x)*0.01;
    scene.rx -= (y-mouse_y)*0.01;

    if(scene.rx > -0.1) scene.rx = -0.1;
    if(scene.rx < -1.2) scene.rx = -1.2;

The objects on top

Every frame, each object gets its transform built again from scratch. There are five turns, each at its own speed, and each object skips a different one, so no two spin alike:

      if(i != 0) st[i].trans.rotateX(scene.time * 0.18428);
      if(i != 1) st[i].trans.rotateY(scene.time * 0.38291);
      if(i != 2) st[i].trans.rotateZ(scene.time * 0.29219);
      if(i != 3) st[i].trans.rotateY(scene.time * 0.50291);
      if(i != 4) st[i].trans.rotateX(scene.time * 0.18428);

      st[i].trans.scale(1, scale[i], 1);

Then it's put back on its pillar the same way as when it was made, but 2.85 up instead of 2.95.

The wobble is a squash and stretch in height. Every 25 frames it moves on to the next object, and gives it a sine wave that dies away:

    double[] scale = {1, 1, 1, 1, 1};
    i = (frameno / 25)%5;

    scale[i] = 1 + Math.exp(-(frameno%25)*0.1)*Math.sin(frameno*3.14159/5);

The sine wave goes round every 10 frames, and starts out big enough to stretch the object to nearly twice its height and squash it to about half. By the 25th frame it has died down to under a tenth of that, and the next object starts.

Loose ends

• In the white outline version, dragging changes rx and ry just as in the other, but MyScene.render sets them again from the clock every frame, so the drag does nothing.
• LinkShape6 is a scattered ring of thirteen LinkShape1s, to lie on each quarter of the floor as rocks. It's behind a rocky_floor flag, which is false.
• Tri is a copy of Poly without the see-through fill, with an index buffer "for shape picking" that's never made. Nothing uses it. Surface is empty, and Square is never used, and adds a line to a fifth corner it doesn't have.
• Site3D123 is an older applet that draws with an AWT Graphics and flashes a small blue and yellow square in the corner every frame. The page doesn't use it.
• Where the screen is cleared each frame, there's a commented-out alternative that blurs the last frame instead, by averaging each pixel's four neighbours.
• The TinyPTC in the white outline version prints a line to the Java console every time one of its methods is called: four lines a frame.
• Scene.java, Shape.java and Site3Da.java aren't part of the project. They're a simpler scene graph that plots points as single white pixels, and an applet skeleton with the start of a World class. Site3D.java declares its own Scene, Shape and Site3D, so they can't be built together.