Как мне инициализировать 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

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