このページはインターネットエクスプローラ4.0以降に調整されています
2002.05.31,00:34

Windows

タイルの回転拡大縮小～RotoZoomer～

其ノ壱～タイル表示～
其ノ弐～回転～
其ノ参～回転最適化～
其ノ四～計算最適化～
其ノ伍～状況限定最適化①～
其ノ六～状況限定最適化②～
其ノ七～拡大縮小～
其ノ八～中心指定①～
其ノ九～中心指定②～
其ノ拾～テーブル～

其ノ壱～タイル表示～

ただ,タイルを並べただけの図です.
水色がディスプレイ
黄緑が表示されてるタイル
緑が表示されていないタイル
黄色はタイルの座標系
を表しています.

画面上の座標を(x,y)とすれば,
タイル上の座標(tX,tY)は,

tX = x % iTileSizeX;
tY = y % iTileSizeY;

と表せる.
ちなみに,iTileSizeX,iTileSizeYは,タイルのサイズです.

其ノ弐～回転～

画面の左上を中心に,θだけ反時計回りにタイルを回転させました.
このまま話を進めてもいいんですが,これは少しわかりにくい気がするので,
次のようにします.
タイルの回転図03

画面の左上を中心に,θだけ時計回りに画面を回転させました.
同じ事ですが,こちらの方が見やすい気がします.
タイル上の座標(tX,tY)は,iAngle = θとすると

tX = (x * cos(iAngle) - y * sin(iAngle)) % iTileSizeX;
tY = (x * sin(iAngle) + y * cos(iAngle)) % iTileSizeY;

で,イメージとしてはこんな感じになりますね.


for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　tX = (x * cos(iAngle) - y * sin(iAngle)) % iTileSizeX;
　　tY = (x * sin(iAngle) + y * cos(iAngle)) % iTileSizeY;
　　pSurface[y * lSurfacePitch + x] = iTileBuf[tY * iTileSizeX + tX];
　}
}

これで,タイルの回転は実現できますが,このままでは使いものになりません.
いくら最近のCPUが速いといっても,画面一つ埋めるのに,
640 x 480 = 307200回は,ちょっと荷が重いです.
そこで,最適化していきます.

其ノ参～回転最適化～

画面に描画するときのことを考えます.
普通は,左上(0,0)から右上(n,0),一段下がって左(0,1)から右(n,1)
という具合に,右下(n,m)まで描画していきます.

そこで,画面上のx軸に注目してみます.
タイルの回転図04

描画時は,xの値が1ずつ増加していきます.
では,このときタイル上の座標(tX,tY)は,どのように変化するでしょうか.
tXはcosθ,tYはsinθずつ増加していきます.
そこで,この増加量を定数にしてしまいましょう.

iHorizontalIncX = cos(iAngle)
iHorizontalIncY = sin(iAngle)

すると,左上から右上までは

iHorizontalIncX = cos(iAngle);
iHorizontalIncY = sin(iAngle);

tX = 0;
tY = 0;

for(int x=0;x<iViewWidth;x++){
　pSurface[y * lSurfacePitch + x] = iTileBuf[tY * iTileSizeX + tX];
　tX = (tX + iHorizontalIncX) % iTileSizeX;
　tY = (tY + iHorizontalIncY) % iTileSizeY;
}

ループの中から厄介者(sin,cos)を追い出せました.
さて,画面上のy軸についても同様に考えてみましょう.
タイルの回転図05

yの値が1増加するとタイル上の座標(tX,tY)は,どのように変化するでしょうか.
tXは-sinθ増加,tYはcosθ増加します.
同じように,この増加量を定数にしてしまいましょう.

iVerticalIncX = -sin(iAngle)
iVerticalIncY = cos(iAngle)

これをどう使うかというと.

iHorizontalIncX = cos(iAngle);
iHorizontalIncY = sin(iAngle);
iVerticalIncX = -sin(iAngle);
iVerticalIncY = cos(iAngle);

