ライン・ルーチン

(2)線分のクリッピング

前回のルーチンでは、与えられた座標値が有効範囲を超えていた場合の処理が入っていないため、ここでクリッピングの処理を加えます。線分のクリッピング処理は、描画する線分と描画可能な矩形領域(以下「ウィンドウ」と略記)の辺との交点を求めて、矩形外の部分を切り捨てる事で行います。


1)両端点の分類

まず第一段階として、線分の両端点がウィンドウの中にあるか(以下「可視」と略記) 外にあるか(以下「不可視」と略記)、また不可視の場合、線分がウィンドウの辺のいずれと交わる可能性があるかを調べます。両端点が可視の場合は線分全体が可視であるため、クリッピングは必要ありません。端点のうち片側のみ不可視である場合、線分は部分的に不可視であり、両端点とも不可視の場合は線分は完全に不可視か、部分的に不可視かのどちらかになります。
端点の位置を4ビットのコードで表すと、「可視」と「不可視」の分類が効率的にできるようになります。この4ビットコードの各ビットは、ウィンドウの各辺及びそれを延長した直線に対応しており、端点がウィンドウの辺の内側にあるか外側にあるかを01で表します。ここでは、このコードを「端点分類コード」と呼ぶことにします。下図では

0ビットウィンドウの左辺
1ビットウィンドウの右辺
2ビットウィンドウの上辺
3ビットウィンドウの下辺

のように対応させてあり、中央の枠が画像を描画するウィンドウを表すことになります。

端点分類コード
010101000110
000100000010
100110001010

両端点の分類コードが0000である場合、線分は完全に可視であるからクリッピングの必要はありません。また、両端点の分類コードの論理積(AND)が非0の場合、両端点はともに「同じ辺の不可視側にあるから」線分は完全に不可視となります。


2)交点算出処理

続いて、ウィンドウの辺と線分との交点を算出していきます。 このとき、まだ線分が完全に不可視である(すなわち交点が存在しない)場合があることに注意する必要があります(下図左側)。また、場合によっては最大2回のクリッピングをしないと正しい交点が得られない場合もあり得ます。よって一辺でクリッピングしたら必ずその点がウィンドウ内にあるかをチェックする必要があります(下図右側)。

fig1-2-1

具体的な交点の算出方法に進みます。まず、始点(X0,Y0)の分類コードが0001、終点(X1,Y1)の分類コードが0000であるような線分(X0,Y0)-(X1,Y1)をクリッピングする場合を考えます。このときは(X0,Y0)をウィンドウ左辺でクリッピングすればよいことになります。
交点の算出方法として、最初に中点分割アルゴリズムを紹介します。これはソフトウェアよりもハードウェアによる実現に適したアルゴリズムです。

A.中点分割アルゴリズム

このアルゴリズムでは、まず両端点の中点の座標(mx,my)を求め、線分を

( X0, Y0 ) - ( mx, my )
( mx, my ) - ( X1, Y1 )

に二分割します。中点の座標はそれぞれ

mx = ( X0 + X1 ) / 2
my = ( Y0 + Y1 ) / 2

で得られます。

ウィンドウの左辺でクリッピングする場合、得られたmxとウィンドウ左辺のX座標(以下minXとする)を比較することで、二分割した線分のどちら側に辺との交点があるか判断できます。その後、辺との交点が存在する側の線分をさらに二分割して、同様の比較を繰り返します。1回分割する毎に線分の長さは半分になり、線分がこれ以上分割できない状態(すなわち点)になったらその点が求める交点となります。

以下に、線分 (-30,15)-(16,19)を、中点分割アルゴリズムによりウィンドウの左辺 X=0でクリッピングしたときの中点の変化を示します。

回数12345
中点の座標(-7,17)(4,18)(-2,17)(1,17)(0,17)

中点算出時に座標値を半分にする処理を1ビットの右シフトで行うとすれば、座標値の範囲が16bit(-3276832767)の場合、最大16回の分割作業で交点が見つかるし、上の例のように途中で中点とウィンドウの辺が交わればそれ以上の分割は必要ないため、この方法は見かけ以上に高速に動作します。
問題は、2で割るときの端数の扱いです。上の例では2で割ったときの余りはすべて切り捨てているため、得られる座標値は実際の交点[≒(0, 17.6)]よりも負の方向へシフトしています。浮動小数点演算で処理してやればこの誤差もなくすことができますが、処理が重くなるのでそれはなるべく避けたいということで、ここではこの誤差については見送ることにします。ちなみに、浮動小数点演算でなく固定小数点演算を使って誤差をなくす方法がありますが、ここでは触れません。別の機会に紹介したいと思います。

B.数学的手法による交点の算出

中点分割アルゴリズムは比較的ハードウェアでの実現に適した方法であり、ソフトウェアによる実現では実際に交点を算出したほうが高速になります(らしい)。

