Approaching the Third Dimension: Raycasting

Let’s think for a moment about how to implement 3D graphics. One 3D graphics technique, ray-tracing, takes inspiration from the physical world. In the physical world, roughly, sources of illumination (the sun, electric lights, etc) shine in straight lines, which bounce around (potentially changing colour as they bounce) and some reach your eye. Simulating graphics this way is horribly inefficient, because you simulate all the light that never even reaches your eye. So ray-tracing inverts this idea, and instead projects virtual rays from your eyes, Superman-style (one ray per pixel on the screen), and bounces them around until it finds a light-source. Ray-tracing produces good quality graphics, but slowly — so it’s used in 3D films (e.g. Pixar’s films), but not in 3D games.

There are various ways to greatly increase the speed of this technique. One that we’ll look at in this post is to use virtual scenes where one ray per column of pixels is sufficient: this reduces the number of rays from, say, 800*600 down to just 600. This optimised version is called raycasting, and was used in a few early “3D” games such as Wolfenstein 3D:

Note how there is only one solid wall in each vertical slice (column) of the image. So if for each column you send a ray to find which wall it hits, you can draw this seemingly 3D scene quite quickly.

Cubes

The simplest type of scene that raycasting can be used with is a grid of squares. Lots of games use grids (or close enough for games): Bomberman, Pac-Man, etc. Raycasting in this grid allows you to see the grid from your character’s perspective. Here’s an example world that we’ll be using for our raycasting, as seen from above — the white dot is the player, light grey is empty, and the coloured or black sections are walls:

So now we need a method that can take a straight line, and figure out which squares the ray passes through, in order to find the first non-empty square that it will hit. This sounds familiar: we’ve already seen used our line-drawing algorithm to implement line of sight calculations. The only change is that instead of projecting rays in a circle, we’ll project them in front of us, through an imaginary screen.

Here is a zoomed in portion of our world. The white square is the one that the player is standing in. Their eye is in the centre of the square, and is looking through a screen in front of them (facing at 45 degrees). We project lines from the eye, through the imaginary screen and see where they hit:

So most of the screen will be displaying the green wall, and the red wall will be visible on the far left of the screen. The line that escapes the image ends up hitting a black wall, so a small portion of black wall will be visible.

Height

We can use our line-following algorithm to find out which square we’ve hit, and uses that as the colour for the column. But if we just draw that colour from the top to the bottom of the image, we get this:

That doesn’t look 3D! The key addition is to draw the right height in each column, by working out how high the wall is when projected on to the screen. For each ray that’s projected, we know the distance from the eye to the screen (always 0.5 for us), we know the height of the wall compared to where the eye hits (again, always 0.5 for us), so it just remains to use the distance of the wall from the eye (the length of the ray, which we get using Pythagoras) to calculate the height on the screen:

To work out h, we can use the law of similar triangles. The small triangle on the left (with red sides 0.5 and h) is a scale replica of the larger triangle (with purple sides 1.5 and 0.5). When triangles are scale replicas, the ratio of any two sides is the same in each triangle. So:

So in this case:

More generally, where the distance from the eye to the screen is screenDist, and the distance from the eye to the wall is rayLength:

You can then multiply (which will be between 0 and 0.5) by the height of the screen to get how high the wall is above the vertical-centre line. And because our eye is exactly halfway up the wall, the wall is the same “height” below the vertical-centre line. Here’s the code:

double distX = r.getHitX() - eyeX;
double distY = r.getHitY() - eyeY;
double rayLength = Math.sqrt(distX * distX + distY * distY);
height = (int)(((0.5 * screenDist) / rayLength) * img.getHeight());
            
img.drawLine(column, img.getHeight()/2 - height, column, img.getHeight()/2 + height);

We’re drawing on to an image named “img”. When we display this in Greenfoot, our previously block-colour picture now looks 3D:

The effect is even more convincing when you can turn around, so go play the scenario. Left and right turn your view, and the WASD keys move you around the grid (but not necessarily the way you’re facing).