tX = iTileStartX = 0;
tY = iTileStartY = 0;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　pSurface[y * lSurfacePitch + x] = iTileBuf[tY * iTileSizeX + tX];
　　tX = (tX + iHorizontalIncX) % iTileSizeX;
　　tY = (tY + iHorizontalIncY) % iTileSizeY;
　}
　tX = iTileStartX = (iTileStartX + iVerticalIncX) % iTileSizeX;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) % iTileSizeY;
}

という具合になります.
これで,完全に厄介者を排除したわけです.

一応説明しておくと,iTileStartX,iTileStartYは
画面上の左端,座標(0,y)に対応するタイル上の座標を保存しています.
画面の右端まで描画し終わったら左端に戻らなければなりません.
(そのまま下に行って,渦巻きみたいにぐるぐる回るのも面白いかも)
そこで,iTileStartX,iTileStartYにiVerticalIncX,iVerticalIncYを加えて
下に移動させ,それをtX,tYに代入してやります.
これで,次の行の左端に戻ることが出来ます.

其ノ四～計算最適化～

ここまででも,そこそこ速くなっていると思いますが,
まだまだ無駄な部分があります.

まず,浮動小数点演算はやっぱり遅いです.
そこで,なるべく整数で処理することにします.
整数値の下位8bitを小数と見なします.
分解能は1/256 = 約0.004,ゲームで使うには,十分な値です.
では,順番に整数化していきましょう.

iHorizontalIncX = cos(iAngle); → iHorizontalIncX = (int)(256 * cos(iAngle));
iHorizontalIncY = sin(iAngle); → iHorizontalIncY = (int)(256 * sin(iAngle));

浮動小数点の値を256倍して,整数型にキャストします.

iVerticalIncX = -sin(iAngle); → iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = cos(iAngle); → iVerticalIncY = iHorizontalIncX;

同じ計算を二度するのは無駄ですね.

pSurface[y * lSurfacePitch + x] = iTileBuf[tY * iTileSizeX + tX];

これは,ループのまっただ中にありますね.
ここに,か掛け算を置いておくのは得策ではありません.

まず,pSurface[y * lSurfacePitch + x]を何とかしましょう.
xは,1ずつ増えるので,pSurface++にしてしまって問題ないですね.
yが増えるときはどうかというと,lSurfacePitchずつ増えています.

ここで,lSurfacePitch = iViewWidthが保証されているならば,
何もすることはありません,右端の次は一段下の左端です.

しかし,DirectDrawでは,保証されていないので注意が必要です.
そこで,lSurfacePitchを右端から一段下の左端までの増分にしてしまいましょう.
lSurfacePitch -= iViewWidthとするだけです.
これでどのようになるかというと,

lSurfacePitch -= iViewWidth;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[tY * iTileSizeX + tX];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) % iTileSizeX;
　　tY = (tY + iHorizontalIncY) % iTileSizeY;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) % iTileSizeX;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) % iTileSizeY;
}

次は,iTileBuf[tY * iTileSizeX + tX]の部分ですが,
整数化の影響をもろに受けています.
まず,そこから修正していきましょう.

tX,tYは実際の値の256倍ですから,単純に256で割ってやります.

iTileBuf[tY /256 * iTileSizeX + tX /256]

でも,せっかく整数型にしたので,シフトを使う方がいいですね.
このときのために,256倍 = 2⁸倍としたわけですね.

iTileBuf[(tY >>8) * iTileSizeX + (tX >>8)]

掛け算が残ってしまっていますが,これは後回しです.
他にも整数化の影響を受けている部分があるので,そこも修正します.

iTileSizeX,iTileSizeYはもともと整数型ですね.
他の256倍で整数化されたものと使うときは,これも256倍されてないといけません.

iTileSizeX → (iTileSizeX <<8)
iTileSizeY → (iTileSizeY <<8)

これもシフトしてやればいいですね.
さらに,これは定数ですから,ループの外に出しましょう.

