グラフィック・パターンの扱い

(3)パターンの回転

下図に示したように、三角関数の加法定理を利用すると、原点を中心として点( x, y )を角度θだけ回転したときの座標 ( x', y' ) を求めることができます。

画像の回転

この変換式を利用すると、矩形 ( x0, y0 ) - ( x1, y1 ) を、矩形の中心

( ox, oy ) = ( ( x0 + x1 ) / 2, ( y0 + y1 ) / 2 )

を原点としてθだけ回転した時、矩形内の任意のピクセル ( x, y ) は

x' = ( x - ox )cosθ - ( y - oy )sinθ + ox

y' = ( x - ox )sinθ + ( y - oy )cosθ + oy

に変換されることがわかります。

パラメータとして回転の中心 ( ox, oy )を与える場合、( x, y ) は、

( ox - dx / 2, oy - dy / 2 )

から X方向に dx、Y方向にdyの分だけ上式による変換を順次行い、パターンのピクセルを描画すればよいことになります。但し、( dx, dy ) は矩形パターンの大きさを表します。すなわち、

dx = ( x1 - x0 + 1 )

dy = ( y1 - y0 + 1 )

になります。

これをそのままコーディングすると、画面に描画する部分は以下のようになります。

/* (ox,oy) : 回転の中心
   (dx,dy) : 取り込んだパターンの大きさ
   r       : 回転角度                   */

:
/* 描画位置の左上座標 */
sx = ox - dx / 2;
sy = oy - dy / 2;

for ( py = sy ; py < sy + dy ; py++ ) {
  for ( px = sx ; px < sx + dx ; px++ ) {
    rx = ( px - ox ) * cos( r ) - ( py - oy ) * sin( r ) + ox;
    ry = ( px - ox ) * sin( r ) + ( py - oy ) * cos( r ) + oy;
    pset( rx, ry, *pat++ );
  }
}
:

上記処理を使った場合、拡大・縮小ルーチンと同じく描画した画像に隙間ができてしまう問題が発生します。よって、ここでも「画面上の各ピクセルが矩形パターン上のどのピクセルに該当するか」を順次調べて描画する形式を取る必要があります。描画する対象に対して回転元のパターンのピクセルがどの位置になるのかを計算すればよいので、回転する方向に対して逆方向に変換して座標を求めることになります。よって、座標変換式は次のようになります。

x = ( x' - ox )cos(-θ) - ( y' - oy )sin(-θ) + ox

y = ( x' - ox )sin(-θ) + ( y' - oy )cos(-θ) + oy

これをコーディングした結果を以下に示します。

/*
  double型のデータを小数点以下四捨五入してint型として返す

  double d : 対象データ
*/
int roundHalfUp( double d )
{
  if ( d > 0 )
    d += 0.5;
  else
    d -= 0.5;

  return( (int)d );
}


/*
  パターンの回転描画

  GPSet& pset : 描画用関数オブジェクト
  Coord<int> o : パターンの中心位置
  double r : 回転角度
  double scale : 拡大・縮小率
*/
void GPattern::rotPut( GPSet& pset, Coord<int> o, double r, double scale )
{
  if ( scale <= 0 ) return;
  if ( size.x == 0 || size.y == 0 ) return;
  if ( ( pset.size() ).x == 0 || ( pset.size() ).y == 0 ) return;

  Coord<double> d( (double)( size.x ) / 2, (double)( size.y ) / 2 ); // パターンの中心から両端までの距離
  Coord<int> s( roundHalfUp( (double)o.x - d.x ), roundHalfUp( (double)o.y - d.y ) ); // 描画開始位置
  if ( s.x >= ( pset.size() ).x || s.y >= ( pset.size() ).y ) return;

  Coord<int> max( s.x + size.x, s.y + size.y ); // 描画終了位置
  if ( max.x < 0 || max.y < 0 ) return;

  if ( s.x < 0 ) s.x = 0;
  if ( s.y < 0 ) s.x = 0;
  if ( max.x > ( pset.size() ).x ) max.x = ( pset.size() ).x;
  if ( max.y > ( pset.size() ).y ) max.y = ( pset.size() ).y;

  Coord<int> p;
  double cosr = cos( -r );
  double sinr = sin( -r );
  for ( ; s.y < max.y ; ++( s.y ) ) {
    Coord<int> c( s );
    for ( ; c.x < max.x ; ++( c.x ) ) {
      p.x = roundHalfUp( ( (double)( c.x - o.x ) * cosr - (double)( c.y - o.y ) * sinr ) / scale + d.x );
      p.y = roundHalfUp( ( (double)( c.x - o.x ) * sinr + (double)( c.y - o.y ) * cosr ) / scale + d.y );
      if ( p.x >= 0 && p.x < size.x && p.y >= 0 && p.y < size.y ) {
        pset.col = pattern[p.y * size.x + p.x];
        pset( c );
      }
    }
  }
}

