Short answer: rounding down.
Long answer:
The ray in the image above might be represented as r = u + tv where u = <0,-3/4> and v = <1, 8/9>, i.e. r follows the line y = (3/4)+ (9/8)x.
Note: that is a typo, it should read y = (3/4)+ (8/9)x.
Thus, ray.origin.x = 0 and ray.origin.y = -3/4.
We can start from these terms: y = y₀ + mx. The ray crosses the vertical axis at y₀, and has a slope of m. Now, the vector u would be (0, y₀) which is the point where the ray crosses the vertical axis. And the vector v would be (1, m).
Constructing the ray in this fashion we would always have 1 on the horizontal axis of v. Which would prevent us from representing a vertical ray. Also, v is not normalized. However, this poses no problem for our purposes.
Based on grid (given at initialization) we know that
grid.corners = [(0,0),(0,2), (2,2),(2,0)];
Here we are defining a rectangle that contains the whole grid. We want to know where the ray enters the rectangle.
Thus, we can determine the boundary at which r intersects the grid. In particular, we see the y = 0 boundary of the grid is represented by the vector r2 = <0,0> + <1,0>t;
At y = 0, there is a boundary of the rectangle that contains the grid. That boundary starts at (0, 0) and ends at (2, 0). We can create a second ray line that corresponds to the boundary. That second ray line r2. The second ray starts at u2 = (0, 0), and v2 would be (1, 0).
solving for r2 = r yields t = 27/32.
That is, we find the point where the two rays intersect. We can easily check the particular solution:
r2 = r <0,0> + <1,0>t = <0, -3/4> + <1, 8/9>t <0,0> - <0, -3/4> = <1, 8/9>t - <1,0>t => 0 = 0t 3/4 = (8/9)t => 3*9 = (4*8)t 27 = 32t 27/32 = t
Note: We discarded the not useful 0 = 0t.
This is not a general approach. It works thanks to both rays using the horizontal axis as parameter. And we were able to discard 0 = 0t, which is not always the case.
I'll go ahead and find a general solution:
r(t) = r2(t2) u + tv = u2 + t2v2 u.x + tv.x = u2.x + t2v2.x u.y + tv.y = u2.y + t2v2.y u.x + tv.x = u2.x + t2v2.x u.x - u2.x + tv.x = t2v2.x (u.x - u2.x + tv.x)/v2.x = t2 (u.x/v2.x) - (u2.x/v2.x) + t(v.x/v2.x) = t2 u.y + tv.y = u2.y + t2v2.y u.y + tv.y = u2.y + ((u.x/v2.x) - (u2.x/v2.x) + t(v.x/v2.x))v2.y u.y + tv.y = u2.y + (u.x*v2.y/v2.x) - (u2.x*v2.y/v2.x) + t(v.x*v2.y/v2.x) u.y + tv.y - t(v.x*v2.y/v2.x) = u2.y + (u.x*v2.y/v2.x) - (u2.x*v2.y/v2.x) tv.y - t(v.x*v2.y/v2.x) = u2.y + (u.x*v2.y/v2.x) - (u2.x*v2.y/v2.x) - u.y t(v.y - (v.x*v2.y/v2.x)) = u2.y + (u.x*v2.y/v2.x) - (u2.x*v2.y/v2.x) - u.y t = (u2.y + (u.x*v2.y/v2.x) - (u2.x*v2.y/v2.x) - u.y)/(v.y - (v.x*v2.y/v2.x)) t = (u.x*v2.y - u.y*v2.x - u2.x*v2.y + u2.y*v2.x)/(v.y*v2.x - v.x*v2.y)
Thus:
t = (u.x*v2.y - u.y*v2.x - u2.x*v2.y + u2.y*v2.x)/(v.y*v2.x - v.x*v2.y) t = (0*0 - (-3/4)*1 - 0*0 + 0*1)/((8/9)*1 - 1*0) t = (3/4)/(8/9) t = (3/4)*(9/8) t = (3*9/4*8) t = 27/32
let us figure out the coordinates:
p = r(t) p = <0,-3/4> + <1, 8/9>t p = <0,-3/4> + <1, 8/9>(27/32) p = <0,-3/4> + <27/32, (8/9)*(27/32)> p = <0,-3/4> + <27/32, 3/4> p = <27/32,0>
Since we had constructed the ray with v = (1, m) the solution point is simply (t, 0). The approach above is not limited to such cases.
On the other hand, if we construct vertical rays with v = (0, 1) we will find other optimizations for such case.
Thus, at the annoying value of t = 27/32, the ray r will intersect the boundary of the grid. Note that this value of t is the least such value of t for all boundary crossings.
Note: 27/32 = 0.84375. Thus, the entry point on the grid is <0.84375, 0>which is on the cell (0, 0), as depicted on the image. We find that simply by rounding down (assuming the cell size is 1).
Now that you have a general formula, you can apply it for all the boundaries and find the one that yields the lowest t (tMin). The corresponding point is the point where the ray enters the grid.
You can define the four boundaries of the rectangle as follows:
r2(t) = <0, 0> + <1, 0>t r3(t) = <0, h> + <1, 0>t r4(t) = <0, 0> + <0, 1>t r5(t) = <w, 0> + <0, 1>t
Assuming the grid has a corner at the origin, and w, h define the size of the grid (not the number of cells, but the length of the sides of the rectangle that contains the gird).
As you can see we have a lot of 0s, which will result in a lot of cancellations, which is room for optimization.
