Shadow Volume(2)

DirectX11

この間「整理する」って言ってたShadow Volume関連のアルゴリズムだけど。いろいろ検討していたら、エッジ検出アルゴリズムだけで結構な分量になりそうなのでいったんエッジ検出アルゴリズムだけまとめ。

  • エッジ判定のキモ

Shadow Volumeを作るためには、光源から見た物体の輪郭(エッジ)を見つけないといけないわけだけど、エッジって下の図に書いたような角になる部分だと思う。

図だと２の頂点がちょうど角になってる。それで、角をプログラムから判別する方法だけど、

    • 光線と法線のなす角がいったん90°に近付いてから遠ざかる場所(90°をまたぐ場所)

がエッジだと思う。本当はぴったり90°になる場所がエッジだけど、とりあえず頂点単位で処理を進めることにする。Geometry ShaderでShadow Volumeの頂点を生成するときに計算でぴったり90°になる場所を使えば正確になるだろうけど、影と物体たちで頂点の位置がずれるのはきれいに見えないかもしれないのでやめておく。


  • 仮定

アルゴリズムを決めるにあたって以下の仮定を置く

    1. 物体たちは閉じたモデルである(スキマや穴があいたりしていない)
    2. なだらかなモデル(隣り合う頂点間で法線を共有する)である
    3. 光源と三角形の各頂点からの距離がすべて等しい場合は考慮しない
    4. 凹ポリゴンの影は考慮しない

最初の仮定は対応すると面倒な気がするので(^^;

２つ目の仮定は、仮定を置くことでエッジ判定用にadjacency付き頂点データを用意する必要が無くなるので簡単のために導入する。隣り合う頂点間で法線を共有しないってことは、つまりモデルが角ばってるってことで直方体みたいな物体なんだけど、角かどうかを検出するにはある三角形だけ見ても分からないんだよね。きっと法線は全部同じ方向を向いているのである三角形だけを見ると90°をまたがなくって、隣の三角形を見ると突然法線が90°とか変化してるので「あっ、角なんだ」ってわかる感じ。図にするとこうかな。

仮に直方体みたいな角ばったモデルの影を作りたい場合はadjacency付き頂点データを用意して処理すれば良いと思う。同じ考え方でエッジ判定はできるので。adjacencyで統一しない理由は後述。

３つ目の仮定は簡単のために導入。たぶん対応もできるけど、距離が等しいってことは真正面に光源があったり三角形が超巨大だったりするようなレアケースだと思うので省略する。

最後の仮定は、単に凹ポリゴンを無視しても凸ポリゴン側がエッジになるはずできっと目立たないので簡単のために無視するだけ。どうせ１ポリゴン未満の世界なので気になる場合はバンプマップとかでPixel単位で影をつけてあげれば良いと思う。

あと、図に示したように以降のアルゴリズムでは三角形の辺が法線によって曲がっていると考えることとする。実際は三角形の辺は直線でラスタライズされるだろうけど、エッジ判定的には曲線と仮定する。曲線と考えることでadjacency無しの頂点データでもエッジを判定できるようになる。


前置きが長くなったけど、判定は以下のように行う。

    • 各三角形に対して以下の処理を行う
      • 各頂点と光源の距離を算出する(距離の２乗でもOK)
      • 各頂点で光線ベクトルと法線ベクトルの引き算をしたベクトルについて長さを求める(同じく長さの２乗でOK)
      • 各辺を構成する２頂点(全部で３辺分)について以下の判定を行う*1
        1. 光源との距離が短い方の頂点について引き算ベクトルの長さが２未満であるか？*2
        2. 光源との距離が長い方の頂点について引き算ベクトルの長さが２以上であるか？
      • 上記１と２が両方ともtrueであった場合は光源との距離が長い方をエッジ頂点と判定する
      • エッジ頂点の分布から以下の３パターンでエッジ辺を求める*3
        • エッジ頂点が共通である場合(パターン１)はエッジ頂点を含む辺をエッジ辺とする
        • エッジ頂点が共通でない場合(パターン２)はエッジ頂点にはさまれた辺をエッジ辺とする
        • エッジ頂点が１つしかない場合(パターン３)エッジ頂点を含む辺をエッジ辺とする


凸ポリゴンのみを考えているので、"90°をまたぐ"の判定は以下のように考える。

まず、光線ベクトルと法線ベクトルを２辺にもつ三角形を考えたときに、残りの１辺の長さの２乗は光線と法線のなす角が90°である場合に、ピタゴラスの定理*4から１の２乗＋１の２乗＝２となる。
このとき、光線ベクトルと法線ベクトルは正規化済みと仮定する。(ので、長さは１である)
さらに、正弦定理*5から、光線ベクトルと法線ベクトルのなす角(正確にはsin値)は対辺の長さに比例する、はず(^^;なので

    • なす角が90°未満であれば対辺の長さの２乗は２より小さい
    • なす角が90°以上であれば対辺の長さの２乗は２以上

となる。はず(^^; 幾何学的にはそんな感じに見える(ぇー
以上により、"90°をまたぐ"=="対辺の長さの２乗が２より小さい頂点と２以上の頂点で挟まれている"となる。(辺の途中のどこかになす角が90°==長さの２乗がちょうど２となる場所がある)
それで、対辺の長さの２乗は光線ベクトルと法線ベクトルを引き算して出来たベクトルの長さの２乗となる。(引き算の方向はどちらでもOK。引き算して出来たベクトルは長さが対辺と等しく、原点が引き算先？のベクトルの先っぽとなるベクトルのはず)
エッジ頂点の判定は光源から近い方でも良いと思う。判定を頂点単位とするためにどちらかに寄せてるだけ。また、エッジ辺で３パターンに分けたがエッジ頂点を含む辺をエッジ辺として統一しても変わらない気がする。このあたりは実際にいろんなモデルで表示してみないと何とも言えないかな。


  • adjacencyで統一しない理由

実際に確かめてないけど、adjacency付き頂点データってたぶんモデルデータを作るときにadjacencyを含めなきゃいけない気がする。ドライバとかでadjacencyを見つけるのは厳しいけど、モデルデータ作成時なら隣の頂点がどれかってわかるはずなので。あと、これも確かめてないけどadjacencyの頂点も座標変換とかしなきゃいけない気がするし、もしかしたらラスタライズされちゃって無駄に処理しちゃうかもしれない。
仮にそうだとすると影のためだけにadjacency付きデータを用意するかって話とかが出そうで嫌だったのでadjacency無しで処理できるアルゴリズムを目指してみた。
建物とかは角ばっているのでadjacency付きデータを用意するしかないかもしれないけど、建物はキャラクタとかに比べると高精細なモデルにしなさそうなので問題ないかなと思う。たぶん。

*1:仮定３により光源との距離が等しい場合はfalse判定とする

*2:長さの２乗を使わない場合はルート２に読み変えること

*3:Shadow Volumeはエッジ辺から引き延ばす

*4:http://ja.wikipedia.org/wiki/%E3%83%94%E3%82%BF%E3%82%B4%E3%83%A9%E3%82%B9%E3%81%AE%E5%AE%9A%E7%90%86

*5:http://ja.wikipedia.org/wiki/%E6%AD%A3%E5%BC%A6%E5%AE%9A%E7%90%86