上記プログラムで処理した場合、回転前の描画範囲のみに対してパターンが描画されることになるので、パターンの四隅が欠けた状態になります。パターン全体を描画したい場合は、それを踏まえて、あらかじめ余白部分をパターンに用意する必要があります。

回転処理のイメージ

上図は、サンプル・プログラムがどのような変換処理をしているかを表したものです。パターン全体を、パターンの中央を原点として、指定した向きとは逆の方向に回転し、そのパターンの上側から順に、一ラインずつ切り取っては描画領域に水平に貼り付けていくと、目的の図形を描画することができます。これを見ると、斜めのライン上に並んだピクセルを読み込む処理をしていることになるので、拡大・縮小ルーチン同様 Bresenhamの線分発生アルゴリズムが利用できそうです。
一ライン分を読み込んだ後は、次の読み込み対象として、すぐ下側にあるラインの両端点を求める必要があります。この端点も直線上に並んでいるので、やはり Bresenhamの線分発生アルゴリズムを利用することができ、結局、xy方向の Bresenham二重ループを使って処理をする形に変更することが可能です。

しかし、 Bresenhamの線分発生アルゴリズムを使って実際にコーディングする前に、いくつかの問題点をクリアせねばなりません。
まずはクリッピング処理です。パターンを逆回転して得られる各ラインを、画面上に水平に描画することで回転処理を実現することは前述の通りですが、ラインの両端が、回転前のパターンからはみ出る場合があるので、まずはこの部分をクリッピングする必要があります。読み込む範囲がクリッピングされるので、描画する範囲もそれに合わせてクリッピングしなければなりません。上図の中で、赤色で示した部分が実際に描画する箇所になり、抽出するパターンが両端を切り取られた形になっているため、描画範囲も左端からではなく、切り取られた分だけ右側に移動した位置からになっています。さらに、描画領域がグラフィック画面外にある場合もあるので、描画範囲が画面内にあるかをもう一度確認して、はみ出している場合はクリッピングを行います。
次が一番やっかいな問題ですが、グラフィック画面上では、水平線分を回転させた時、線分の描画に必要なピクセル数は水平線分のそれより少なくなってしまいます。例えば、原点 ( 0, 0 ) から ( 9, 9 ) に直線を引いたときの距離は、普通に計算すれば

{ ( 9 - 0 )2 + ( 9 - 0 )2 }1/2 = 9√2 ≒ 12.7

となるのに対し、グラフィック画面上に並ぶピクセルの数は 10です。x または y 座標の差が等しいとき、斜めに描画したラインと水平・垂直線分は、描画されるピクセルの数が変化しません。

斜線と水平線のピクセル数

通常、パターンを逆回転すると、パターン内の水平・垂直線分は斜線に変化します。斜線にしても元のパターンの大きさと計算上は変わらないのですが、グラフィック画面上ではピクセル数が少なくなってしまうわけです。この問題を回避するためには、x方向、y方向両側について、拡大・縮小処理をしながら描画しなければなりません。これも前回で紹介したとおり Bresenhamの線分発生アルゴリズムを利用することになり、結局、回転描画では、斜めの線分を描画するときと、拡大・縮小処理を行うときとで Bresenhamのアルゴリズムを縦方向と横方向合わせて四回行うことになります。
しかし、この拡大・縮小処理をうまく使うことで、任意の倍率で拡大・縮小を行いつつ回転処理を行うことも可能になります。

