コンピュータグラフィックスにおいて、ラインクリッピングとは、対象領域（ビューポートまたはビューボリューム）の外側にある線または線の一部を削除（クリッピング）するプロセスです。通常、表示領域外にある線の一部は削除されます。
ラインクリッピングには、 Cohen–SutherlandとLiang–Barsky という2 つの一般的なアルゴリズムがあります。
ラインクリッピング法は様々な要素から構成されます。まず、与えられた線分がビューエリアまたはボリュームの外側にあるかどうかを判定します。次に、 1つ以上のクリッピング境界との交差計算を行います。[1]線のどの部分がクリッピングボリュームの内側か外側かを判断するには、交差を基準として線分の端点を処理します。
コーエン・サザーランド
コンピュータグラフィックスにおいて、コーエン・サザーランドアルゴリズム（ダニー・コーエンとアイヴァン・サザーランドにちなんで名付けられた）は、線クリッピングアルゴリズムです。このアルゴリズムは2次元空間を9つの領域に分割し、そのうち中央部分（ビューポート）のみを可視領域とします。
1967 年、ダニー・コーエンによるフライト シミュレーションの研究がきっかけとなり、アイヴァン・サザーランドと共同でコーエン - サザーランド コンピュータ グラフィックスの 2 次元および 3 次元ライン クリッピング アルゴリズムを開発しました。
リャン・バルスキー
Liang–Barskyアルゴリズムは、直線の媒介変数方程式とクリッピングボックスの範囲を記述する不等式を用いて、直線とクリッピングボックスの交点を決定します。これらの交点を用いて、直線のどの部分を描画すべきかを判断します。このアルゴリズムはCohen–Sutherlandアルゴリズムよりもはるかに効率的ですが、Cohen–Sutherlandアルゴリズムは単純な受理と棄却をはるかに高速に行うため、クリッピングする必要がある直線のほとんどがクリップウィンドウの内側または外側にある場合は、Cohen–Sutherlandアルゴリズムを検討する必要があります。
サイラス・ベック
Liang–Barskyラインクリッピングアルゴリズムと非常によく似ています。違いは、Liang–Barskyは簡略化されたCyrus–Beck変種であり、長方形のクリップウィンドウに最適化されている点です。
サイラス・ベックアルゴリズムは、主に2次元の凸多角形または3次元の凸多面体に対してパラメトリック形式の線をクリッピングすることを目的としています。[2]
ニコル・リー・ニコル
Nicholl–Lee–Nichollアルゴリズムは、Cohen–Sutherlandアルゴリズムのように、単一の線分が複数回クリッピングされる可能性を低減する高速な線クリッピングアルゴリズムです。クリッピングウィンドウは、クリッピング対象となる線分の開始点の位置に応じて、複数の異なる領域に分割されます。
高速クリッピング
このアルゴリズムはコーエン・サザーランド法と類似点がある。開始位置と終了位置は、9つの領域からなるグリッドのどの部分を占めるかによって分類される。大きなswitch文は、それぞれのケースに対応する専用のハンドラにジャンプする。一方、コーエン・サザーランド法では、同じケースを処理するために複数回の反復処理が必要になる場合がある。[3]
お（lg北）アルゴリズム
このアルゴリズムは、頂点を暗黙の形式p : ax + by + c =0で与えられた直線に対して分類します。多角形は凸型と仮定され、頂点は時計回りまたは反時計回りに順序付けられているため、バイナリサーチを適用することができ、実行時の複雑さはO (lgN )になります。 [4]
スカラ
このアルゴリズムは同次座標と双対性に基づいています。[5]これは、長方形ウィンドウだけでなく凸多角形に対しても線分または線分のクリッピングに使用できます。このアルゴリズムは、クリッピングウィンドウの頂点を直線p : ax + by + c = 0 で与えられる半空間に対して分類することに基づいています。分類の結果から、直線pが交差するエッジが決定されます。このアルゴリズムは単純で実装が容易であり、凸ウィンドウにも拡張可能です。直線または線分p は、同次座標で与えられた点r 1、r 2から、外積を直接使用して 計算できます。
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
または
- p = r 1 × r 2 = ( x 1 , y 1 , 1) × ( x 2 , y 2 , 1) です。
参照
参考文献
- ^ Renka, RJ (2014-10-19). 「Line Clipping」（PDF） . ノーステキサス大学コンピュータサイエンス＆エンジニアリング学部. 2016年1月12日閲覧。
- ^ Cyrus, M., Beck, J.: 一般化された 2 次元および 3 次元クリッピング、Computers & Graphics、Vol. 3、No. 1、pp. 23–28、1978 年。
- ^ Sobkow, Mark S.; Pospisil, Paul; Yang, Yee-Hong (1987). 「ラインエンコーディングによる高速2次元ラインクリッピングアルゴリズム」. Computers & Graphics . 11 (4): 459– 467.
- ^ Skala, V.: O (lg N ) ラインクリッピングアルゴリズム、E2、Computers & Graphics、Pergamon Press、Vol. 18、No. 4、1994。
- ^ Skala, V.: 同次座標における線分および線分のクリッピングへの新しいアプローチ、The Visual Computer、ISSN 0178-2789、Vol. 21、No. 11、pp. 905–914、Springer Verlag、2005年。