y = m( minX - X0 ) + Y0 ( ただしm = ( Y1 - Y0 ) / ( X1 - X0 ) )

を解いてやればいいことになるので、中点分割アルゴリズムで示した例の場合、

m = (19-15) / {16-(-30)} = 2/23

y = (2/23) * {0-(-30)} + 1517.6

整数化して(0,17)が求める交点となります。


以下に、クリッピング処理のサンプル・プログラムを示します(ウィンドウの辺との交点は「数学的手法による交点の算出」で求めています)。

/* 端点分類コード */
enum Edge {
  LEFT = 1,
  RIGHT = 2,
  TOP = 4,
  BOTTOM = 8,
};

/* 座標定義用構造体 */
typedef struct Coord
{
  int x;
  int y;
} Coord;

/* クリッピングエリア */
Coord Min, Max;

/*
  calc_seq_code : 端点分類コードを求める

  Coord c : 座標値

  戻り値 : 端点分類コード
*/
int calc_seq_code( Coord c )
{
  int code = 0;
  if( c.x < Min.x ) code += LEFT;
  if( c.x > Max.x ) code += RIGHT;
  if( c.y < Min.y ) code += TOP;
  if( c.y > Max.y ) code += BOTTOM;

  return( code );
}

/*
  calc_midP : 中点分割法による交点の算出メインルーチン

  int a0, int b0, int a1, int b1 : 線分の座標
  int clip_a : クリッピングする座標

  クリッピング対象は bの方になる。

  戻り値 : クリッピング結果
*/
int calc_midP( int a0, int b0, int a1, int b1, int clip_a )
{
  /* もう一方の端点がウィンドウの辺上にある場合の対処 */
  if ( a0 == clip_a ) return( b0 );
  if ( a1 == clip_a ) return( b1 );

  /*
    線分の始点と終点を求める
     (必ず sa < ea となるようにする)
  */
  int sa, sb, ea, eb;
  if ( a0 < a1 ) {
    sa = a0, sb = b0;
    ea = a1, eb = b1;
  } else {
    sa = a1, sb = b1;
    ea = a0, eb = b0;
  }

  int ca, cb;
  do {
    ca = ( sa + ea ) >> 1;
    cb = ( sb + eb ) >> 1;
    if ( ca < clip_a ) {
      sa = ca;
      sb = cb;
    } else {
      ea = ca;
      eb = cb;
    }
  } while ( ca != clip_a );

  return( cb );
}

/*
  calc_midP_x : 中点分割法による交点の算出(左右の辺)

  Coord c0, c1 : クリッピング前の線分座標
  int clip_x : 左(または右)の辺のX座標
  Coord* c : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
int calc_midP_x( Coord c0, Coord c1, int clip_x, Coord* c )
{
  int cy = calc_midP( c0.x, c0.y, c1.x, c1.y, clip_x );

  /* エリア外の場合はFalseを返す */
  if ( ( cy < Min.y ) || ( cy > Max.y ) ) return( 0 );

  c->x = clip_x;
  c->y = cy;

  return( 1 );
}

/*
  calc_midP_y : 中点分割法による交点の算出(上下の辺)

  Coord c0, c1 : クリッピング前の線分座標
  int clip_y : 上(または下)の辺のY座標
  Coord* c : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
int calc_midP_y( Coord c0, Coord c1, int clip_y, Coord* c )
{
  int cx = calc_midP( c0.y, c0.x, c1.y, c1.x, clip_y );

  /* エリア外の場合はFalseを返す */
  if ( ( cx < Min.x ) || ( cx > Max.x ) ) return( 0 );

  c->x = cx;
  c->y = clip_y;

  return( 1 );
}

/*
  calc_intsec_x : 数学的手法による交点の算出(左右の辺)

  Coord c0, c1 : クリッピング前の線分座標
  int clip_x : 左(または右)の辺のX座標
  Coord* c : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
int calc_intsec_x( Coord c0, Coord c1, int clip_x, Coord* c )
{
  int cy = ( c1.y - c0.y ) * ( clip_x - c0.x ) / ( c1.x - c0.x ) + c0.y;

  /* エリア外の場合はFalseを返す */
  if ( ( cy < Min.y ) || ( cy > Max.y ) ) return( 0 );

  c->x = clip_x;
  c->y = cy;

  return( 1 );
}

/*
  calc_intsec_y : 数学的手法による交点の算出(上下の辺)

  Coord c0, c1 : クリッピング前の線分座標
  int clip_y : 上(または下)の辺のY座標
  Coord* c : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
int calc_intsec_y( Coord c0, Coord c1, int clip_y, Coord* c )
{
  int cx = ( c1.x - c0.x ) * ( clip_y - c0.y ) / ( c1.y - c0.y ) + c0.x;

  /* エリア外の場合はFalseを返す */
  if ( ( cx < Min.x ) || ( cx > Max.x ) ) return( 0 );

  c->x = cx;
  c->y = clip_y;

  return( 1 );
}

