RTRay: a realtime raytracer

RTRay is a raytracer for Windows that renders spheres with shadows and reflections fast enough to turn the scene with the mouse. A raytracer fires a ray through every pixel and works out what it hits, and on a PC of 2002 there wasn't time to do that for every pixel of every frame. So RTRay fires as few rays as it can get away with, and fills in the rest.

It comes in two main versions. RTRay A, from 2002, renders a classic scene of a dozen reflective spheres on a floor, tracing only the corners of each 8×8 tile of pixels and filling a tile with one colour when its corners agree. RTRay B, from 2003 to 2005, drops the shadows and reflections to concentrate on the first ray, and renders hundreds of spheres by keeping a short list of the spheres each part of the screen could possibly hit.

As the old LewpenLab site put it when it offered the first one for download:

Raytracing is possible in realtime on modern CPUs with a few tricks! This is my first attempt and the performance is reasonable for small numbers of spheres, even with accurate reflection, shadows and flat shaded lighting.

The classic scene

RTRay A draws into a 480×360 window, a size rounded up to a multiple of 8 for the tiles. The scene is twelve spheres in orange (0xFFBB00), purple (0xBB00FF) and white, and a floor, which is a thirteenth sphere with a radius of 1,000, so big that its top is nearly flat, at a height of −1.5:

  rt_addSphere( 1.0, -1.0, 6.0-6.0, 1.0, texOrange);
  rt_addSphere( 1.0,  3.0, 6.0-6.0, 1.5, texPurple);
  rt_addSphere(-1.0,  2.0, 5.0-6.0, 1.2, texOrange);
...
  rt_addSphere( 8.0, -1.5, 17.0-6.0, 0.7, texPurple);

  rt_addSphere( 0, -1001.5, 0, 1000, 0x666666);

Dragging with the left mouse button turns the spheres about the centre of the scene, which sits 13 units in front of the camera. The light, at (1, 5, 2), isn't turned with them, so it stays in the same place as seen from the camera.

The first versions were built on the same small “pattern” framework as the other C++ graphics effects of the time, and version 002 already has the spheres casting shadows on the floor:

Version 007 brought a “new, optimised image subdivision scheme”, and by version 008, the “proper scene”, the spheres reflect each other and the floor. Version 008 was built twice, as Classic scene.exe and Animated scene.exe; the animated one moves the spheres along sine waves every frame.

Version 009 starts with the note “2002.08.19 - Picked up after ages”. From version 010 the raytracer moved onto the class library of the PolyCSG polygon experiments, and its notes say it “cut out texture & envmap support” and set the next steps as “Optimising subdivision” and “Pre-calcuation”, with a quote dated 9 September 2002: “Think of all you've done, and double it!” Version 013, at 520×390, is the one at the top of this page.

Tracing the corners of each tile

Most of a frame is large areas of one thing: the floor, the face of a sphere, or the black sky. RTRay A only spends rays where something changes. It divides the screen into tiles of 8×8 pixels, traces a ray at each corner of every tile, and then looks at the four corners of each tile. If they agree, the whole tile is filled with the top-left corner's colour without tracing anything else. If they don't, it traces five more rays, at the middle of each edge and the centre, and checks each 4×4 quarter the same way, then each 2×2 block, and if a 2×2 block still disagrees, it traces its other three pixels one by one:

The rays are kept in a grid with a point for every other pixel in each direction, which the code calls superpixels. Each one remembers which frame it was traced in, so a corner shared by four tiles, or a midpoint shared by two, is only ever traced once.

“Agree” means four things are the same at the two corners: the sphere the ray hits, whether that point is in shadow, the sphere seen in its reflection, and whether the reflected point is in shadow. The colours themselves aren't compared:

inline bool rt_comparePixels(RT_PIXEL *pix1, RT_PIXEL *pix2)
{
  return
    pix1->sphere == pix2->sphere &&
    ((bool)pix1->shadow_sphere) == (bool)(pix2->shadow_sphere)
  &&
    pix1->refl_sphere == pix2->refl_sphere &&
    ((bool)pix1->refl_shadow_sphere) == (bool)(pix2->refl_shadow_sphere)
  ;
}

