Topic : Advanced Raycasting Techniques
Author : Andreas Seidel
Page : << Previous 2  Next >>
Go to page :

we calculate won't be the correct ones. We have to correct them before using them. This correction is done by multiplying the found distance with a correction-cosine. How do we get this 'correction-cosine'?

Imagine the player stands right in front of a wall. If you calculate the distance of the ray with the player-angle to this wall, you get the radius of a circle. Take this distance and change the angle in head! You get a circle! Remember that the height of a wall-slice is affected by it's distance to the player. If the player now stands in front of a straight wall the rays with another angle than the player-angle won't hit the wall, if they have the same distance as the first ray! That's a problem. In effect the rays must hit the wall. And the result is a bigger distance. That would result in a non-straight wall on-screen. And that's not what we want to have! But there's a solution for that...

You just have to find the 'correction-cosine' which is nothing else than the cosine of the difference-angle between the player-angle and the angle of the casted ray. This difference is zero for the ray with the player-angle and so the cosine is 1. In any other case this cosine has a different value. Just multiply this cosine with your calculated distance and you're done! You see that the multiplication does not affect the player-angle-ray since it's 1 there...

Calculating the height of a wall-slice
If a wall is closer to the player it has to be displayed bigger. That's not hard to know. But how do we implement that in our raycaster?

It's an easy thing. Just divide a certain value by the found distance to the wall. What you get is a value which is getting smaller as the distance gets bigger and vice versa. That's all you want, isn't it? It's up to you which value you choose. It depends on a lot of factors. You'll propably want to have walls with same height and width. So it may take some time until you find a more or less correct value for your engine. Just play around with that value until you get to the point...

Here's an example of the formula:

if (distance == 0) distance = 1;     // prevent the formula from dividing by zero
height = certain_value / distance;   // get the height by just dividing

It is that easy! Most of the time goes up for finding the right values.

One word about different heights: if you assign a different 'certain_value' to every sector, you have walls with different heights without having too much trouble!

Scaling the wall-slices
You propably want to put some textures onto your walls?! You have to scale a column of a texture onto one wall-slice. This is done by using a rather simple scaling algorithm that can be implemented in C or assembler. If you want to do it really fast, use assembler, otherwise C does a good job too. The idea is to draw the slice pixel by pixel and advance a certain number of texels within the texture. Since this value won't be an integer-value, we need to use fixed-point arithmetic here, since floating-point math is simply too slow for that job.

Please refer to some other article to learn something on fixed-point arithmetic, I don't want to explain it at this point, sorry.

You get your scaling-factor by just dividing the texture-y-dimension by the height of the wall-slice.

Look at this example for better understanding:

long scale;
scale = (texture.y_dim << 16) / height;      // use 16 bits fixed-point value here

We just take the y-dimension of the texture, reserve 16 bits for the decimal part of the scaling-factor and divide this new value by the height of the wall-slice. Now, we can draw the whole wall-slice by starting at texture-index 0 and advance by the scaling-factor whenever a new pixel is drawn.

Look at the following loop:

int i;                // loop-variable
long index_frac;      // holds the 16 bits fixed-point version of texture-index  
int tex_index;        // the 'normal' texture-index without decimal part

index_frac = 0;       // reset the fixed-point-version of the texture-index to zero
tex_index = 0;        // set texture-index to the first texel
for (i = 0; i < height; i++)
  tex_index += (index_frac >> 16);      // cut off the decimal part and add the whole part of
                                        // index_frac to the texture index
  // place pixel here using tex_index

  index_frac += scale;      // advance index by scale-factor
  index_frac &= 66535;      // mask out the whole part and just keep the decimal part of the
                            // texture-index

I hope you can get this. If not, try to find some other article on scaling-algorithms. Maybe you can find one. I used this algorithm in my engine and it produces good results!

Keep in mind to use as much bits as possible for your decimal part. This improves accuracy. On the other hand you need enough place for the whole part. So 16 bits is a good middle-way.

Handling sectors
One thing is different to 'conventional raycasting'. You're working with sectors. You need to do that to reduce the number of intersections you have to calculate. You need to mark all walls that connect one sector with another as transparent walls. For these walls your not drawing a wall but display another sector instead. You should do that recursively.

So it may look like this:

-> get_intersection_to_wall
   -> is the wall transparent?
      + Yes, draw_column_for(next_sector)
      - No, draw_wall_slice

You see that this algorithm is recursively drawing columns for a certain sector. This is the best way to deal with that.

Finding the right intersections within one sector
One thing is important when trying to find intersections to walls within one sector. You will always find two walls that intersect with a ray. That's just because a ray is a straight line. It can intersect with a wall in front and with one wall behind the player! Ok, and it's up to you to consider which wall should be drawn and which not. Since the two found intersection will always lie in different quadrants of your cartesian coordinate-system, it's easy though to decide which one is the right for you. Just find out in which quadrant the ray's angle is in, and your intersection must occur in the same quadrant! Want to know how?

Here it is:

int get_quadrant(int angle)
  if ((angle >= 0) && (angle < 90)) return(1);        // angle in first quadrant
  if ((angle >= 90) && (angle < 180)) return(2);      // angle in second quadrant
  if ((angle >= 180) && (angle < 270)) return(3);     // angle in third quadrant
  if ((angle >= 270) && (angle < 360)) return(4);     // angle in fourth quadrant

That's how to get the quadrant for the ray. Not too hard. But we have to find out about the quadrant of that intersection too. We just use the x- and y-differences again, to find out about it!

If the x-difference is > 0 it can only be the 1st or the 4th quadrant, otherwise the 2nd or 3rd. If the y-difference is > 0 it can only be the 3rd or the 4th quadrant, otherwise the 1st or 2nd.

If you put these two conditions together you have it! Look at this piece of source:

int get_intersection_quadrant(int xs, ys)  // xs, ys => intersection-point
  int x_diff, y_diff;

  x_diff = playerx - xs;
  y_diff = playery - ys;

  if (x_diff > 0)
    if (y_diff > 0) return(4); else return(1);
  } else {
    if (y_diff > 0) return(3); else return(2);

Well, and it should be easy now to figure out, how a function could look like, that tells you whether an intersection is correct, isn't it?

int correct_intersection(int xs, ys, angle)

Page : << Previous 2  Next >>