線のラスタライズ：線のグラデーションに関係なく、すべてのピクセルをカバーしますか？

Question

基本的には、自分のレイキャスターの衝突をチェックするセルを決定するためにラインアルゴを使用したいと思います。

Bresenhamは、統一された厚さのアプローチを使用しているため、これはあまり適していません。これは、ラインを少なくとも半分覆っていないセルを無視することを意味します。私のラインのいくつかのセグメントがセルとの交差点をチェックされておらず、エラーにつながっていることを意味するからです。

"thick-line"アルゴリズムが見つからないと思います。

グリーン：私は何をしたいですか？
赤：私が現在持っていて望んでいないもの。

Answer 1

私はまったく同じ問題を抱えていて、非常に簡単な解決策を見つけました。

public void drawLine(int x0, int y0, int x1, int y1, char ch) { 
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1; 
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; 
    int err = dx + dy, e2; // error value e_xy 

    for (;;) { 
     put(x0, y0, ch); 

     if (x0 == x1 && y0 == y1) break; 

     e2 = 2 * err; 

     // horizontal step? 
     if (e2 > dy) { 
      err += dy; 
      x0 += sx; 
     } 

     // vertical step? 
     if (e2 < dx) { 
      err += dx; 
      y0 += sy; 
     } 
    } 
} 

今あなたがしなければならないすべては二if前elseを挿入することです：

public void drawLineNoDiagonalSteps(int x0, int y0, int x1, int y1, char ch) { 
    int dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1; 
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; 
    int err = dx + dy, e2; 

    for (;;) { 
     put(x0, y0, ch); 

     if (x0 == x1 && y0 == y1) break; 

     e2 = 2 * err; 

     // EITHER horizontal OR vertical step (but not both!) 
     if (e2 > dy) { 
      err += dy; 
      x0 += sx; 
     } else if (e2 < dx) { // <--- this "else" makes the difference 
      err += dx; 
      y0 += sy; 
     } 
    } 
} 

を、それは2次元座標を増やす必要があるかどうかを判断するためだ場合通常、ブレゼンハムは、2つの連続があります今度は、アルゴリズムはもう一度、両方の座標を変更しません。 これを徹底的にテストしたわけではありませんが、うまく機能しているようです。

Answer 2

対角線移動が許可されていないという追加の制約はありますか？伝統的なアルゴリズムでポイントを生成し、後処理ステップとして直交移動のみを行うために必要な余分なステップを挿入します。 GPU Gemsの中に利用できる興味深い記事があり

Answer 3

、多分それはあなたを助けることができる：Chapter 22. Fast Prefiltered Linesは

Answer 4

あなたの光線が水平グリッド線を持っている全ての交点を見つけることができるし、その行のすべてのセルをマークしています一方の側に交点を有するか、またはその行上の交点を有する2つのセルの間にある。

交差点を見つけるには、最初の交差点にポイントを進めて（そしてプロセス内のセルにマークを付ける）、交差点から次の交差点に向かうベクトルを見つける（両方の操作基本的な類似の三角形（または三角形）です。そして、あなたが十分遠くになるまで、列ごとに前進します。列ごとに進めるには、列ごとに1つのベクトルを追加し、交点を持つセルの間にセルを埋め込む小さなループを作成します。セルをオンザフライで処理している場合は、「マーク」を「プロセス」に置き換えます。このアルゴリズムは、各セルを1回だけマークすることが保証されています。

同じことが縦線でも行えますが、グリッドは一般的に水平スライスに保存されています。 trigを使用している場合は、特殊なケースで直線の水平線を処理する必要があります。

ところで、私が知る限り、これは古い格子ベースのレイキャスター「3D」ゲーム（Wolfenstein 3Dなど）がどのように行われたかです。私はまずthis bookからこのアルゴリズムについて読みました。その後、一般性を失うことなく

Answer 5

、X2> = X1を想定し、

int x = floor(x1); 
int y = floor(y1); 
double slope = (x2 - x1)/(y2 - y1); 
if (y2 >= y1) { 
    while (y < y2) { 
    int r = floor(slope * (y - y1) + x1); 
    do { 
     usepixel(x, y); 
     ++x; 
    } while (x < r); 
    usepixel(x, y); 
    ++y; 
    } 
} 
else { 
    while (y > y2) { 
    int r = floor(slope * (y - y1) + x1); 
    do { 
     usepixel(x, y); 
     ++x; 
    } while (x < r); 
    usepixel(x, y); 
    --y; 
    } 
} 

階の呼び出しはおそらく、キャスト・ツー・整数として記述することができます。

Answer 6

このスレッド古いが、私はそれがインターネット上でこれを置く価値があると思った：

// This prints the pixels from (x, y), increasing by dx and dy. 
// Based on the DDA algorithm (uses floating point calculations). 
void pixelsAfter(int x, int y, int dx, int dy) 
{ 
    // Do not count pixels |dx|==|dy| diagonals twice: 
    int steps = Math.abs(dx) == Math.abs(dy) 
      ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy); 
    double xPos = x; 
    double yPos = y; 
    double incX = (dx + 0.0d)/steps; 
    double incY = (dy + 0.0d)/steps; 
    System.out.println(String.format("The pixels after (%d,%d) are:", x, y)); 
    for(int k = 0; k < steps; k++) 
    { 
     xPos += incX; 
     yPos += incY; 
     System.out.println(String.format("A pixel (%d) after is (%d, %d)", 
      k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos))); 
    } 
}