algorithm - 如何初始化 "A Fast Voxel Traversal Algorithm for Ray Tracing"中的 t 变量？

Question

我正在尝试实现本文中解释的算法，用于按照直线顺序遍历网格单元，这对光线追踪很有用:

http://www.cse.yorku.ca/~amana/research/grid.pdf

论文将算法描述为两个部分:初始化和迭代遍历。我可以理解迭代遍历部分，但我无法理解初始化部分中的某些变量是如何计算的。

我需要帮助初始化 tMaxX、tMaxY、tDeltaX 和 tDeltaY。它们的初始化过程解释如下:

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.

我无法从上面给出的英文描述中推断出我需要的代码。有人可以帮我把它翻译成数学/伪代码表达式吗？

Answer 1

X坐标变量的初始化(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

示例:

  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

我们可以看到第一个单元格边界将在参数 t = 0.15 处出现