水平方向のパターンを描画するとき、その傾きや増分は毎回、同じ値となります。よって、傾きと拡大・縮小処理に対する増分はあらかじめ計算して配列に持たせることで、計算処理を軽減することができます。これは、拡大・縮小処理で x方向の増分を先に計算しておいたのと同じ考え方によります。

回転処理を行なうためのサンプル・プログラムを以下に示します。

/*
  GPattern::calcDiffAndSign : 二座標間の差分と向きを求める

  const Coord<int>& s, e : 始点と終点の座標
  Coord<int>& diff : 差分
  Coord<int>& sign : 向き
*/
void GPattern::calcDiffAndSign( const Coord<int>& s, const Coord<int>& e, Coord<int>& diff, Coord<int>& sign )
{
  diff.x = e.x - s.x;
  diff.y = e.y - s.y;

  if ( diff.x >= 0 ) {
    sign.x = 1;
  } else {
    sign.x = -1;
    diff.x *= -1;
  }

  if ( diff.y >= 0 ) {
    sign.y = 1;
  } else {
    sign.y = -1;
    diff.y *= -1;
  }
}

/*
  GPattern::calcError : 一ライン分の傾きと増分を求める(回転処理専用)

  Coord<int> lu, ru : パターンから取り込む線分の両端
  Coord<int>& diff : ラインの両端の差分
  Coord<int>& sign : ラインの傾き
  vector< Coord<int> >& eVec : 傾きと増分
*/
void GPattern::calcError( Coord<int> lu, Coord<int> ru, Coord<int>& diff, Coord<int>& sign, vector< Coord<int> >& eVec )
{
  calcDiffAndSign( lu, ru, diff, sign );

  int e = ( diff.x >= diff.y ) ? -diff.x : -diff.y;  // 誤差項
  int ed = ( diff.x >= diff.y ) ? -diff.x : -diff.y; // 増分用の誤差項

  for ( int x = 0 ; x < size.x ; ++x ) {
    if ( diff.x >= diff.y ) {
      int add = 0;
      for ( ed += 2 * diff.x ; ed >= 0 ; ed -= 2 * size.x )
        ++add;
      eVec.push_back( Coord<int>( sign.x * add, 0 ) );
      e += 2 * diff.y;
      while ( e >= 0 ) {
        e -= 2 * diff.x;
        eVec[eVec.size() - 1].y += sign.y * add;
      }
    } else {
      int add = 0;
      for ( ed += 2 * diff.y ; ed >= 0 ; ed -= 2 * size.x )
        ++add;
      eVec.push_back( Coord<int>( 0, sign.y * add ) );
      e += 2 * diff.x;
      while ( e >= 0 ) {
        e -= 2 * diff.y;
        eVec[eVec.size() - 1].x += sign.x * add;
      }
    }
  }
}

