Tips: 単純な衝突判定について
■ 主旨
衝突判定のアルゴリズムには様々なものが存在しますが、ここではおそらく最も単純であろうベクトルと三角形ポリゴンとの衝突判定を取り上げます。 計算方法などの詳細は PDF 版を御覧下さい。 三角形以上のポリゴンのサポートや、球との判定、ポリゴン同士の判定など、様々なアプローチに興味がある人は各自で考えてみて下さい。 ちなみに、coldet と言う素敵なライブラリも存在しますのでこれを利用するのも手でしょう。
simple collision
↑キー(ijkm)でベクトルを移動できます。
■ ヒント
今回もサンプルを用意しました。 このファイルには、衝突判定のサンプルの他に、犬が動く中途のサンプルプログラムも入っています。

とりあえず衝突判定ルーチンが完成すれば、あとは前回作成した tri ファイルから衝突用のポリゴン群を作り出すこともできると思います。 ac3d で作成したモデルに対し、そのまま任意のベクトルとの衝突判定が実現できるはずです。
しかしそこで問題になるのは、効率や処理速度となるでしょう。 下記の画像にある粒子が落ちるサンプルプログラムでは、全体的に処理数が少ないので目立ちませんが、これが数百数千ものポリゴンやベクトルに及ぶ場合、それらを相互に全て衝突検査するのは非効率的です。 もしそのようなシーンが必要になった場合は、衝突の検査に Octree や Binary Space Partition (BSP) などに代表される効率化のためのアルゴリズムを考慮しなくてはいけません。
それらについての説明は省略しますが、今回紹介した単純なアルゴリズムと BSP を組み合わせるだけでも、多少複雑なモデル(例えば部屋)でもウォークスルーが高速化できます。

drop
↑複数のポリゴンと粒子の衝突

[ 戻る ]

Written by Yasuhiro Yamazaki, 2001.