矩形 ( 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 ) ずつ増加していくことから、次のようなアルゴリズムに変えることができます。
これは、Y方向のループ処理でも有効ですから、結局はBresenhamの二重ループ処理を行うことになります。
上に示したアルゴリズムではまだ整数化されていませんから、ラインルーチン同様に整数化して、Y方向のループ処理を加えると、全体のアルゴリズムは次のように示すことができます。
* 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ライン描画後にライン先頭へアドレスを戻す方法としては、描画前にアドレスを保持しておくやり方と、サンプル・プログラムのように、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.97 | 8.00 | 8.11 | 8.03 |
別バージョン | 11.51 | 11.54 | 11.61 | 11.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; }
◆◇◆更新履歴◆◇◆
記述の中で、拡大・縮小変換式そのものに間違いがあったため訂正しました。傾きの部分は
では正しい変換ができなくて、実際には
です。そうしないと、両端の座標値を代入したときに等号が成り立ちません。
前に戻る | タイトルに戻る |