/*
  GPattern::drawLine : 一ライン分の描画処理(回転処理専用)

  Coord<int> s : 描画開始位置
  Coord<int> lu, ru : パターンから取り込む線分の両端
  const Coord<int>& diff : X方向ラインの差分
  const Coord<int>& sign : X方向ラインの向き
  const vector< Coord<int> >& eVec : 増分を持った配列
  GPSet& pset : 点描画オブジェクト
*/
void GPattern::drawLine( Coord<int> s, Coord<int> lu, Coord<int> ru, const Coord<int>& diff, const Coord<int>& sign, const vector< Coord<int> >& eVec, GPSet& pset )
{
  // 描画範囲外か
  if ( s.x >= ( pset.size() ).x ) return;

  Coord<int> clipLU( lu ), clipRU( ru ); // クリッピング後のライン両端座標
  vector< Coord<int> >::const_iterator it = eVec.begin(); // 増分読み取り位置

  // ラインをクリッピング
  GLine clip;
  if ( clip.clipping( clipLU, clipRU, size ) < 0 ) return;

  int maxX; // 描画終了位置
  if ( diff.x >= diff.y ) {
    double rate = ( diff.x != 0 ) ? (double)( size.x ) / (double)( diff.x ) : 0; // パターンに対する描画エリアの比率
    // クリッピングされていたら、描画開始位置と増分の読み込み位置を調整する
    if ( clipLU.x != lu.x ) {
      int l = roundHalfUp( (double)( abs( clipLU.x - lu.x ) ) * rate );
      s.x += l;
      it += (unsigned int)l;
    }
    // 描画終了位置を調整
    maxX = s.x + roundHalfUp( (double)( abs( clipLU.x - clipRU.x ) ) * rate );
  } else {
    double rate = ( diff.y != 0 ) ? (double)( size.x ) / (double)( diff.y ) : 0; // パターンに対する描画エリアの比率
    // クリッピングされていたら、描画開始位置と増分の読み込み位置を調整する
    if ( clipLU.y != lu.y ) {
      int l = roundHalfUp( (double)( abs( clipLU.y - lu.y ) ) * rate );
      s.x += l;
      it += (unsigned int)l;
    }
    // 描画終了位置を調整
    maxX = s.x + roundHalfUp( (double)( abs( clipLU.y - clipRU.y ) ) * rate );
  }

  // 描画終了位置と描画エリアの比較
  if ( maxX < 0 ) return;
  if ( maxX > ( pset.size() ).x ) maxX = ( pset.size() ).x;

  // 描画開始位置が描画エリア外ならば、パターン読み取り位置と増分の読み込み位置を再調整
  if ( s.x < 0 ) {
    clipLU.x += sign.x * roundHalfUp( (double)( -s.x ) * (double)( diff.x ) / (double)( size.x ) );
    clipLU.y += sign.y * roundHalfUp( (double)( -s.x ) * (double)( diff.y ) / (double)( size.x ) );
    it += (unsigned int)( -s.x );
    s.x = 0;
  }

  // 一ライン描画
  for ( ; s.x < maxX ; ++( s.x ) ) {
    if ( clipLU.x >= 0 && clipLU.y >= 0 && clipLU.x < size.x && clipLU.y < size.y ) {
      int i = clipLU.y * size.x + clipLU.x;
      pset.col = pattern[i];
      pset( s );
    }
    clipLU.x += it->x;
    clipLU.y += it->y;
    ++it;
  }
}