/*
  クリッピング後の座標を求める

  int code : 端点分類コード
  Coord c0, c1 : 線分の座標
  Coord* c : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
int calc_clipped_point( int code, Coord c0, Coord c1, Coord* c )
{
  /* ウィンドウの左端より外側にある */
  if ( ( code & LEFT ) != 0 )
    if ( calc_intsec_x( c0, c1, Min.x, c ) )
    /* if ( calc_midP_x( c0, c1, Min.x, c ) ) */
      return( 1 );

  /* ウィンドウの右端より外側にある */
  if ( ( code & RIGHT ) != 0 )
    if ( calc_intsec_x( c0, c1, Max.x, c ) )
    /* if ( calc_midP_x( c0, c1, Max.x, c ) ) */
      return( 1 );

  /* ウィンドウの上端より外側にある */
  if ( ( code & TOP ) != 0)
    if ( calc_intsec_y( c0, c1, Min.y, c ) )
    /* if ( calc_midP_y( c0, c1, Min.y, c ) ) */
      return( 1 );

  /* ウィンドウの下端より外側にある */
  if ( ( code & BOTTOM ) != 0 )
    if ( calc_intsec_y( c0, c1, Max.y, c ) )
    /* if ( calc_midP_y( c0, c1, Max.y, c ) ) */
      return( 1 );

  return( 0 );  /* クリッピングされなかった場合、線分は完全に不可視 */
}

/*
  クリッピングメインルーチン

  Coord* c0 : 始点の座標
  Coord* c1 : 終点の座標

  戻り値 :
   >0 ... クリッピングされた
   0  ... クリッピングの必要なし
   <0 ... 線分は完全に不可視
*/
int clipping( Coord* c0, Coord* c1 )
{
  int code0, code1; /* 端点分類コード */

  code0 = calc_seq_code( *c0 );  /* 始点の端点分類コードを求める */
  code1 = calc_seq_code( *c1 );  /* 終点の端点分類コードを求める */

  /* 端点分類コードがどちらも0000ならばクリッピングは必要なし */
  if ( ( code0 == 0 ) && ( code1 == 0 ) ) return( 0 );

  /* 始点・終点の端点分類コードの論理積が非0ならば線分は完全に不可視 */
  if ( ( code0 & code1 ) != 0 ) return( -1 );

  /* 始点のクリッピング */
  if( code0 != 0 )
    if ( ! calc_clipped_point( code0, *c0, *c1, c0 ) )
      return( -1 );

  /* 終点のクリッピング */
  if( code1 != 0 )
    if ( ! calc_clipped_point( code1, *c0, *c1, c1 ) )
      return( -1 );

  return( 1 );
}

calc_intsec_xcalc_intsec_yは、数学的手法による交点の算出用ルーチン、calc_midP, calc_midP_x, calc_midP_yは中点分割アルゴリズムによる交点算出用ルーチンです。クリッピング後の座標を求めるcalc_clipped_pointの中で切り替えを行うと、いずれかの方法でクリッピングができます。


◆◇◆更新履歴◆◇◆

◎ サンプルソースで、以前はクリッピング領域と線分の交点を算出する計算式が

CX=(x1-x0)/(y1-y0)*(MIN_Y-y0)+x0;
CY=(y1-y0)/(x1-x0)*(MIN_X-x0)+y0;

となっていましたが、これでは丸めによる誤差が大きくなるとの指摘があり、修正しました。

さらに小数点以下切り捨てではなく、下のような式で四捨五入を行うことで、精度を向上させる案も送っていただきました。精度重視の場合はこちらを使用した方がいいでしょう。

CX=(2*(x1-x0)*(MIN_Y-y0)/(y1-y0)+1)/2+x0;
CY=(2*(y1-y0)*(MIN_X-x0)/(x1-x0)+1)/2+y0;

◎ 「クリッピング時に0除算をする」場合があることが判明しました。

サンプルのソースを使った場合、「片側の点がクリッピング枠上にあり、もう一方の点が枠外にあるとき」は、枠外にある点のクリッピングが一度終わった段階で、2点の座標が一致してしまうため、さらにクリッピングを続けると0除算が発生してしまいます。この場合は残りの処理はする必要はないし、してはいけないため、修正を行いました。

最後になりますが、いろいろな御指摘どうもありがとうございました。


◎ サンプルソースを大幅に変更しました。中点分割アルゴリズムによる交点算出用ルーチンをサンプル・プログラムに追加し、他のルーチンも見直しを行っています。


[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system