1

(x0, y0) から (x1, y1) まで、幅 2^n の正方形タイルで作られたグリッドを通る線があります。ラインが交差するタイルを見つけるだけでなく、対応する入口と出口のポイントも見つける必要があります。これに関するすべてのSOの質問は、タイル内の交差点が発生する場所を気にせずに「1x1」タイルを扱うことがわかります。

ここに画像の説明を入力

ポイントは常に正確に整数になるとは限りません。場合によっては自然な床を使用し、他の場合は切り上げます。ただし、すべての場合に自然に床に置くことは、今のところ問題ありません。

最終的に整数を使用したレイトレーシングの非常に単純なケースになる例を見つけましたが、交点を追跡せず、中心を通る線以外には適応されません (0.5、0.5 オフセットと仮定) 1x1 タイル。

void raytrace(int x0, int y0, int x1, int y1)
{
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int x = x0;
    int y = y0;
    int n = 1 + dx + dy;
    int x_inc = (x1 > x0) ? 1 : -1;
    int y_inc = (y1 > y0) ? 1 : -1;
    int error = dx - dy;
    dx *= 2;
    dy *= 2;

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            x += x_inc;
            error -= dy;
        }
        else
        {
            y += y_inc;
            error += dx;
        }
    }
}

交差する 2^nx 2^n グリッド タイルを見つけながら、関連する 2 つの交点を取得するにはどうすればよいでしょうか? タイル内の「どこからでも」開始する機能は、このアルゴリズムを実際に混乱させているようです。私の解決策は、除算を使用し、おそらく反復ごとにエラーを蓄積するように設定することになります。そして、それは良くない...

また、最初と最後のタイルについては、エンドポイントは「他の」交点であると見なすことができると思います。

4

3 に答える 3

2

Woo、Amanatidesによる有用な記事「FastVoxelTraversalAlgorithm... 」があります。実際の実装（グリッドトラバーサルセクション）も見てください。私はこの方法を使用して、良い結果を得ました。

于 2012-12-14T18:36:43.083 に答える
2

座標系全体を 2^n で割ることにより、2^n X 2^n のタイル サイズを 1 X 1 に縮小できます。

正確には、この場合、線の始点と終点の座標を 2^n で割ることを意味します。これからは、問題を 1X1 サイズのタイルの問題として扱うことができます。問題の終わりに、解に 2^n を掛け直すので、2^n X 2^n 解の答えを求めます。

次に、各タイルの入口と出口のポイントを見つける部分です。直線が (2.4, 4.6 ) で始まり (7.9, 6.3) で終わるとします。

  • 線の始点と終点の x 座標は 2.4 と 7.9 であるため、それらの間のすべての整数値は線と交差します。つまり、x 座標が 3,4,5,6,7 のタイルは交差する。入力ラインの方程式を使用して、これらの x 座標に対応する y 座標を計算できます。
  • 同様に、線の始点と終点の y 座標間のすべての整数は、線とタイルの間の交点の別のセットにつながります。
  • これらすべての点を x 座標に基づいて並べ替えます。それらをペアで選択します。1 番目が入口になり、2 番目が出口になります。
  • 元の問題の解決策を得るには、これらのポイントを 2^n で乗算します。

Algorithm Complexity : O(nlog n )ここで、n は線の開始座標と終了座標の間の整数の範囲です。マイナーな変更により、これをさらに O(n) に減らすことができます。

于 2012-12-15T12:58:17.730 に答える
1

x0..x1 の範囲の x の各整数値を代入し、各 y について解きます。これにより、タイルの側面にある交点の位置がわかります。

y0..y1 の範囲の y の各整数値を代入し、x について解きます。これにより、タイルの上部/下部の交点の位置がわかります。

編集

さまざまなサイズのタイルを処理し、タイル内で開始する場合、コードは少し見苦しくなりますが、考え方は同じです。これはC＃のソリューションです（LINQPadでそのまま実行されます）：

List<Tuple<double,double>> intersections = new List<Tuple<double,double>>();

int tile_width = 4;

int x0 = 3;
int x1 = 15;
int y0 = 1;
int y1 = 17;

int round_up_x0_to_nearest_tile = tile_width*((x0 + tile_width -1)/tile_width);
int round_down_x1_to_nearest_tile = tile_width*x1/tile_width;

int round_up_y0_to_nearest_tile = tile_width*((y0 + tile_width -1)/tile_width);
int round_down_y1_to_nearest_tile = tile_width*y1/tile_width;

double slope = (y1-y0)*1.0/(x1-x0);
double inverse_slope = 1/slope;

for (int x = round_up_x0_to_nearest_tile; x <= round_down_x1_to_nearest_tile; x += tile_width)
{
    intersections.Add(new Tuple<double,double>(x, slope*(x-x0)+y0));
}

for (int y = round_up_y0_to_nearest_tile; y <= round_down_y1_to_nearest_tile; y += tile_width)
{
    intersections.Add(new Tuple<double,double>(inverse_slope*(y-y0)+x0, y));
}

intersections.Sort();

Console.WriteLine(intersections);

この方法の欠点は、線がタイルの角で正確に交差する場合 (つまり、交差の x 座標と y 座標が両方とも整数である場合)、2 つのそれぞれから同じ交点がリストに追加されることです。ループします。その場合、重複する交点をリストから削除する必要があります。

于 2012-12-14T18:27:47.727 に答える