/*
  GPattern::rotPut : パターンの回転描画

  GPSet& pset : 描画用関数オブジェクト
  Coord<int> o : パターンの中心位置
  double r : 回転角度
  double scale : 拡大・縮小率
*/
void GPattern::rotPut( GPSet& pset, Coord<int> o, double r, double scale )
{
  if ( scale <= 0 ) return;
  if ( size.x == 0 || size.y == 0 ) return;
  if ( ( pset.size() ).x == 0 || ( pset.size() ).y == 0 ) return;

  double cosr = cos( -r );
  double sinr = sin( -r );

  Coord<double> d( (double)( size.x ) / 2, (double)( size.y ) / 2 ); // パターンの中心から両端までの距離
  Coord<int> s( roundHalfUp( (double)( o.x ) - d.x ), roundHalfUp( (double)( o.y ) - d.y ) ); // パターン描画開始位置

  // パターン上の座標を回転
  Coord<int> lu( roundHalfUp( ( ( -d.x ) * cosr - ( -d.y ) * sinr ) / scale + d.x ),
                 roundHalfUp( ( ( -d.x ) * sinr + ( -d.y ) * cosr ) / scale + d.y ) );
  Coord<int> ru( roundHalfUp( ( ( d.x ) * cosr - ( -d.y ) * sinr ) / scale + d.x ),
                 roundHalfUp( ( ( d.x ) * sinr + ( -d.y ) * cosr ) / scale + d.y ) );
  Coord<int> ld( roundHalfUp( ( ( -d.x ) * cosr - ( d.y ) * sinr ) / scale + d.x ),
                 roundHalfUp( ( ( -d.x ) * sinr + ( d.y ) * cosr ) / scale + d.y ) );

  // ラインの差分と向き、増分を算出
  Coord<int> diffX, signX, diffY, signY; // X,Y方向のラインの差分と向き
  vector< Coord<int> > eVec; // X方向のラインの増分
  calcError( lu, ru, diffX, signX, eVec );
  calcDiffAndSign( lu, ld, diffY, signY );

  // Y方向の誤差項と増分を計算
  int e = ( diffY.x >= diffY.y ) ? -diffY.x : -diffY.y;  // 誤差項
  int ed = ( diffY.x >= diffY.y ) ? -diffY.x : -diffY.y; // 増分

  // 下方向のクリッピング
  int maxY = s.y + size.y; // パターン描画終了位置
  if ( maxY < 0 ) return;
  if ( maxY > ( pset.size() ).y ) maxY = ( pset.size() ).y;

  // 上方向のクリッピング
  if ( s.y < 0 ) {
    lu.x += signY.x * roundHalfUp( (double)( -s.y ) * (double)( diffY.x ) / (double)( size.y ) );
    lu.y += signY.y * roundHalfUp( (double)( -s.y ) * (double)( diffY.y ) / (double)( size.y ) );
    ru.x += signY.x * roundHalfUp( (double)( -s.y ) * (double)( diffY.x ) / (double)( size.y ) );
    ru.y += signY.y * roundHalfUp( (double)( -s.y ) * (double)( diffY.y ) / (double)( size.y ) );
    s.y = 0;
  }

  // 描画ラインの両端を変化させながら一ラインずつ描画
  for ( ; s.y < maxY ; ++( s.y ) ) {
    // 一ライン描画
    drawLine( s, lu, ru, diffX, signX, eVec, pset );

    if ( diffY.x >= diffY.y ) {
      int add = 0;
      for ( ed += 2 * diffY.x ; ed >= 0 ; ed -= 2 * size.y )
        ++add;
      lu.x += signY.x * add;
      ru.x += signY.x * add;
      e += 2 * diffY.y;
      while ( e >= 0 ) {
        e -= 2 * diffY.x;
        lu.y += signY.y * add;
        ru.y += signY.y * add;
      }
    } else {
      int add = 0;
      for ( ed += 2 * diffY.y ; ed >= 0 ; ed -= 2 * size.y )
        ++add;
      lu.y += signY.y * add;
      ru.y += signY.y * add;
      e += 2 * diffY.x;
      while ( e >= 0 ) {
        e -= 2 * diffY.y;
        lu.x += signY.x * add;
        ru.x += signY.x * add;
      }
    }
  }
}

メイン・ルーチンは rotPut になります。まず最初に、描画開始位置とパターンを逆回転したときの座標を求めます。逆回転後の座標は、左上(lu)・右上(ru)・左下(ld)のみを求め、lu - ru が x方向、lu - ld が y方向の線分を表します。なお、描画開始位置は、中心座標からパターンの大きさの半分だけ左上方向へ移動したところになります。また、パターンを逆回転したときの座標は、回転前のパターンの左上隅座標が原点となっています。
次に、サブ・ルーチン calcError を使って、x方向のラインに対する傾き及び拡大・縮小処理用の増分をあらかじめ求め、配列 eVecに格納します。傾きに対する移動量と拡大・縮小処理に対する増分は一つの配列に格納することができるので、それぞれ分けてはいないことに注意してください。符号が向きを、絶対値が増分をそれぞれ表す形になります。
今度は、y方向のラインに対して、Bresenhamの線分発生アルゴリズムのため誤差項 e(傾き用) と ed(拡大・縮小用) を初期化した後、クリッピング処理を行ないます。線分をクリッピング処理することになるので、ここでは、ライン描画ルーチンで利用したクリッピング処理用のプログラムをそのまま利用しています。クリッピング後、Bresenhamの線分発生アルゴリズムを使って x方向のラインの両端を求めながら、一ラインずつ描画処理を行ないます。

x方向のラインを描画する処理は、drawLine で行ないます。描画のために使用するパターン上の線分に対し、最初にクリッピング処理を行ないます。この時、描画範囲と増分の読み込み範囲も同時に調整する必要があります。また、最後に、描画範囲がグラフィック画面からはみ出した場合、読み取り位置を再調整していることに注意してください。クリッピング処理は、パターンからの読み取り範囲と描画範囲の二つに対して行なっていることになります。クリッピングが完了すれば、増分はすでに計算済みなので、パターンのデータを元に描画しながら、配列内の増分を座標に加算する処理を繰り返すだけになります。

