コーエン・サザーランドアルゴリズム
コンピュータグラフィックスにおいて、コーエン・サザーランドアルゴリズムは線分のクリッピングに用いられるアルゴリズムです。このアルゴリズムは、2次元空間を9つの領域に分割し、中心の関心領域（ビューポート）に表示される線分および線分の一部を効率的に決定します。
このアルゴリズムは1967年にダニー・コーエンとイヴァン・サザーランドによってフライトシミュレーターの開発中に開発された。[ 1 ]
アルゴリズム
アルゴリズムは、以下の基準に基づいて、行を含めるか、除外するか、部分的に含めるかを決定します
- 両方のエンドポイントがビューポート領域内にあります (エンドポイントのビット単位の OR = 0000):単純に受け入れます。
- 両方のエンドポイントは少なくとも 1 つの非表示領域を共有しており、これは線が表示領域を横切らないことを意味します。(エンドポイントのビット単位の AND ≠ 0000):単純な拒否。
- 両端点が異なる領域内にある場合：このような状況では、アルゴリズムは2点のうちビューポート領域外にある点を見つけます（少なくとも1点はビューポート領域外にあります）。次に、アウトポイントと拡張ビューポート境界の交点（つまり、直線の媒介変数方程式）を計算し、この新しい点をアウトポイントに置き換えます。アルゴリズムは、自明な承認または却下が行われるまで繰り返されます。
下の図の数字はアウトコードと呼ばれます。アウトコードは、線上の2つの点それぞれに対して計算されます。アウトコードは、2次元クリッピングの場合は4ビット、3次元クリッピングの場合は6ビットになります。点がビューポートの上にある場合、最初のビットは1に設定されます。2次元アウトコードのビットは、上、下、右、左を表します。例えば、アウトコード1010は、ビューポートの右上にある点を表します。
左 中央 右 上 1001 1000 1010 中央 0001 0000 0010 下 0101 0100 0110
クリッピングが発生した後、 エンドポイントのアウトコードは各反復で再計算する必要があることに注意してください。
Cohen–Sutherland アルゴリズムは、長方形クリップ ウィンドウでのみ使用できます。
C/C++実装例
typedef int OutCode ;const int INSIDE = 0b0000 ; const int LEFT = 0b0001 ; const int RIGHT = 0b0010 ; const int BOTTOM = 0b0100 ; const int TOP = 0b1000 ;//対角線上で (xmin, ymin) と (xmax, ymax) で囲まれたクリップ長方形を使用して、点 (x, y) のビットコードを計算します。// xmax、xmin、ymax、ymin はグローバル定数であると想定します。OutCode ComputeOutCode ( double x , double y ) { OutCode code = INSIDE ; // クリップウィンドウの内側として初期化されますif ( x < xmin ) // クリップ ウィンドウコードの左側|= LEFT ; else if ( x > xmax ) // クリップ ウィンドウコードの右側|= RIGHT ; if ( y < ymin ) // クリップ ウィンドウコードの下|= BOTTOM ; else if ( y > ymax ) // クリップ ウィンドウコードの上|= TOP ;戻りコード; }// Cohen–Sutherland クリッピング アルゴリズムは、(xmin, ymin) から (xmax, ymax) までの対角線を持つ四角形に対して、P0 = (x0, y0)から P1 = (x1, y1) までの線をクリップします。 bool CohenSutherlandLineClip ( double & x0 , double & y0 , double & x1 , double & y1 ) { // P0、P1、およびクリップ四角形の外側にある点のアウトコードを計算しますOutCode outcode0 = ComputeOutCode ( x0 , y0 ); OutCode outcode1 = ComputeOutCode ( x1 , y1 ); bool accept = false ;while ( true ) { if ( ! ( outcode0 | outcode1 )) { // ビットごとの OR は 0 です: 両方のポイントがウィンドウの内側にあります。当然、accept してループを終了します。 accept = true ; break ; } else if ( outcode0 & outcode1 ) { // ビットごとの AND は 0 ではありません: 両方のポイントが外側のゾーン (LEFT、RIGHT、TOP、または BOTTOM) を共有しているため、両方ともウィンドウの外側にある必要があります。ループを終了します (accept は false) break ; } else { // 両方のテストに失敗したため、外側のポイントからクリップ エッジとの交差点までのクリップする線分を計算します。 double x , y ;// 少なくとも 1 つのエンドポイントがクリップ四角形の外側にあるので、それを選択します。OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0 ;// 次に交点を探します。// 次の数式を使用します: // slope = (y1 - y0) / (x1 - x0) // x = x0 + (1 / slope) * (ym - y0) (ym は ymin または ymax) // y = y0 + slope * (xm - x0) (xm は xmin または xmax) // いずれの場合も、テストされるアウトコード ビットによって分母が 0 以外になることが保証されるため、ゼロ除算を心配する必要はありません。 if ( outcodeOut & TOP ) { // ポイントはクリップ ウィンドウの上にあります。x = x0 + ( x1 - x0 ) * ( ymax - y0 ) / ( y1 - y0 ); y = ymax ; } else if ( outcodeOut & BOTTOM ) { // ポイントはクリップ ウィンドウの下にありますx = x0 + ( x1 - x0 ) * ( ymin - y0 ) / ( y1 - y0 ); y = ymin ; } else if ( outcodeOut & RIGHT ) { // ポイントはクリップ ウィンドウの右側にありますy = y0 + ( y1 - y0 ) * ( xmax - x0 ) / ( x1 - x0 ); x = xmax ; } else if ( outcodeOut & LEFT ) { // ポイントはクリップ ウィンドウの左側にありますy = y0 + ( y1 - y0 ) * ( xmin - x0 ) / ( x1 - x0 ); x = xmin ; }// ここで、外側の点を交差点に移動してクリップし、次のパスの準備をします。if ( outcodeOut == outcode0 ) { x0 = x ; y0 = y ; outcode0 = ComputeOutCode ( x0 , y0 ); } else { x1 = x ; y1 = y ; outcode1 = ComputeOutCode ( x1 , y1 ); } } } return accept ; }注記
- ^インタラクティブコンピュータグラフィックスの原理、p.124、252、ボブ・スプロール、ウィリアム・M・ニューマン著、1973年、マグロウヒル・エデュケーション、国際版、 ISBN 0-07-085535-8。
参照
同じ目的で使用されるアルゴリズム：
参考文献
- James D. Foley著『コンピュータグラフィックス：原理と実践』Addison-Wesley Professional、1996年、113ページ
外部リンク
