« テクスチャマッピングの高速化 その1 | メイン | テクスチャマッピング アルゴリズム 最大最小法 »
2008年02月21日
吉里吉里 その他の開発日誌:: テクスチャマッピングの高速化 その2
Tweet @jin1016をフォロー前回書いたようにポリゴン1個1個描画するのではなく、各スキャンラインでそのスキャンライン上にある全ポリゴンの辺と交差判定するようにしてみた。
その際、8ラインごとにポリゴンの辺と交差するかどうかを保持することにした。
これは頂点が上か下か判定する時に、上から下まで配列にそのポリゴンの辺のインデックスを追加して実現した。
つまり、配列は高さ / 8 個になる。
そして、画像の上から下までスキャンラインを移動させ、辺のインデックスを保持した配列から交差する可能性のある辺を取得して、交差判定後、交差位置を割り出し、1ライン分終わったら、X軸値でソートして、左から順にUV値を補間しつつ描画した。
ポリゴンの辺は、左端にあるものほど先に入りようにしており、X軸値はほぼソート済みとなっている。
そのため、交差する辺の数も少ないことから挿入ソートで実装した ( ソートの有り無しで速度はそれほど変わらなかった ) 。
で、時間を計ってみたのだが、28% も遅い。
交差する辺の絞込み周りがネックになっているようだ。
これを4ラインごとにすると少し速くなるが、1ラインごとにすると遅くなった。
そもそも、交差する辺を判定しなくても良いようにならないものか…… と考えていて気付いた。
スキャンライン基準ではなく、ポリゴンの辺基準でやればいい。
つまり、全ての辺の上端から下端までの範囲に辺のインデックスを格納してしていけばいい。
こうすれば判定は不要になり、そのスキャンラインを通る辺のみが各Y座標値にリストとして得られる。
また、補間に使うY軸値の比も毎スキャンライン計算するのではなく、1.0 / (y2 - y1) で得られた値を加算していけばよくなる。
そして、再度時間を計ってみたのだが、18% 遅い。先ほどと比べると 10% 短縮されているが遅い。
ただ、この方法だと凹ポリゴンをより正確に描ける。
1個1個描画するバージョンは、各辺を順に見ていく関係上凹ポリゴンの時、最初に交差した2辺間を塗ってしまう。
つまり、凹ポリゴンの時、以下の図のように塗られることになる。
炎の動きが激しくない場合は、それほど凹ポリゴンがないので、気にならないレベルだが、激しくすると破綻しているところが見える。
まあ、普通に使う分にはわからないのだが。
よくよく考えれば、交差位置の計算は必要ないことに気付いた。
前回、右方向、左方向で進めていく方法について書いたが、それと同じように辺ごとに上から少しずつ値を加算していけばいい。
ただ、前回 20% 程度速くなっていたということは、今回の方法でこれを使っても大差ないレベルに出来るというだけの話か。
実際は、テンポラリの変数が増えるのでもっと遅くなりそうか。
この辺りで手を打つかな。
画面全体でやろうとした場合、かなり速い CPU でないと無理そうで、そうなるともう GPU に任せるだろうから。
部分的に適用するものと言う事で使うか。
もっと根本的にリアルタイムで炎を生成せずに、アルファチャンネル付きムービーを実装してしまうと言う手もあるが (笑) 。
関連記事・続きの記事
テクスチャマッピングの高速化 その3
テクスチャマッピングの高速化を書きつつ、そのアルゴリズムを知らない人にとっては意... [続きを読む]
投稿者 Takenori : 2008年02月21日 00:05
comments powered by Disqus