So there's one test for everything: a tile is subdivided when the edge of a shadow crosses it, even if it's all on the same sphere, and the subdivision then traces the full ray, with its reflection, at every new point. The surface and the shadow aren't refined separately. A plan for doing it in layers turns up later, in RTRay B's rendering.txt: fill the block when the object and its shadow agree, then look at the reflection on its own.

if( same(obj) && same(inshadow) )
{
  fillwithshadow()

  if( same(reflection) && same(reflectioninshadow) )
  {
  }
  else
  {
  }
}
else
{
  subdivide()
}

The subdivision itself is a recursive function, called with the tile's top-left superpixel and its size, 4 superpixels for an 8×8 tile:

void rt_render_recursive(int i, int j, int size)
{
  int offset = j*sw + i;
  int pixoffset = i*2 + j*w*2;

  int hsize = size >> 1;
  int dsize = size << 1;

  //- If all pixels are the same then just draw a solid square

  if( rt_comparePixels(&spixel[ offset ], &spixel[ offset + size]) &&
      rt_comparePixels(&spixel[ offset ], &spixel[ offset + sw*size]) &&
      rt_comparePixels(&spixel[ offset ], &spixel[ offset + sw*size + size]) )
  {
    int col = spixel [ offset ].col;

    for(v=0; v<dsize; v++)
    {
      for(u=0; u<dsize; u++) buf[ pixoffset ++ ] = col;
      pixoffset += w - dsize;
    }
  }

  //- Otherwise subdivide unless we've got to 2x2

  else if(size > 1)
  {
    rt_spix( &spixel[ offset + hsize ], i*2+size, j*2);
    rt_spix( &spixel[ offset + sw*hsize ], i*2, j*2+size);
    rt_spix( &spixel[ offset + sw*hsize + hsize ], i*2+size, j*2+size);
    rt_spix( &spixel[ offset + sw*hsize + size ], i*2+size+size, j*2+size);
    rt_spix( &spixel[ offset + sw*size + hsize ], i*2+size, j*2+size+size);

    rt_render_recursive(i, j, hsize);
    rt_render_recursive(i+hsize, j, hsize);
    rt_render_recursive(i, j+hsize, hsize);
    rt_render_recursive(i+hsize, j+hsize, hsize);
  }

  //- Special case to deal with 2x2

  else
  {
    buf[ pixoffset ] = spixel[offset].col;

    RT_PIXEL spix;

    spix.frame = 0; rt_spix( &spix, i*2+1, j*2  ); buf[ pixoffset + 1     ] = spix.col;
    spix.frame = 0; rt_spix( &spix, i*2  , j*2+1); buf[ pixoffset + w     ] = spix.col;
    spix.frame = 0; rt_spix( &spix, i*2+1, j*2+1); buf[ pixoffset + w + 1 ] = spix.col;
  }
}

At 480×360 that's a grid of 241×181 superpixels and 2,700 tiles. The first pass traces 2,806 corners, one ray for every 62 pixels, and a frame where nothing crosses a tile would cost no more than that. Each traced point is more than one ray, though: there's a shadow ray to the light, a reflected ray, and a shadow ray from wherever the reflection lands.

The catch is that anything which fits between the corners of a tile can be missed: a sphere, a shadow or a reflection smaller than 8 pixels that doesn't touch any of the tile's four corners isn't seen at all, and the tile is filled straight over it.

Shadows and reflections

Every surface is flat shaded: a point on a sphere has the sphere's colour, halved if it's in shadow, with no shading across the surface. Where the shading changes is decided by the shadows, and there are two ways for a point to be in shadow:

• If the surface faces away from the light, the point is in the sphere's own shadow, and no ray is needed: the test is the sign of the dot product of the surface normal with the direction to the light. That gives each sphere its hard line between the lit and the dark side.
• Otherwise a shadow ray goes from the point to the light, tested against the other spheres. The spheres are kept in a linked list for this, and when one is found to cast a shadow it's moved to the front of the list, so the next pixel, which is most likely shadowed by the same sphere, finds it first.

  //  Check object normal

  float d = pix->nx * shadow_ray.dx + pix->ny * shadow_ray.dy + pix->nz * shadow_ray.dz;
  if(d < 0) return pix->sphere;