最初に作成したものに比べると、かなり大掛かりなプログラムになりました。前回の拡大・縮小ルーチンと比べても、コーディング量は増えています。果たして、それに見合うだけの効果があったのかを検証してみたいと思います。まずは、処理速度を調べてみます。処理時間の計測には、以下のようなテストルーチンを利用しました。

// テストルーチン(1)
// g : 点描画関数オブジェクト
// width,height : 描画領域のサイズ

for ( double d = 0 ; d <= 2.01 * M_PI ; d += 0.1 ) {
  pat.rotPut( g, Coord<int>( width * d / ( 2 * M_PI ), height * d / ( 2 * M_PI ) ), d, 1.0 );
}

中心座標を画面の左上から右下に移動させ、0.1(rad) 刻みで一回転しながら描画する処理を行ないます。クリッピング処理の効果を加味したルーチンになります。

テストルーチン(1)
Bresenham使用(sec.)Bresenham未使用(sec.)
12.404.70
22.364.62
32.414.62
平均2.39 (1.00)4.65 (1.94)

上表で、平均値の右に記された()内の数値は、Bresenhamを使用した場合の処理時間を 1 としたときの比率を表しています。Bresenhamを利用すると、処理速度は約二倍程度にまで高速化できることが上の表から分かります。

// テストルーチン(2)

for ( double d = 0 ; d <= 2.01 * M_PI ; d += 0.1 ) {
  pat.rotPut( g, Coord<int>( width * d / ( 2 * M_PI ), height * d / ( 2 * M_PI ) ), d, d + 1.0 );
}

テストルーチン(2)は、テストルーチン(1)に拡大処理を付加したものです。

テストルーチン(2)
Bresenham使用(sec.)Bresenham未使用(sec.)
12.114.27
12.104.30
12.104.28
平均2.10 (1.00)4.28 (2.04)

テストルーチン(1)と比べると、ほんの少しだけ処理時間が短くなっています。点描画回数は変わらないはずなのですが、いろいろ試してみたところ、拡大倍率を大きくするほどその傾向は大きくなるようです。ちなみに、縮小した場合は描画回数が減少するので、拡大時よりも顕著に処理時間が短くなります。

// テストルーチン(3)

for ( double d = 0 ; d <= 2.01 * M_PI ; d += 0.1 ) {
  pat.rotPut( g, Coord<int>( width / 2, height / 2 ), d, 1.0 );
}

テストルーチン(3)は、中心座標を画面中央固定にしたもので、クリッピング範囲が少なく(点描画回数が多く)なります。

テストルーチン(3)
Bresenham使用(sec.)Bresenham未使用(sec.)
13.516.51
23.536.52
33.506.55
平均3.51 (1.00)6.53 (1.86)

こちらは予想通り、前のテストより処理時間が長くなりました。全体を通してみると、クリッピングの有無に関係なく、Bresenhamを利用した方が処理時間は半減します。プログラムの長さに拘らず、Bresenhamアルゴリズムによってかなりの効果があったことになります。
しかし、Bresenhamアルゴリズムには欠点があって、斜線上のピクセルを水平線分に写す処理をしている上に、斜線の両端も y方向の線分を元に決定しているため、座標を毎回求める場合に比べて誤差が大きくなります。特に、拡大処理を伴うときは、同じ水平線分を何度も使って処理する場合が多くなることから、エッジ部分などで歪みが目立つようになります。

Bresenham未使用Bresenham使用
Bresenham未使用 Bresenham使用

上の図は、回転角度 110度、拡大率二倍で格子模様の画像を処理した結果を示しています。右側の、Bresenham アルゴリズムを使用した方は、歪みがかなり大きくなっているのがハッキリと分かります。これを見る限り、画質を優先したい場合は、座標を毎回計算する方法で処理する方式を選択した方がいいようです。逆に、速度を優先したいときは、Bresenham版の処理が有効です。例えば、グラフィック・エディタで回転処理を行なうとき、回転角度を決める際、回転後の画像をリアルタイムで表示するときは速度を優先して処理を行い、条件が決まったら画質優先で処理を行うなど、場合に応じて使い分けると便利ではないかと思います。

◆◇◆更新履歴◆◇◆

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