如何初始化“的快速体素遍历算法光线跟踪”的T-变量？(How do I initialize the

我想实现的算法本文用于遍历网格单元，以下面一条直线，这是光线追踪有用的解释：

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

本文介绍的算法为两个部分：初始化和迭代遍历。 我可以undersand迭代遍历的一部分，但我无法理解如何在一些初始化部分的变量的计算。

我需要帮助初始化tMaxX ， tMaxY ， tDeltaX ＆ tDeltaY 。 他们的初始化过程说明如下：

接着，我们确定吨的在其中光线穿过第一个垂直边界的体素的值并将其存储在变量tMaxX。 我们执行y中类似的计算和存储结果tMaxY。 这两个值的最小值将表明我们多少可以沿着线行驶，但仍保持在目前的体素。

最后，我们计算tDeltaX和tDeltaY。 TDeltaX指示我们多远沿射线必须移动（在t单位）这样的运动的水平分量等于一个体素的宽度。 类似地，存储在tDeltaY运动沿着具有垂直分量等于一个体素的高度的射线量。

我不能推断出我需要形成上面给出的英文说明的代码。 可有人把它翻译为我数学/伪的表达？

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

Answer 2:

在3D为我工作的积极和消极的方向（在CUDA C）中的一种：

#define SIGN(x) (x > 0 ? 1 : (x < 0 ? -1 : 0))
#define FRAC0(x) (x - floorf(x))
#define FRAC1(x) (1 - x + floorf(x))

float tMaxX, tMaxY, tMaxZ, tDeltaX, tDeltaY, tDeltaZ;
int3 voxel;

float x1, y1, z1; // start point   
float x2, y2, z2; // end point   

dx = SIGN(x2 - x1);
if (dx != 0) tDeltaX = fmin(dx / (x2 - x1), 10000000.0f); else tDeltaX = 10000000.0f;
if (dx > 0) tMaxX = tDeltaX * FRAC1(x1); else tMaxX = tDeltaX * FRAC0(x1);
voxel.x = (int) x1;

int dy = SIGN(y2 - y1);
if (dy != 0) tDeltaY = fmin(dy / (y2 - y1), 10000000.0f); else tDeltaY = 10000000.0f;
if (dy > 0) tMaxY = tDeltaY * FRAC1(y1); else tMaxY = tDeltaY * FRAC0(y1);
voxel.y = (int) y1;

int dz = SIGN(z2 - z1);
if (dz != 0) tDeltaZ = fmin(dz / (z2 - z1), 10000000.0f); else tDeltaZ = 10000000.0f;
if (dz > 0) tMaxZ = tDeltaZ * FRAC1(z1); else tMaxZ = tDeltaZ * FRAC0(z1);
voxel.z = (int) z1;

while (true) {
    if (tMaxX < tMaxY) {
        if (tMaxX < tMaxZ) {
            voxel.x += dx;
            tMaxX += tDeltaX;
        } else {
            voxel.z += dz;
            tMaxZ += tDeltaZ;
        }
    } else {
        if (tMaxY < tMaxZ) {
            voxel.y += dy;
            tMaxY += tDeltaY;
        } else {
            voxel.z += dz;
            tMaxZ += tDeltaZ;
        }
    }
    if (tMaxX > 1 && tMaxY > 1 && tMaxZ > 1) break;
    // process voxel here
}

注意，网格单元的宽度/高度/深度都等于在我的情况1，但你可以很容易地修改它为您的需求。

文章来源: How do I initialize the t-variables in “A Fast Voxel Traversal Algorithm for Ray Tracing”?