...
      if(s != pix->sphere)
      {
  	    if( s->shadow_stamp >= stamp && rt_shadow_sphere(&shadow_ray, s) )
        {
	        if(ls)
          {
            ls->shadow_list = s->shadow_list;
	          s->shadow_list = shadow_list;
	          shadow_list = s;
          }
  	      return s;
        }
      }

The reflection is a single bounce. The reflected ray is traced from the hit point against all the spheres, the point it lands on gets its own shadow test, and its colour is blended into the surface's at 48 parts in 256, a little under a fifth. A ray that hits nothing counts as black.

Two more ways of saving work are in the code. The first ray is only tested against a sphere if it passes through the sphere's bounding box on the screen, worked out each frame from the sphere's centre and radius. And there are “stamps” on each sphere, meant to mark which spheres were found at a block's corners so that the rays inside the block need only test those; the code that sets them is there but commented out, and every sphere is always tested. That idea is where RTRay B starts.

Version 008 also shaded the inside of each solid block from a small environment texture, looked up with the surface normal interpolated across the block, which gives the bands of light and dark across its spheres. The second screenshot of version 008 has a lighter floor, and the reflections of the spheres in it are fainter:

Hundreds of spheres

With a dozen spheres, testing every ray against every sphere is affordable. With hundreds, it's the whole cost. RTRay B starts again from a reference version, 0004, that does the least a raytracer can:

Simple 4x supersample

First ray only

Spheres only

No shadows

No reflections

29.75 FPS

Tests each sphere

The scene is a string of spheres along a looping 3D curve, each a little different in size and colour: 32 or 64 in the first versions, then 501 in version 0006, 500 in 0007 and 300 from 0008. Sphere 0 is a black background sphere, which is what a ray that hits nothing returns. From version 0002 each 4×4 cell is rendered from its corners, but every sphere is still tested at every corner:

A box around each sphere

The first step is to work out, for each sphere, the rectangle it covers on the screen. A sphere seen in perspective is an ellipse on the screen, and the rectangle is where that ellipse's edges are tangent to the horizontal and the vertical. Version 0008's comment on the function:

  Given a sphere's position and radius, we work out the bounding rect onscreen
  Pretty clever actually, took 4 pages of scribbles and help from Derive.

  Assumes view point is at (0,0,0)
  Assumes screen plane is (u,v,1) - u and v are our screen_x and screen_y positions

The ellipse is written as a quadratic in the screen position u, whose coefficients depend on v. The top and bottom of the ellipse are the values of v where that quadratic has exactly one solution, where B² − 4AC = 0, which is another quadratic, this time in v, and its two roots are the top and bottom of the box. The same again with u and v swapped gives the left and right. If either has no roots, the sphere is off the screen.

Entering and leaving

Each box is then turned into four entries, in four arrays of linked lists with one list for every 4-pixel column or row of the screen: the column where the sphere starts, the column after it ends, the row where it starts, and the row after it ends. The box is made 4 pixels bigger on the right and at the bottom, to cover the cells it touches.

Then, as the renderer goes across a row of 4×4 cells and down the screen, it keeps a list of the spheres whose boxes contain the current cell. Each sphere has two flags, one for being inside its columns and one for being inside its rows, and it's in the list when both are set. Moving one cell to the right means taking out the spheres in that column's “leaving” list and adding the ones in its “entering” list:

