リャン・バースキーアルゴリズム

コンピュータグラフィックスにおいて、リアン・バルスキーアルゴリズム（ You-Dong LiangとBrian A. Barskyにちなんで命名）は、 1984年初頭に初めて公開されたラインクリッピングアルゴリズムです。リアン・バルスキーアルゴリズムは、ラインの媒介変数方程式とクリッピングウィンドウの範囲を記述する不等式を使用して、ラインとクリップウィンドウの交点を決定します。これらの交点により、ラインのどの部分を描画すべきかがわかります。そのため、このアルゴリズムはコーエン・サザーランドアルゴリズムよりもはるかに効率的です。リアン・バルスキークリッピングアルゴリズムの考え方は、ラインの交点を計算する前に、できるだけ多くのテストを行うことです。

このアルゴリズムでは、直線のパラメトリック形式を使用します。

${\displaystyle x=x_{0}+t(x_{1}-x_{0})=x_{0}+t\Delta x,}$

${\displaystyle y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\デルタ y.}$

ポイントがクリップウィンドウ内にある場合、

${\displaystyle x_{\text{min}}\leq x_{0}+t\Delta x\leq x_{\text{max}}}$

そして

${\displaystyle y_{\text{min}}\leq y_{0}+t\Delta y\leq y_{\text{max}},}$

これは4つの不等式で表すことができる

${\displaystyle tp_{i}\leq q_{i},\quad i=1,2,3,4,}$

どこ

${\displaystyle {\begin{aligned}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(left)}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(right)}}\\p_{3}&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(bottom)}}\\p_{4}&=\Delta y,&q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(top)}}\end{aligned}}}$

最終的な線分を計算するには:

