線描画アルゴリズム

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

対照的に、連続媒体では線を描くのにアルゴリズムは必要ありません。例えば、ブラウン管オシロスコープはアナログ電子回路を用いて直線や曲線を描きます。高速CPUが登場する以前は、このようなモニターはワイヤーフレーム描画を用いた自動車設計などの高度なCAD/CAM分野で使用されていました。これらのシステムでは、コンピューターから少量の(x,y)ベクトルリストを受け取るだけで、即座に線画を描くことができました。ピクセルの強度のみを受け入れるディスプレイ上で視覚化を行うには、デジタルアルゴリズムを発明する必要がありました。

単色線描画アルゴリズム

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

目的の直線の始点と終点は通常、整数座標で与えられ、アルゴリズムが考慮する点と重なる。そのため、ほとんどのアルゴリズムは、このような始点と終点のみを対象として定式化されている。

シンプルな方法

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

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

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

$y_{i+1}-y_{i}\!$	$=(m(x_{i+1}-x_{1})+y_{1})-(m(x_{i}-x_{1})+y_{1})\!$
	$=m(x_{i+1}-x_{i})\!$
	$=m\!$ 。

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

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

これらのアルゴリズムは、（つまり、傾きが 1 以下の場合）には問題なく動作しますが、（つまり、傾きが 1 より大きい場合）には、線がまばらになり、ギャップが多くなり、の極限の場合には、ゼロ除算例外が発生します。 $dx\geq dy$ $dx<dy$ $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) から直線 (符号付き) までのユークリッド距離 D = 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 ]}

参照

参考文献

^ Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: a Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 ( 2024年4月23日アーカイブai.univ-paris8.fr (エラー: アーカイブURL不明) )
^ Robert F. Sproull:プログラム変換を用いた線描画アルゴリズムの導出ACM Transactions on Graphics 1, 4 (1982年10月): 259–273, ISSN 0730-0301
^ Alex T. Pang:並列マシンのための線描画アルゴリズムIEEE Computer Graphics and Applications 10, 5 (1990年9月): 54–59
^例えば、Pere Marès Martí、Antonio B. Martínez Velasco著「非増分アルゴリズムに基づく並列線描画のためのメモリアーキテクチャ」 Euromicro 2000 Proceedings: Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
^例えば、Robert McNamara ua: Prefiltered Antialiased Lines Using Half-Plane Distance Functions. In HWWS 2000 Proceedings: 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3
^ Chengfu Yao, Jon G. Rokne:積分線形補間法による増分直線アルゴリズムの設計. Journal of Computational and Applied Mathematics 102, 1 (1999年2月): 3–19, ISSN 0377-0427
^ Mitchell A. Harris, Edward M. Reingold: Line drawing, leap years, and Euclid. ACM Computing Surveys 36, 1 (2004年3月): 68–80, ISSN 0360-0300 ( 2006年12月16日アーカイブemr.cs.iit.edu (エラー: アーカイブURLが不明) )

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

[1] Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: a Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 ( 2024年4月23日アーカイブai.univ-paris8.fr (エラー: アーカイブURL不明) )

[2] Robert F. Sproull:プログラム変換を用いた線描画アルゴリズムの導出ACM Transactions on Graphics 1, 4 (1982年10月): 259–273, ISSN 0730-0301

[3] Alex T. Pang:並列マシンのための線描画アルゴリズムIEEE Computer Graphics and Applications 10, 5 (1990年9月): 54–59

[4] 例えば、Pere Marès Martí、Antonio B. Martínez Velasco著「非増分アルゴリズムに基づく並列線描画のためのメモリアーキテクチャ」 Euromicro 2000 Proceedings: Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8

[5] 例えば、Robert McNamara ua: Prefiltered Antialiased Lines Using Half-Plane Distance Functions. In HWWS 2000 Proceedings: 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3

[6] Chengfu Yao, Jon G. Rokne:積分線形補間法による増分直線アルゴリズムの設計. Journal of Computational and Applied Mathematics 102, 1 (1999年2月): 3–19, ISSN 0377-0427

[7] Mitchell A. Harris, Edward M. Reingold: Line drawing, leap years, and Euclid. ACM Computing Surveys 36, 1 (2004年3月): 68–80, ISSN 0360-0300 ( 2006年12月16日アーカイブemr.cs.iit.edu (エラー: アーカイブURLが不明) )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[