線描画アルゴリズム

線を引く最も簡単な方法は、線方程式からピクセル位置を直接計算することです。開始点が与えられた場合${\displaystyle (x_{1},y_{1})}$そして終点${\displaystyle (x_{2},y_{2})}$直線上の点は方程式を満たす${\displaystyle y=m(x-x_{1})+y_{1}}$、 と${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$これは直線の傾きです。直線は、次の擬似コードに示すように、単純なループを使用してこの方程式を評価することによって描画できます。

dx = x2 − x1 dy = y2 − y1 m = dy/dx x1からx2までxについて​ y = m × (x − x1) + y1 plot(x, y)

ここでは、ポイントはすでに次のように順序付けられています。${\displaystyle x_{2}>x_{1}}$。

このアルゴリズムは、ループに乗算が含まれているため、不必要に遅くなっています。乗算は、ほとんどのデバイスで加算や減算よりも大幅に遅いためです。より高速な方法は、連続する2つのステップ間の差分を見ることで実現できます。

したがって、単にその地点から始めるだけで十分です${\displaystyle (x_{1},y_{1})}$そして、${\displaystyle y}$による${\displaystyle m}$ループの各反復で一度だけ実行されます。このアルゴリズムはデジタル微分解析器として知られています。

丸め処理のため${\displaystyle y}$最も近い整数に丸めることは、四捨五入することと同じです。${\displaystyle y+0.5}$下方向への丸めを回避するには、0.5で初期化された追加の制御変数を使用します。${\displaystyle m}$は、各反復でこの変数に追加されます。次に、この変数が 1.0 を超えると、${\displaystyle y}$は1ずつ増加し、制御変数は1ずつ減少します。これにより、アルゴリズムは丸めを回避し、整数演算のみを使用できます。ただし、短い行の場合、この高速なループは、コストのかかる除算を補うものではありません。${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$これは、初期段階では依然として必要である。

これらのアルゴリズムは、${\displaystyle dx\geq dy}$（つまり、傾きが1以下である場合）${\displaystyle dx<dy}$（つまり、傾きが 1 より大きい場合）、線は多くのギャップで非常に疎になり、極限の場合、${\displaystyle dx=0}$ゼロ除算例外が発生します。

特定の状況下では、単色線描画アルゴリズムは次のような問題に直面する。

Gupta -SproullアルゴリズムはBresenhamの線アルゴリズムに基づいているが、アンチエイリアシングを追加している。

Gupta-Sproullアルゴリズムの最適化されたバリアントは、擬似コードで次のように記述できます。

DrawLine(x1, x2, y1, y2) { x = x1; y = y1; dx = x2 − x1; dy = y2 − y1; d = 2 * dy − dx; // 判別器 // 点(x,y)から直線(符号付き)までのユークリッド距離 D = 0; // 点 (x1, y1) と (x2, y2) 間のユークリッド距離 長さ = sqrt(dx * dx + dy * dy); sin = dy / length; cos = dx / 長さ; while (x <= x2) { IntensifyPixels(x, y − 1, D + cos); IntensifyPixels(x, y, D); IntensifyPixels(x, y + 1, D − cos); x = x + 1 if (d <= 0) { D = D + sin; d = d + 2 * dy; }それ以外{ D = D + sin − cos; d = d + 2 * (dy − dx); y = y + 1; } } }

IntensifyPixels(x,y,r) 関数は、放射状の線変換を受け取り、ピクセル (x,y) の強度を、線からピクセルまでの距離 r に依存する 3 次多項式の値で設定します。

BoyerとBourdinは、理想的な直線の真下にあるピクセルに色を付ける近似アルゴリズムを導入しました。^{[ 1 ]}このようにレンダリングされた直線は、利用できる特別な特性をいくつか示します。たとえば、このような場合、直線のセクションは周期的です。これにより、特に長い直線の場合、正確なバリアントよりも大幅に高速なアルゴリズムが実現します。品質の低下は、傾斜が非常に小さい直線でのみ見られます。

単色線ラスタライズを並列化する簡単な方法は、複数の線描画アルゴリズムに、互いに一定の距離だけ離れたオフセットピクセルを描画させることです。^{[ 2 ]}別の方法としては、線をほぼ等しい長さの複数のセクションに分割し、それらを異なるプロセッサに割り当ててラスタライズする方法があります。主な問題は、これらのセクションの正しい開始点と終了点を見つけることです。

数千個のプロセッサを備えた大規模並列プロセッサアーキテクチャ向けのアルゴリズムも存在する。これらのアルゴリズムでは、ピクセルのグリッドから各ピクセルが単一のプロセッサに割り当てられ、そのプロセッサが与えられたピクセルに色を付けるかどうかを決定する。^{[ 3 ]}

ラスタライズ中のメモリアクセスを高速化するために、特別なメモリ階層が開発されました。たとえば、メモリを複数のセルに分割し、各セルが独立してラインの一部をレンダリングします。^{[ 4 ]} アンチエイリアシングを伴うラスタライズは、専用ハードウェアによってもサポートできます。^{[ 5 ]}