今何を見ているの？ 全員がベクトルモニターに座っているパラレルユニバースからではない場合、ビットマップイメージがあります。 このストリップを見てください：/。 モニターの近くに移動すると、ベクトル線のふりをしようとするピクセルステップを見ることができます。 この目的のために、あらゆる種類のラスター化アルゴリズムがありますが、ラスター座標でベクトルセグメントの近似値を見つけるBresenhamアルゴリズムとUアルゴリズムについてお話したいと思います。
建築計画の手続き型ジェネレーターに取り組んでいる間、ラスタライズの問題に直面する機会がありました。 部屋の壁を2次元配列のセルとして想像する必要がありました。 同様の問題は、物理的な計算、パス検索アルゴリズム、または空間分割が使用されている場合の照明計算で発生する可能性があります。 ラスタライズアルゴリズムを知ることがいつか役立つと誰が考えたでしょうか？
Bresenhamアルゴリズムの動作原理は非常に単純です。 線とその初期座標xが取得されます。 サイクルのXに、セグメントの終わりに向かって1つずつ追加します。 各ステップで、エラーが計算されます-この位置の実際のy座標と最も近いグリッドセルの間の距離。 エラーがセルの高さの半分を超えない場合、塗りつぶされます。 これがアルゴリズム全体です。
これがアルゴリズムの本質であり、実際、すべては次のように見えます。 最初に、角度係数（y1-y0）/（x1-x0）が計算されます。 セグメントの開始点でのエラー値（0,0）はゼロに等しくなり、最初のセルが塗りつぶされます。 次のステップで、角度係数がエラーに追加され、その値が分析されます。エラーが0.5未満の場合、セル（x0 + 1、0）が満たされ、それ以上の場合、セル（x0 + 1、0+ 1）が満たされ、単位がエラー値から減算されます。 以下の図では、ラスタライズ前の線が黄色、緑、赤で表示されています-最も近いセルまでの距離です。 角度係数は6分の1に等しく、最初のステップで、誤差は0.5より小さい角度係数に等しくなり、これは縦座標が同じままであることを意味します。 ラインの中央までに、エラーが境界を越え、そこから単位が差し引かれ、新しいピクセルが上に上がります。 セグメントの終わりまで続きます。
別のニュアンス。 x軸上のセグメントの投影がy軸上の投影よりも小さい場合、またはセグメントの開始と終了が再配置された場合、アルゴリズムは機能しません。 これを回避するには、ベクトルの方向とその傾きを確認し、必要に応じてセグメントの座標を交換し、軸を回転させ、最終的にすべてを1つまたは少なくとも2つのケースに減らします。 描画中に覚えておくべき主なことは、軸をその場所に戻すことです。
計算を最適化するために、すべての分数変数にdx =（x1-x0）を掛けたトリックが適用されます。 次に、各ステップで、角度係数の代わりにdy =（y1-y0）によって、ユニティの代わりにdxによってエラーが変化します。 また、ロジックをわずかに変更し、エラーを「移動」して境界がゼロになるようにすることもできます。エラーの兆候を確認することで、より高速になります。
このようなものは、ブレゼンハムアルゴリズムを使用してラスターラインを描画するコードのように見えるかもしれません。 ウィキペディアの擬似コードは、C＃で再作成されています。
void BresenhamLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // // , if (steep) { Swap(ref x0, ref y0); // Swap(ref x1, ref y1); } // , if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } int dx = x1 - x0; int dy = Math.Abs(y1 - y0); int error = dx / 2; // dx, int ystep = (y0 < y1) ? 1 : -1; // y int y = y0; for (int x = x0; x <= x1; x++) { DrawPoint(steep ? y : x, steep ? x : y); // error -= dy; if (error < 0) { y += ystep; error += dx; } } }
Bresenhamアルゴリズムには、円を描くための修正があります。 いくつかの点でより簡単に、すべてが同様の原則に従ってそこで動作します。 計算は1オクタントに対して行われ、円の他のすべての部分は対称的に描画されます。
C＃のサンプル円描画コード。
void BresenhamCircle(int x0, int y0, int radius) { int x = radius; int y = 0; int radiusError = 1 - x; while (x >= y) { DrawPoint(x + x0, y + y0); DrawPoint(y + x0, x + y0); DrawPoint(-x + x0, y + y0); DrawPoint(-y + x0, x + y0); DrawPoint(-x + x0, -y + y0); DrawPoint(-y + x0, -x + y0); DrawPoint(x + x0, -y + y0); DrawPoint(y + x0, -x + y0); y++; if (radiusError < 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }
さて、滑らかな線を描くためのWu Xiaolinのアルゴリズムについて。 各ステップで、ラインに最も近い2つのピクセルに対して計算が行われ、距離に応じて異なる強度で塗りつぶされる点が異なります。 ピクセルの中央の正確な交点は100％の強度を与えます。ピクセルが0.9ピクセルの距離にある場合、強度は10％になります。 言い換えれば、強度の100％が、両側のベクトル線に接するピクセル間で分割されます。
上の画像では、2つの隣接するピクセルまでの距離が赤と緑で示されています。
エラーを計算するには、浮動小数点変数を使用して、小数部分からエラー値を取得できます。
C＃のWu Xiaolinによる平滑化された線のサンプルコード。
private void WuLine(int x0, int y0, int x1, int y1) { var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) { Swap(ref x0, ref y0); Swap(ref x1, ref y1); } if (x0 > x1) { Swap(ref x0, ref x1); Swap(ref y0, ref y1); } DrawPoint(steep, x0, y0, 1); // steep DrawPoint(steep, x1, y1, 1); // — float dx = x1 - x0; float dy = y1 - y0; float gradient = dy / dx; float y = y0 + gradient; for (var x = x0 + 1; x <= x1 - 1; x++) { DrawPoint(steep, x, (int)y, 1 - (y - (int)y)); DrawPoint(steep, x, (int)y + 1, y - (int)y); y += gradient; } }
将来グリッドを突然操作しなければならない場合は、しばらく考えてみてください。車輪を再発明し、実際にはピクセルを操作しているかもしれませんが、これはわかりません。 これらのアルゴリズムの変更をゲームで使用して、マップ上のユニットの前にあるセルを検索したり、ショットヒットの面積を計算したり、オブジェクトの美しい配置を計算したりできます。 または、以下のリンクを使用するプログラムのように、単に線を引くことができます。
Unity Web Player | Windows | Linux | Mac | GitHubソース
マウスの左ボタン-Bresenham、マウスの右ボタン-Y、スペースバー-クリア、Esc-終了。
Linuxユーザーの場合：「chmod + x BresenhamWu」を使用してBresenhamWuファイルを実行可能にし、実行します。
Rosetta Codeには、BresenhamアルゴリズムとUアルゴリズム用の異なる言語のコードがあります。 Wu Xiaolinによる記事へのリンク