Loading article…
コンピュータグラフィックスにおいて、ラインクリッピングとは、関心領域（ビューポートまたはビューボリューム）の外側にある線または線の一部を削除（クリッピング）するプロセスです。通常、表示領域外にある線の一部は削除されます。
ラインクリッピングには、 Cohen–SutherlandとLiang–Barsky という2 つの一般的なアルゴリズムがあります。
ラインクリッピング法は、さまざまな部分から構成されています。特定のラインセグメントに対してテストを実行し、それがビューエリアまたはボリュームの外側にあるかどうかを調べます。次に、 1つ以上のクリッピング境界を使用して交差計算を実行します。[1]ラインのどの部分がクリッピングボリュームの内側または外側にあるかを判断するには、交差点に関してラインの端点を処理します。
コーエン・サザーランド
コンピュータグラフィックスにおける Cohen-Sutherland アルゴリズム (Danny Cohen と Ivan Sutherland にちなんで命名) は、ラインクリッピング アルゴリズムです。このアルゴリズムは、2D 空間を 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 年。
- ^ Mark S. Sobkow、Paul Pospisil、Yee-Hong Yang。ラインエンコーディングによる高速2次元ラインクリッピングアルゴリズム//Computer & Graphics、Vol. 11、No. 4、pp. 459–467、1987年。
- ^ 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年。