計測自動制御学会東北支部 第 231 回研究集会 (2006.10.31)
資料番号 231-8

DirectXによる校舎内移動シミュレーションの開発
Development of the Moving Simulation in a School Building byDirectX○大木崇嗣 ∗ ，大久保重範 ∗ , 及川一美 ∗ , 高橋達也 ∗Takashi Oki∗ , Sigenori Okubo∗ , Kazumi Oikawa∗ , Tatsuya Takahashi∗*山形大学*Yamagata University
キーワード : DirectX(DirectX)，衝突判定 (Collision Judgment), インタラクティブアニメーション (InteractiveAnimation)

連絡先 : 〒 992-8510 山形県米沢市城南 4-3-16 山形大学 工学部 機械システム工学科 大久保研究室
大久保重範，Tel.: (0238)26-3245, E-mail: sokubo@yz.yamagata-u.ac.jp

1.

緒言

3.

製作環境

近年の 3D 技術は目覚しい進化を遂げ、本物によ校舎のモデリングには 98 年升澤大志氏製作の旧り近い表現が可能となった。この 3D を利用するこ

米沢高等工業学校 (以下『旧校舎』) モデルを、人とで過去の建造物をリアルにディスプレイ上に表物には DirectX のサンプル『Tiny』を使用する。[1]示し、ユーザーが自由に中を歩き回り、見渡すこプログラムには Visual Studio.NET、DirectX にはとが出来れば写真や動画では伝わらない臨場感がDirectX SDK(December 2004) を使用する。

出せるのではないかと思われる。そこで本研究では、DirectX を用いて旧米沢高等工業学校の中を自由に歩きまわれるリアルインタラクティブアニ

4.

衝突判定

4.1

以前の判定方法メーションの製作を行い、リアルさを出すために人物と壁との衝突の表現を第一の目的とする。

2.

DirectX

DirectX とは、Microsoft 社が同社の Windows シリーズのマルチメディア機能を強化するために提供している拡張 API 群の事であり、DirectGraphics、DirectMusic、DirectInput、DirectPlay、DirectShowの 5 つからなる。

–1–

Fig.1:Ray Tracing.

これまで使用していた方法は、レイと呼ばれる線

この直方体の縦と横の長さを、作りたい球の半径分を4方向に飛ばし、旧校舎モデルのポリゴンの表で割る事で球が半径分重なった状態で並んだ個数裏判定を行うことで衝突判定を行っていたが、こが割り出せるので、その数分だけ球を配置する。の方法はモデルのポリゴンを 1 フレーム毎に全部この状態からモデルの形に沿って球の座標を移動調べているので大変非効率であると共に大変重いさせるが、ここで以前の判定方法で使用していた処理であった。

レイを使用して形をトレースする。

4.2

新しい判定方法

新しく考えた方法は、バウンディング球を使用した判定方法である。バウンディング球という球状のポリゴンを使用し、球体同士で判定を行う方法である。球体同士の交差判定は半径の大小だけで判断できるので高速な処理方法として利用されているが、球体でモデルを囲った場合、モデルのFig.3:Setting Bounding Sphere.

存在しない部分にも範囲が及んでしまい、判定が甘くなるという欠点がある。

球の中心から 4 方向にレイを飛ばし、レイがモデ

その欠点を補うには球の半径を小さくし、モデルの形に沿って沢山配置することで解消できるのではないかと考えた。しかし、モデルの形毎に手作業で球を配置するのは大変なので、モデルの形ルと接触した場合、モデルと球との距離を測定し、その距離だけ球を移動させることでモデルに沿って配置することが出来る。それを全ての球に対して行なう事で Fig.3 の様にする事が出来た。に沿って自動で球を並べる方法を考えた。

5.

自動生成

モデルの形を調べる為に、まずモデルを囲む最小の大きさの直方体を作る。これは、モデルの右上と左下の座標から作成することが出来る。

Fig.4:Moved Bounding Sphere.
現在は 2 方向以上レイがモデルと衝突を検出した
場合、距離の長い方向に移動させている為、同じ場所に固まってしまうという現象が生じた。そこで、次に球体同士が重なっているかを調べる方法を考えた。