The list is doubly linked through the spheres themselves, with sphere 0, the background, as its head, so adding and removing are a few pointer changes with no memory to allocate:

  void rt_scanline_nextColumn( RT_SCENE *scene, int x )
  {
    int i, s;
    int prev, next;

    RT_SPHERE *sphere = scene->sphere;

    x >>= 2;

    //  Go through each sphere we have just left, removing from list

    for( i = x_spheres_end[x].header.first; i != -1; i = x_spheres_end[i].node.next )
    {
      s = x_spheres_end[i].node.sphere;

      //  remove from linked list if the flag was 3 (ie it was in both x and y)

      if( sphere[s].in_xy == 3 )
      {
        prev = sphere[s].in_prev;
        next = sphere[s].in_next;

        sphere[ prev ].in_next = next;
        sphere[ next ].in_prev = prev;
      }

      sphere[s].in_xy &= 0xFFFFFFFE;  // remove the x flag (0x1)
    }

    //  Go through each sphere we have just come into, adding to list

    for( i = x_spheres_start[x].header.first; i != -1; i = x_spheres_start[i].node.next )
    {
      s = x_spheres_start[i].node.sphere;

      if( ( sphere[s].in_xy |= 1 ) == 3 ) //  set x flag
      {
        //  add to linked list if x and y flags both set

        sphere[s].in_prev = sphere[0].in_prev;
        sphere[s].in_next = 0;

        sphere[ sphere[0].in_prev ].in_next = s;

        sphere[0].in_prev = s;
      }
    }

    //  Phew!  Now we have an up-to-date linked list of the spheres available in this superpixel
  }

Moving down to the next row clears the list, updates the row flags from that row's lists, and starts again from the spheres that begin in the first column. A ray then only has to be tested against the spheres in the list:

  for( i = scene->sphere[0].in_next; i; i = scene->sphere[i].in_next )
  {
    dd = rt_intersect_first_sphere( ray, scene->sphere+i );
    if(dd > RT_NEAR_PLANE && dd < d) { d = dd; foundi = i; }
  }

Rendering the cells

A frame is two passes over the screen in 4×4 cells, each walking the lists in the same way. The first traces the top-left pixel of every cell. The second looks at each cell's four corners, and if they all hit the same sphere it fills the cell with that sphere's colour; if not, it traces the other fifteen pixels. RTRay B compares only the sphere that was hit, since there are no shadows or reflections to compare.

Along the way it draws graphs of how the lists change. Version 0008, the “best in & out graphs”, has two: for each row of cells, the spheres entering it in orange and the spheres leaving it in blue, and the same for each column. They're drawn one pixel per row or column of cells, so they come out a quarter of the size of the screen, at the top right and the bottom left. Version 0006, at 800×600 with 501 spheres, drew the total number of spheres on each row as yellow bars from the left edge and on each column as blue bars from the top, with the change from one to the next in white and red along the edges:

Version 0015, based on 0008, renders 300 spheres at 520×390 with the window title “www.lewpen.com - Realtime Raytrace”, and was put up for download as Realtime Raytracer v2. The numbers along the top are the frame count, the seconds running, and the frame rate measured three ways: from the last frame, over the last second and over the last ten frames.

Its description on LewpenLab:

The image below shows 300 spheres packed into a long trail. This is the worst case scenario for the algorithm because at any pixel there are a large number of spheres which a ray could potentially hit. This renders at 30+ fps on a minimum spec desktop machine.

Later versions

The versions after 0008 add simple lighting (0009, which also “produced an interesting accidental effect”), basic specular lighting (0012), “z plane hit testing” (0013), and sorting the spheres by z, which “seems to actually slow down hit tests” (0014). The notes kept with version 0012, dated 7 August 2005, sum up where it had got to, and sketch how the same lists could do CSG, combining spheres with and, or and minus:

Realtime rendering system
-

. First-hit optimisation for spheres
. One light source, no shadowing yet apart from dark side of objects
. Can render 500 spheres with 10fps on my 2.2GHz laptop
...
CSG - A method
-

Get all the entry and exit points of all the spheres at this pixel
Order entry and exit points with the nearest to the viewer first

Have an array of flags, one for each sphere

For each point, starting at the viewer:
  If you are entering a sphere, set that sphere's flag
  If you are leaving a sphere, clear that sphere's flag
  Check against the formula for this CSG
    eg. ( A | B ) & ( C - D )
...
  The first time the result is 1 is where the ray intersects the CSG