« 平方根の逆数の高精度化 | メイン | アルファムービーをやや強引に入れるアイデア »

2008年02月25日

吉里吉里 その他の開発日誌:: テクスチャマッピングの高速化 その3

    

テクスチャマッピングの高速化を書きつつ、そのアルゴリズムを知らない人にとっては意味不明のエントリーだろうなぁと思って、アルゴリズムについて解説するエントリーでも書こうかなと考えた。
そして、まずは最大最小法だろうなどと考えている時に気付いた。
全ての辺をまとめてやって遅いのなら、1個1個のポリゴンでやればいいのではないか?と思った。
まとめてやると速度が出ないのは、メモリ使用量の増加と間接参照の増加が原因ではないかと思われる。
1個1個やると計算量は 1/2+1 にはならないが、それでも速くできるかもしれない。

基本的なアプローチは一度にやる方法に近い。
まず、左右の X 座標と UV 座標を最初に全て求める。
次に、この間を補間しつつ描画する。
左右の座標を求めるのは、辺が右か左で判断し、2辺目に移った時に、Y座標が上になっていたら、凹ポリゴンか辺が逆に移った可能性がある。
この時、辺が外側に向いていたら凹ポリゴン、内側に向いていたら辺が移ったことになる。
これは下図を参照してもらうとよくわかると思う。
20080225_side_order.png
内側か外側かは単純にX軸の値を見ればわかる。

また、間を補間するための値の計算は4つまとめて SSE を使って出来る。
この方法で全スキャンラインで交差判定する方法よりも少し速くなったんだけれど、少し不具合があって時々アクセス違反で落ちる。
Y 軸も X 軸も変化量を加算して求めているために誤差が出ているのか、アルゴリズムに見落としがあるのかわからないが、時々テクスチャ画像の範囲外にアクセスしてしまう。
テクスチャ画像へアクセスする時に範囲チェックをすれば解決するが、それをやると 25% 程度速度が低下するので、かなり遅くなってしまう。
アルゴリズム的な問題は何度か見直したが、解決しない。
どうするかと考え、全スキャンラインで交差判定する方法でも同様に SSE で高速化できるのでは? と思った。
全スキャンラインで交差判定する方法の SSE 化は何度かやろうとしたのだが速度が出なかった。
それは垂直演算に近いことを単に2並列でやろうとしていたからだったのではないかと思う ( U と V を同時に計算しようとするなど ) 。
そうではなく、4 ライン同時に処理すればいいのではないかと思った。
つまり、最初に 4 ライン分の交差判定を済ませ、その後 4 ライン同時に処理する。
また、SSE を使ってスワップやクリッピングを行うので分岐が消える。

実装してみると 9% 程度速度が向上した。
ここからさらに交差判定も SSE 化することでさらに速度向上できるのではないかと思う。
また、横方向の補間も SSE2 を使うことで 4 ライン同時処理出来るので、もしかしたら速くなるかもしれない ( 横方向ラインによって幅が異なるので、終了位置がバラけるのと、テクスチャ画像の参照位置と書き込み位置がバラバラなので、速度が出るかどうかは不透明 ) 。

まだもう少し高速化できそうだ。



投稿者 Takenori : 2008年02月25日 17:27




comments powered by Disqus
Total : Today : Yesterday : なかのひと