「レイトレーシングの高速ボクセルトラバーサルアルゴリズム」でt変数を初期化するにはどうすればよいですか？</p> <p><a href="http://www.cse.yorku.ca/~amana/research/grid.pdf">http://www.cse.yorku.ca/~amana/research/grid.pdf</a></p> <p>紙は、2つの部分としてのアルゴリズムを説明：私はアルゴリズムを実装しようとしている

Question

は、レイトレーシングのために有用である直線、次の順序でグリッドセルを横断するために使用される、この論文に説明しました：初期化と反復トラバーサル。私は反復的なトラバーサル部分を理解することができますが、初期化部分の変数のいくつかがどのように計算されているか理解できません。

私はtMaxX、tMaxY、tDeltaX & tDeltaYを初期化する助けが必要。

次に、我々は、光線が第一に 垂直ボクセル境界を横切ると可変tMaxXに格納れるTの値を決定する次のようにそれらの初期化手順について説明します。我々はyにおいて同様の計算を 実行し、その結果をtMaxYに格納する。 の最小値は、これらの2つの値は、光線に沿ってどれだけ多く移動でき、まだ現在のボクセルに残っているかを示します。

最後に、tDeltaXとtDeltaYを計算します。 TDeltaXは、水平方向に移動する必要があるレイに沿ってどのくらいの距離移動する必要があるかを示します（単位はt）。ボクセルの幅に等しくなるような移動のコンポーネントです。同様に、 は、ボクセルの高さに等しい垂直成分が のレイに沿った移動量をtDeltaYに格納します。

上記の英語の説明に必要なコードを推測できません。誰かがそれを私のための数式/擬似コード式に翻訳できますか？

Answer 1

初期X座標変数（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 

我々は、第1のセル境界が=パラメータ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ですが、必要に応じて簡単に変更できます。