« Warp Map で炎 | メイン | テクスチャマッピングの高速化 その1 »
2008年02月18日
吉里吉里 その他の開発日誌:: 炎エフェクトのクオリティアップと高速化
Tweet @jin1016をフォロー
テクスチャマッピングの実装でミスっていたというか、以前使っていた用途に限定して高速化していたのを忘れていて、そのまま使っていた部分を直した。
後、カラーテーブルも少し改良。
他に風が吹いているように見せたり、最後消火するなど出来るようにした。
で、右側から風が吹いているようにして描画したのが、上の画像。
最初の実装はかなり重く、Core 2 Duo E6750 で 480 x 480 の範囲に炎を描いても処理落ちしていた ( 60 FPS )。
で、これを改善するべく高速化に取り組んだ。
Warp Map のアルゴリズムはまとめると以下のような処理になる。
1. Heat Mapへ火種を描画 (加算合成)
2. Wrap Mapを動かす (バネを模倣した動き)
3. Heat MapへWrap Mapを適用する (テクスチャマッピング)
4. Heat MapへCooling Mapを適用する (減算合成)
5. Heat Mapをぼかす (ガウスブラー)
6. Heat Mapを1ピクセル上へ移動する
7. 描画対象へHeat Mapを適用 (強度に応じた色で塗る)
8. Cooling Mapを1ピクセル上へ移動する
1 ～ 8 を繰り返す。Heat Map はクリアせずに使いまわす。
Heat Map は呼び名がないと不便なので適当に名付けた。仮想的な温度というか濃度というかそういうものを表している。
で、最初はほぼこの通りに実装していた( テクスチャマッピング時に減算合成を同時にしていたが )。
そこで、この 4 ～ 7 のプロセスをまとめ、キャッシュ効率やレジスタ効率を上げることにした。
なお、ガウスブラーは 3x3 で以下の比率でブラーをかけている。
| 1/16 | 1/8 | 1/16 |
| 1/8 | 1/4 | 1/8 |
| 1/16 | 1/8 | 1/16 |
この比率がガウス関数に沿ったものかどうかは知らない。
ガウスブラーは、横方向にブラーをかけたものに縦方向にブラーをかけると、結果的に矩形範囲でブラーをかけたのと同じになるので、1方向で見てみると 1/4、1/2、1/4 を適用すればいいことになるため、効率的なので、上のマトリックスを使っている ( つまり、( 右 + 2 * 中心 + 左 ) / 4 となるため、足し算とシフトだけで計算できる )。
で、いわゆる縦横の for 二重ループ内で 4 ～ 7 を全てやってしまおうとするわけだけど、そのままだとうまく行かない。
横方向ブラーは、1ピクセル遅れ、縦方向ブラーは1ライン遅れで処理していく必要がある。
ただ、縦方向は後でスクロールするから、一番上のラインを処理しても意味はないので、3ライン目以降になる。
ということで、最初の2ラインは減算合成して、1ピクセル遅れで横方向ブラーをかけて書き込んでいく。
3ライン目からは、減算合成して、1ピクセル遅れで横方向ブラーをかけて、上の2ライン分横方向ブラー済みのデータを読み込んで、直前に処理した横方向ブラー後のデータを使って縦方向ブラーをかけて、その結果を使って色テーブルから色を取って来て最終描画対象の1ライン上に書くのとHeat Mapの1ライン上に書き込む。
このようにして出来るだけデータを使いまわして順に処理していくように書き換えた。
これで、MMX など使わなくても 40% ぐらい速くなった。
で、ここから MMX や MMX2、SSE、SSE2 を使って高速化していった。
最初は、この 4 ～ 7 の処理を SIMD 化して高速化した。
横方向ブラーは、単純に直前の8ピクセルと直後の8ピクセルから1ピクセルを得られるようにシフトして、 or を取ったものと、現在の8ピクセルで処理すれば実現できる。
縦方向ブラーは、特に深く考えずに処理できる。
で、SSE2 まで実装してみたところ、MMX2 よりも SSE2 の方が Athlon 64 X2 でも速くなった。
以前のアルファブレンドでは大差なかったが、ある程度の処理を行う場合は、SSE2 の方が効率が良いようだ。
後、シフトと or をとる部分を SSSE3 のアライメント調整命令で実装してみたが、ほんの少ししか速くならなかったので、結局使わないことにした。
次に Wrap Map を動かす部分の高速化に取り掛かった ( 加算合成の部分の SIMD 化はさくっとやった ) 。
プロファイル結果を見るとそれほど処理時間を使っていないが、他の高速化は大変そうなのでやることにした。
ここは 5 x 5 の範囲で 元の位置関係の距離と移動後の位置関係の距離の差に係数をかけた結果を速度に加算して、最後にその速度を位置に加算する処理をする。
元の位置関係の距離は定数となることから元はテーブルで求めていたが、そこを毎回計算するようにしてみた。
つまり、元は len[abs(y-y1)][abs(x-x1)] のようになっていたのを、sqrt( (y-y1)*(y-y1) + (x-x1)*(x-x1) ) とした。
で、計測すると毎回計算する方が速い。
sqrt は比較的重い処理だと良く書いているのだが、abs やテーブルを引く処理の方が遅いのか……
で、次にこの処理の部分をインライン関数化して、24個並べた。
24個並べると、距離は計算する必要がないので、事前に計算した直値をいれる方法に。テーブルを引くのではなく、直接コードに埋め込まれるはず。
これで思っていた以上に速くなった。
速くなりそうだったので、ここを SSE 化した。
SSE 化した時、最初アライメントを気にして処理を分けたのだが、アライメント関係なく読み込む遅い方のを使って分岐しないようにした方が速かった。
やはり、ループ中で分岐するのは遅くなるようだ。
次にテクスチャマッピングの高速化に取り掛かることにした。
テクスチャマッピングの処理が全体の50%を占めているのでここを速く出来れば、かなり高速化できると思うが大幅な高速化は難しい。
続く……
投稿者 Takenori : 2008年02月18日 00:20
comments powered by Disqus