Raycasting tutorial / vector math question

Question

I'm checking out this nice raycasting tutorial at http://lodev.org/cgtutor/raycasting.html and have a probably very simple math question.

In the DDA algorithm I'm having trouble understanding the calcuation of the deltaDistX and deltaDistY variables, which are the distances that the ray has to travel from 1 x-side to the next x-side, or from 1 y-side to the next y-side, in the square grid that makes up the world map (see below screenshot).

In the tutorial they are calculated as follows, but without much explanation:

//length of ray from one x or y-side to next x or y-side
double deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
double deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));

rayDirY and rayDirX are the direction of a ray that has been cast.

How do you get these formulas? It looks like pythagorean theorem is part of it, but somehow there's division involved here. Can anyone clue me in as to what mathematical knowledge I'm missing here, or "prove" the formula by showing how it's derived?

Answer 1

Ahh yes. I threw my math at it and I think I hit it. You're correct it does involve the Pythagorean theorem and some scaling.

You start with your normalized vector that represents your ray.

It has an x component and a y component. First we want to see how long it is when it travels one unit in the x direction. So what do we do? We want to scale the entire vector so that the x component equals 1. To figure out what to scale it by, we do the following:

scaleFactor = 1/rayDirX;

Writing that out in math it's really just

scaledX = rayDirX * (1/rayDirX) = 1

So we can just call that 1.

Then for the y component:

scaledY = rayDirY * (1/rayDirX) = rayDirY/rayDirX

So now we have our scaled components as (1, rayDirY/rayDirX)

Now, we want to know the length. Now Pythagorean comes into play. Which is

length = sqrt((x * x) + (y * y))

So plugging in our scaled components we get:

length = sqrt((1 * 1 ) + (rayDirY / rayDirX) * (rayDirY / rayDirX))

Apply some algebra and simplify and we get:

length = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX))

Same goes for the length when the y component travels one unit, except we'll have (rayDirX/rayDirY, 1) which results in

length = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY))

There we have your two equations from your question. Pretty neat. Thanks for the algebra exercise.

Answer 2

Assuming the unit length of each grid distance is 1.

The triangle (Triangle 1) in the posted diagram (OP question) consisting of deltaDistX as the hypotenuse, has the same cosine value of it's angle as cosine value of angle formed in the triangle formed by the constituents of the rayDir# Vector (Triangle 2)

So the following can be equated (vector magnitudes below), and simplified (1-3)

Remember : cos = Base/Hypotenuse

0. cosine_triangle_2                   = cosine_triangle_1
1. rayDirX/sqrt(rayDirX^2 + rayDirY^2) = 1/deltaDistX
2. (rayDirX*deltaDistX)^2              = rayDirX^2 + rayDirY^2
3. deltaDistX                          = sqrt(1+ rayDirY^2/rayDirX^2)

Similarly the equation for deltaDistY can be derived.