2008/04/15(火)描画アルゴリズム

2008/04/15 25:09 MegaAVR::LCDライブラリ

下調べの段階。昔も線分描画を作ったので流用可能ですが、再度調べてまとめておきたいと思います。といいつつ、ググって貼り付けるだけという酷い話で(ぉ


Fussyのホームページで詳しく解説されています。*1 X68erのようですねぇ。やはりこの辺の基礎がしっかりしているのには納得がいきますネ。パワーユーザばかりの印象があります。1人だけゲーマーとして持っている人を見た記憶がありますが('A`

とりあえず、補完のためコードだけ抜粋して流用したいと思います... dotを打つ処理が重いので、その点に関しては実装時に最適化をしてやる必要があります。とくにブレンド処理なんかを考えている場合は要注意です. VRAM外付け or 別デバイスのためにR/Wが遅いケースが致命傷です。マイコンのメモリに余裕があれば仮想VRAMとして割り当て、定期的に全画面転送したほうが無難かもしれません。

「Bresenhamの線分発生アルゴリズム」のサンプル・プログラム

void line( int x0, int y0, int x1, int y1, unsigned int col )
{
  int i;

  int dx = ( x1 > x0 ) ? x1 - x0 : x0 - x1;
  int dy = ( y1 > y0 ) ? y1 - y0 : y0 - y1;
  int sx = ( x1 > x0 ) ? 1 : -1;
  int sy = ( y1 > y0 ) ? 1 : -1;

  /* 傾きが1以下の場合 */
  if( dx >= dy ) {
    int E = -dx;
    for( i = 0 ; i <= dx ; i++ ) {
      pset( x0, y0, col );
      x0 += sx;
      E += 2 * dy;
      if( E >= 0 ) {
        y0 += sy;
        E -= 2 * dx;
      }
    }
  /* 傾きが1より大きい場合 */
  } else {
    int E = -dy;
    for( i = 0 ; i <= dy ; i++ ) {
      pset( x0, y0, col );
      y0 += sy;
      E += 2 * dx;
      if( E >= 0 ) {
        x0 += sx;
        E -= 2 * dy;
      }
    }
  }
}

クリッピング処理のサンプル・プログラム

/* 端点分類コード */
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 );

  /* 始点・終点の端点分類コードの論理積が非０ならば線分は完全に不可視 */
  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 );
}

*1 : ほかのアルゴリズム説明に読み浸ってしまいました(^^; なんとも懐かしいやら, 説明が旨いやら... なんとなくやったけど忘れてるなぁ、というのが正直なところ... otz