Box & reflective tetrahedron

A grey box turns through a red tetrahedron whose faces are mirrors, and the box shows up reflected in them. The objects are all flat-filled polygons. The source file is called Raytrace.java, but nothing in it traces rays: it's polygon rendering, and the reflections are made by drawing a mirrored copy of the box inside each face.

There are two hard parts. The objects pass through each other, so neither one can just be drawn before the other. And a reflection has to stay inside its face, stop where the box goes through the mirror, and show only the parts of the box that are in front of it. One BSP tree, built again every frame, handles all of that. It cuts the box along the planes of the tetrahedron's faces, it gives the order to draw everything in, and it hands each mirror exactly the pieces of the box in front of it, ready to be reflected. The tree is kept in flat, fixed-size arrays, so building it allocates nothing.

The scene

There are two objects, both centred 5 units in front of the eye, and they turn independently of each other. The tetrahedron has its four corners on alternate corners of a cube 3.6 across:

    o1_x[0] =  1.8; o1_y[0] =  1.8; o1_z[0] =  1.8;
    o1_x[1] = -1.8; o1_y[1] =  1.8; o1_z[1] = -1.8;
    o1_x[2] =  1.8; o1_y[2] = -1.8; o1_z[2] = -1.8;
    o1_x[3] = -1.8; o1_y[3] = -1.8; o1_z[3] =  1.8;

That makes a regular tetrahedron with edges 5.09 long. Its four faces are triangles listed by corner number, and makenormal_o1() works out each face's normal once at start-up, from the cross product of two of its edges. They all point outwards.

The box is the four walls of a box with no lid and no base: a rectangle 3 by 5 on the outside and 2 by 4 inside, 1 deep, so each wall is 0.5 thick. The outer corners are at ±1.5 and ±2.5 and the inner ones at ±1.0 and ±2.0, so the walls meet in mitred joints, like a picture frame. Each wall is four faces (top, inner side, bottom and outer side), which makes 16 corners and 16 faces:

    o2_x[ 0] =  1.5; o2_y[ 0] =  0.5; o2_z[ 0] =  2.5;
    o2_x[ 1] =  1.0; o2_y[ 1] =  0.5; o2_z[ 1] =  2.0;
    o2_x[ 2] =  1.0; o2_y[ 2] = -0.5; o2_z[ 2] =  2.0;
    o2_x[ 3] =  1.5; o2_y[ 3] = -0.5; o2_z[ 3] =  2.5;
    o2_x[ 4] =  1.5; o2_y[ 4] =  0.5; o2_z[ 4] = -2.5;
...
    makenormal_o2( 0,  0,  4,  5,  1);
    makenormal_o2( 1,  1,  5,  6,  2);
    makenormal_o2( 2,  2,  6,  7,  3);
    makenormal_o2( 3,  3,  7,  4,  0);

The walls are thinner than the tetrahedron is wide, so as the two turn, the tetrahedron's corners keep poking out through the walls and out of the opening in the middle.

The screen and the palette

The applet is 160x160 pixels. The render buffer is a byte array which is displayed using a MemoryImageSource and an IndexColorModel (this is 256 colours), so each pixel is one byte holding a colour number:

    pal = new IndexColorModel(8, 256, r, g, b);
    src = new MemoryImageSource(image_w, image_h, pal, buf, 0, image_w);
    src.setAnimated(true);
    im = createImage(src);

setAnimated(true) tells the image to expect more frames. Every frame is drawn straight into buf, and then newPixels() sends it on to the screen.

The palette is four ramps of 64 colours:

    for(i=0; i<64; i++) {
      r[i] = (byte)(i*4);
      g[i] = (byte)(i*4);
      b[i] = (byte)(i*4);
    }

    for(i=0; i<64; i++) {
      r[i+64] = (byte)(i*4);
      g[i+64] = (byte)(0);
      b[i+64] = (byte)(0);
    }
...
    for(i=0; i<64; i++) {
      r[i+128] = (byte)(255);
      g[i+128] = (byte)(i*3);
      b[i+128] = (byte)(i*3);
    }

The order of the ramps matters. Grey and red go up in the same steps of 4, and the pink ramp carries on from the top of the red one. That lets the program add red light to a pixel just by adding to its colour number, which comes up in Adding the red.

The background is made once in init() and copied into the buffer at the start of every frame. It's a glow from the blue ramp, colour 192 + r² × 0.0035 where r is the distance from the middle, so it goes from black in the centre to colour 236, (0, 0, 176), in the corners.

