« テクスチャマッピング アルゴリズム 最大最小法 | メイン | テクスチャマッピング アルゴリズム 辺沿いに描画 »
2008年02月21日
基本テクニック:: テクスチャマッピング アルゴリズム 毎ライン交差判定
Tweet @jin1016をフォローテクスチャマッピングでポリゴンの辺を基準にするのではなく、スキャンラインを基準として、各 Y 座標値で各辺と交差判定し、その間を補間しながら描画する方法がある。
まず、以下の図のようなポリゴンがあったとする。
最初に全ての頂点で Y 軸の最小値と最大値を求める ( 図では 0 と 14 が当てはまる ) 。
次にこの Y 軸の最小値から最大値までのスキャンラインで交差判定していく。
交差判定は単純に、辺 0-1、辺 1-2、辺 2-0 の順で行い、最初に交差した2点間を描画する。
交差するかどうかの判定は、単純に 2 頂点の Y 軸値の間に現在のスキャンラインの Y 軸値が入っているかどうかで判定できる。
交差していた場合は、その Y 座標値での、X 座標値と UV 座標値を求める。
辺 0-1 間なら、k = ( y - y0 ) / ( y1 - y0 ) で Y 座標の比を求める。
後は、これを用いて計算する。
x = x0 + k * ( x1 - x0 );
u = u0 + k * ( u1 - u0 );
v = v0 + k * ( v1 - v0 );
このようにして求めた X 座標値と UV 座標値は、右か左端のどちらかの 1 点となる。
同様にして、辺 1-2、辺 2-0 と順に交差判定と計算を行い、最初に交差した 2 点を使う。
交差した 2 点は、右左がわからないので、X 座標値で大小判定し、左と右を決定する。
後は X 座標値が小さい方 ( 左 ) から、大きい方へ向かって、UV 座標値を補間しつつ、テクスチャ画像のその UV 座標からピクセルを現在の XY 座標にコピーしていけばいい。
この時上の Y 座標値のように計算していたのでは重いので、X 座標値が 1 増えると UV 座標値がいくら増えるか求めて、後はその変化量を加算して行って求める。
毎ライン交差判定するので重そうだが、思っているよりは軽い。
また、毎ライン交差位置を計算するので、誤差は軽減される。
関連記事・続きの記事
2D テクスチャマッピング アルゴリズムについて
テクスチャマッピング アルゴリズムについていくつか書いた。 テクスチャマッピング... [続きを読む]
投稿者 Takenori : 2008年02月21日 20:08
comments powered by Disqus