ラインセグメントと交差するすべてのタイルを見つける

Question

ラインセグメントと交差するタイルはすべて見つけなければならないが、Bresenhamのラインアルゴリズムは自分の要求に合わない。私はすべての細胞を見つける必要があります。私は交差点を知る必要はない、交差点の事実だけ。手伝ってくれてありがとう。

私は、線の方向ベクトルを見つけ出し、段階的にセルをタイルサイズで除算することによって見つけると考えました。しかし、正しいステップサイズを選択する方法はわかりません。 1 pxのステップが悪いと思います。 2D及び3Dの場合、Amanatides及びWoo "レイトレーシングのための高速ボクセルトラバーサルアルゴリズム"の

Answer 1

Here is articleたぶんあなたはy=mx+n方程式を推定し、ちょうどあなたのタイルにマッチしてご覧二つの点を通過するあなたの座標系であなたのラインを持っているhttp://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtmlか

：Practical implementation.

Answer 2

あなたはで見られる多くのライン方程式のいずれかを使用する場合があります座標系の単位でxを任意の方向に動かしながら交差する場合は、タイルの最小xから最大のxまでの任意の方向を選択します。座標系が画面の場合、1ピクセルで十分です。

これはあなたが直面している問題の正確な性質について詳しく知ることなく、私が知ることができるヒントです。

Answer 3

Bresenhamのアルゴリズムを変更して、必要なものを追跡するのは簡単です。アルゴリズムの関連する部分は次のとおりです。

plot(x,y); 
error = error + deltaerr; 
if (error >= 0.5) 
{ 
    y = y + ystep; 
    error = error - 1.0; 
} 

すべてのセルを追跡するには、別の変数が必要です。私はこれを厳密にチェックしていないことに注意してください。

plot(x,y); 
olderror = error. 
error = error + deltaerr; 
if (error >= 0.5) 
{ 
    y = y + ystep; 
    error = error - 1.0; 
    extra = error+olderror; 

    if (extra > 0) 
    { 
     plot (x,y); /* not plot (x-1,y); */ 
    } 
    else if (extra < 0) 
    { 
     plot (x+1,y-1); /* not plot (x+1,y); */ 
    } 
    esle 
    { 
     // the line goes right through the cell corner 
     // either do nothing, or do both plot (x-1,y) and plot (x+1,y) 
     // depending on your definition of intersection   
    } 
}