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

(2)パターンの拡大・縮小描画

矩形 ( x0, y0 ) - ( x1, y1 ) を ( x0', y0' ) - ( x1', y1' ) に拡大・縮小した時、変換前の矩形のピクセル ( x, y ) は

x' = { ( x1' - x0' ) / ( x1 - x0 ) } * ( x - x0 ) + x0'

y' = { ( y1' - y0' ) / ( y1 - y0 ) } * ( y - y0 ) + y0'

に写されます。

これを矩形パターン描画ルーチンに適用した場合、取り込んだ矩形の大きさ ( dx, dy ) = ( x1 - x0 + 1, y1 - y0 + 1 )となるので、上式は

x' = { ( x1' - x0' ) / ( dx - 1 ) } * x + x0'

y' = { ( y1' - y0' ) / ( dy - 1 ) } * y + y0'

( x0, y0 はプットルーチンでは必要ないので、無視しても可)

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

/*
  ( x0, y0 ) - ( x1, y1 ) : 拡大縮小先の矩形範囲
  ( dx, dy ) : 取り込んだパターンの大きさ
*/
:
for ( py = 0 ; py < dy ; py++ ) {
  ry = ( y1 - y0 ) * py / ( dy - 1 ) + y0;
  for ( px = 0 ; px < dx ; px++ ) {
    rx = ( x1 - x0 ) * px / ( dx - 1 ) + x0;
    pset( rx, ry, *pat++ );
  }
}
:

しかし、このやり方で実際に図形の拡大縮小を行うと、縮小時はうまく行ったように見えますが、拡大した場合はピクセルどうしに隙間ができてしまいます。
これは、「矩形パターンの各ピクセルが画面上のどこに写るか」を順次調べているのが原因であり、この場合だと、問題ないように見えた縮小時には、矩形パターンのピクセルを同じ場所に何度も描画することになってしまいます。これを回避するには、「画面上の各ピクセルが矩形パターン上のどのピクセルに該当するか」を順次調べればよいので、先の式の逆変換によって得られる式

x = { ( dx - 1 ) / ( x1' - x0' ) } * ( x' - x0' )

y = { ( dy - 1 ) / ( y1' - y0' ) } * ( y' - y0' )

を使い、描画対象の座標に対応する矩形パターンの座標を求めるようにして処理します。

以上を考慮してコーディングした場合、上で示したループの部分は以下のようになります。

/*
  ( x0, y0 ) - ( x1, y1 ) : 拡大縮小先の矩形範囲
  ( dx, dy ) : 取り込んだパターンの大きさ
*/
:
for ( gy = y0 ; gy <= y1 ; gy++ ) {
  ry = ( dy - 1 ) * ( gy - y0 ) / ( y1 - y0 );
  for ( gx = x0 ; gx <= x1 ; gx++ ) {
    rx = ( dx - 1 ) * ( gx - x0 ) / ( x1 - x0 );
    pset( gx, gy, pat[rx + ry * dx]);
  }
}
:

ところで、上記の式は、前に紹介した線分を表す式によく似ていることに気付いた方もいらっしゃると思います。ライン・ルーチンの章で紹介した通り、拡大・縮小ルーチンにはBresenhamの線分発生アルゴリズムを利用することができます。

上記の内容を見ると、X方向のループ処理で rxを毎回計算しています。しかし、gxが 1増加するごとに rxは ( dx - 1 ) / ( x1 - x0 ) ずつ増加していくことから、次のようなアルゴリズムに変えることができます。

  1. x = x0で初期化する。また、誤差項 Eを 0に初期化する。
  2. 点 ( x, y ) を *patでプロットする。
  3. x に 1を加える。
  4. E に ( dx - 1 ) / ( x1 - x0 ) を加える。
  5. E が 1/2 以上になった場合、*pat のアドレスを一つ進めて Eから 1を引く。この操作を Eが 1/2未満になるまで繰り返す。
  6. x > x1になるまで 2 〜 5 を繰り返す。

これは、Y方向のループ処理でも有効ですから、結局はBresenhamの二重ループ処理を行うことになります。

上に示したアルゴリズムではまだ整数化されていませんから、ラインルーチン同様に整数化して、Y方向のループ処理を加えると、全体のアルゴリズムは次のように示すことができます。

  1. y = y0で初期化する。また、誤差項 Ey = -( dy - 1 ) に初期化する。
  2. x = x0で初期化する。また、誤差項 Ex = -( dx - 1 ) に初期化する。
  3. 点 ( x, y ) を *patでプロットする。
  4. xに 1を加える。
  5. Ex に 2( dx - 1 ) を加える。
  6. Exが 0以上になった場合、*patのアドレスを一つ進めて Exから 2( x1 - x0 )を引く。この操作を Exが 0未満になるまで繰り返す。
  7. x > x1になるまで 3 〜 6 を繰り返す。
  8. yに 1を加える。
  9. *patのアドレスを dxだけ戻す。
  10. Eyに 2( dy - 1 )を加える。
  11. Eyが 0以上になった場合、*patのアドレスを dxだけ進めて Eyから 2( y1 - y0 )を引く。この操作を Eyが 0未満になるまで繰り返す。
  12. y > y1になるまで 2 〜 11 を繰り返す。