iTileSizeMaskX = iTileSizeX <<8;
iTileSizeMaskY = iTileSizeY <<8;

ここまでのコードをまとめてみましょう.

iHorizontalIncX = (int)(256 * cos(iAngle));
iHorizontalIncY = (int)(256 * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX = 0;
tY = iTileStartY = 0;

lSurfacePitch -= iViewWidth;

iTileSizeMaskX = iTileSizeX <<8;
iTileSizeMaskY = iTileSizeY <<8;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[(tY >>8) * iTileSizeX + (tX >>8)];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) % iTileSizeMaskX;
　　tY = (tY + iHorizontalIncY) % iTileSizeMaskY;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) % iTileSizeMaskX;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) % iTileSizeMaskY;
}

まぁまぁ速くなったと思います.

其ノ伍～状況限定最適化①～

今までは,一般的な場合について考えていましたが,
状況を限定することで,さらに無駄を減らすことが出来ます.

手始めに,タイルのサイズを 2ⁿ x 2^m に絞ってみます.

これで何が変わるかというと,
%を論理演算に置き換えることが出来るようになります.
ただそれだけですが,馬鹿には出来ません.
ループの中心にある2個の % が消えますからね.

iTileSizeMaskX = iTileSizeX <<8; → iTileSizeMaskX = (iTileSizeX <<8) -1;
iTileSizeMaskY = iTileSizeY <<8; → iTileSizeMaskY = (iTileSizeY <<8) -1;

としてやり, % を & に変えます.

iHorizontalIncX = (int)(256 * cos(iAngle));
iHorizontalIncY = (int)(256 * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX = 0;
tY = iTileStartY = 0;

lSurfacePitch -= iViewWidth;

iTileSizeMaskX = (iTileSizeX <<8) -1;

iTileSizeMaskY = (iTileSizeY <<8) -1;


for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[(tY >>8) * iTileSizeX + (tX >>8)];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) & iTileSizeMaskX;
　　tY = (tY + iHorizontalIncY) & iTileSizeMaskY;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) & iTileSizeMaskX;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) & iTileSizeMaskY;
}

だいぶ速くなったと思います.

其ノ六～状況限定最適化②～

さらに,タイルのサイズを 2⁶ x 2⁶ (64x64)に絞ってみます.
ここまでくると,限定され過ぎてしまい,一般性の欠片もなくなりますね.
ゲームで使う分にはあまり問題無い気もしますが,使いまわし難くなりますね.

とりあえず,iTileSizeX,iTileSizeYを定数に置き換えてしまいます.

iTileSizeX → 64
iTileSizeY → 64

ついでに計算できる部分は計算してしまいましょう.

(iTileSizeX <<8) -1 → 16383 → 0x3fff
(iTileSizeY <<8) -1 → 16383 → 0x3fff
iTileSizeMaskX → 0x3fff
iTileSizeMaskY → 0x3fff
iTileBuf[(tY >>8) * iTileSizeX + (tX >>8)] → iTileBuf[(tY >>8 <<6) + (tX >>8)]

これで,ループの中から掛け算も消えてしまいました.

でも,tY >>8 <<6 って無駄な気がしますね.
何故こうなるかというと,tY >>2としてしまうと,
tYの下位6bitが生き延びてしまい,配列をオーバーしてしまう事があるんですね.

ここで,整数化したときに256(2⁸)倍したのを,64(2⁶)倍に変えてみましょう.

(iTileSizeX <<6) -1 → 4095 → 0x0fff
(iTileSizeY <<6) -1 → 4095 → 0x0fff
iTileSizeMaskX → 0x0fff
iTileSizeMaskY → 0x0fff
iTileBuf[(tY >>8) * iTileSizeX + (tX >>8)] → iTileBuf[(tY & 0xfc0) + (tX >>6)]

