連続接触判定 回転速度を少し考えるタイプが可能か？ • Minkowski Sumと原点が触れるときが衝突 v v+w 回転がない場合 v 回転で接触するとき • 原点の速度を求めて使えばよい。 v+w 原点の速度といっても • Minkowski和なので、 原点は１箇所ではない • どこをとるのか？ – 一番相対速度が大きいところ • 両端 どの向き？ 並進速度が少ない場合は、 一度向きを求めないとだめかも？ 一度向きを求めると？ 新接触判定 • CCD 連続接触判定 – 回転を考えないタイプは非常に少ない計算量で 実現可能 – GJKの改良 接触時刻と判定 r z 右側当たらない 左側そのうち当たるかも 中：よく分からない そのうち当たる すでに当たってる 当たってた 当たらない 黒以外の場合 1. 時刻を昔に戻す 2. 最初に接触する点を求める 未来 過去 連続接触 ２D投影版（ミスあり） 初期処理 相対速度ベクトル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. はみ出すのは， 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が２辺からはみ出した場合： assert oが△ w0w1w2の内部の場合： 1. △w0w1w2の法線を v, supportをw w=wi： oと△w0w1w2の交点が解 新しいwを次ページの方法でwiを決 めて置き換え． o w1 w0 線分探索: oがw0w1上に乗っているとき， v0 解の解釈 △の内部： 接触法線=△法線 エッジ： 接触法線=r-rのエッジ成分 頂点：接触法線=r 連続接触 ２D投影版（ 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. はみ出すのは， 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 と２点を使ってoを含む三角形を見つける。 相対速度ベクトルr w2 w3 w4 o w1 w0 GJK処理終了条件 すでに出ているsupport点と同じ点が出たとき 辺の選択 頂点は正しい順に並んでいる 新しい点と1辺で新しい三角形を作る 原点を含む三角形は？ １．三角形を作ってみる ２．各辺と原点の有向距離を求める． ３．最大有向距離を求める ４．最大有向距離が最小になる 三角形を選ぶ 連続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 相対速度ベクトルとの交点 最近傍点 × 交点 ○ 法線が動くので最近傍点も動く 内積計算を６回やる必要あり 相対速度ベクトルの向きは変わらない どちらに入っているかの判定は， 増えた3線だけでよい CCDGJKと法線 速度の考え方 凸形状単位で まずその場で回って， その後並進したと考える Meshとの接触判定 一般Mesh対Convex Boundingについて • 最初のBoundingは本当にAABBが良いのか？ AABB 更新： 判定： 球 更新： 判定： • ２番目以降は？ supportを６回計算 和・比較 なし 和・比較
© Copyright 2024 ExpyDoc
