algorithm - ¿Cómo puedo inicializar las variables t en “Un algoritmo de recorrido voxel rápido para el trazado de rayos”?

math language-agnostic

Question

Estoy tratando de implementar el algoritmo explicado en este documento, que se utiliza para atravesar las celdas de la cuadrícula en orden siguiendo una línea recta, que es útil para el trazado de rayos:

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

El artículo describe el algoritmo como dos partes: inicialización y recorrido iterativo. Puedo entender la parte transversal transversal iterativa, pero me cuesta entender cómo se calculan algunas de las variables en la parte de inicialización.

Necesito ayuda para inicializar tMaxX , tMaxY , tDeltaX y tDeltaY . Su procedimiento de inicialización se explica a continuación:

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

Finalmente, calculamos tDeltaX y tDeltaY. TDeltaX indica la distancia a lo largo del rayo que debemos mover (en unidades de t) para que el componente horizontal de tal movimiento sea igual al ancho de un vóxel. De manera similar, almacene en un momento 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 que se indica más arriba. ¿Puede alguien traducirlo a una expresión de pseudocódigo matemática para mí?

Answer 1

El que me funcionó en 3D para ambas direcciones, positiva y negativa (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
}

Tenga en cuenta que el ancho / alto / profundidad de la celda de la cuadrícula son todos iguales a 1 en mi caso, pero puede modificarlo fácilmente para sus necesidades.

Answer 2

Inicialización para variables de coordenadas X (igual 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:

  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 el primer borde de la celda se cumplirá en el parámetro t = 0.15