線描画アルゴリズム

コンピュータグラフィックスにおいて、線描画アルゴリズムは、ピクセルベースのディスプレイやプリンタなどの離散的なグラフィックメディア上で線分を近似するアルゴリズムです。このようなメディアでは、線描画には近似が必要です(重要な場合)。基本的なアルゴリズムでは、線は 1 色でラスタライズされます。複数の色のグラデーションでより適切に表現するには、高度なプロセスである空間アンチエイリアシングが必要です。

対照的に、連続メディアでは、線を描くのにアルゴリズムは必要ありません。たとえば、ブラウン管オシロスコープは、アナログ現象を利用して線や曲線を描きます。

単色線描画アルゴリズムでは、背景に単一の前景色で線を描画します。単色ディスプレイでの使用に適しています。

目的の線分の始点と終点は通常、整数座標で指定されるため、アルゴリズムで考慮される点上に直接位置します。このため、ほとんどのアルゴリズムは、このような始点と終点のみを対象にして策定されます。

線を描く最も簡単な方法は、線方程式からピクセル位置を直接計算することです。始点と終点 が与えられると、線上の点は方程式 を満たし、 は線の傾きです。次の疑似コードに示すように、この方程式を単純なループで評価することで、線を描くことができます。 ${\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
    プロット(x, y)

ここでは、点はすでに となるように順序付けられています。 ${\displaystyle x_{2}>x_{1}}$

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

したがって、ポイントから開始し、ループの反復ごとに 1 つずつ増やすだけで十分です。このアルゴリズムは、デジタル微分解析器として知られています。 ${\displaystyle (x_{1},y_{1})}$${\displaystyle y}$${\displaystyle m}$

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

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

特定の状況では、単色の線描画アルゴリズムで問題が発生します。

同じ長さで傾斜が異なる線を描く場合、異なる数のピクセルが描画されます。これにより、同じ長さの傾斜の急な線は傾斜の緩やかな線よりもピクセル数が少なくなり、傾斜の急な線が傾斜の緩やかな線よりも明るく表示されます。この問題は、モノクロ デバイスでは避けられません。

クリッピングとは、ラスタライズを限られた、通常は長方形の領域に制限する操作です。これは、指定された線の開始点と終了点がこの領域の外側にある場合、その領域の境界まで移動することによって行われます。通常、これにより、これらの点の座標は整数ではなくなります。これらの座標が単純に丸められると、結果の線の傾斜は意図したものと異なります。この問題を回避するには、クリッピング後に追加のテストが必要です。

単色の線描画アルゴリズムの最大の問題は、線が粗くギザギザに見えることです。複数の明るさのレベルを表示できるデバイスでは、この問題はアンチエイリアシングによって回避できます。このため、線は通常、2 次元形式で、一般的には希望する太さの長方形として表示されます。これらの線を描画するには、この長方形の近くにある点を考慮する必要があります。

Gupta-Sproull アルゴリズムはBresenham のライン アルゴリズムに基づいていますが、アンチエイリアシングが追加されています。

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

線を引く(x1, x2, y1, y2) {
    x = x1;
    y = y1;
    dx = x2 − x1;
    dy = y2 − y1;
    d = 2 * dy − dx; // 判別子

    // 点 (x,y) から直線までのユークリッド距離 (符号付き)
    0 = 0;

    // 点 (x1, y1) と点 (x2, y2) 間のユークリッド距離
    長さ = sqrt(dx * dx + dy * dy);

    sin = dx / 長さ;
    cos = dy / 長さ;
    (x <= x2)の間{
        ピクセル強度を増加します(x, y − 1, D + cos);
        ピクセルを強調します(x, y, D);
        IntensifyPixels(x, y + 1, D − cos);
        x = x + 1
        （d <= 0）の場合{
            D = D + サイン;
            d = d + 2 * dy;
        }それ以外{
            D = D + sin − cos;
            d = d + 2 * (dy − dx) です。
            y = y + 1;
        }
    }
}

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

線描画アルゴリズムは、近似法、直接的なハードウェア実装の使用、並列化によって効率化できます。このような最適化は、多数の線をリアルタイムでレンダリングするときに必要になります。

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

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

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

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

線は 8 連結だけでなく 4 連結で描画することもできます。つまり、水平方向と垂直方向のステップのみが許可され、対角方向のステップは禁止されます。正方形のピクセルのラスターが与えられると、線の一部を含むすべての正方形が色付きになります。4 連結の線描画方法を 3 次元に一般化する方法は、ボクセルグリッドを扱うときに使用されます。たとえば、最適化されたレイ トレーシングでは、特定のレイが交差するボクセルを決定できます。

線描画アルゴリズムは、対角線ステップをほぼ均等に分配します。したがって、線描画アルゴリズムは、指定された間隔内の整数座標を持つ点を均等に分配するためにも使用できます。^[6] この方法の可能な用途には、信号処理における線形補間またはダウンサンプリングが含まれます。ユークリッドの互除法や、ファレー数列、および関連する数学的構成のいくつかとの類似点もあります。 ^[7]

• ブレゼンハムのラインアルゴリズム
• 円描画アルゴリズム
• ラスタライズ

• コンピュータグラフィックスの基礎、第 2 版、AK Peters、Peter Shirley著