* 9で *patのアドレスを dxだけ戻しているのは、6の操作ですでに一ライン分だけアドレスが進んでいるからです。

この処理の中で、X方向の描画部分 (2〜7) に着目したとき、Bresenhamのアルゴリズムによって得られる増分は毎回同じ結果になるので、繰り返し計算処理を行なうのは全くの無駄になります。よってこの部分をループの外に出してしまえばいくらか処理速度をアップさせることができます。

描画部分のアルゴリズムが固まったところで次に考えなければならないのはクリッピング処理です。まず第一に、描画範囲がクリッピングエリアの境界と交差していた場合、描画範囲におけるクリッピングエリア領域の外側がターンのどの領域に対応しているかを調べる必要があります。これは単に大きさの比率から計算してやればいいので、描画領域におけるクリッピングエリア外の大きさを ( gx, gy ) とした時、パターンのクリッピングエリア外の大きさ ( px, py ) は

px = gx * ( ( dx - 1 ) / ( x1 - x0 ) )

py = gy * ( ( dy - 1 ) / ( y1 - y0 ) )

で計算できます。

クリッピングエリア外になるパターンの上側の領域は、パターンの読み込み開始位置がクリップエリア内になるように補正すれば対応できます。また、下側は単に無視するだけになります。パターンの左右に対しては、最初に、クリップエリア外にあるピクセル分だけ読み込み開始位置をずらしておき、1ラインの描画が完了した後で、最初に読み込んだ位置までいったん戻ってから、パターンの幅分だけ加えることで次のラインへ移動します。クリップエリア外にあるパターンの幅を保持しておいて、1ライン描画した後でそれを加えるやり方もありますが、誤差によって位置がずれる可能性があることを考慮して、先のやり方を行ないます。

実際のフローは以下のようになります。

  1. 描画領域がクリッピングエリアからはみ出しているかを上下左右の境界について調べ、エリア外の大きさを変数に取り込む (上側gu, 左側gl, 右側gr, 下側gd) とともに、拡大・縮小先矩形の座標 ( x0, y0 ) - ( x1, y1 ) を変更する。
  2. パターンのクリッピングエリア外の大きさを、gu, gl, gr, gd から計算する (上側pu, 左側pl, 右側pr, 下側pd)。
  3. パターンのアドレスを ( gu * dx + gl )だけ進める (この時、パターンのアドレスはクリッピングエリア内にあるパターン矩形の左上頂点を示す)。
  4. クリッピングエリア領域 ( x0から x1まで ) の範囲で x方向に一ライン分描画したあと、パターンのアドレスをライン先頭に戻す。
  5. 4の操作を y > y1になるまで繰り返す。

1ライン描画後にライン先頭へアドレスを戻す方法としては、描画前にアドレスを保持しておくやり方と、サンプル・プログラムのように、x方向の増分を計算するとき先に戻る分をカウントしておくやり方が考えられます。

パターンの拡大・縮小描画を行うサンプル・プログラムを以下に示します。

