21

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

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

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

我需要帮助初始化tMaxX, tMaxY, tDeltaX& tDeltaY。它们的初始化过程解释如下：

接下来，我们确定光线穿过第一个垂直体素边界时的 t 值，并将其存储在变量 tMaxX 中。我们在 y 中执行类似的计算并将结果存储在 tMaxY 中。这两个值中的最小值将指示我们可以沿着射线行进多少并且仍然保留在当前体素中。

最后，我们计算 tDeltaX 和 tDeltaY。TDeltaX 表示我们必须沿着射线移动多远（以 t 为单位），才能使这种移动的水平分量等于体素的宽度。类似地，将沿射线的移动量存储在 tDeltaY 中，该射线的垂直分量等于体素的高度。

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

4

2 回答 2

12

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 处满足

于 2012-09-11T13:09:23.703 回答
8

在正向和负向（在 CUDA C 中）在 3D 中为我工作的那个：

#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   

int 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，但您可以根据需要轻松修改它。

于 2016-07-24T13:42:48.180 回答