Fig.2:Create Bounding Box.

–2–6.

3 種類の検索方法

3) 長さ 2nの配列 Xを用意し、そこに Sxyz 、Exyzを格納する。

どの球体と重なっているかを調べる為に次に記

4) 配列 X を昇順に並び替える。

す 3 種類の検索方法を実装し、それぞれの検索時間を比較した。[2]6.1

5) Xj について次の処理を行う。
(a) Xj = (Sx )i 、Xj+1 = (Ex )i であれば Oi

総当り法

は衝突判定のリストに加えない。
この方法は全部の球の座標を調べ、指定した範(b) Xj = (Sx )i 、Xj+h = (Ex )i の時、Xj+s

囲内に別の球の座標が存在した場合に検出とみなに格納されている物体を判定リストにす方法である。しかし、調べる数は球の全体数の加える。(0 < s < h)

二乗オーダで増加していく為、数が多い場合には

6) リストに加えられた物体だけで今度は Z 軸に不向きである。

ついて 2 の方法を使用する。

6.2

原点距離比較法

7) 残った物体のみで衝突判定を行う。

この方法は原点と球との距離を調べ、調べたい球の距離と近い距離の球だけを抜き出して検索す

7.

測定結果る方法である。アルゴリズムは以下の通りである。

Table.1に生成個数と生成時間の平均を、Fig.4に
1) 球体数を n 個で Oi (i = 0 · · · n) とし、球の半径XYZ 法と原点比較法のグラフを記す。

を r とする。

Table.1:Processing time.
生成個数 (個)14055018322) 原点からの距離 Di を測定する。
3) Di を基準に、物体を昇順に並べ替える。
4) ある物体 Oi について以下の処理を行う。

5492

総当り法

9.77

199.3

2252.220237.2

原点比較法

0.27

1.20

3.60

11.10

XYZ 法0.33

1.33

3.77

11.30
単位 (ms)(a) Oi+h (h = 1, 2, 3 · · · ) との距離の差を Diと Di+h から求める。

(b) 差が r 以下なら衝突判定を行う。

6.3

XYZ 法

3 つ目の方法は、3 軸毎に順次調べていく方法で
Fig.5:Compare Collision Judgment.

ある。アルゴリズムは以下の通りである。

1) 球体数を n 個で Oi (i = 0 · · · n) とし、球の半径を r とする。

グラフの通り、XYZ 法と原点比較法はほぼ同じ検索速度となった。しかし、次に示す検索の為の準2) (球の中心座標-r) を Sxyz 、(球の中心座標+r)

備時間で差が現れた。

を Exyz を設定する。

–3–

生成個数 (個)Table.2:Setting time.
14055018325492

原点比較法

141.52314.1

27411.6

263469.9

XYZ 法

178.7

3058.034541.0350150.4

単位 (ms)Fig.8:Alrady-known Ploblem(2).
Fig.7 の様に、レイがモデルと触れない部分の球はその場から動かないようにしている為、無駄な球が出来てしまう。また、Fig.8の凸型モデルの場合、Fig.6:Compare Setting time.

2方向以上壁を検出する場合は距離の遠い方へ移動
準備時間は、球の数が多くなるに連れて XYZ 法の時間が増え始めた。XYZ 法は配列に球の全体数の2 倍用意する必要がある為、数が増えるにつれて差が顕著に現れたのではないかと考えられる。この結果より、全体的に一番速度の速かった原点距させているのでそこの部分は球の密度が薄くなってしまう。今後は、レイがモデルと触れない球を再利用し、2 方向以上検出した場合は片方に移動させるのではなく、球を一つ増やして両方へ移動させる等の方法を考えている。

離比較法を使用する事にした。

8.

現在の問題点9.

結言

今回は新しく実装した衝突判定の方法について述べた。今後は現在わかっている問題点の解消をしていきたい。

参考文献
1) 升澤大志: コンピュータグラフィックスに関する研究, 山形大学大学院修士論文 (1998)

2) 大森祐:複数基準によるシリアライズを利用しFig.7:Alrady-known Ploblem(1).

た衝突判定の高速化アルゴリズムに関する研究, 東京工科大学卒業論文 (2002)–4–