¿Cómo inicializo las variables t en "Algoritmo de recorrido rápido de Voxel para rastrear rayos"?

Question

Estoy tratando de implementar el algoritmo se explica en este documento, que sirve para atravesar celdas de la rejilla con el fin siguiendo una línea recta, que es útil para el trazado de rayos:

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

el documento se describe el algoritmo como dos partes : inicialización y recorrido iterativo. Puedo entender la parte transversal iterativa, pero tengo problemas para entender cómo se calculan algunas de las variables en la parte de inicialización.

Necesito ayuda para inicializar tMaxX, tMaxY, tDeltaX & tDeltaY. Su procedimiento de inicialización se explica como sigue:

A continuación, se determina el valor de t en el que el rayo atraviesa la primera límite voxel vertical y la almacena en la variable Tmaxx. Realizamos un cálculo similar en y almacenamos el resultado en tMaxY. El mínimo de estos dos valores indicará cuánto podemos viajar a lo largo del rayo y permanecer en el vóxel actual.

Finalmente, calculamos tDeltaX y tDeltaY. TDeltaX indica qué tan lejos a lo largo del rayo debemos mover (en unidades de t) para el componente horizontal de tal movimiento para igualar el ancho de un vóxel. De manera similar, almacena en tDeltaY la cantidad de movimiento a lo largo del rayo que tiene un componente vertical igual a la altura de un vóxel.

No puedo deducir el código que necesito de la descripción en inglés dada anteriormente. ¿Alguien puede traducirlo a una expresión de matemáticas/pseudocódigo para mí?

Answer 1

de inicialización para variables (la misma para 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 

Ejemplo coordenada X:

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 

Podemos ver que primero borde de la celda será recibido en el parámetro t = 0,15

Answer 2

El que funcionó para mí en 3D para direcciones positivas y negativas (en 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 
} 

Nota: el ancho/alto/profundidad de la celda de la cuadrícula son todos iguales a 1 en mi caso, pero puede modificarlo fácilmente según sus necesidades.