« 炎エフェクトのクオリティアップと高速化 | メイン | テクスチャマッピングの高速化 その2 »
2008年02月19日
吉里吉里 その他の開発日誌:: テクスチャマッピングの高速化 その1
Tweet @jin1016をフォロー現在、テクスチャマッピングは、各スキャンラインで各辺を順に交差判定し、交差したX座標間のUV値を補間しながら描画している。
他のアルゴリズムも試したが、炎エフェクトの描画では使えないことがわかった。
それは、炎エフェクトで使われるテクスチャマッピングでは、凹ポリゴンが含まれているからだ。
この制限がなければ、より高速なアルゴリズムが使える。
とりあえず、今回は使えないことがわかったアルゴリズムは……
最初に試そうとしたのは、各辺のXとUV座標値をY軸値の変化に沿って変化させる方法。
が、初めうまく行かなかった。
で、この方法の考え方を用いて、各スキャンラインで交差判定するが、判定対象の辺を限定する方法を思い付いた。
現在、各頂点は右回りで格納されている。
そのため、頂点番号を-1すると左側へ、+1すると右側へ進む。
また、頂点数は4個なので、 & 0x03 とすれば、判定なしで 0 ～ 4 の範囲を循環する。
このことを利用して、一番上の頂点から、左右の辺を求め、その辺に対して交差判定することで、交差する辺が限定できる。
Y軸値が、辺の下端の値を超えたら次の辺に進めばいい。
また、左右の位置関係もわかっているので、交差判定後にX座標値の大小値を比較してスワップする必要もない。
が、これもうまく行かなくてなぜだろうと思っていて気付いた。
Y軸値は、整数値で変化させているが、この開始値は浮動小数点値からキャストしたものだ。
つまり、切捨てとなっている。
そのため、この整数のY軸値と交差判定しても、交差する辺はない ( 小数点以下が 0 となるまれなケースでは交差するが ) 。
ということで、この整数のY軸値は最初に1加算することにした。
これで、Yの範囲は常に交差するようになり、右方向と左方向へ辺を見て行って判定する方法でうまく行くようになったと思ったのだが…… しばらく動かしているとアクセス違反で落ちた。
なぜ？ と思って調べたら、凹ポリゴンだった。
うーん…… この方法で 2% 程度高速化したのだが、この方法は使えないようだ。
( 整数のY軸値を１加算する方法は、1回ループが減るので元のアルゴリズムでも使うことにした )
この+1する必要があるということがわかったので、最初に試そうとしたアルゴリズムを試してみた。
凹ポリゴンが描けないので使えないのはわかっているが、どの程度速くなるか見てみようということで。
アルゴリズムは上述の通り、左右の辺を求めて、その辺でY軸値が1増加するごとにX座標値とUV座標値がいくら増加するか求め、Y軸値が1進むごとにX座標値とUV座標値をその増加値分進めるという方法。
この方法では、交差判定が必要ないので、高速であることが期待出来る。
事実、20% 近く速かった。
でも、今回は使えないんだけど。
ちなみに、最大最小法 + ブレゼンハム でやる方法は、最近の CPU では遅いようだ。
以前、テクスチャマッピングではなく、単純なポリゴン描画で試したことがあるのだが、かなり遅くなったので使わなかった。
これらのアルゴリズムはループ中に分岐を多く含んでいるため、速度が出ないとか。
ライン描画もブレゼンハムではなく、素直に固定小数点でやった方が速いという話も ( 今回のことから考えると浮動小数点でもブレゼンハムより速そう ) 。
このライン描画については一度試してみようと思う。
ライン描画の前にブレゼンハムの考え方を使った拡大縮小を別ので使っているので、そちらでまず試すか。
これを書いていて気付いたけど、凹ポリゴンかどうか判定してアルゴリズムを切り替えると速くなるかもしれないと思った。
ただ、その判定コストに見合うだけ速いのかどうかはわからないが。
後、試したことは……
全て固定小数点で処理するようにしてみたが、逆に遅くなった。
ということで、現在X軸方向が増加する時にUV座標値を増減させる部分のみ固定小数点で処理している。
他に固定小数点にしてMMXやSSE2の倍精度浮動小数点でUV値を同時に処理するなど試してみたが、変換コストの方が大きいのか、遅くなった。
ポリゴン4個同時処理のような並列処理でなければ、速度は出し辛いのかもしれない。
いろいろ試して感じたのは、多少計算量が増えようともループ中の分岐を出来るだけ減らした方が速いということ。
このことを元に、ループ中の分岐を出来るだけ削るなどして、今使っているアルゴリズムでも、4～5%ぐらいは高速化出来た ( ループ中での分岐が1,2個減ることで数%高速になったりする。ループ数が多いところではたぶんもっと効く ) 。
ただ、今のアルゴリズムでこれ以上高速化するのは少し辛い。
もっと別のアプローチで高速化しなければ、速くなったと思うほど高速化することは難しいように思う。
今考えているのは、上に書いたような複数ポリゴンの同時描画。
SSE を使って 4個同時描画に近づける。
炎エフェクトでは、複数ポリゴンで1枚のテクスチャを使う形なので、各スキャンラインである程度絞り込まれた辺と交差判定し、その辺間を補間しながら描画すればいいのではないかと考えている。
各ポリゴンは辺を共有しているので、交差判定後のX座標値やUV座標値の計算量は 1/2+1に減る。
絞り込む処理やまとめて処理することによる速度低下が懸念されるが、計算量ほぼ1/2 + SSE による4個同時処理の恩恵の方が上回ってくれたらいいなぁと思う。
まあ、実際はやってみないとどうなるかわからない。
ちなみに、現在のソースだと 480 x 480 の領域に炎を 60 FPS で描くとしたら、1 ～ 1.5 GHzぐらい必要だと思う。
30 FPS でいいのなら、800 MHz程度でも動くのではないかと思う。
後、領域が狭ければ、劇的に軽くなる。
実際炎を描画するのは画面の一部だろうから、現在でも実用的な範囲に入っていると考えている。
そのうち、Athlon XP 1600 と Pen III 800 MHz でどの程度動くか試してみたい。
関連記事・続きの記事
テクスチャマッピングの高速化 その2
前回書いたようにポリゴン1個1個描画するのではなく、各スキャンラインでそのスキャ... [続きを読む]
投稿者 Takenori : 2008年02月19日 00:55
comments powered by Disqus