グラフィック・パターンの扱い (4)パターンの自由変形

ここでは、パターンの自由変形について取り上げます。矩形パターンを任意の形に変形することができれば、それを使って前に紹介したパターンの拡大・縮小・回転などにも応用させることができます。

ある矩形パターンの各頂点を任意の座標に移動させたとき、矩形パターン内の任意のピクセルは、変形後の四角形の向かい合った辺どうしを同じ比率で分割した点を結んでできる二本の線分の交点上に移されます。下図を使って説明すると、矩形パターン ABCD の内部を通る、X, Y 方向それぞれの辺に平行な線分 ef, gh の交点 P は、自由変形によって

しかし、わざわざ点単位で交点を求めてプロットしていたのでは効率が悪く、前の拡大・縮小ルーチン同様に、点と点の間に隙間ができる場合も発生するので、点単位ではなく線分単位でパターンを貼りつけていく方法を考えます。上図を使って簡単に説明すると、パターン上のライン ef を、変形後の図形上にある線分 e'f' に合うように、適当に形を変形して貼りつけることで実現させます。
しかし、図形を隙間なく描画するためには、パターン左右の辺に対応する変換後図形の辺 (上図の辺 A'B', C'D' のこと) のうち長い方のピクセル数だけ線分単位の貼り付けを行う必要があります。また、この方法では短い側の辺近くで線分どうしが重なるため、重複して描画されるピクセルも発生しますが、ここでは無視することにします。

処理の流れとしては、おおまかに次の三つのステップに分かれます。

1) 描画先線分の決定

2) 描画パターンの決定

3) パターンの貼りつけ

上記アルゴリズムを実際にコーディングする上で、いくつか問題が発生します。

まず、上記アルゴリズムで線分を描画して図形を書いた場合、描画先線分の階段状になった部分に隙間が発生する場合が生じます。これを回避するために、線分を、「八連結」ではなく「四連結」で描画することで隙間を埋めるようにします。線分を描画するとき、次のピクセルの候補を周囲 8ピクセルとした場合は「八連結」になります。この時、ピクセルは斜めに並ぶことが許されます。それに対し、上下左右の 4ピクセルを候補とする場合を「四連結」といい、ピクセルは上下左右に並べられ、斜めに進むことができなくなります。

次に、図形描画で必ず必要となるクリッピング処理ですが、文献では、線分のクリッピングを使用した場合、クリッピングによって求めた端点の座標値にどうしても小数点以下の誤差が生じ、それがもとで図形に隙間が生じる可能性があることが指摘されています。ここでは文献に倣い、ピクセルごとに描画前でチェックをするようにしました。

結局のところ、図形の自由変形という一見複雑そうな処理も、今までのアルゴリズムを応用することにより割と単純な処理で実現することができます。また、自由変形ルーチンがあれば、先に紹介してきた様々なプットルーチンの代わりにも利用することが可能となります。
但し、欠点もあります。実行速度は、さすがに専用のルーチンにはかないません。左右・上下反転などの代わりに使用するのはあまり意味はないかもしれませんが、それでも回転ルーチンの代わりなんかには結構使えると思います。
回転ルーチンへの応用は簡単で、回転後の図形の各頂点を計算して求めたら、それをパラメータとして自由変形ルーチンに渡すだけです。

パターンの自由変形を行なうためのサンプル・プログラムを以下に示します。

/* Bresenhamアルゴリズム用パラメータ */
struct bresenham_param {
  int error; // 誤差項
  int add;   // 増分
  int rev;   // 補正値
};

/* 自由変形用パラメータ */
struct transput_param {
  bresenham_param grad;   // 傾きに対するパラメータ
  bresenham_param length; // 拡大・縮小処理に対するパラメータ
  Coord<int> add;         // 座標の増分
  Coord<int> rev;         // 座標の補正分
};

