I am trying to implement the algorithm explained on this paper, used to traverse grid cells in order following a straight line, which is useful for ray tracing:
http://www.cse.yorku.ca/~amana/research/grid.pdf
The paper describes the algorithm as two parts: initialisation and iterative traversal. I can undersand the iterative traversal part, but I'm having trouble understanding how some of the variables in the initialisation part are calculated.
I need help initialising tMaxX, tMaxY, tDeltaX & tDeltaY. Their initialisation procedure is explained as follows:
Next, we determine the value of t at which the ray crosses the first vertical voxel boundary and store it in variable tMaxX. We perform a similar computation in y and store the result in tMaxY. The minimum of these two values will indicate how much we can travel along the ray and still remain in the current voxel.
Finally, we compute tDeltaX and tDeltaY. TDeltaX indicates how far along the ray we must move (in units of t) for the horizontal component of such a movement to equal the width of a voxel. Similarly, store in tDeltaY the amount of movement along the ray which has a vertical component equal to the height of a voxel.
I'm not able to deduce the code I need form the English description given above. Can someone translate it to a math/pseudocode expression for me?
Initialization for X-coordinate variables (the same for Y)
DX = X2 - X1
tDeltaX = GridCellWidth / DX
tMaxX = tDeltaX * (1.0 - Frac(X1 / GridCellWidth))
//Frac if fractional part of float, for example, Frac(1.3) = 0.3, Frac(-1.7)=0.3
Example:
GridCellWidth, Height = 20
X1 = 5, X2 = 105
Y1 = 5, Y2 = 55
DX = 100, DY = 50
tDeltaX = 0.2, tDeltaY = 0.4
tMaxX = 0.2 * (1.0 - 0.25) = 0.15 //ray will meet first vertical line at this param
tMaxY = 0.4 * (1.0 - 0.25) = 0.3 //ray will meet first horizontal line at this param
We can see that first cell border will be met at parameter t = 0.15