RENDERING PROCESS:

• Introduction
• Principles
• World structure
• Projection
• Finding walls
• Horizontal intersections
• Vertical intersections

MISCELLANEOUS:

• Glossary
  
• Downloads
  
• Links
  

INTRODUCTION:
This page has quite a lot of information on it, and is basically the heart of this site (the casting routines are a big part of the engine's core). The text is maths-oriented, and to keep everything clear, I'll show the derivative steps in finding equations as well. Enjoy :)

OVERVIEW:
The basis of checking horizontal grid-lines is the diagram that is shown below, fig10:

fig10: A ray intersecting horizontal grid-lines

Here we see a ray, r, being cast out from the point P (this is in world coordinates, not cell coordinates) at an angle of alpha degrees (for the sake of clarity and to make life easier, alpha in the diagram isn't in our special world orientation system (as you can see it's measured from the horizontal); it makes no difference to the maths, in case you were wondering).

Along the way to the three wall cubes, you can see the ray intersects four horizontal grid-lines, labelled i₁ to i₄ (note that the part of the wall between i₃ and i₄ is ignored, as that's on a vertical grid-line...)

Another point to note is that the blue triangles are all the same size (this can be proven by using similar triangles, I believe; but you can take my word for it :) except for the one with corners at i₁ and P, which is a special case. OK, now that you hopefully the diagram, it's time to get stuck in...

STARTING OFF:
To begin with, we've got to calculate the position of the first intersection, i₁. In fig10, you can see that there's a small blue triangle with one corner at P and one corner at i₁ (this is the one that's different to all of the other blue ones). We can deduce the Y coordinate of this intersection, as it's simply the Y coordinate of the gridline above P. This is trivial to derive, and can be done like so:

i₁.y = (int(P.y / CELL_HEIGHT) * CELL_HEIGHT) - 1

Basically, the above just rounds P.y to the gridline above P (remember to round down...). However, you'll notice that there's an extra term tagged onto the end that you probably weren't expecting; a -1. This is to ensure that the intersection point is viewed as part of the cell above.

While we're on the subject of Ys, you can see that dy in the diagram is the height of a cell, and it would be negative due to the direction of the ray (remember the direction axes I presented in step I).

But, what if the ray was being cast in a downwards direction ? Well, then we would have to add CELL_HEIGHT onto i₁.y to get the gridline below P, and also obviously make dy positive. A little chunk of pseudo-code to calculate these values may look like this:

if (ray going upwards)
{
	i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) - 1;
	dy  = -CELL_HEIGHT;
}
else
{
	i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) + CELL_HEIGHT;
	dy  = CELL_HEIGHT;
}

And now we've finished our warm-up...the next part enters into the wonderful world of trigonometry...'Yay !' I hear you cry :)

FINDING THE X STUFF:
As with finding the Y stuff, the first bits I'll derive will be to do with the first intersection point, i₁ (shortened to just i from here on in). It's time for another diagram:

fig11: Finding i₁'s X coordinate

The above figure is just the first blue triangle from fig10 blown up, and with a few extra labels. P is the ray's origin, and i is the point of first intersection. We can see that the vertical side of the triangle has length i.y - P.y, and since we know both from the above equations, the actual length of it can be calculated.

Using basic trigonometry, the formula:

         i.y - P.y
TAN(a) = ---------
         i.x - P.x

can be constructed. A quick rearrangement yields:

            i.y - P.y
i.x - P.x = ---------
             TAN(a)

But that gives us the length of the side, and we need to know the X coordinate of the intersection; no problem. We can simply add P.x (which we already know) to both sides of the equation, which gives us:

      i.y - P.y
i.x = --------- + P.x
        TAN(a)

as the final equation; viola !

And using the same trigonometrical principles, we can determine dx as shown in fig10:

         dy
TAN(a) = --
         dx

Changing the subject of the above, the value of dx can be found, thus:

       dy
dx = ------
     TAN(a)

