# Find the next cell in a grid from a point and direction

I'm trying to solve a very simple problem but I'm unable to come-up with an efficient solution so far. What I'm really trying to do is voxelize triangles in a three dimensional environment but I'll give a 2D example of my problem.

I have a point P and a direction d. P is somewhere inside a cell in the grid. I can easily calculate which cell.

My questions is. When I trace a line from P in direction d what are the coordinates of the first cell I will encounter, and at what location will I enter it? Or, in other words, at what edge and where on that edge will I exit the cell?

As a picture says a thousand words:

I'll also place the broader context here to see if I'm going about this the right way. My idea is to voxelize the triangle with vertices t0,t1,t2 by first voxelizing the edge t0-t1 and then filling in the triangle by tracing multiple edges along the line t0-t1 towards t1-t2. This way I can create the shell of the mesh after which In can start filling it in

lets rephrase it a bit

you have a point p and a direction d, find the smallest t>0 such that p+t*d has one of its coordinates on a whole multiple of cell size in the same dimension.

then it is easy

take p.x and find how much you need to go in the x direction so that we are on a multiple of width xstep = frac(p.x/w)*w

then you find how many d.x you need to add take to get there, if d.x is negative then replace xstep with w-xstep and negate v.x then you do tx = xstep/d.x.

repeat for each of the axis and take the minimum of the ts

• I cannot believe I didn't think of that. Thanks! – Roy T. May 23 '14 at 11:38

You can calculate the distance until the player crosses the next vertical line, and horizontal line. The smallest of the two will be the first to be crossed, so you will know the player will be in the next cell on the right, bottom, left or top.

As you can see on the following image there are two right triangle. You can know Y and X quite easily and if you have the direction you also know a.

Cos(a) = Y/diagonal_distance


The diagonal distance until the next horizontal line is Y/cos(a), and until the next vertical line is X/cos(pi/2 - a).

When d faces down right

if (Y/cos(a) > X/cos(pi/2 - a))
{
//next cell is down
}
else
{
//next cell is right
}


This is just to give you the idea. The calculus isn't exactly the same when d faces other direction. You should probably calculate the distance until the next horizontal line (if d faces up or down), the distance until the next vertical line (if d faces right or left) then compare the two values.