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

2004年度卒業論文紹介
ハイブリッド並行制約プログラミング
における多物体衝突モデルの高速
化
上田研究室
3605U085-0
飛田伸一
1
研究の概要
Grifonは制約に基づいてアニメーションを表現する
ためのツールである
Grifonではアニメーションの時間的変化をハイブ
リッド並行制約(以下HCC)で表現している
HCCで多物体衝突モデルを単純に書くと計算に膨
大な時間を要する事が分かった
本研究ではモデルの高速化を行い,気軽に多物体
衝突モデルを用いてアニメーション出来るようにす
ることを目的とする
2
ボールの衝突モデル
今回多物体衝突モデルの例としてボールの衝突
モデルを用いた
仕様





対象空間は2次元空間でx座標方向に150, y座標空間に300
ボールの半径は全て3
空間の端に当たったボールは跳ね返る
ボール同士は衝突する
空気抵抗, 摩擦は考えない
実装

半
径
は
3
ソースは別紙参照のこと
150
300
3
多物体衝突モデルの空間分割
多物体衝突モデルHCCプログラム高速化の手法



空間分割
ask制約(if文など)の削減
default制約(unless文など)の削減
空間分割



ボールの数をnとする
2
空間分割前のボールの衝突判定の回数は n n  n
1
1
1
n
n

n

2

空間を2分割すると衝突判定の回数は 2 2
2
2
→今回は空間分割を使う
4
空間分割をしたモデル
仕様


空間,ボールの大きさは前のモデルと同じとする
所属空間に存在するボールの間だけで衝突判定を行
う
実装

空
間
は
リ150
ス
ト
ボールが所属する空間に対応するリストをつくり,それ
を操作する事で空間分割を実装する
半
径
は
3
150
150
5
実験内容
ボールの個数,空間分割数を変えてプログラムの実行時間がどのよ
うに変化するかを調査した
空間分割の成果が出るようにするために,ボールの所属する空間が
なるべく変わらないようボールの位置とその速度を設定(下図参
照)
シミュレーション時間は10である.5回ずつ測定し,実行時間が最短
だったデータを採用した
List 1
List 2
6
結果
ボールの数分割なし(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
ボールの数32～76の部分を抜粋
ボールの数56以上で黄色の部分は
約3倍の高速化ができている
7
考察
ボールの数が少ないと空間分割した方が実行時
間が多くなってしまう
原因:リスト操作などのオーバーヘッド
実行時間が急激に増大
原因:処理系がサンプルを取るたびにPointフェーズ
とIntervalフェーズを繰返していることによるオー
バーヘッド(処理系の詳細モードで調査)
8
まとめ・今後の課題
まとめ

HCCにおける多物体衝突モデルは空間分割により高速
化できた
今後の課題


現在の処理系の実装では並列にリストを操作できない
ので,空間を多数に分割出来ない
並列にリストを操作できる機能の実装が必要
他のモデルの高速化
9
終わり
10
おまけ -前期にやりたいことGrifonのアニメーションの保存



SVG形式
avi,mpgなどの通常の動画フォーマット
Grifon独自のフォーマット
形状変化する物体のアニメーション

ボールが弾む時に歪むアニメーション
11

Download Report