There is a catch, however. If the ray is facing downwards, then dx must be negated. For those of you who are interested in knowing why this is so, then I present an explanation below. For those of you who are happy just to accept the reason `because it is and I said so', then you can safely skip over these ramblings.

The reason that dx must be negated is due to the signs of tangents in different circle quadrants, and the choice of our orientation system. Consider the following diagram:

fig12: Tangent signs in different circle quadrants

The above shows that the tangent of any angle between 0 and 90 degrees will be positive, and so will those for angles 180 to 270 degrees. Also marked on the diagram, in red, are the signs that dx and dy must be for the ray to be headed in the right direction for each quadrant. So, to cast a ray at, say, 45°, then dx must be positive, and dy must be negative if the ray is to step through the grid in the right direction. Now, let's plug some values into our equations for calculating the two deltas (dx and dy).

Let's assume that we're casting a ray at 45°, which would mean dx would have to be positive, and dy negative. So we have:

dy = -CELL_HEIGHT

        dy
dx  = -------
      TAN(45)

Since -CELL_HEIGHT is always negative (or at least it should be...), and TAN(45°) = +1, then the value placed into dx must be negative. That satisfies the signs for the two deltas in that quadrant. Let's see if that is so for a ray being cast at 275°...

dy = CELL_HEIGHT

         dy
dx  = --------
      TAN(275)

The dy delta is positive, which is correct for the quadrant, and TAN(275°) is -11.430052303... A positive value over a negative one yields a negative value, so dx would be negative; from fig12 we can see this is WRONG ! This is why dx must be negated for the lower two circle quadrants (if alpha is > 180° using our orientation system). It may be an idea to try it yourself for the other quadrants and familiarise yourself with the concept, as getting this wrong produces strange effects that are hard to track down in the code.

With everything we've done so far in mind, a quick bit of pseudo-code may look something like:

dy = CELL_HEIGHT;
dx = dy / tangent(alpha);

if (ray going upwards)
{
	i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) - 1;
	dy  = -dy;
}
else
{
	i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) + CELL_HEIGHT;
	dx  = -dx;
}

i.x = P.x + ((i.y - P.y) / tangent(alpha));

There. We've finished the initialization code of the horizontal ray-casting function. That's right...the more observant among you will have realised we haven't actually cast the ray yet...

AFTER ALL OF THAT...
It turns out that casting the ray is a lot more simple than all the stuff I went through above. The casting process is a loop, which basically has the following form:

• Check that the current grid intersection point is within world boundaries
• Check for a wall in the current cell
• If there's a wall:
  • Calculate the length of the ray
  • Return casting information, such as the cell coordinates, ray length, etc.
• If there's no wall, then determine the next intersection point and continue to the first step

KEEPING IN BOUNDS:
To make sure that our engine doesn't ungracefully exit (core dumps and Blue Screens of Death aren't exactly elegant, are they ? :) we must check that the intersection point we have calculated isn't outside of the world boundaries. To make sure we don't fall off the end of the world, the loop condition would look something like this:

while (WORLD_TO_CELL_X(i.x) >= 0 and WORLD_TO_CELL_X(i.x) < world_width and
       WORLD_TO_CELL_Y(i.y) >= 0 and WORLD_TO_CELL_Y(i.y) < world_height) {
	/* Check for walls and do other stuff described below */

	...
};

The WORLD_TO_CELL_?() functions convert world-coordinates to cell coordinates (usually just a rounded-down division by CELL_WIDTH or CELL_HEIGHT for X and Y coordinates, respectively). The variables world_width and world_height are the numbers of cells running in the horizontal and vertical direction in the world, respectively. Now onto what we put into this loop...

CHECKING FOR A WALL:
Checking for a wall is simple. We simply convert the gridline intersection points to cell coordinates, just as in the loop above, and perform an array look-up. That point in the array will hold wall information, such as its texture, etc. In the world_cell structure I defined in step II, there's a height field. If this is set, then there's a wall occupying the cell. Thus, the test is as follows:

if (cells[WORLD_TO_CELL_Y(i.y)][WORLD_TO_CELL_X(i.x)].height > 0)
{
	/* There's a wall in this cell */

	...
}

It couldn't really be any simpler, could it ?

WE'VE FOUND A WALL !
When a wall is found, the minimum that we need to do is calculate the length of the ray and return it (more trigonometry...woo-hoo ! :) We'll also return the X coordinate of the intersection (which can be used in determining the offset into the texture bitmap, as I'll describe later) and the world_cell entry from the cells array (this gives us wall information such as its height, texture, etc.)

If you look back to fig10, you will see there's a large red triangle, with the hypotenuse marked as Ray `r'. It should be obvious that this is the ray we cast, and thus its length needs to be calculated. When we've intercepted a wall, i.x and i.y should have the coordinates of the contact, and P.x and P.y should be left unchanged. Using that knowledge, the large red triangle becomes:

fig13: Finding the length of the ray

As fig13 shows, there are three ways to find the length of the ray, r. The first is to use Pythagoras' Theorem, which states that the length of a right-angled triangle's hypotenuse is equal to the square root of the sum of the squares of the other two sides' lengths. There are two things wrong with using this for the finding r. The first is that is requires a square root to be performed, which is an expensive calculation for a computer. The second is that it can't easily be placed into a Look-Up-Table (LUT), as there are virtually unlimited possibilities for (i_y - P_y)² + (i_x - P_x)². Sine and cosine values, however, can be placed into a LUT easily, as alpha can only be in the range of 0° to 360° (and increments of less that one degree are accecptable).

