Jak zainicjować zmienne t w "Algorytmie szybkiego przekierowania Voxela dla śledzenia promieni"?

Question

ja próby wdrożenia algorytmu opisane na tym dokumencie, używane na przechodzenie komórek siatki, aby po linii prostej, która jest użyteczna do wykrywania promieniowania:

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

Dokument opisuje algorytm w dwóch częściach : inicjalizacja i iteracyjne przejście. Potrafię wskazać część iteracyjną, ale mam problem ze zrozumieniem, jak obliczane są niektóre zmienne w części inicjalizującej.

Potrzebuję pomocy inicjalizacji tMaxX, tMaxY, tDeltaX & tDeltaY. Ich procedura inicjalizacji jest wyjaśnione następująco:

Następnie możemy określić wartość t, przy której promień przecina RST fi pionową granicę woksela i przechowywać go w zmiennej tMaxX. Dokonujemy podobnego obliczenia w y i przechowujemy wynik w tMaxY. Minimum tych dwóch wartości będzie wskazywać, ile możemy podróżować wzdłuż promienia i nadal pozostać w aktualnym wokselu.

Wreszcie obliczamy tDeltaX i tDeltaY. TDeltaX wskazuje, jak daleko wzdłuż promienia musimy się poruszać (w jednostkach t) dla poziomego składnika takiego ruchu, aby był równy szerokości woksela. Podobnie, przechowuje w tDeltaY wielkość ruchu wzdłuż promienia, który ma pionowy komponent równy wysokości woksela.

Nie jestem w stanie wydedukować kodu potrzebnego z angielskiego opisu podanego powyżej. Czy ktoś może przetłumaczyć dla mnie wyrażenie matematyczne/pseudokodowe?

Answer 1

inicjalizacji dla współrzędnej X zmiennych (taka sama dla 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 

przykład:

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 

Widać, że pierwsza krawędź komórki zostaną spełnione w parametru t = 0,15

Answer 2

Ten, który pracował dla mnie w 3D dla kierunków pozytywnych i negatywnych (w 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 
} 

Uwaga: szerokość/wysokość/głębokość komórki siatki są w moim przypadku równe 1, ale można ją łatwo modyfikować zgodnie z potrzebami.