数値の精度は落ちてしまいましたが,シフト2回が論理和1回になりましたね.
タイルを大きくすれば,精度は上がるし,小さくすれば下がることになります.
まぁ,小数部が6bitあれば十分でしょう.

最終的なコードは

iHorizontalIncX = (int)(64 * cos(iAngle));
iHorizontalIncY = (int)(64 * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX = 0;
tY = iTileStartY = 0;

lSurfacePitch -= iViewWidth;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[(tY & 0xfc0) + (tX >>6)];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) & 0x0fff;
　　tY = (tY + iHorizontalIncY) & 0x0fff;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) & 0x0fff;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) & 0x0fff;
}

そうとう速くなったと思います.

其ノ七～拡大縮小～

拡大縮小は簡単です.
画面上の座標に対するタイル上の座標の増加量を変えてやればいいだけ.
増加量が小さくなると拡大,大きくなると縮小なところに注意.

拡大縮小をiScaleで与えるとすると,64倍してやって
実寸をiScale = 64とすると具合がいいです.
元に戻すと iScale / 64 です.
すると

64 * cos(iAngle) → 64 * iScale / 64 * cos(iAngle) → iScale * cos(iAngle)
64 * sin(iAngle) → 64 * iScale / 64 * sin(iAngle) → iScale * sin(iAngle)

なんか,あっけなかったですね.
全体は,こんな感じです.

iHorizontalIncX = (int)(iScale * cos(iAngle));
iHorizontalIncY = (int)(iScale * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX = 0;
tY = iTileStartY = 0;

lSurfacePitch -= iViewWidth;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[(tY & 0xfc0) + (tX >>6)];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) & 0x0fff;
　　tY = (tY + iHorizontalIncY) & 0x0fff;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) & 0x0fff;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) & 0x0fff;
}

速さそのままです.
注意:16 < iScale < 256 (4倍～1/4倍)程度が適当だと思います.

其ノ八～中心指定①～

けっこう重要だけど,あまり問題ではないので後回しにしました.
これも,拡大縮小と同様,初期値を変えるだけなので,あっけないです.
タイルの回転図06

変更するのは
tX,tY,iTileStartX,iTileStartY の初期値だけです,

画面上の回転中心座標を(iViewCenterX,iViewCenterY)とすると,
左にiViewCenterX,上にiViewCenterY行ったところにあるタイル上の点から
描画を開始すればいいですね.

画面座標でiViewCenterXに対応するのは,タイル座標では
tX = iViewCenterX * iHorizontalIncX
tY = iViewCenterX * iHorizontalIncY

画面座標でiViewCenterYに対応するのは,タイル座標では
tX = iViewCenterY * iHorizontalIncX
tY = iViewCenterY * iHorizontalIncY

したがって,初期値の計算は次のようになります.

tX = iTileStartX
   = iTileSizeX * 64
    - (iViewCenterX * iHorizontalIncX + iViewCenterY * iVerticalIncX)
    % (iTileSizeX * 64);
tY = iTileStartY
   = iTileSizeY * 64
    - (iViewCenterX * iHorizontalIncY + iViewCenterY * iVerticalIncY)
    % (iTileSizeY * 64);

最適化してやれば,

tX = iTileStartX
   = 0x4000 - (iViewCenterX*iHorizontalIncX+iViewCenterY*iVerticalIncX) & 0x0fff;
tY = iTileStartY
   = 0x4000 - (iViewCenterX*iHorizontalIncY+iViewCenterY*iVerticalIncY) & 0x0fff;

って感じかな.
もう少し何とかなりそうだけど,そのうちね.