The equation that will be used to find the length of the ray will be the one involving sine, as we do not wish to divide by zero (the cosines of 90° and 270° are 0, so we'd get a divide-by-zero error when checking horizontal intersections at those angles; since there is no need to cast rays that check horizontal gridlines at 0° and 180° (since they'd never intersect anything, because they run parallel with the gridlines) and the sines of those angles are both 0, then it is the perfect choice). A bit of pseudo-code may look something like:

/* We've found a wall.  Calculate the length of the ray */

ray_length = ABS((i.y - P.y) / sine(alpha));


/* Return all necessary information back to the caller */

return(i.x,				/* The intersection's X coordinate */
       cells[WORLD_TO_CELL_Y(i.y)][WORLD_TO_CELL_X(i.x)],	/* The cell */
       ray_length);			/* The length of the ray */

Note the use of the ABS() function to take the absolute value of the calculation (ie. always give a positive result). This is needed in case one of the sub-calculations produces a negative result, in which case a negative ray length would be given. A negative ray-length would mean a negative distance from the camera to the wall, which isn't really possible.

IF NO WALL WAS FOUND...
If no wall was found, then we continue execution through the loop. The next part of the loop is simply two additions; incrementing the current X and Y coordinates by the pre-calculated deltas to achieve the coordinate of the next intersection of the ray with the horizontal gridline. Pseudo-code for this would look like:

/* No wall was found on this gridline, so jump to the next one */

i.x = i.x + dx;
i.y = i.y + dy;

FALLING OFF THE END OF THE WORLD...
The test condition of our casting loop was one that checked the current intersection point against the world dimensions and made sure we were within bounds. However, what do we do if we reach the edge of the world and find no walls ? Although this shouldn't happen in a properly designed map (or indeed `good practice' perhaps dictates that the engine's world-loading code should have some saftey measures in place to work around this), it sometimes does. When this event occurs, our loop terminates. So, at the end of our loop, and indeed our ray-casting function, we shall have a default set of values returned that key in with no wall being intercepted, like so:

/* Columbus was wrong...:) */

return(0,				/* No X intersection coordinate */
       NULL,				/* No cell */
       MAX_DISTANCE);			/* Ray is at infinity */

Testing for these returned values, our engine can determine whether a slice of a wall should be drawn or not.

AND IN CONCLUSION:
I will conclude this page with a complete pseudo-code listing, piecing together all of the individual extracts given above. Even if you didn't understand everything, you still have the code below as a guide to creating your own horizontal intersection-checking raycasting function.

function cast_horiz_ray(coordinate P, angle alpha)
{
	integer dy;			/* Integer variables */

	real dx, ray_length;		/* Decimal variables */

	coordinate i;			/* Intersection point */


	/* Calculate the intersection increment deltas */

	dy = CELL_HEIGHT;
	dx = dy / tangent(alpha);


	/* Make sure the deltas have the right signs for the ray's direction */

	if (alpha < 180 DEGREES)
	{
		/* Calculate the Y coordinate of the first intersection point,
		   and reverse the sign of the Y delta */

		i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) - 1;
		dy  = -dy;
	}
	else
	{
		/* Calculate the Y coordinate of the first intersection point,
		   and reverse the sign of the X delta */

		i.y = ((P.y / CELL_HEIGHT) * CELL_HEIGHT) + CELL_HEIGHT;
		dx  = -dx;
	}


	/* Calculate the X coordinate of the first intersection point */

	i.x = P.x + ((i.y - P.y) / tangent(alpha));


	/* Iterate through the possible horizontal gridline intersections */

	while (WORLD_TO_CELL_X(i.x) >= 0 and WORLD_TO_CELL_Y(i.y) >= 0 and
	       WORLD_TO_CELL_X(i.x) < world_width and
	       WORLD_TO_CELL_Y(i.y) < world_height) {

		/* Check for a wall on the current gridline intersection */

		if (cells[WORLD_TO_CELL_Y(i.y)][WORLD_TO_CELL_X(i.x)].height>0)
		{
			/* We've found a wall.  Calculate the length of the
			   ray (the distance to the wall slice) */

			ray_length = ABS((i.y - P.y) / sine(alpha));


			/* Return all necessary information back to the
			   caller */

			return(i.x,
			    cells[WORLD_TO_CELL_Y(i.y)][WORLD_TO_CELL_X(i.x)],
			    ray_length);
		}


		/* No wall was found on this gridline, so jump to the next
		   one */

		i.x = i.x + dx;
		i.y = i.y + dy;
	};


	/* Columbus was wrong...:) */

	return(0, NULL, MAX_DISTANCE);
}

There will be some working C code later. The next step will deal with vertical intersection checking; you'll love that one, too :)

NEXT PAGE

PREVIOUS PAGE