/*
  GPattern::calcBresenhamParam : Bresenhamアルゴリズムのパラメータを計算する(自由変形処理専用)

  const Coord<int>& s,e : 線分の両端の座標
  transput_param& param : 計算したパラメータ
  int patSize : パターンのサイズ(XまたはY成分)

  戻り値 : 両端の差分のうち、X/Y成分の大きい側
*/
int GPattern::calcBresenhamParam( const Coord<int>& s, const Coord<int>& e, transput_param& param, int patSize )
{
  Coord<int> diff; // 差分
  Coord<int> sign; // 向き
  GLine line;

  line.calcDiffAndSign( s, e, diff, sign );

  // 傾き用パラメータ
  param.grad.error = - max( diff.x, diff.y );
  param.grad.add = 2 * min( diff.x, diff.y );
  param.grad.rev = 2 * max( diff.x, diff.y );

  // 拡大・縮小用パラメータ
  param.length.error = - max( diff.x, diff.y );
  param.length.add = 2 * patSize;
  param.length.rev = 2 * max( diff.x, diff.y );

  // 増分と補正値
  param.add.x = ( diff.x > diff.y ) ? sign.x : 0;
  param.rev.x = ( diff.x > diff.y ) ? 0 : sign.x;
  param.add.y = ( diff.x > diff.y ) ? 0 : sign.y;
  param.rev.y = ( diff.x > diff.y ) ? sign.y : 0;

  return( max( diff.x, diff.y ) ); /* 戻り値としてdiff.x,diff.yの絶対値のうち大きい方を返す */
}


/*
  GPattern::calcNextPoint : 次に描画するポイントの座標を計算する(自由変形処理専用)

  Coord<int>& c : 計算した座標値
  transput_param& param : 計算用パラメータ
  GPSet* pset : 点描画用関数オブジェクト
*/
void GPattern::calcNextPoint( Coord<int>& c, transput_param& param, GPSet* pset )
{
  c.x += param.add.x;
  c.y += param.add.y;
  param.grad.error += param.grad.add;
  if ( param.grad.error > 0 ) {
    if ( pset != 0 ) {
      if ( c.x >= 0 && c.y >= 0 && c.x < ( pset->size() ).x && c.y < ( pset->size() ).y )
        (*pset)( c );
    }
    c.x += param.rev.x;
    c.y += param.rev.y;
    param.grad.error -= param.grad.rev;
  }
}

/*
  GPattern::calcNextPattern : 次に色コードを抽出するパターン・アドレスを計算する(自由変形処理専用)

  transput_param& param : 計算用パラメータ
  vector<RGB>::const_iterator& it : 求めるパターン・アドレス
  int add : パターンの増分
*/
void GPattern::calcNextPattern( transput_param& param, vector<RGB>::const_iterator& it, int add )
{
  param.length.error += param.length.add;
  if ( param.length.rev > 0 ) { // revが0の場合、ここで無限ループしてしまうため
    while ( param.length.error > 0 ) {
      it += add;
      param.length.error -= param.length.rev;
    }
  }
}

/*
  GPattern::drawLine : 線分描画ルーチン(自由変形処理専用)

  Coord<int> c : 描画開始位置
  vector<RGB>::const_iterator it : パターンの読み取り開始位置
  int length : 描画する長さ
  transput_param& line : 計算用パラメータ
  GPSet& pset : 点描画用関数オブジェクト
*/
void GPattern::drawLine( Coord<int> c, vector<RGB>::const_iterator it, int length, transput_param& line, GPSet& pset )
{
  for ( int i = 0 ; i <= length ; i++ ) {
    if ( c.x >= 0 && c.y >= 0 && c.x < ( pset.size() ).x && c.y < ( pset.size() ).y ) {
      pset.col = *it;
      pset( c );
    }
    calcNextPoint( c, line, &pset );
    calcNextPattern( line, it, 1 );
  }
}

