ハイブリッド並行制約プログラミングにおける多物体衝突モデルの高速化

2004年度卒業論文
ハイブリッド並行制約プロ
グラミングにおける多物体
衝突モデルの高速化
上田研究室
1G01P069-7
飛田伸一
研究の動機と目的
• Grifonは制約に基づいてアニメー
ションを表現するためのツールであ
る
• Grifonではアニメーションの時間的
変化をハイブリッド並行制約(以下
HCC)で表現している
• HCCで多物体衝突モデルを単純に
書くと計算に膨大な時間を要する事
が分かった
• 本実験ではモデルの高速化を行い、
気軽に多物体衝突モデルを用いて
アニメーション出来るようにすること
を目的とする
多物体衝突モデルの空
間分割
• 今回プログラムを高速化するにあ
たり空間分割の手法を用いた
• ボールの数をnとすると空間分割前
のボールの衝突判定の回数はn^2
となる
• 空間を2分割すると衝突判定の回
数は1/2 n^2となる
空間分割をしていない
モデル
• 今回多物体衝突モデルの例として
ボールの衝突モデルを用いた
• 仕様
– 対象空間は2次元空間でx座標方向に150, y
座標空間に300
– ボールの半径は3
– 空間の端に当たったボールは跳ね返る
– ボール同士は衝突する
– 空気抵抗, 摩擦は考えない
• 実装
– 問題なく実装できた
半
径
は
3
150
300
空間分割をしたモデル
• 前記のモデルを空間分割して高速
化を目指す
• 仕様
– ボールが所属する空間に対応するリ
ストをつくり、それを操作する事で空間
分割を実装する
半
径
は
3
150
150
150
実験内容
• 今回はボールの数を変えて時間がどのように変化す
るかを調査した.
• また,分割したモデルと分割なしのモデルとで実行
時間がどのように変化するかも調査した.
• そこでボールの所属する空間がなるべく変わらない
ようにボールの位置とその速度を設定した.
• シミュレーション時間は10である.また各5回ずつ測
定した.
List 1
List 2
結果
ボールの数分割なし(s) 2分割(s) 4分割(s)
32
2.58
2.63
2.57
36
3.34
3.38
3.5
40
4.21
4.28
4.82
44
5.36
5.31
6.29
48
6.4
6.39
7.28
52
7.83
7.82
8.79
56
295.95
9.33
10.13
60
579.86
10.87
11.66
64
766.17
207.61
13.91
68
1024.35
352.02
16.1
72
1342.14
437.19
18.48
76
1694.19
552.32
76.36
考察
• 非常に時間が掛かっている部
分では空間分割により高速化
が可能である事が分かった
• ボールの数が少ないと空間分
割のオーバーヘッド(list操作な
ど)の方が大きくなってしまう
• 実行時間が急激に増大してい
る部分がある。研究の結果原
因は処理系にあるらしいことが
判明した
まとめ・今後の課題
• HCCにおける多物体衝突モデ
ルは空間分割により高速化で
きることが分かった
• 現在の処理系の実装では並列
にリストを操作できないので、
空間を多数分割出来ない
• 並列にリストを操作できる機能
の実装が必要である
• 他のモデルの高速化が今後の
課題である
ありがとうございました
1 2
n
2
n2

Download Report