Как инициализировать t-переменные в "Алгоритм обхода ускоренного Voxel для трассировки лучей"?

Я пытаюсь реализовать алгоритм, описанный в этой статье, используемый для пересечения сетчатых ячеек по следующей прямой, что полезно для трассировки лучей:

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

В статье описывается алгоритм как две части: инициализация и итеративный обход. Я могу игнорировать итеративную часть обхода, но мне трудно понять, как вычисляются некоторые из переменных в части инициализации.

Мне нужна помощь, инициализирующая tMaxX, tMaxY, tDeltaX и tDeltaY. Их процедура инициализации объясняется следующим образом:

Далее, мы определяем значение t, при котором луч пересекает первый вертикальной границы вокселя и сохранить его в переменной tMaxX. Мы выполняем аналогичное вычисление по y и сохранение результата в tMaxY. Минимум эти два значения будут указывать, сколько мы можем перемещаться вдоль луча и все еще остаются в текущем вокселе.

Наконец, мы вычисляем tDeltaX и tDeltaY. TDeltaX показывает, насколько далеко вдоль луча мы должны двигаться (в единицах t) для горизонтальной компонент такого движения, равный ширине воксела. По аналогии, хранить в tDeltaY количество движения вдоль луча, которое имеет вертикальная составляющая, равная высоте воксела.

Я не могу вывести код, который мне нужен, из приведенного выше английского описания. Может ли кто-нибудь перевести его на выражение математики/псевдокода для меня?

Ответ 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

Ответ 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, но вы можете легко изменить ее для своих нужд.