Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
You'd probably also like to check scratchapixel.com/lessons/3d-basic-lessons/… which has a very nice and detailed explanation of DDA. –  Grieverheart Dec 5 '12 at 23:35
    
Looks good! Thanks –  mattboy Dec 6 '12 at 0:26

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
ahh you beat me to it! Very nice! –  Philip Dec 5 '12 at 22:22
    
Ha, I kept checking to see if there were any new answers! I felt like I was racing someone :) –  Byte56 Dec 5 '12 at 22:24
    
Very nice, thanks! Was a lot less obvious than I was expecting it to be. –  mattboy Dec 5 '12 at 22:29
    
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 :) –  Byte56 Dec 5 '12 at 22:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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