/*
  GPattern::transPut : パターンの自由変形

  GPSet& pset : 描画用関数オブジェクト
  Coord<int> lu,ru,rd,ld : 変形後の各頂点(左上・右上・右下・左下)
*/
void GPattern::transPut( GPSet& pset, Coord<int> lu, Coord<int> ru, Coord<int> rd, Coord<int> ld )
{
  transput_param left,right; // 左右の辺用パラメータ
  transput_param line;       // 水平方向線分描画時のパラメータ
  bresenham_param lr_length; // Y方向の増分計算用パラメータ

  vector<RGB>::const_iterator it = pattern.begin(); // パターン読み取り位置

  Coord<int> patSize = size(); // 矩形の大きさ
  patSize.x -= 1;
  patSize.y -= 1;

  int leftLen,rightLen; // 左右の辺の長さ(X,Y成分のうち大きい方)

  // 左右両辺の誤差項を計算
  leftLen = calcBresenhamParam( lu, ld, left, patSize.y );
  rightLen = calcBresenhamParam( ru, rd, right, patSize.y );

  // Y方向の増分計算用パラメータ
  lr_length.error = - max( leftLen, rightLen );
  lr_length.add = min( left.length.rev, right.length.rev );
  lr_length.rev = max( left.length.rev, right.length.rev );

  for ( int i = 0 ; i <= max( leftLen, rightLen ) ; i++ ) {
    // 描画する線分の誤差項を計算
    int lineLen = calcBresenhamParam( lu, ru, line, patSize.x ); // 描画する線分の長さ
    drawLine( lu, it, lineLen, line, pset );

    if ( leftLen > rightLen ) {
      calcNextPoint( lu, left, 0 );
      calcNextPattern( left, it, patSize.x + 1 );
      lr_length.error += lr_length.add;
      if ( lr_length.error > 0 ) {
        calcNextPoint( ru, right, 0 );
        lr_length.error -= lr_length.rev;
      }
    } else {
      calcNextPoint( ru, right, 0 );
      calcNextPattern( right, it, patSize.x + 1 );
      lr_length.error += lr_length.add;
      if ( lr_length.error > 0 ) {
        calcNextPoint( lu, left, 0 );
        lr_length.error -= lr_length.rev;
      }
    }
  }
}

メイン・ルーチンは transPut になります。最初にパターン左右の辺を自由変形したときの線分から、傾きと拡大・縮小率に対する Bresenhamアルゴリズム用のパラメータを求めます。このパラメータは、calcBresenhamParam で計算し、その結果は transput_param構造体に保持します。transput_param構造体は、さらに傾きと拡大・縮小率それぞれに対して bresenham_param構造体を含み、その中に誤差項(error)・増分(add)・補正値(rev)が格納されます。また、描画位置は線分に沿って移動するので、その移動方向を決めるパラメータとして増分(add)と補正値(rev)を別に用意しています。描画位置は、線分の傾きによって場合分けが必要でしたが、それを不要にするために、あらかじめパラメータとして変化量を計算しておくわけです。この方法は、通常の線分描画でも利用することができます。
calcBresenhamParamは、線分の長さ(X,Y成分のうち長い方)を戻り値として返します。回転処理の章で説明したように、グラフィック画面上では、斜線と水平・垂直線分の間にピクセル数の差がないので、水平・垂直成分のうち長い方が、線分描画に必要なピクセル数ということになります。左右の辺から、描画すべき線分の両端を決定するために、左右の辺のうち長い側を基準に、短い側の進む速さを求める必要があります。この処理を Bresenhamアルゴリズムで行なうため、bresenham_param構造体 lr_lengthに必要なパラメータを登録します。
これで前処理は完了したので、パターンの最上位にある線分から順番に、drawLineを使って線分を描画しては、次の両端点を求める処理を繰り返します。calcNextPoint は、次に描画する線分の両端を求めるため、calcNextPatternは次に読み込むパターンの Y座標をそれぞれ求めるためのサブ・ルーチンです。描画領域において、左辺の方が長ければ、左辺は毎回次の点へ移動し、右辺は Bresenhamアルゴリズムを使って移動すべきかどうかを判定します。右辺の方が長ければ、その逆のことを行ないます。パターンの移動量は、描画領域の大きさの比率に従って、やはり Bresenhamアルゴリズムを使って求めています。