/*
  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>& s, e : パターンの描画開始・終了位置
  iterator_base& x, y : 描画方向
*/
void GPattern::resizePut( GPSet& pset, Coord<int>& s, Coord<int>& e, iterator_base& x, iterator_base& y )
{
  // 描画オブジェクトの大きさを取得
  Coord<int> dSize = pset.size();

  // 左上・右下の大小関係が逆の場合は入れ替える
  if ( s.x > e.x ) swap( s.x, e.x );
  if ( s.y > e.y ) swap( s.y, e.y );

  // 描画範囲内か
  if ( s.x >= dSize.x || s.y >= dSize.y ) return;
  if ( e.x < 0 || e.y < 0 ) return;

  // パターンの読み込み開始位置
  vector<RGB>::const_iterator it = pattern.begin();

  // 拡大・縮小後の画像の大きさ
  Coord<int> gSize( e.x - s.x, e.y - s.y );

  /*
    クリッピング処理
    s.x=e.x, s.y=e.y のときは、これらの処理は必ず行なわれないので、ゼロ除算チェックは不要
  */
  if ( s.y < 0 ) {
    it += roundHalfUp( (double)( -s.y ) * (double)( size.y - 1 ) / ( (double)( gSize.y ) ) ) * size.x;
    s.y = 0;
  }
  if ( s.x < 0 ) {
    it += roundHalfUp( (double)( -s.x ) * (double)( size.x - 1 ) / ( (double)( gSize.x ) ) );
    s.x = 0;
  }
  if ( e.x >= dSize.x ) e.x = dSize.x - 1;
  if ( e.y >= dSize.y ) e.y = dSize.y - 1;

  // 先にX方向でのループの増加分を計算
  int error = -( size.x - 1 );      // 誤差 E
  vector<int> gradX( gSize.x + 1 ); // X方向の増分
  int xLen = 0;                     // X方向の描画ピクセル数
  for ( x.set( s.x, e.x ) ; x.valid() ; x.next() ) {
    error += 2 * ( size.x - 1 );
    if ( size.x <= 1 || gSize.x <= 0 ) continue;
    while ( error >= 0 ) {
      ( gradX[x.value() - s.x] )++;
      xLen++;
      error -= 2 * gSize.x;
    }
  }

  // 描画処理
  error = -( size.y - 1 ); // 誤差 E
  for ( y.set( s.y, e.y ) ; y.valid() ; y.next() ) {
    for ( x.set( s.x, e.x ) ; x.valid() ; x.next() ) {
      pset.col = *it;
      pset( Coord<int>( x.value(), y.value() ) );
      it += gradX[x.value() - s.x];
    }
    it -= xLen;
    if ( size.y <= 1 || gSize.y <= 0 ) continue;
    error += 2 * ( size.y - 1 );
    while ( error >= 0 ) {
      it += size.x;
      error -= 2 * gSize.y;
    }
  }
}

ライン・ルーチンで実験したように、Bresenhamの線分発生アルゴリズムを使って整数演算にしたことで本当に効果があるかを調べてみたいと思います。描画処理部分を、次のように変更した別バージョンを作成して、それぞれについて描画時間を計測して比較してみます。

:
// 描画処理(座標を直接計算)
int dy = 0; // 拡大・縮小先のy座標
for ( y.set( s.y, e.y ) ; y.valid() ; y.next() ) {
  int dx = 0; // 拡大・縮小先のx座標
  double py = (double)( dy ) * (double)( size.y - 1 ) / (double)( gSize.y ); // パターン上ののy座標
  for ( x.set( s.x, e.x ) ; x.valid() ; x.next() ) {
    double px = (double)( dx ) * (double)( size.x - 1 ) / (double)( gSize.x ); // パターン上ののx座標
    pset.col = it[roundHalfUp( py ) * size.x + roundHalfUp( px )];
    pset( Coord<int>( x.value(), y.value() ) );
    ++dx;
  }
  ++dy;
}

Bresenhamの線分発生アルゴリズムを使った場合と比較すると、かなり短いプログラムになっています。x方向でのループ増加分を計算するところも完全に除去できるので、半分程度の行数になります。増分を加算していくのではなく、毎回パターン上の座標を計算して求めています。
実際に計測した結果を以下に示します。1024 x 768のパターンを、大きさゼロから始めて二倍になるまで、画面の中央から広がるように描画します。描画領域の大きさも 1024 x 768なので、パターンより拡大して描画されると、クリッピングが発生します。拡大率は 0.01刻みで大きくなるようにしています。

// テスト用ループ
for ( double d = 0 ; d <= 2 ; d += 0.01 ) {
  pat.resizePut( g, Coord<int>( ( 1.0 - d ) * 512, ( 1.0 - d ) * 384 ), Coord<int>( ( 1.0 + d ) * 512, ( 1.0 + d ) * 384 ) );
}

計測結果(単位は sec.)

テスト・ルーチン一回目二回目三回目平均値
Bresenham版7.978.008.118.03
別バージョン11.5111.5411.6111.55

今回は、Bresenhamの線分発生アルゴリズムを使った方が処理が早いという結果が得られました。こうして見ると、Bresenhamアルゴリズムもまだまだ有用であると思っていいような気がします。ちなみに、増分を浮動小数点演算で求める方法で時間を計測した結果、平均で 9.72 sec.になりました。直接座標を計算する場合に比べれば早くなりますが、それでも整数演算を使った方が早いという結果が今回は得られました。

:
// 描画処理(増分を浮動小数点数で計算)
double dx = (double)( size.x - 1 ) / (double)( gSize.x ); // xの増分
double dy = (double)( size.y - 1 ) / (double)( gSize.y ); // yの増分
double py = 0; // パターン上のy座標
for ( y.set( s.y, e.y ) ; y.valid() ; y.next() ) {
  double px = 0; // パターン上のx座標
  for ( x.set( s.x, e.x ) ; x.valid() ; x.next() ) {
    pset.col = it[roundHalfUp( py ) * size.x + roundHalfUp( px )];
    pset( Coord<int>( x.value(), y.value() ) );
    px += dx;
  }
  py += dy;
}

◆◇◆更新履歴◆◇◆

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