Wie initialisiere ich die T-Variablen in "Ein schneller Voxel Traversal Algorithmus für Ray Tracing"?

Question

Ich versuche, den Algorithmus zu implementieren erklärte auf diesem Papier verwendet, um Gitterzellen, um nach einer geraden Linie durchquert, die für Raytracing nützlich ist:

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

Das Papier beschreibt den Algorithmus als zwei Teile : Initialisierung und iteratives Traversieren. Ich kann den iterativen Traversal-Teil unterschreiben, aber ich habe Probleme zu verstehen, wie einige der Variablen im Initialisierungsteil berechnet werden.

Ich brauche Hilfe Initialisierung tMaxX, tMaxY, tDeltaX & tDeltaY. Ihre Initialisierungsprozedur wird wie folgt erläutert:

Als nächst wir den Wert von t bestimmen, an dem der Strahl durchquert den ersten vertikale Voxel Grenze und speichert sie in Variable tMaxX. Wir führen eine ähnliche Berechnung in y durch und speichern das Ergebnis in tMaxY. Das Minimum von Diese beiden Werte zeigen an, wie viel wir entlang des Strahls fahren können und immer noch im aktuellen Voxel bleiben.

Schließlich berechnen wir tDeltaX und tDeltaY. TDeltaX gibt an, wie weit entlang des Strahls wir (in Einheiten von t) für die horizontale Komponente einer solchen Bewegung bewegen müssen, um der Breite eines Voxels zu entsprechen. Ähnlich speichert in tDeltaY die Menge der Bewegung entlang des Strahls, die eine vertikale Komponente von hat, die der Höhe eines Voxels entspricht.

Ich bin nicht in der Lage, den Code abzuleiten, den ich benötige, bilden Sie die englische Beschreibung, die oben gegeben wird. Kann jemand es für mich in einen Mathe/Pseudocode-Ausdruck übersetzen?

Answer 1

Initialisierung für X-Koordinaten-Variablen (das gleiche für 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 

Beispiel:

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 

wir, dass die erste Zellengrenze sehen können, wird am Parameter t erfüllt werden = 0,15

Answer 2

Die eine, die für mich in 3D für sowohl positive als auch negative Richtungen arbeitete (in 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 
} 

Hinweis: Gitterbreite/-höhe/-tiefe sind in meinem Fall alle gleich 1, aber Sie können sie leicht für Ihre Bedürfnisse anpassen.