ITUKI over TCP / TimePlant

Algorithm/Algorism(Fade)

クロスフェード高速化

クロスフェードは画像Ａから画像Ｂへ切り替える際のエフェクトの一種です。
αチェンネルを連続的に変化させて２つの画像の透明度を変えながら表示することでこの効果を作成できます。
普通にやると遅いんですよね……これ。
一応、対象は32BitColorとします。
実行するマシンは32Bitマシンとします。
応用すれば（ビットシフトとａｎｄ使えば）24BitColorとか16BitColorにも使えると思います。
……8BitColor？怪しいなぁ……（笑）
以下、でてくる数値は、640x480,32BitColorで処理した結果です。（これら以外の場合、注を付けてあります）

αチェンネルを使うタイプの一番基本的なパターンは、
Z = AY + (1-A)X ……(a)
（Zは出力画像、Xは開始画像、Yは終了画像。A:0->1と変化）
というのは、公式みたいな物です。
A=0の時、Z=0Y+(1-0)X=X
A=1の時、Z=1Y+(1-1)X=Y
の間で連続変化する事から、比較的分かりやすいと思います。

さて、(a)式の通りにプログラムを組むことができます。
結果、3FPS位でした。(FPS=Frame per Second.一秒当たりのコマ数です。多い方がスムーズです）
このままだと、はっきりいって役に立ちません。遅すぎます。

最も簡単に早くする方法は、Aを実数ではなく、整数で扱うことです。
A=a/Mとおけば、a,Mは整数ですみます。
この場合、Z=(a/M)Y+(1-a/M)Xですが、このままだとa/Mが結果0になってしまう（小数点以下切り捨てられるため）ため、意味がないです。
すこし変形しましょう。
Z=(a/M)Y+(1-a/M)X=aY/M+(M/M-a/M)X=aY/M+(M-a)X/M=(a/M+(M-a)X)/M
となります。これで実際にプログラムすると8FPS位になりました。
（実数演算の方が速いマシンでは結果が異なるかもしれません）

さて、(a)式を変形していきましょう。
Z=AY+(1-A)X=AY+X-AX=X+(Y-X)A
となります。ここで、Y-Xは定数なので、D(=Y-X)とおきます。（変化するのはAのみ）
よって、
Z=X+DA
という式が出来ます。
実際にこの式でプログラムを組んでみると、（A=a/Mとします）約10FPSになりました。
ここで注意しなければならないのは、DはY,Xのビット数より大きいと言うことです。
今回、各色について処理しますので、Y,Xはそれぞで8Bit（符号無し）です。
0<= X,Y <=255が成り立ちますので、-255<= Y-X <=255,-255<= D <=255 となり8Bitに入らなくなります。
とりあえず、32Bit(符号有り）で表しました。

さて、この式をよく見ると、Dの値は有限（しかも、小さい範囲）です。
何度もかけ算・わり算を行うのは時間がかかるため、ここをテーブルにしてみましょう。
配列には-の値は使えないため、Dに255を加える必要があります。
毎回同じ値を加えるのには時間がかかるため、D=Y-X+255と再定義します。
なんとこの時点で20FPS位でるようになりました。

この辺でやめても良いのですが、もうちょっと早くならないか考えてみます。
式的な変形はこれくらいが限界と思われるので、マシンに依存した方法で早くしていきましょう。

さて、今マシンが32Bitという仮定がありますので、32Bit単位で処理した方が早くなると思われます。
（これまでの計測では、各色バラバラに(8Bitで）計算していました）
ここで、XのそれぞれのRGBをX_r X_g X_bと表すことにします。（それぞれ8Bitです）

さて、Z=Z_r<<16 + Z_g<<8 + Z_b …(b)となるZを出力することを考えます。
（この画像形式は、Windowsの32Bit/24BitColorで使われています）
Z=X+DAより、(D=Y-X)
Z_r=X_r+A*D_r … (c)
Z_g=X_g+A*D_g … (d)
Z_b=X_b+A*D_b … (e)
です。
ここで各Zの値が8Bitに入っていることを保証しなければなりません。
この証明は比較的簡単です。これらはZ = X+(Y-X)Aと等価のため、この式でZが8Bitであることを証明すればよいのです。
変化するのはAだけなので、この式は一次式です。そして一次式なので、ZはAの取りうる最大の値と最小の値の間に必ず存在します。
Aの取りうる最大の値と最小の値は、A=0,1なので、ZはXとYの間に存在することになります。
また、X,Yは正の8Bitで表現される数なので、Zも正で8Bitで表現される数になります。
よって、Zは8Bitに入ります。

なぜ、わざわざZが8Bitに入るかを証明したかというと、それらが成り立たないと、複数のX,Y,Zをまとめて扱えないからです。

(b)式に、(c),(d),(e)を代入しましょう。
Z=Z_r<<16 + Z_g<<8 + Z_b = (X_r+A*D_r)<<16 + (X_g+A*D_g)<<8 + X_b+A*D_b
ここで、Z_r,Z_g,Z_bはそれぞれ8Bitに入っているため、RGBがお互いに干渉することはありません。

さらに展開してみましょう。
Z = (X_r+A*D_r)<<16 + (X_g+A*D_g)<<8 + X_b+A*D_b = (X_r<<16)+((A*D_r)<<16) + (X_g<<8)+((A*D_g)<<8) + (X_b)+(A*D_b) = (X_r<<16) + (X_g<<8) + X_b + ((A*D_r)<<16) + ((A*D_g)<<8) + (A*D_b)
とする事が出来ます。

ここで、X_r,X_g,X_bは他の部分と干渉しない(8Bit)だから良しとして、
A*D_r,A*D_g,A*D_bは他の部分と干渉する可能性があります。（負の場合。正の場合は8Bit内に収まるため大丈夫です。）
例えば、A*D_rが負の場合、上位ビットによけいな1が足されてしまいます。
しかし、上で証明したことにより、X_r+A*D_rが8Bit内に収まってしまうため、X_rを加えると、オーバーフローが起こり、干渉ないのと同じ状況になります。
（ビットシフトをかけ算と等価と見ると、さらに明らかです）

さて、ここでX_r<<16 + X_g<<8 + X_bは定数です。
（これは32Bitの変数にZと同様の形式で値を入れた物と等しくなります。）
これを、Xとおきます。
すると、
Z = X + ((A*D_r)<<16) + ((A*D_g)<<8) + (A*D_b)
となります。(D=Y-X)
ここで、A=a/Mとおきます。（Aが実数のため、整数演算にするため）
すると、Z = X + ((A*D_r)<<16) + ((A*D_g)<<8) + (A*D_b) = X + (((a/M)*D_r)<<16) + (((a/M)*D_g)<<8) + ((a/M)*D_b) = X + (((a*D_r)/M)<<16) + (((a*D_g)/M)<<8) + ((a*D_b)/M)
となります（かけ算を最初にやるのは、a/Mを整数演算するとa<Mの場合必ず0となるため）

ここで、((a*D_r)/M)<<16を(((a<<16)*D_r)/M)<<16とやってしまうと、誤差が大きくなるため(M>256の時、D_r/M=0より、明らかにおかしくなる）この辺で式の変形をやめます。

さて、今Z = X + (((a*D_r)/M)<<16) + (((a*D_g)/M)<<8) + ((a*D_b)/M)です。
このまま作っても良いのですが、D_r,D_g,D_b,はそれぞれ-255～255までの範囲の為、これらを扱うのは少し面倒です。（-を表したまま一つにまとめるのが難しい）
そこで、だいぶ上でもやりましたが、D = Y - X + 255と再定義して、0 <= D <= 511にします。
さらに、そのDから、a*D/Mの値を求めるテーブルdを作ってやります。（dは512のサイズです）
すると、
Z = X + d[D_r]<<16 + d[D_g]<<8 + d[D_b]
となります。（各RGB毎にdを別個定義することも可能です。がキャッシュサイズによっては遅くなるかも？）

このままだと、Dがすべて9Bitになってしまうため、32Bitにパックする方法を考えます。
これは単純に
D = D_r<<18 | D_g<<9 | D_b
として、
Z = X + d[D>>18]<<16 + d[(D>>9) & 0x000001FF]<<8 + d[D & 0x000001FF] ……(f)
( = X + d16[D>>18] + d8[(D>>9) & 0x000001FF] + d[D & 0x000001FF] ……(g))
としてやればＯＫです。(d16はdを16ビット右シフト、d8はdを8ビット右シフトした物です)
複雑になったように見せますが、Dは32Bitの中に全部入っているので、コンパイラに最適化を任せちゃいましょう。
これを実行すると、約44FPS((f)式)、約47FPS((g)式)となりました。
（おそらく、キャッシュの少ないマシンだと、(f)式の方が早いのでは？）

今のところ、きちんと32BitColorで演算(全RGBを8Bitで演算）する方法では、これ以上方法が思いつきません。

さて、どうも演算回数をちょっとだけ増やして、メモリを少なくできれば早くなる可能性が高いという事が分かります。
（当然、大量のデータを処理する場合です。）
というわけで、32Bitのうち、現在使っていない最上位8ビットに使える値を入れてみました。
（このとき、差(D)が1Bitあふれてしまうので、1ビット右シフトして8Bitに合わせてやります。これは±2以内の誤差として現れます）
詳細は省略しますが、ちょっとだけ早くなりました。
4ドット単位でしか処理出来ないと言う問題は残りますが……
RRGB+GRGB+BRGBと、４ビットを３バイトにパックした場合、49FPS((f)式改),50FPS((g)式改)となりました。
なお、この場合出力がRGBの24Bit形式であれば、RGBR+GBRG+BRGBでパックすれば変換が不要になるのでかなり早いですね。
（そんなことやっていいのか？という疑問はともかくとして）

おっと。ここで一応計算を。
画像１枚あたり1200KByteです。(32BitColorで出力しているため）
これを１秒間に50枚転送しているので、60000KByte/s≒59MByte/s書き込んでいるわけです。
CreateDIBSectionを使っているので、Windowsがユーザーメモリーから画像を転送しているはずなので2倍ほど転送しているはずです。
よって、出力に59*2=118MByte/s使っていると考えられます。
で、差の分(D)が、画像一枚当たり900KByte(24Bitにパックしているため）
これはほぼ固定ですが、普通キャッシュには入らないサイズなのでメモリからよんでいると推測すれば、45000KByte/s≒43MByte/s
同様に、元ソースの分(X)が、画像一枚当たり900KByte(24Bitにパックしているため）
よって、見えないデータのロードに43*2=86MByte/s使っていると考えられます。
おそらくテーブルはキャッシュに入っている(4*256*3=3072=3KByte)と思うので転送はおきてないでしょう。
とすると、合計して、204MByte/s程度メモリ－ＣＰＵ間の帯域を専有してるはずです。
環境がAGPなのでバスから直接書けるとして、59MByte/s前後をビデオカードに出力しているので、プログラム全体としては263MByte/s使ってると思われます。
ベースクロックが100MHzなので、最大転送速度は、400MByte/sです。(64Bitバスなら800MByte/s)
少なくとも1/2以上は使っているでしょう。(メモリとのバスが32Bitの場合ですが……）
これ以上高速にしようと思うと、
1)データを8Bit以下にする
2)ＣＰＵ演算をもう少し少なくしてみる（限界？）
3)ビデオメモリに直接書く
等が必要かと思います。

(g)式（きちんと全ビット計算をする）で、描画ルーチン(BitBlt)を抜いたら73FPSでました。
パックしてないので、87600KByte/s≒85MByte/s(出力バッファへ転送）、87600*2Kbyte=171MByte/s（入力）という事で、256MByte/s位でてます。
同様に、４ビットを３バイトにパックした場合、描画ルーチン(BitBlt)を抜いたら、82FPSでてました
82FPSって事は、98400KByte/s≒96MByte/s(出力バッファへ転送）、73800*2KByte/s≒72*2MByte/s＝144MByte/s（入力）って事で、やっぱり合計240MByte/s前後でてる計算になります。
（パックした方が遅いのは、必要なデータを取得するために少し計算量が増えるため。ただ、関係のないデータを転送しない分FPSは早くなる）
まぁ、これくらいで勘弁して下さい（笑）
こんど暇見てDirectDrawバージョン作ってみます。

他に改善案があれば、メール( ituki@fc.to )でお願いします。
間違い（誤字・脱字・理論的間違い等）も上記アドレスで受け付けています。

[ Algorithm/Algorismへ戻る | トップページへ戻る ]