ＣＧ: 2005年11月アーカイブ
GAME PROGRAMMING GEMSのアルゴリズム。
水平な（すべての頂点のY座標が０な）４角形があるとして、ある点P(X,Z)がその４角形の各辺からどのぐらいの割合の位置にあるのかを高速に割り出せるものです。一度に一方向（縦横/前後）しか測定できませんが、それでも高速です。
とりあえず前後方向に調べるとして
P:調べたい位置
Pl:後方の辺上の任意の点
Pt:前方の辺上の任意の点
Nl:内側を向いた後方の辺上の単位法線
Nt:内側を向いた前方の辺上の単位法線
・：ベクトルの内積
Vlp=P-Pl
Vtp=p-pt
として求める値、D(0~1の浮動小数点数値)は
D=Vlp・Nl/(Vlp・Nl + Vtp・Nt)
このDは後方の辺から前方の辺への位置の割合を示していて、後方の辺上では0.0、前方の辺上では1.0になるばかりではなく、中間では0.5、４角形から前方にはみ出すと1.0以上、後方に出ると、0.0以下と適切な値を返してくれます。この関数が驚異的なのは早さもありますが、４角形がどんな形であっても使えるということです。もちろん後方の辺と前方の辺が平行でなくても全然かまいません。すごいっすねぇ
デバック用に頂点だとか辺法線を表示してますが、一応ちゃんと当たり判定してます。あたった後の処理は減速するだけなんですが。まぁとりあえず一息つけます。
でもよく考えてみたら、これは当たり判定に使うべきではない？この限定条件ならもっと高速なアルゴリズムがあるんだろうか？
GAME PROGRAMMING GEMSにレースゲームでのコース移動距離を調べる面白いアルゴリズムが載っていたので、それを使ってモデリングで作る当たり判定領域ができないか考えています。
んで、そのためには３角ポリゴンの塊であるコースを調べて、４角ポリゴンに分けなくてはいけません。これが思ってたより難しく、手間取りました。
やり方としては
１． 最初の４角形を決める
１．１． １番目の３角形を最初の４角形の１部とする。
１．２． それに隣接する（２頂点を共有する）３角形を探す（必ず２つある）
１．３． ２つの３角形をそれぞれ元の三角形と合わせて４角形を作り、その全長が短い方を正しい４角形とする。
１．４． 最初の４角形に隣接する（２頂点を共有する）３角形を探す（必ず２つある）。そして、（どちらでもいいので）最初の３角形を次の４角形の一部とする。
２．２つ目以降の４角形を決める
２．１． 今回の４角形の一部である３角形は決まっているので、これに隣接する３角形を探す
２．２． そのうち、前回の４角形の一部ではないもの（１点しか共有しないもの）を選び、合わせて４角形を作る。
２．３． この４角形に隣接する（２頂点を共有する）３角形を探す（必ず２つある）
２．４． そのうち、前回の４角形の一部ではないもの（共有点を持たないもの）を次の４角形の１部とする。
以下 ２．１．〜２．４．を繰り返し
人間が物を見て何気なく判別してることって、コンピュータにやらせると難しいのだと改めて感じました。もっとシンプルなアルゴリズムがあるはずなので、なんか思いついたら教えてください、よろしく。
とりあえずMilkShape 3D でデータを作って、プログラムにかけました。それが次の画像。
３角ポリゴンの並んだ面が、４角ポリゴンの面になっています、成功〜。