1. その境界にはクリッピング ウィンドウのエッジに平行な線があります。${\displaystyle p_{i}=0}$
2. の場合、線は完全に外側にあるため、削除できます。${\displaystyle i}$ ${\displaystyle q_{i}$
3. のとき、線はクリップ ウィンドウの外側から内側に進みます。 のとき、線は内側から外側に進みます。${\displaystyle p_{i}$ ${\displaystyle p_{i}>0}$
4. がゼロ以外の場合、直線とウィンドウの端（投影されている可能性あり）の交点が与えられます。${\displaystyle p_{i}}$ ${\displaystyle u=q_{i}/p_{i}}$ ${\displaystyle t}$
5. 線と窓の端との実際の交点は、もし存在するならば、 および で表され、以下のように計算されます。 について、 の境界（つまり、外側から内側へ）を調べます。の中で が最大となるようにします。 について、 の境界（つまり、内側から外側へ）を調べます。 が最小となるようにします。${\displaystyle u_{1}}$ ${\displaystyle u_{2}}$ ${\displaystyle u_{1}}$ ${\displaystyle p_{i}$ ${\displaystyle u_{1}}$ ${\displaystyle \{0,q_{i}/p_{i}\}}$ ${\displaystyle u_{2}}$ ${\displaystyle p_{i}>0}$ ${\displaystyle u_{2}}$ ${\displaystyle \{1,q_{i}/p_{i}\}}$
6. の場合、線は完全にクリップウィンドウの外側にあります。 の場合、線は完全にクリップウィンドウの内側にあります。${\displaystyle u_{1}>u_{2}}$ ${\displaystyle u_{1}<0<1<u_{2}}$

// Liang–Barsky ラインクリッピングアルゴリズム#include <iostream> #include <graphics.h> #include <math.h>名前空間stdを使用します。// この関数は最大値を返します。float maxi ( float arr [], int n ) { float m = 0 ; for ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }// この関数は最小値を返します。float mini ( float arr [], int n ) { float m = 1 ; for ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }void liang_barsky_clipper ( float xmin , float ymin , float xmax , float ymax , float x1 , float y1 , float x2 , float y2 ) { // 変数の定義float p1 = - ( x2 - x1 ); float p2 = - p1 ; float p3 = - ( y2 - y1 ); float p4 = - p3 ;浮動小数点q1 = x1 - xmin ;浮動小数点q2 = xmax - x1 ;浮動小数点q3 = y1 - ymin ;浮動小数点q4 = ymax - y1 ;float exitParams [ 5 ], entryParams [ 5 ]; int exitIndex = 1 , entryIndex = 1 ; exitParams [ 0 ] = 1 ; entryParams [ 0 ] = 0 ;rectangle ( xmin , ymin , xmax , ymax ); // クリッピングウィンドウを描画するif (( p1 == 0 && q1 < 0 ) || ( p2 == 0 && q2 < 0 ) || ( p3 == 0 && q3 < 0 ) || ( p4 == 0 && q4 < 0 )) { outtextxy ( 80 , 80 , "線はクリッピング ウィンドウと平行です!" ); return ; } if ( p1 != 0 ) { float r1 = q1 / p1 ; float r2 = q2 / p2 ; if ( p1 < 0 ) { entryParams [ entryIndex ++ ] = r1 ; exitParams [ exitIndex ++ ] = r2 ; } else { entryParams [ entryIndex ++ ] = r2 ; exitParams [ exitIndex ++ ] = r1 ; } } if ( p3 != 0 ) { float r3 = q3 / p3 ; float r4 = q4 / p4 ; if ( p3 < 0 ) { entryParams [ entryIndex ++ ] = r3 ; exitParams [ exitIndex ++ ] = r4 ; } else { entryParams [ entryIndex ++ ] = r4 ; exitParams [ exitIndex ++ ] = r3 ; } }float clippedX1 、clippedY1 、clippedX2 、clippedY2 ; float u1 、u2 ; u1 = maxi ( entryParams 、entryIndex ); // エントリポイントの最大値u2 = mini ( exitParams 、exitIndex ); // エグジットポイントの最小値if ( u1 > u2 ) { outtextxy ( 80 , 80 , "行はクリッピングウィンドウの外側にあります!" ); return ; }クリップされたX1 = x1 + ( x2 - x1 ) * u1 ;クリップされたY1 = y1 + ( y2 - y1 ) * u1 ;クリップされたX2 = x1 + ( x2 - x1 ) * u2 ;クリップされたY2 = y1 + ( y2 - y1 ) * u2 ;setcolor ( CYAN ); line ( clippedX1 , clippedY1 , clippedX2 , clippedY2 ); // クリップされたセグメントを描画するsetlinestyle ( 1 , 1 , 0 ); line ( x1 , y1 , clippedX1 , clippedY1 ); // 元の開始位置からクリップされた開始位置までline ( x2 , y2 , clippedX2 , clippedY2 ); // 元の終了位置からクリップされた終了位置まで}int main () { cout << " \n Liang-Barsky 線クリッピング" ; cout << " \nシステム ウィンドウのレイアウトは、左下が (0,0)、右上が (631, 467) です" ; cout << " \nウィンドウの座標 (xmin、ymin、xmax、ymax) を入力します: " ; float xmin 、ymin 、xmax 、ymax ; cin >> xmin >> ymin >> xmax >> ymax ;cout << " \n線分 (x1, y1) と (x2, y2) の終点を入力します: " ; float x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;int gd = DETECT , gm ; initgraph ( & gd , & gm , "" ); // winbgimを使用するliang_barsky_clipper ( xmin 、ymin 、xmax 、ymax 、x1 、y1 、x2 、y2 ); getch (); closegraph (); }

参照

同じ目的で使用されるアルゴリズム:

• サイラス・ベックアルゴリズム
• ニコル・リー・ニコルアルゴリズム
• 高速クリッピング

参考文献

• Liang, YD、およびBarsky, B.、「ラインクリッピングの新しい概念と方法」、ACM Transactions on Graphics、3(1):1–22、1984年1月。
• Liang, YD, BA, Barsky、および M. Slater、「パラメトリック ライン クリッピング アルゴリズムのいくつかの改良」、CSD-92-688、コンピュータ サイエンス部門、カリフォルニア大学バークレー校、1992 年。
• ジェームズ・D・フォーリー著『コンピュータグラフィックス：原理と実践』Addison-Wesley Professional、1996年、117ページ。

外部リンク

• http://hinjang.com/articles/04.html#eight
• Skytopia: Liang-Barsky ライン クリッピング アルゴリズムを簡単に説明します。