w 0 が解

連続接触判定
回転速度を少し考えるタイプが可能か?
• Minkowski Sumと原点が触れるときが衝突
v
v+w
回転がない場合
v
回転で接触するとき
• 原点の速度を求めて使えばよい。
v+w
原点の速度といっても
• Minkowski和なので、
原点は1箇所ではない
• どこをとるのか?
– 一番相対速度が大きいところ
• 両端
どの向き?
並進速度が少ない場合は、
一度向きを求めないとだめかも?
一度向きを求めると?
新接触判定
• CCD 連続接触判定
– 回転を考えないタイプは非常に少ない計算量で
実現可能
– GJKの改良
接触時刻と判定
r
z 右側当たらない
左側そのうち当たるかも
中:よく分からない
そのうち当たる
すでに当たってる
当たってた
当たらない
黒以外の場合
1. 時刻を昔に戻す
2. 最初に接触する点を求める
未来
過去
連続接触 2D投影版(ミスあり)
初期処理
相対速度ベクトルr
•
v0 : =r v0のsupportをw0
w2
w3
•
o→w0 (z:=0)をv1そのsupportをw1
(v1=0:w0が解,oがw1の外:解なし)
w4
•
o→w0-w1をv2 (v2=0ならv2= v0 + v1)
そのsupportをw2
繰り返し処理
oが△w0w1w2の1辺からはみ出す間:
1.
はみ出すのは, w0-w2 かw1-w2
はみ出した辺 がw0-w2:
w:=o→w0-w2のsupport, w1:=w2,
はみ出した辺 がw1-w2:
w:=o→w1-w2のsupport, w0:=w2,
oがwの外 or w= w1 or w=w2 :解なし
w2 : =w
oが2辺からはみ出した場合: assert
oが△ w0w1w2の内部の場合:
1.
△w0w1w2の法線を v, supportをw
w=wi: oと△w0w1w2の交点が解
新しいwを次ページの方法でwiを決
めて置き換え.
o
w1
w0
線分探索: oがw0w1上に乗っているとき,
v0
解の解釈
△の内部: 接触法線=△法線
エッジ: 接触法線=r-rのエッジ成分
頂点:接触法線=r
連続接触 2D投影版( 2007.12.27修正)
初期処理
•
v0 : =r v0のsupportをw0
•
o→w0 (z:=0)をv1そのsupportをw1
(v1=0:w0が解,oがw1の外:解なし)
•
o→w0-w1をv2 (v2=0ならv2= v0 + v1)
そのsupportをw2
繰り返し処理
oが△w0w1w2の1辺からはみ出す間:
1.
はみ出すのは, w0-w2 かw1-w2
はみ出した辺 がw0-w2:
w:=o→w0-w2のsupport, w1:=w2,
はみ出した辺 がw1-w2:
w:=o→w1-w2のsupport, w0:=w2,
oがwの外 or w= w1 or w=w2 :解なし
w2 : =w
GJK処理
oが△w0w1w2の内部にあるとき
- △w0w1w2の法線で新しいwを求める。
- w と2点を使ってoを含む三角形を見つける。
相対速度ベクトルr
w2
w3
w4
o
w1
w0
GJK処理終了条件
すでに出ているsupport点と同じ点が出たとき
辺の選択
頂点は正しい順に並んでいる
新しい点と1辺で新しい三角形を作る
原点を含む三角形は?
1.三角形を作ってみる
2.各辺と原点の有向距離を求める.
3.最大有向距離を求める
4.最大有向距離が最小になる
三角形を選ぶ
連続GJK(by Gino)
3
2
相対速度
1
連続GJK(by Gino)
3
2
相対速度
1
以降OBSOLUTE
三角形の選択
外積の符号を見る.
(wi+1-w) ^ (wi-w) >0となるように頂点を並べる
(o-w)^ (wi-w)<0かつ(o-w)^ (wi+1-w)>0
eexi =0のとき,△i はつぶれているので使わない
全部つぶれているときは,近い2点wiwjと
vivj法線をつくる.
辺・頂点が重なった場合
-
-
+ -
+
+ 0
0
-
+ 0
-
-
0
0
-
0
0
0
-
0
+
0
0 0
+-がそろわない:
0が3つ:
wNewに近いw[i]を置き換え
-
0
+
+
0
-
-
最近傍点の求め方
b
p = ta+(1-t)b
p*(b-a) = 0
a
l = (b-a)
(ta+(1-t)b)*(b-a)
= (tab+(1-t)bb)-(taa+(1-t)ab)
=(2ab-bb-aa)t+bb-ab
t(b-a)^2 = b(b-a)
t = b(b-a)/(b-a)^2
= bb – ba / (aa +bb-2ab)
p = (b(b-a)/(b-a)^2)a
+(a(a-b)/(b-a)^2)b
=(bl/l^2)a - (al/l^2)b
最近傍点の求め方
a
b
p = sa+tb+uc
l = (b-a)
(a-b)*p = 0
(b-c)*p = 0
(c-a)*p = 0
p
c
p=ann
n
s
 
a b c  t   p  nna
u 
 
s
 
a  p b  p c  p  t   0
u 
 
最近傍点を探すか、交点を探すか
• 最近傍点 vs 相対速度ベクトルとの交点
最近傍点 ×
交点 ○
法線が動くので最近傍点も動く
内積計算を6回やる必要あり
相対速度ベクトルの向きは変わらない
どちらに入っているかの判定は,
増えた3線だけでよい
CCDGJKと法線
速度の考え方
凸形状単位で
まずその場で回って,
その後並進したと考える
Meshとの接触判定
一般Mesh対Convex
Boundingについて
• 最初のBoundingは本当にAABBが良いのか?
AABB
更新:
判定:
球
更新:
判定:
• 2番目以降は?
supportを6回計算
和・比較
なし
和・比較