線分を描画する前に、対象の線分に対して、calcBresenhamParamを使って Bresenhamアルゴリズム用のパラメータを求めています。線分描画は drawLineが行い、ここでも Bresenhamアルゴリズムを使って、描画する位置と読み込むパターンの位置を求めながら点を描画するためです。

calcNextPattern の中で、誤差項が正になった場合の補正計算前に、補正値がゼロより大きいかどうかの判断をしています。線分の両端が重なった場合、Bresenhamアルゴリズム用のパラメータにある増分と誤差項はゼロになります。この時は補正計算をスキップしないと無限ループに陥ってしまいます。このようなことが発生する他の条件としては、左辺または右辺の長さがゼロ(上下の座標値が等しい)場合がありますが、いずれもループ回数は一回のみになるので補正計算をスキップしても問題はありません。
また、calcNextPointでは点描画用関数オブジェクトを渡して、誤差項を補正するとき同時に点描画を行なっていますが、これは、四連結による線分描画を実現するための処理です。しかし、実際に線分を描画するとき以外でもこのルーチンを利用しているので、少々強引なやり方ですが、点描画オブジェクトへのポインタが NULL の場合は点描画処理をしないようにしています。

少々複雑に見えますが、全て Bresenhamアルゴリズムを組み合わせて実現していますので、それほど難しいプログラムではないと思います。前回の回転処理と比較しても、こちらの方がわかりやすいのではないでしょうか。しかも、このルーチンを使って回転処理を行なった場合、前回の処理のように、パターンの角が表示されないような現象は発生しなくなります。以下に、自由変形ルーチンを利用したバージョンの回転処理ルーチンを示しておきます。

/*
  GPattern::rotPut : パターンの自由変形を利用した回転処理

  GPSet& pset : 描画用関数オブジェクト
  Coord<int> lu,ru,rd,ld : 変形後の各頂点(左上・右上・右下・左下)
*/
void GPattern::rotPut( GPSet& pset, Coord<int> o, double r, double scale )
{
  double cosr = cos( r );
  double sinr = sin( r );

  Coord<double> d( (double)( size.x ) / 2, (double)( size.y ) / 2 ); // パターンの中心から両端までの距離

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

  transPut( pset, lu, ru, rd, ld );
}

前回作成した回転処理専用ルーチンと、パターンの自由変形を利用した回転処理とのパフォーマンスを比較してみます。利用するテストルーチンも前回と同じものを使用します。

// g : 点描画関数オブジェクト
// width,height : 描画領域のサイズ

// テストルーチン(1)
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 );
}

// テストルーチン(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 );
}

// テストルーチン(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 );
}

テストルーチン(1) は、中心座標を画面の左上から右下に移動させ、0.1(rad) 刻みで一回転しながら描画する処理で、クリッピング処理の効果を加味したルーチンになります。テストルーチン(2) はテストルーチン(1) に拡大処理を付加したもので、クリッピングエリアを無視した場合、描画範囲は極端に広くなります。テストルーチン(3) は中心座標を画面中央固定にしたもので、クリッピング範囲が少なく(点描画回数が多く)なります。

テストルーチン(2) を除けば、Bresenham使用版と Bresenham未使用版の中間の性能であるといえます。しかし、テストルーチン(2) での性能の悪さが目立ちます。クリッピングを行なわずに処理をしているため、描画対象が広がるほど極端に処理時間が長くなってしまうことが原因です。描画結果に隙間が生じるのを承知の上でクリッピングを行うか、速度を犠牲にして今の状態にするか、利用法によっても選択は変わると思いますが、一回の処理に掛かる時間を考えれば現状でも我慢できる速さと考えられるので、リアルタイム性が要求されなければ現状のままでもいいのではないかと判断します。