The background also has the letters LKS in its bottom right corner, five pixels high. They come from a string, s, built up in five pieces between the palette loops. Only the * and % characters count, and the rest are filler:

*(!'1*89%])%%.      X....X..X..XX.
%^(1@% %) *^).      X....X.X..X...
%4$(@**.? ^*%-      X....XX....XX.
* !1(%?*/?^89*      X....X.X.....X
*%*%-*//*?*%*+      XXXX.X..X.XXX.

Each one sets a pixel to colour 255, the brightest blue, with a black pixel diagonally below it as a shadow:

    k=image_w*(image_h-7)-16;
    for(j=0; j<5; j++) {
      for(i=0; i<14; i++) {
        if(s.charAt(i+14*j) == '*' || s.charAt(i+14*j) == '%') {
          back[k] = (byte)255;
          back[k+image_w+1] = (byte)192;
        }
        k++;
      }
      k += image_w-14;
    }

The same letters are in the message init() prints at start-up, LKS Renderer v0.1, and in the title of the applet's page, raytrace.html: "LKS Render (Java) v0.1". That page shows the applet in the middle of a black page, with "Box & Reflective Tetrahedron" under it in small cyan Arial.

Turning and projecting

Angles are whole numbers, with 4096 to a full turn, and init() fills a sine table and a cosine table with 4096 entries each. An angle is looked up with &4095, so it can count up or down forever and still land in the table. Each object has three angles, and maketrans() turns them into a rotation matrix:

  public void maketrans(int rx, int ry, int rz) {
    double cx, sx, cy, sy, cz, sz;

    cx = costable[rx&4095]; cy = costable[ry&4095]; cz = costable[rz&4095];
    sx = sintable[rx&4095]; sy = sintable[ry&4095]; sz = sintable[rz&4095];

    m[0][0] =          cy*cz; m[0][1] =          cy*sz; m[0][2] = -sy;
    m[1][0] = sx*sy*cz-cx*sz; m[1][1] = sx*sy*sz+cx*cz; m[1][2] = sx*cy;
    m[2][0] = cx*sy*cz+sx*sz; m[2][1] = cx*sy*sz-sx*cz; m[2][2] = cx*cy;
  }

That's the rotations about x, y and z multiplied together into one 3x3 matrix. Each frame, every corner is turned by its object's matrix, moved out to the object's centre, and projected onto the screen:

    for(i=0; i<o1_numpoints; i++) {
      o1_tx[i] = m[0][0]*o1_x[i] + m[0][1]*o1_y[i] + m[0][2]*o1_z[i] + o1_cx;
      o1_ty[i] = m[1][0]*o1_x[i] + m[1][1]*o1_y[i] + m[1][2]*o1_z[i] + o1_cy;
      o1_tz[i] = m[2][0]*o1_x[i] + m[2][1]*o1_y[i] + m[2][2]*o1_z[i] + o1_cz;

      o1_sx[i] = (image_w*0.5) + 100.0*o1_tx[i]/o1_tz[i];
      o1_sy[i] = (image_h*0.5) - 100.0*o1_ty[i]/o1_tz[i];

The eye is at the origin looking along z, with x to the right and y up. The projection divides by depth and scales by 100, so at the objects' distance of 5 one unit is 20 pixels, and the view is 77 degrees across. With every angle at zero, the tetrahedron's corner 0 is at (1.8, 1.8, 6.8) and lands on the screen at (106.47, 53.53). Screen positions stay as doubles: nothing is rounded to a pixel until the polygons are filled.

The face normals are turned by the same matrix, without the move. They're used for three things: which way a face points, the planes in the BSP tree, and the shading. The shading is one sum, 32 + 31 × the x of the normal, so the light comes from the right. A box face pointing right is colour 63, the brightest grey, one pointing left is colour 1, nearly black, and one facing the eye is 32. The tetrahedron uses the same sum, in the red ramp.

The BSP tree

This was built for efficiency with a single-class binary space tree implementation. The tree is stored in flattened, fixed size arrays for optimal performance - no expensive memory allocation and object creation or deletion.

Each node of the tree is one polygon, and the polygon's plane splits space in two: in front, the side its normal points to, and behind. A node's bsp_left branch holds everything behind its plane, and bsp_right everything in front. Here are the arrays:

  static int bsp_size = 256;
  static int bsp_polysize = 8;

  int bsp_num;
  int bsp_left[];
  int bsp_right[];
  int bsp_poly_num[];
  double bsp_poly_sx[][], bsp_poly_sy[][];
  double bsp_poly_x[][], bsp_poly_y[][], bsp_poly_z[][];
  double bsp_nx[], bsp_ny[], bsp_nz[];
  double bsp_x[], bsp_y[], bsp_z[];
  int bsp_object[];

A node is an index, and its fields are that entry in each array. bsp_object says which object it came from, 1 for the tetrahedron and 2 for the box. bsp_left and bsp_right are the indexes of its children, or -1 for none. bsp_poly_num is how many corners it has, and the next arrays hold those corners in 3D and on the screen. The plane is a normal, bsp_nx/ny/nz, and a point on it, bsp_x/y/z.

All of it is allocated once in init(), and emptying the tree each frame is just this:

  public void bsp_clear() {
    bsp_num = 0;
    polystack_sp = 0;
    polystack_bp = 0;
  }

New nodes go on the end, at bsp_num, and the links between them are array indexes, so building a tree is all plain stores into arrays that already exist.

The tree is built from scratch every frame, after the corners have been turned: the tetrahedron goes in first, then the box.

The tetrahedron goes in first

Faces of the tetrahedron that point away from the eye are skipped. The eye is at the origin, so a face points away when the dot product of its normal with one of its corners is positive:

    //  Ignore backfacing polygons

    if(o1_tnx[poly]*o1_tx[p1] +
       o1_tny[poly]*o1_ty[p1] +
       o1_tnz[poly]*o1_tz[p1] > 0) return;

The faces that are left go in whole, by testing the middle of each one against the planes already in the tree. The tetrahedron is convex, so every face is behind every other face's plane. The first face is the root, the second goes behind it, on the left, and a third goes behind that. It's always a chain down the left, and a face only ever stores its corners on the screen, not in 3D.

Over a full cycle of the animation, which is 4,096 frames, one face points at the eye in 1,735 frames, two in 2,298 and three in 63. With every angle at zero there are two. Face 0, with its normal (0.577, 0.577, -0.577), faces up, right and towards the eye, and face 1 faces down and left. They meet along the edge from corner 1 to corner 2, the nearest edge to the eye, which runs diagonally across the screen.

Then the box, cut by the tetrahedron

The box's 16 faces go in next, all of them, including the ones facing away. (The test for that is there in bsp_add_o2() but commented out, and they need to be in the tree: a face turned away from the eye can still face a mirror, as we'll see.) Each one is put on a small stack of polygons and pushed down the tree from the root by bsp_add_o2_recurse():

    split = 0;
    if(bsp_object[ptr] != 2) {
      split = needsplit(poly, ptr);
    }

    if(split == 0) {

      //  No split - just add in front or behind depending on center point

      if(bsp_nx[ptr]*(polystack_cx[poly]-bsp_x[ptr]) +
         bsp_ny[ptr]*(polystack_cy[poly]-bsp_y[ptr]) +
         bsp_nz[ptr]*(polystack_cz[poly]-bsp_z[ptr]) < 0) {

        if(bsp_left[ptr] != -1) {
          bsp_add_o2_recurse(bsp_left[ptr], poly);
        } else {
          bsp_left[ptr] = bsp_add_o2_poly(poly);
        }

      } else {
...
    } else {

      // Split polygon

      int sp = polystack_sp;

      split = splitpoly(poly, ptr);

      if(bsp_left[ptr] != -1) {
        bsp_add_o2_recurse(bsp_left[ptr], poly);
      } else {
        bsp_left[ptr] = bsp_add_o2_poly(poly);
      }

      if(bsp_right[ptr] != -1) {
        bsp_add_o2_recurse(bsp_right[ptr], split);
      } else {
        bsp_right[ptr] = bsp_add_o2_poly(split);
      }

      polystack_sp = sp;

    }

At each node, if the polygon has corners on both sides of the node's plane, it's split in two along the plane. The half behind carries on down the left branch and the half in front down the right. If it's all on one side, it goes that way whole, judged by its middle. When a branch runs out, the polygon becomes a new node there.

The test at the top is the interesting part: a polygon is only split by nodes that aren't part of the box. Box faces never cut each other; only the tetrahedron's planes cut the box. So the box gets cut exactly where it passes through the planes of the tetrahedron's faces, which is what the intersection needs, and nowhere else.

The split goes round the polygon's edges, and where an edge crosses the plane, splitline() finds the crossing from the two ends' distances to the plane:

  public void splitline(int ptr) {

    double d1 = planedist(ptr, split_x, split_y, split_z);
    double d2 = planedist(ptr, split_xx, split_yy, split_zz);

    if(d1<0) d1 =- d1;
    if(d2<0) d2 =- d2;

    split_cx = split_x + d1*(split_xx-split_x)/(d1+d2);
    split_cy = split_y + d1*(split_yy-split_y)/(d1+d2);
    split_cz = split_z + d1*(split_zz-split_z)/(d1+d2);

  }

Let's take the inner side of the right-hand wall, with every angle at zero. It's the rectangle at x = 1.0 from (1.0, 0.5, 7.0) to (1.0, -0.5, 3.0), and it stands across face 0's plane. That plane goes through corner 0 at (1.8, 1.8, 6.8) with the normal (1, 1, -1)/√3, so a point is (x + y - z + 3.2)/√3 in front of it. The top edge runs from z = 7.0, which is 2.3/√3 behind the plane, to z = 3.0, which is 1.7/√3 in front, so it's cut 2.3/4.0 of the way along, at z = 4.7. The bottom edge is cut at z = 3.7.

The part from z = 3.0 to the cut is in front of face 0 and goes to the right of the root. The part behind goes left, reaches face 1, is wholly behind that too, and ends up in the branch behind both faces.

The polygon stack is fixed-size too, 256 polygons of 8 corners. bsp_add_o2_recurse() notes the top of the stack before a split and puts it back afterwards, so the two halves only use the stack while they're being placed. A polygon starts with 4 corners and gains one each time a plane cuts a corner off, and the most any piece reaches is 6, so 8 is room enough.

With every angle at zero, the 16 faces are split 12 times and the tree ends up with 30 nodes: the two faces of the tetrahedron, 8 pieces of box in front of face 0, 8 in front of face 1 and behind face 0, and 12 behind both. Over a whole cycle it varies from 17 to 46 nodes, with up to 27 splits, well inside the 256.

Drawing back to front

There's no depth buffer. The tree is drawn back to front, like a painter, and later polygons simply cover earlier ones. bsp_recurse() does it:

    if(ptr == -1) { return; }

    left = 1;
    if(bsp_nx[ptr]*bsp_x[ptr] +
       bsp_ny[ptr]*bsp_y[ptr] +
       bsp_nz[ptr]*bsp_z[ptr] < 0) { left = -1; }
...
    //  Do far branch

    if(left < 0) {
      bsp_recurse(bsp_left[ptr]);
    } else {
      bsp_recurse(bsp_right[ptr]);
    }

    //  Draw polygon

    poly_clear();

    i = ptr;
    for(j=0; j<bsp_poly_num[i]-1; j++)
      poly_line(bsp_poly_sx[i][j], bsp_poly_sy[i][j], bsp_poly_sx[i][j+1], bsp_poly_sy[i][j+1]);
    poly_line(bsp_poly_sx[i][j], bsp_poly_sy[i][j], bsp_poly_sx[i][0], bsp_poly_sy[i][0]);

    if(bsp_object[ptr] == 1) {
      poly_fill_col((byte)0);
    } else {
      col = (byte)(32+31*bsp_nx[ptr]);
      poly_fill_col(col);
    }

    //  If it's reflective do more stuff

    if(bsp_object[ptr] == 1) {
      if(left < 0) {
        bsp_reflect_recurse(bsp_right[ptr], ptr);
      } else {
        bsp_reflect_recurse(bsp_left[ptr], ptr);
      }

      col = (byte)(64+32+31*bsp_nx[ptr]);
      poly_fill_add(col);
    }

    //  Do near branch

    if(left < 0) {
      bsp_recurse(bsp_right[ptr]);
    } else {
      bsp_recurse(bsp_left[ptr]);
    }

At each node it works out which side of the plane the eye is on. The eye is at the origin, so that's the sign of the normal dotted with a point on the plane, and negative means the eye is in front. Then it draws the far branch first, then the node's own polygon, then the near branch. Nothing on the far side of a plane can cover anything on the near side, so that's always the right order.

A box polygon is filled in its shade of grey. A tetrahedron face is where the reflections happen: it's filled with colour 0, black, then its near branch is drawn into it mirrored, then red is added over the whole face, and only then is the near branch drawn for real, on top. The next section takes those steps one at a time.

This is also where the intersection comes out right. A box face that goes through a tetrahedron face has been cut along the plane, so the piece behind is drawn before the tetrahedron face, which covers it, and the piece in front is drawn after it, on top. The line where they meet is exactly where the box goes into the face.

With every angle at zero, the 30 nodes are drawn in this order: the 12 pieces behind both faces, then face 1 with its reflection, then the 8 pieces in front of face 1, then face 0 with its reflection, and last the 8 pieces in front of face 0. The box's faces that point away from the eye are drawn too, since they're in the tree, and the faces in front of them cover them up afterwards.

Reflections

Each tetrahedron face that faces the eye is a flat mirror, drawn as a window onto a mirrored copy of the box, cropped to the face's outline. There are five parts to that: how to mirror the box, how to keep it inside the face, which parts of the box to use, what order to draw them in, and how to shade them.

Mirroring in a face

A flat mirror shows the world turned inside out through the mirror's plane: every point appears as far behind the plane as it really is in front, straight across. So to draw the reflection of a point P, the program draws the point P′ instead. P's distance in front of the plane, d, comes from a dot product, and P is moved back along the normal by 2d:

    for(j=0; j<bsp_poly_num[i]; j++) {
      xx = x; yy = y; zz = z;
      sxx = sx; syy = sy;

      x = bsp_poly_x[i][j];
      y = bsp_poly_y[i][j];
      z = bsp_poly_z[i][j];

      npa = bsp_nx[refl]*(x-bsp_x[refl]) +
            bsp_ny[refl]*(y-bsp_y[refl]) +
            bsp_nz[refl]*(z-bsp_z[refl]);

      x -= 2*bsp_nx[refl]*npa;
      y -= 2*bsp_ny[refl]*npa;
      z -= 2*bsp_nz[refl]*npa;

      sx = (image_w*0.5) + 100.0*x/z;
      sy = (image_h*0.5) - 100.0*y/z;

      poly2_line(sxx, syy, sx, sy);
    }

refl is the tetrahedron face's node, so bsp_x/y/z[refl] is a point on its plane (its first corner) and npa is d. The mirrored corner is projected like any other, and its edges go into a span table with poly2_line(), which we'll come to.

Let's take the piece of the inner wall that was cut off in front of face 0 above. Its corner P = (1.0, 0.5, 3.0) is d = (1.0 + 0.5 - 3.0 + 3.2)/√3 = 0.98 in front of the plane. Moving it back by 2 × 0.98 along the normal (0.577, 0.577, -0.577) gives P′ = (-0.13, -0.63, 4.13), which projects to (76.8, 95.3) on the screen.

The eye looks at P′ through the point Q on the plane, and that's exactly where light from P would bounce off the mirror into the eye, at equal angles either side of the normal. It's what a raytracer would find too, by sending a ray from the eye to Q and bouncing it off. For a flat mirror, drawing the mirrored box gives the same picture, one bounce deep.

The piece's other two corners are the ones made by the cut, at (1.0, 0.5, 4.7) and (1.0, -0.5, 3.7). They're on the plane, so d is 0 and they stay where they are. So the reflection meets the real wall exactly along the cut, as anything touching a mirror should.

Cropping to the face

P′ at (76.8, 95.3) is outside face 0 on the screen, below the edge it shares with face 1, and so is a lot of this mirrored piece. It has to be cropped to the face.

The cropping is done in 2D, on the screen, a row at a time. A polygon is filled from a span table: for each row of pixels, where the polygon starts and where it ends (see Filling polygons). When a tetrahedron face is drawn, its spans go into poly_xmin and poly_xmax, and they're left there while its reflections are drawn. Each mirrored piece makes its own spans, in a second table, poly2_xmin and poly2_xmax, and the fill cuts every row down to the face's row before filling it:

    if(poly2_ymin < poly_ymin) { poly2_ymin = poly_ymin; }
    if(poly2_ymax > poly_ymax) { poly2_ymax = poly_ymax; }
...
    for(y=poly2_ymin; y<poly2_ymax; y++) {

      if(poly2_xmin[y] < poly_xmin[y]) { poly2_xmin[y] = poly_xmin[y]; }
      if(poly2_xmax[y] > poly_xmax[y]) { poly2_xmax[y] = poly_xmax[y]; }
...
      o = oo + poly2_xmin[y];
      for(x=poly2_xmin[y]; x<poly2_xmax[y]; x++) buf[o++] = c;

      oo += image_w;
    }

That's the whole crop: on each row, keep the overlap of two ranges. There's no polygon clipping at all. The mirrored piece covers rows 70 to 107 of the screen, and once it's cropped to face 0, 328 pixels of it are left, in rows 70 to 100.

The real wall piece is drawn after the reflection, in the near branch, and it starts exactly where the reflection stops, along the cut.

Which pieces get reflected

Only the parts of the box in front of a mirror's plane can be seen in it, and the tree has already sorted those out. A tetrahedron face's near branch, bsp_right, holds the pieces in front of it, already cut along its plane. So bsp_recurse() just hands that branch to bsp_reflect_recurse(), with the face's node as refl, and it walks the branch drawing every piece mirrored. Only the box is ever reflected: the tetrahedron's other faces are all behind the mirror.

The root face gets every piece in front of it. A face further down the chain gets less: face 1's near branch only has the pieces in front of face 1 that are also behind face 0, since anything in front of face 0 went right at the root. That turns out to be enough. Say the eye looks along d at a point X on face 1, and the ray bounces off as r = d - 2(d·n₁)n₁. How fast it heads out in front of face 0 is r·n₀ = d·n₀ - 2(d·n₁)(n₁·n₀), and in a regular tetrahedron the normals of any two faces have a dot product of -1/3, so that's d·n₀ + ⅔(d·n₁).

Both terms are negative: the ray is heading into face 1, and the eye is in front of face 0 while X isn't. So the bounced ray starts on or behind face 0's plane and only goes further behind it, and nothing in front of face 0 can ever be seen in face 1. (That holds because the faces meet at less than a right angle.)

This is also why the box's back faces are kept. With every angle at zero, the eye is level with the middle of the box, so it sees neither the top nor the bottom. But face 0 shows a piece of the bottom of the right-hand wall, and face 1 a piece of the top of the left-hand one, because they face the mirrors.

The faces that point away from a mirror are dropped for free. Mirroring turns a polygon inside out, so a face turned towards the mirror comes out wound the other way round on the screen. poly2_line() is poly_line() with left and right swapped to match: an edge that would set poly_xmax sets poly2_xmin:

//    x1 = image_w-x1;
//    x2 = image_w-x2;

    if(y2>y1) {

      // line going down - right hand side
...
      for(y=iy1; y<iy2; y++) {
        x = (int)(x1 + (x2-x1)*(y-y1)/(y2-y1));
        if(x > image_w) { x = image_w; }
        if(x < 0) { x = 0; }
        poly2_xmin[y] =  x;
      }

A mirrored polygon facing the right way gets spans that run left to right and is filled. One facing the wrong way gets every span backwards, its start after its end, and the fill loop in poly2_fill_col() does nothing. (The two commented-out lines at the top would flip the picture left to right instead.)

The order inside a reflection

bsp_reflect_recurse() walks its branch the same way as bsp_recurse(), far side first, and decides which side is far with the same test: which side of each plane the real eye is on. But the mirrored box is really seen from the eye's mirror image, behind the face (the hollow point in the diagram above), and for a plane that passes between the two, the order comes out the wrong way round.

In practice it hardly shows. Running the same sums for every seventh frame of the cycle with the mirrored eye in that test instead, 13 of the 586 frames come out differently, by at most 59 of the 25,600 pixels.

Shading the reflection

A mirrored piece is shaded with the same sum as a real one, 32 + 31 × the x of its normal, but with the normal mirrored too:

    if(bsp_object[ptr] == 2) {

      x = bsp_nx[ptr];
      y = bsp_ny[ptr];
      z = bsp_nz[ptr];

      npa = bsp_nx[refl]*x +
            bsp_ny[refl]*y +
            bsp_nz[refl]*z;

      x -= 2*bsp_nx[refl]*npa;
      y -= 2*bsp_ny[refl]*npa;
      z -= 2*bsp_nz[refl]*npa;

      col = (byte)(32+31*x);
      poly2_fill_col(col);
    }

So the reflection is lit as if the mirrored box were a real object behind the mirror, with the light still coming from the right. The inner wall piece points straight left, so it's colour 1, nearly black, but its mirrored normal is (-0.33, 0.67, -0.67), and its reflection is colour 21.

Adding the red

Once the reflections are in, the face's own colour goes on top. poly_fill_add() adds 64 + 32 + 31 × the x of the face's normal to every pixel of the face, using the face's spans, which are still there. That's the face's shade in the red ramp, 64 up from the same shade in grey, and Java's byte addition simply wraps past 127.

Where nothing was reflected, the pixel is still 0 and turns into plain red. Where there's a grey reflection, the grey and the red add up. If the two shades come to less than 64 the result is a brighter red, and if they go over, it runs on into the third ramp, from red towards white. Face 0's normal x is 0.577, so it adds 113, and face 1's is -0.577, so it adds 78:

So the reflections come out as light added to the mirror's own red, and the bright ones wash out towards pink, with one byte add per pixel and no lookup table. The greys go up to 63 and the red up to 127, so the sum never gets past 190 and never wraps round into the blue.

Then the near branch is drawn for real, over the top, and the face is done.

Filling polygons

Everything is drawn by one small polygon filler, and every pixel of every polygon goes through it, so this is where the speed comes from. It works on spans: for each row of the screen, where the polygon starts and where it ends.

Span tables

poly_clear() empties the table, setting every row's start to 160 and its end to 0. Then each edge of the polygon goes in with poly_line():

    if(y2>y1) {

      // line going down - right hand side

      iy1 = (int)(y1)+1;
      iy2 = (int)(y2)+1;

      if(iy1 >= image_h) { return; }
      if(iy2 <= 0) { return; }
      if(iy1 < 0) { iy1 = 0; }
      if(iy2 > image_h) { iy2 = image_h; }

      if(iy1 < poly_ymin) { poly_ymin = iy1; }
      if(iy2 > poly_ymax) { poly_ymax = iy2; }

      for(y=iy1; y<iy2; y++) {
        x = (int)(x1 + (x2-x1)*(y-y1)/(y2-y1));
        if(x > image_w) { x = image_w; }
        if(x < 0) { x = 0; }
        poly_xmax[y] =  x;
      }

    } else {

      // line going up - left hand side

      t = x1; x1 = x2; x2 = t;
      t = y1; y1 = y2; y2 = t;
...

A polygon facing the eye goes round clockwise on the screen, so every edge going down the screen is on its right and every edge going up is on its left. An edge going down sets the end of each row it crosses, poly_xmax. An edge going up has its ends swapped, so it's always walked from the top, and sets the start of each row, poly_xmin. A convex polygon crosses each row exactly twice, once each way, so one pass round its edges fills in every row it covers, and poly_ymin and poly_ymax remember which rows those were.

Then the fill is two loops, writing one byte per pixel:

  public void poly_fill_col(byte c) {
    int x, y, o, oo;

    oo = image_w*poly_ymin;

    for(y=poly_ymin; y<poly_ymax; y++) {
      o = oo + poly_xmin[y];
      for(x=poly_xmin[y]; x<poly_xmax[y]; x++) buf[o++] = c;

      //  TEMP - draw backfacing as well
      o = oo + poly_xmax[y];
      for(x=poly_xmax[y]; x<poly_xmin[y]; x++) buf[o++] = c;

      oo += image_w;
    }

  }

The second inner loop, marked TEMP, fills rows whose start is after their end, which is what a polygon facing away from the eye gives. That's how the box's back faces get drawn. poly_fill_add() is the same with += in place of =.

Exact edges

The corners are never rounded to pixels. They come out of the projection as doubles, and every edge is worked out from its exact ends, row by row. The first row an edge fills is the first whole row below its top, (int)(y1)+1, and on each row the x is worked out directly from the exact line and then cut down to a whole number.

Let's take the edge where the inner wall meets face 0, from the cut corner A at (101.28, 69.36) to the other cut corner at (107.03, 93.51). Its top is at 69.36, so it starts on row 70 and runs to row 93. On row 70 the line is at x = 101.28 + 5.75 × (70 - 69.36)/24.15 = 101.43, so the span changes over at 101. On row 73 it's at 102.14, and on row 77 at 103.10. There's no stepping from one row to the next and no running total, so no error builds up, and no special first step is needed to get from the corner to the first row: each row is worked out from the corner directly.

What that adds up to is that every pixel is tested at a single point, the top right corner of the pixel, (x + 1, y). A row is in a polygon when y is past the polygon's top edge and not past its bottom edge, and a pixel is in it when its corner is past the left edge and not past the right. Which corner doesn't matter, only that every polygon uses the same rule. The polygon on one side of an edge fills up to exactly the pixel where the polygon on the other side starts, so shared edges have no gaps and no pixel is drawn twice. Both sides always walk the edge from its top end, so they get the same x on every row.

On the left, the reflection and the real wall meet along the exact edge. On the right are the same rows with the corners rounded to whole pixels first, as a simpler filler might do: A moves from (101.28, 69.36) to (101, 69) and the other end to (107, 94). The two sides still meet without a gap, but two of these eight rows have moved by a pixel.

That's what matters for the intersections. The cut corners aren't points of the model: they're made fresh every frame, where the box's edges cross the tetrahedron's planes, and as the objects turn they slide along those edges. With exact positions, the line where the box goes into a face moves smoothly, a fraction of a pixel per frame, and the box's edges stay straight through the cut. Rounded, each corner would jump a whole pixel at a time, each at its own moment, and the line of the intersection would twitch and step against the straight edges either side of it.

Speed

The work per pixel is one byte store in the fill loop (or a byte add, for the red). There's nothing per pixel for the edges or the cropping: those happen once per row. An edge costs a multiply and a divide per row, in doubles, where a lot of fillers would step along in fixed point, but at 160 rows that's small, and it's what gives the exact edges. Add to that a screen of 25,600 one-byte pixels, no depth buffer because the tree gives the order, and no objects made or thrown away while drawing, and a frame is a small amount of work.

Animation

The applet starts a thread that sleeps for 20 milliseconds and draws a frame, over and over:

  public void run() {

    while(true) {
      try {
        runThread.sleep(20);
      } catch (InterruptedException e) {
        return;
      }

      redraw();
    }
  }

Each frame is redraw(): copy the background into the buffer, step the angles, turn and project both objects, build the tree, draw it, add the corner pattern, and send the pixels to the screen. Unless you're dragging, the angles step by fixed amounts:

    if(pause == 0) {
      o1_rx += 1; o1_ry += 17; o1_rz -= 3;
      o2_rx -= 7; o2_ry -= 9; o2_rz += 4;
    }

The steps are all whole numbers, so after 4,096 frames every angle is back where it started and the animation repeats. It can't repeat any sooner, because the tetrahedron's x angle only steps by 1.

The "little cornery moving bit", as the comment calls it, is an 8x8 square in the top left corner, with diagonal stripes of white (colour 63) and red (colour 127) four pixels wide that move along by one pixel every frame:

    k = (k+1)&255;

    for(o=0, j=0; j<8; j++, o+=image_w-8) {
      for(i=0; i<8; i++) {
        buf[o++] = (byte)( (((k+i+j)&4)>>2)*64+63 );
      }
    }

There's no call to repaint() anywhere. newPixels() tells the image a new frame is ready, and since the applet passes itself to drawImage() as the image's observer, AWT repaints it when the frame arrives. update() is overridden to call paint() straight away without clearing the window first, so it doesn't flicker.

The player at the top of the page runs the original Raytrace.class through CheerpJ, a Java runtime for the browser.

Controls

All three handlers use the old Java 1.0 event methods:

  public boolean mouseDown(Event evt, int x, int y) {
    pause = 0;
    mouse_oldx = x;
    mouse_oldy = y;
    return true;
  }

  public boolean mouseUp(Event evt, int x, int y) {
    pause = 0;
    return true;
  }

  public boolean mouseDrag(Event e, int x, int y) {
    pause = 1;
    o1_rx += 12*(y-mouse_oldy);
    o1_ry += 8*(y-mouse_oldy)+4*(x-mouse_oldx);
    o1_rz += 12*(x-mouse_oldx);
    o2_rx += 12*(y-mouse_oldy);
    o2_ry += 8*(y-mouse_oldy)+4*(x-mouse_oldx);
    o2_rz += 12*(x-mouse_oldx);
    mouse_oldx = x;
    mouse_oldy = y;
    return true;
  }

A step of 12 is about 1 degree, so the objects turn about a degree per pixel dragged. Both get the same steps, but since they're at different angles to start with, the same steps don't turn them in quite the same way. Pressing the button clears pause as well as letting go, so the objects keep turning by themselves until the mouse actually moves.

Leftovers

• L3DApplet.java is the start of a different design, with classes: an L3DWorld holding an L3DShapeList, which keeps shapes in blocks of 256 with a link to the next block, and an empty L3DShape. It stops part way through a method, its constructors have no brackets, and it wouldn't compile as it is. Raytrace.java doesn't use it.
• init() builds a 64x256 table, poly_alpha, for blending a colour into the screen, and poly_fill_alpha() uses it, but nothing calls poly_fill_alpha(). Nothing calls poly2_fill_add() either, and polystack_object is made but never used.
• Commented out under the tetrahedron's corners is a second set that puts all four in the plane z = 0, a flat square 3.6 across: a plain flat mirror in place of the tetrahedron.
• Commented out in bsp_add_o1() is a fixed plane for the root node, through the middle at z = 5 and facing along z, in place of the first face's own plane.
• A commented-out block of System.out.println() calls in the middle of redraw(), between the box's faces going into the tree, prints the first eight nodes' planes and links. bsp_recurse() has three more, printing each node as it's visited.
• At the end of redraw() is a block that draws the first 16 nodes' normals as short lines, the only use of line(). A space switches it off: /* * / opens a comment that runs on to the /* */ at the end. Take the space out and the first line closes itself.

Intersections in Flash

Flash 3D: intersection draws shapes passing through each other with the same kind of BSP tree: polygons are split by the planes they cross, and the tree is drawn back to front, there with Flash's vector fills. It's built the other way to this one, with a BSPNode object for every node and a new BSPTree every frame, and every shape is split against every other. Some of its later versions also have a commented-out try at drawing a reflection in a horizontal plane.