« テクスチャマッピングの高速化 その2 | メイン | テクスチャマッピング アルゴリズム 毎ライン交差判定 »

2008年02月21日

基本テクニック:: テクスチャマッピング アルゴリズム 最大最小法

    

テクスチャマッピングのアルゴリズムはいくつかあるが、その中で昔速いと言われていたらしい方法に最大最小法がある。
まずはポリゴンを塗るだけのことを考えるとする。
これはまず高さ分のX軸値の最大値と最小値を保持するバッファを用意する。
次に、最大値に最小値を、最小値に最大値を入れて初期化する ( int なら INT_MAX や INT_MIN ) 。
後は、各ポリゴンの辺についてY座標が小さい方から大きい方へ見ていき、現在のY座標値のX座標値が最大値よりも大きければ最大値バッファに値を入れる。また、最小値よりも小さければ、最小値バッファに値を入れる。
このようにして3辺処理すると、各Y座標値について、X座標の最小値と最大値が入る。
これを図にすると以下のようになる。

20080221_tex_map_minmax.png

上図のようにX座標の最小値と最大値がわかれば、後はこの間を塗ればポリゴンが描ける。

Y座標の変化に従ってX座標値がどのように変化するかを調べるには、昔はブレゼンハムが使われていたようだ。
普通に考えるのなら、単純にY値の比で求めればいい。
つまり、Yの変化量 / 高さ が、現在のY値を比であらわしたもの。 0.0 ~ 1.0 の値になる。
後はこれを幅にかけてやれば、現在のY値の時の、Xの変化量がわかるので、Xの始点座標値に加算してやれば、現在のX座標値が求まる。
ただ、毎回割り算や掛け算していると重いので、Y軸値が1増えた時の変化量をあらかじめ求めておき、後はY軸値が変化するごとに、その変化量を加算していけば結果は同じになる ( 誤差の影響を無視した場合 ) 。

これでポリゴンが描けたとして、テクスチャマッピングの場合はどうするか?
これも考え方は同じ。
まず、各頂点の 0 ~ 2 のそれぞれにテクスチャのUV座標値を持たせる。
その後は、先ほどのX座標値の補間と同じ、Y軸値が1増えた時にU ( V ) 座標値の変化量を求めて、加算していってやれば、各Y軸値の時のUV座標値が求まる。
求まったUV座標値は最大値と最小値を保持するバッファにUV座標値も保持するようにして、そこに入れておく。
こうすればX座標の最小値と最大値とそのUV座標値がわかる。
ポリゴンの時は単純に1色で塗ったけど、テクスチャの時は、X座標値が最小値から最大値まで変化する時のUV座標値を補間しながらUV座標を求め、テクスチャ画像からそのUV座標値のピクセルをコピーしてやればいい。
この時の補間も先ほどY軸でやった方法と同じ考え方で出来る。

この方法は比較的わかりやすく、昔は速かったらしいのだが、最近は分岐があると遅いので、遅くなってしまうようだ。


関連記事・続きの記事

テクスチャマッピング アルゴリズム 毎ライン交差判定
テクスチャマッピングでポリゴンの辺を基準にするのではなく、スキャンラインを基準と... [続きを読む]

関連記事・続きの記事

2D テクスチャマッピング アルゴリズムについて
テクスチャマッピング アルゴリズムについていくつか書いた。 テクスチャマッピング... [続きを読む]


投稿者 Takenori : 2008年02月21日 17:57




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