8
\$\begingroup\$

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).

enter image description here

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?

\$\endgroup\$
8
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ ahh you beat me to it! Very nice! \$\endgroup\$ – Philip Dec 5 '12 at 22:22
  • \$\begingroup\$ Ha, I kept checking to see if there were any new answers! I felt like I was racing someone :) \$\endgroup\$ – MichaelHouse Dec 5 '12 at 22:24
  • \$\begingroup\$ Very nice, thanks! Was a lot less obvious than I was expecting it to be. \$\endgroup\$ – mattboy Dec 5 '12 at 22:29
  • \$\begingroup\$ I only found the answer when I gave up trying to reverse engineer it and tried to find how I would get that value if I were doing it. I thought maybe scaling the vector would be some kind of shortcut, but turns out it's the same way they're doing it :) \$\endgroup\$ – MichaelHouse Dec 5 '12 at 22:32
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.