Get all pixels a ray passses through

Question

I have a 2 dimensional space and a ray in that space.

grid with ray

I need to get the coordinates of the red rectangles in the order of the numbers.

My attempt: I have the starting of the ray which is a double.
I have a value yaw which is the direction in radians.
The I did this to get the coordinate of the next red square.

double tanyaw = Math.tan(yaw);
if ((int) (x + 1/tanyaw) == (int) x) {
    x += 1/tanyaw;
    z += Math.signum(tanyaw);
} else {
    x += Math.signum(tanyaw);
    z += tanyaw;
}

However:
grid

That was with yaw = 3*pi/8 note that the line was made in a drawing program and is only approximatly correct.

Maybe an integer division is done instead of float one? by the way, is this a regular grid for collision optimization? — huseyin tugrul buyukisik, Aug 24 '14 at 13:03
@huseyintugrulbuyukisik The ray is like a gunshot and I'm looking for the entity that will be hit first by it, I'm doing this because I quickly can get the entities in those squares so I don't have to check all the entities in the world. — Alice Ryhl, Aug 24 '14 at 13:06
And you are advancing the ray position / wavefront by small time steps? Maybe like a broad-phase? — huseyin tugrul buyukisik, Aug 24 '14 at 13:08
@huseyintugrulbuyukisik I do that to get the chunks of the world, for each chunk I check if any entity in the chunks are hit. — Alice Ryhl, Aug 24 '14 at 13:09
This looks like a "drawing line on pixels" algortihm but on boxes instead. http://en.wikipedia.org/wiki/Line_drawing_algorithm — huseyin tugrul buyukisik, Aug 24 '14 at 13:29
Look at my answer here: http://stackoverflow.com/questions/25016603/forwarding-drawing-line-in-3d-grid — MBo, Aug 24 '14 at 16:53

Pauli Nieminen · Accepted Answer · 2014-08-24T14:25:40.207

Line equation is:

x = x0 + t*xd
y = y0 + t*yd

For simplicity define that begin of shot leaves at t=0 and the last position to test is at t=1. Then you can simple define step sizes with (assuming that you can simple calculate the end position x1,y1):

xstep = 1/(x1 - x0)
ystep = 1/(y1 - y0)
xpos = x0
ypos = y0

And then simple loop until you hit the intersection or end using:

while(!hitsomething()) {
    if (xpos + xstep - x0 < ypos + ystep - y0) {
           xpos += xstep;
           visit(xpos, ypos);
    } else {
           ypos += ystep;
           visit(xpos, ypos);
    }
}

Get all pixels a ray passses through

1 Answers1