如何在"用于光线跟踪的快速体素遍历算法"中初始化t变量？

Question

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

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

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

我需要帮助正在初始化tMaxX,tMaxY,tDeltaX和tDeltaY.他们的初始化程序解释如下:

接下来,我们确定光线穿过第一个垂直体素边界的t值,并将其存储在变量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

对于我来说,在正面和负面方向上为我工作的那个(在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,但您可以根据需要轻松修改它.