Pebble In The Sky - Tech

当たり判定用コースの判別

GAME PROGRAMMING GEMSにレースゲームでのコース移動距離を調べる面白いアルゴリズムが載っていたので、それを使ってモデリングで作る当たり判定領域ができないか考えています。

んで、そのためには３角ポリゴンの塊であるコースを調べて、４角ポリゴンに分けなくてはいけません。これが思ってたより難しく、手間取りました。

やり方としては
１．　最初の４角形を決める
　１．１．　１番目の３角形を最初の４角形の１部とする。
　１．２．　それに隣接する（２頂点を共有する）３角形を探す（必ず２つある）
　１．３．　２つの３角形をそれぞれ元の三角形と合わせて４角形を作り、その全長が短い方を正しい４角形とする。
　１．４．　最初の４角形に隣接する（２頂点を共有する）３角形を探す（必ず２つある）。そして、（どちらでもいいので）最初の３角形を次の４角形の一部とする。

２．２つ目以降の４角形を決める
　２．１．　今回の４角形の一部である３角形は決まっているので、これに隣接する３角形を探す
　２．２．　そのうち、前回の４角形の一部ではないもの（１点しか共有しないもの）を選び、合わせて４角形を作る。
　２．３．　この４角形に隣接する（２頂点を共有する）３角形を探す（必ず２つある）
　２．４．　そのうち、前回の４角形の一部ではないもの（共有点を持たないもの）を次の４角形の１部とする。
　以下　２．１．〜２．４．を繰り返し

人間が物を見て何気なく判別してることって、コンピュータにやらせると難しいのだと改めて感じました。もっとシンプルなアルゴリズムがあるはずなので、なんか思いついたら教えてください、よろしく。

とりあえずMilkShape 3D でデータを作って、プログラムにかけました。それが次の画像。

３角ポリゴンの並んだ面が、４角ポリゴンの面になっています、成功〜。

投稿者 robosheep : 2005年11月12日 22:39

トラックバック

このエントリーのトラックバックURL:
http://render.s73.xrea.com/mt/mt-tb.cgi/552

コメント

投稿者 robosheep : 2005年11月13日 08:57