Author : Andreas Seidel
Page : 1 Next >>
Copyright © 1999 by Andreas Christian Seidel
All rights reserved!
Abstract
This tutorial is for all those coders out there who want to know how to get more out of raycasting. It is not needed to know something about the 'conventional' way of raycasting, but it may help you to understand what I'm talking about, if you already know how to do raycasting. You will learn how to produce a more complex world using an advanced raycasting technique. There will be no irritating words about BSP trees, portal rendering or something else you propably heard of before, when reading articles about programming a polygonal 3D-engine. This tutorial is dedicated to pure raycasting!
Introduction
The main idea behind raycasting is to follow a virtual ray of light on it's way through a virtual world made up by bits and bytes within your computers memory. The conventional way of raycasting has two main points that are different to the technique I'll explain in this tutorial:
1.the map is a 2D-array where a number > 0 represents a solid block and a zero stands for an empty space
2.the rays casted out are traced in very small steps to get a resolution that is high enough to produce smooth results
This leads to the following restrictions:
- you can only have orthogonal walls
- all walls have the same size, since every entry in the map is same-size
You will surely agree that these are restrictions that nobody is willing to tolerate in a 3D-engine any more. The following sections will show you how to do raycasting in another, better way to produce better results. Enjoy!
Aims
The aims of this new approach are obvious:
- we want to produce levels with non-orthogonal walls
- the walls should not all have the same size
How can we do this?
First step
The first step is to think about a new level-format. If our level should contain any type of walls a 2D-map as used in a conventional raycaster is no longer the right thing. We need a more variable format.
It is a good idea to save all the walls as lines. Every wall has a starting point (x1/y1) and an end point (x2/y2). The resolution of the map depends on how fine the graphical results should be. But more on that later.
But if you think about this, you'll propably get some problems. Let me help you: you think that it is impossible to create a level with hundreds of walls and render the view at acceptable speed, though? Well, if you tried to handle all those walls once per frame you'd propably wait for minutes to get one frame rendered! But there is a solution for that.
Using sectors
The easiest way to get around handling all the walls at once is to use sectors. You put all the walls of one room together to one sector. By doing that, your level will be completely divided into sectors consisting of a certain number of walls. I think it should be easy to understand, that the player is in one sector at level-startup and moves from one sector to the other during the game. Once you have the sector the player is in, you know all the walls that are possibly seen by the player. These are the walls you have to test for rendering first.
Casting out rays through the level
But how do I render those walls using raycasting? Well, here is the answer: Your walls are lines. And you can calculate the slope of a line, right? In case you do not know how, look at the following equation:
m = (y2 - y1) / (x2 - x1)
(where m is the lines slope and x1, x2, y1, y2 are the walls start- and end-points)
So all of your walls defined in your sectors have a slope. Now you define your first ray. It's a line, too. And has a slope of course. Since you don't know any x- or y-values of your ray, but you know it's angle, you can use the tan()-function to get to the ray's slope:
m(ray) = tan(angle_of_ray)
Once you have both of this values you can do some mathematical transformation and get to an equation which lets you find the intersection between your ray and a wall! And that's the whole trick. Now let's look at this 'magic' equation.
Calculating intersections
First of all you have to write down your line-equations for the wall and for the ray:
(wall)
y = m1 * x + b1
(ray)
y = m2 * x + b2
Since we're searching for a point of intersection we need to put those equations together:
m1 * x + b1 = m2 * x + b2
Well, there are a lot of unknown values. We know m1 and m2, but x, b1 and b2 are unknown at the moment. 3 variables and only one equation? That seems to be bad. But it's not that hard.
First we eliminate b2. Think about the following: If we need to calculate an intersection of two lines. So they must be within the same coordinate system. Since the player is moving, the rays are relative to a moving system, whereas the walls remain where they are. That leads to the following idea:
One of the two b-values is a fixed value and the other is changing. It's up to you which value you want to keep and which you want to calculate, I choosed b2 to be fixed. Simply because b2 is always 0, if you define it as being a fixed value. What does this mean to our coordinate system? It means that the coordinate system has it's origin in the player-position and moves around as the player moves!
How do we get b1?
The formula for b1 is rather easy:
b1 = (playerx - x1) * m1 + (playery - y1)
Once you have b1, it is possible to resolve the formula:
x = b1 / (m2 - m1)
And that's the whole thing. After you calculated the x-value of intersection it should be no problem to find the y-value. But in case you don't know how to handle that, look at the following equation:
y = y1 + (x - x1) * m1
This is the y-value of the found intersection. So how do I calculate the intersection within my program?
Just do the following things:
inputs for this function are:
- the angle of the ray (m2)
- the wall, including the walls gradient (w, m1)
return values are:
- the x- and y-values of the intersection
declare local variable b1
b1 = (playerx - w.x1) * m1 + (playery - w.y1)
x = b1 / (m2 - m1)
y = w.y1 + (x - w.x1) * m1
return (x, y)
That's all. You'll have to handle some special cases where the gradients m1 or m2 get infinite or zero, but that shouldn't be a hard thing to do.
Getting the distance
The most important thing after calculating an intersection is to find out about it's distance to the player, since this value tells you how big your wall-slice will be and which scale you'll have to use for drawing it. We won't use the pythagorean theorem to calculate distances, since it's a rather slow algorithm. We'll use sine and cosine for calculating them.
If you have calulated an intersection you always know the angle of the ray you're currently casting. It's easy to get the sine- and cosine-value for that angle by using a look-up table or the slow trigonometric functions. Our traced ray is nothing else than a hypothenuse in a triangle. The sine of this hypothenuse is equal to the y-difference between playery and the y-value of the intersection (ys) and the cosine is equal to the x-difference between playerx and the x-value of the intersection (xs). It's now easy to get that x- and y-differences by applying a simple subtraction:
x_diff = (playerx - xs)
y_diff = (playery - ys)
Now just divide them by cosine/sine and you get the length of the hypothenuse and so the correct distance!
Note: You could use both values in any case. But it's a good idea to use the bigger value of x_diff and y_diff for the calculation since you'll get more precise results for your distance then.
Caution: If the cosine or sine gets zero you must use the other value, since you can't divide by zero!
Example:
if ( abs(x_diff) > abs(y_diff) )
distance = x_diff / cos(angle); else
distance = y_diff / sin(angle);
Correcting the distance
As you may have noticed we used trigonometric functions to calculate the distance. We worked with our coordinates as if we were in a polar-coordinate system. But we're using a cartesian-coordinate system for our map! The distances
Page : 1 Next >>