iHorizontalIncX = (int)(iScale * cos(iAngle));
iHorizontalIncY = (int)(iScale * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX
   = 0x4000 - (iViewCenterX*iHorizontalIncX+iViewCenterY*iVerticalIncX) & 0x0fff;
tY = iTileStartY
   = 0x4000 - (iViewCenterX*iHorizontalIncY+iViewCenterY*iVerticalIncY) & 0x0fff;

lSurfacePitch -= iViewWidth;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[(tY & 0xfc0) + (tX >>6)];
　　pSurface++;
　　tX = (tX + iHorizontalIncX) & 0x0fff;
　　tY = (tY + iHorizontalIncY) & 0x0fff;
　}
　pSurface += lSurfacePitch;
　tX = iTileStartX = (iTileStartX + iVerticalIncX) & 0x0fff;
　tY = iTileStartY = (iTileStartY + iVerticalIncY) & 0x0fff;
}

速さそのままです.

其ノ九～中心指定②～

中心指定①では,タイルの左上しか位置を指定できませんでしたが,
もっと細かい指定を可能にしましょう.
タイルの回転図07

これは,描画開始タイル座標を,ちょっとばかし平行移動してやることで実現できます.
移動量は,白い三角形に対応する分で,
タイル上の中心を(iTileCenterX,iTileCenterY)とすれば,

tX = iTileStartX
   = 0x4000
    - (iViewCenterX*iHorizontalIncX+iViewCenterY*iVerticalIncX - iTileCenterX)
    & 0x0fff;
tY = iTileStartY
   = 0x4000
    - (iViewCenterX*iHorizontalIncY+iViewCenterY*iVerticalIncY - iTileCenterY)
    & 0x0fff;

ソースはかかんよ.
変更これだけだから.

其ノ拾～テーブル～

これでも遅せぇ,ってせっかちな人にはテーブルを使ってもらいましょう.
さて,どんなテーブルを作るかというと,
画面x座標一列分の物です.
これ以上大きな物を作るのは,お馬鹿さんですね.
例えば,画面全体のテーブルとかね.

640x480の画面なら,640x2の配列を用意して,
横一列分のテーブルを作成します.

int iTableX[iViewWidth],iTableY[iViewWidth];

for(int i=0;i<iViewWidth;i++){
　iTableX[i] = tX = (tX + iHorizontalIncX) & 0x0fff;
　iTableY[i] = tY = (tY + iHorizontalIncY) & 0x0fff;
}

こんな感じです.
まとめてみると,

iHorizontalIncX = (int)(iScale * cos(iAngle));
iHorizontalIncY = (int)(iScale * sin(iAngle));
iVerticalIncX = -iHorizontalIncY;
iVerticalIncY = iHorizontalIncX;

tX = iTileStartX
   = 0x4000
    - (iViewCenterX*iHorizontalIncX+iViewCenterY*iVerticalIncX-iTileCenterX)
    & 0x0fff;
tY = iTileStartY
   = 0x4000
    - (iViewCenterX*iHorizontalIncY+iViewCenterY*iVerticalIncy-iTileCenterY)
    & 0x0fff;

int iTableX[iViewWidth],iTableY[iViewWidth];

for(int i=0;i<iViewWidth;i++){
　iTableX[i] = tX = (tX + iHorizontalIncX) & 0x0fff;
　iTableY[i] = tY = (tY + iHorizontalIncY) & 0x0fff;
}

lSurfacePitch -= iViewWidth;

for(int y=0;y<iViewHeight;y++){
　for(int x=0;x<iViewWidth;x++){
　　*pSurface = iTileBuf[((iTileStartX + iTableY[x]) & 0xfc0)
               + ((iTileStartX + iTableX[x]) & 0x0fff) >>6];
　　pSurface++;
　}
　pSurface += lSurfacePitch;
　iTileStartX = (iTileStartX + iVerticalIncX) & 0x0fff;
　iTileStartY = (iTileStartY + iVerticalIncY) & 0x0fff
}

でいいはずです.
こんなん試してないから,知らん.
変わってない気がする….

工事中です
< > &

WinMain
RotoZoomer
Tunnel
Plasma
Fire
MetaBall

Entrance Home Back

Windows

タイルの回転拡大縮小 ～RotoZoomer～

タイルの回転拡大縮小～RotoZoomer～