衝突判定のアルゴリズム
3 次元空間での 2 つの図形の衝突判定を行う計算方法の説明です。
衝突判定 /
距離計算 /
戻る /
トップページ
衝突判定
- 2 つの図形の衝突判定 (コリジョン判定) のアルゴリズムをまとめます。
図が用意できておらず見難いですが、ご勘弁を。
太字はベクトルを表します。
-
- 線分と三角形
-
- 線分を p+tl、
三角形を (1-u-v)q0+uq1+vq2
で表します (t, u, v は媒介変数)。
Tomas Moller のアルゴリズム
|
[-l (q1-q0) (q2-q0)]
|
|t|
|u|
|v|
|
= |
(p-q0)
|
を Cramer の公式で解きます。
0.0≦t≦1.0, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。
-
- 半直線と三角形
-
- 線分と三角形の場合と同様の計算を行います。
0.0≦t, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。
-
- 点と球
-
- 点と球の中心の距離の 2 乗を求めて、
その長さが球の半径の 2 乗以下なら交差と判定します。
-
- 線分と球
-
- 線分の始点から終点へのベクトルを v、
線分の始点から球の中心へのベクトルを c とします。
-
v・c<0 の時、球の中心が線分の始点よりも線分から遠くにあるので、
c の長さが球の半径よりも小さければ交差と判定します。
-
v・c≧0 の時、v・c と v2 の長さを比べます
(v 方向での c の長さと v の比較)。
-
v・c の方が大きければ、球の中心が線分の終点よりも線分から遠くにあるので、
線分の終点と球の中心の距離の 2 乗を求めて、
球の半径の 2 乗よりも小さければ交差と判定します。
-
v2 の方が大きければ、球の中心から線分に降ろした足が線分上に
存在するはずです。
c2-(v・c)2/v2 でその長さの 2 乗が分かり、
球の半径の 2 乗よりも小さければ交差と判定します。
-
- 条件分けが多いため、計算効率が悪く、ゲームなどでの使用は非実用的です。
-
- 半直線と球
-
- 半直線の方向ベクトルを v、半直線の始点から球の中心へを c とします。
-
v・c<0 の時、球の中心が半直線の始点よりも線が伸びていない方向にあるので、
c の長さが球の半径よりも小さければ交差と判定します。
-
v・c≧0 の時、球の中心から半直線に降ろした足が半直線上に存在するはずです。
c2-(v・c)2/v2
でその長さの2乗が分かり、球の半径の2乗よりも小さければ交差と判定します。
-
- 球と球
-
- それぞれの球の中心間の距離の 2 乗を求め、
球の半径の和の 2 乗以下なら交差と判定します。
-
- 点と AABB (Axis Aligned Bounding Box : 辺が座標軸に平行な直方体)
-
- 各軸について、AABB の両面の間に点が存在すれば交差と判定します。
-
- 半直線と箱
-
- 箱の各面に関して次の判定を行います。
一つでも満たしていれば交差と判定します。
-
箱の面を含む平面と半直線を含む直線の交点を求めて、
その点が箱の面内、半直線上にあるならば交差と判定します。
-
- 条件分けが多いため、計算効率が悪く、ゲームなどでの使用は非実用的です。
-
- AABB と AABB
-
- 各軸について次の判定を行い、全て満たしていれば交差と判定します。
-
一方の両面の座標を小さい方から u0, u1、もう一方の両面の座標を
小さい方から v0, v1 とするとき､ !(u1<v0 || v1<u0) かどうか。
-
- 球と三角形
-
- 次の順に判定します。
-
三角形を含む平面と球の中心との距離が球の半径を越えていたら
非交差と判定します。
-
球の中心から三角形を含む平面へ下ろした足を p+t(-n)、
三角形を (1-u-v)q0+uq1+vq2
で表します (t, u, v は媒介変数、n は三角形の法線)。
Tomas Moller のアルゴリズム
|
[n (q1-q0) (q2-q0)]
|
|t|
|u|
|v|
|
= |
(p-q0)
|
を Cramer の公式で解きます。
0.0≦u, 0.0≦v, u+v≦1.0 なら交差と判定します。
-
球の中心と三角形の最短距離を求めて、球の半径よりも小さければ交差と判定します。
最短距離候補として、三角形の3頂点と球の中心との距離の最小値、
もしくは三角形の各辺と球の中心との距離の最小値があります。
-
u<0.0, 1.0<v, 1.0<u+v の時 q2 と球の中心との距離
-
v<0.0, 1.0<u, 1.0<u+v の時 q1 と球の中心との距離
-
u<0.0, v<0.0, u+v<1.0 の時 q0 と球の中心との距離
が最短距離になります。
いずれでもない時、
-
u<0.0 なら線分q0q1 と球の中心との距離、
-
v<0.0 なら線分q0q2と球の中心との距離、
-
1.0<u+v なら線分q1q2と球の中心との距離
が最短距離になります。
ただし、この u, v の値の範囲による場合分けは、
三角形に鈍角が含まれていると破綻するため、ボロノイ領域を厳密に求めるか、
全て求めて最小値を取った方が良いです。
-
- 条件分けが多いため、計算効率が悪く、ゲームなどでの使用は非実用的です。
-
- 円柱と点
-
- 円柱の軸と底面の交差する 2 点を結ぶベクトルを a、
その 1 点から判定対象の点へのベクトルを v とします。
v・a の長さが 0.0 以下であったり、a2 以上であれば、
点は底面よりも遠くにあるので、非交差と判定します。
そうでなければ、v2-(v・a)2/(a2) で
点から円柱の軸への足の長さの 2 乗が求まるので、
円柱の半径の 2 乗よりも小さければ交差と判定します。
-
- 円柱と半直線
-
- 円柱の軸と半直線共に直交する線分 v を求めます。
そして、円柱の一方の底面の中心から半直線の始点へのベクトルを求めて、
v 上へ投影します。
その長さが円柱の半径よりも長ければ非交差と判定します。
半径よりも小さければ、
交点が円柱の軸方向で中に収まっており、かつ半直線上にあるかどうかで判断します。
-
- 円柱と線分
-
- 円柱の軸と線分共に直交する線分 v を求めます。
円柱の一方の底面の中心から線分の始点へのベクトルを求めて、
v 上へ投影します。
その長さが円柱の半径よりも長ければ非交差と判定します。
半径よりも小さければ、
交点が円柱の軸方向で中に収まっており、かつ線分上にあるかどうかで判断します。
-
- 円柱と三角形
-
- 円柱の軸が Y 座標になるような座標系に変換して考えます。
まず、三角形を円柱の底面でクリッピングします。
これで、X, Z 座標系へ投影して、2 次元での判定問題へ落としこめます。
三角形の各辺が円柱の円の中に含まれているかどうかを
円柱の円の中心と、三角形の辺の線分との距離が、
円柱の円の半径より小さいかどうかで判断します。
いずれも交差しない場合には三角形内部に円が含まれて
いないかどうかの可能性も判断します。
-
- クリッピングなど計算が複雑なために計算効率が悪く、
ゲームなどでの使用は非実用的です。
-
- 円柱と球
-
- 円柱の軸と底面の交差する2点を結ぶベクトルを a とします。
また、その 1 点から球の中心へのベクトルを v とします。
-
0.0≦|v・a|≦a2 あれば、
v2-(v・a)2/(a2)
で球の中心から円柱の軸への足の長さの 2 乗が
求まるので、円柱の半径+球の半径の 2 乗よりも小さければ交差と判定します。
-
v・a/|a| が-球の半径よりも小さかったり、|a|+球の半径
より大きければ非交差と判定します。
-
いずれでもなければ、次のようにします。
円柱の底面を含む平面と球の中心の距離を求めます。
球の半径の 2 乗からその距離の 2 乗を引くと、
円柱の底面を含む平面と球の交差によってできる、
円の半径の 2 乗が得られます。
この円の半径と円柱の底面の半径の和が、
円の中心と底面の中心の間の距離よりも大きければ、交差と判定します。
-
- 条件分けが多いため、計算効率が悪く、ゲームなどでの使用は非実用的です。
-
- 球の軌跡 (Capped Cylinder, LSS =Line Swept Sphere) と球
-
- 軌跡を描く球の半径分だけ球の半径を大きくし、
球と線分の交差問題に置き換えます。
-
- 球の軌跡と三角形
-
- 三角形を球の半径分太らせて、
その図形と線分との交差判定問題に置き換えます。
太った三角形は頂点を中心とした球 3 つ、辺にそった円柱 3 つ、
三角形内部の板形状に分解できるので、各々について判定します。
-
- 別解として、「線分対三角形」「LSS 対線分」「LSS 対球」の3つの判定を
組み合わせる方法もあるようです。
-
- 球の軌跡と半直線
-
- 球の始点と終点を結ぶ線分を軸とした円柱、
始点・終点の球の 3 つの図形と半直線の交差で判定します。
-
- 円柱と平面
-
- 円柱の底面の中心 2 点が平面に対して反対側にあるならば、交差と判定します。
円柱の軸と平面の法線の外積で、円柱を縦に切断する平面と直交する平面の
法線が求まります。
この直交平面上では円柱は長方形になっており、
また円柱と平面の最近接点はこの平面上にあります。
直交平面の法線と、円柱の軸の外積から円柱の底面の中心から最近接点へ伸びる
ベクトルが 2 本求まります。
円柱の底面の中心に足すことで、円柱上の平面に最も近い点となる
候補点が 2 点求まります (直交平面上に存在し、円柱の底面の円上の点)。
この 2 点が平面に対して反対側にあれば交差と判定します。
-
- 球と円錐
-
- 球の中心、円錐の底面の中心、円錐の頂点を通る平面を考えます。
この平面と円錐の側面との交線 2 本のうち、
円錐の軸に対して球の中心に近い方を l
(円錐の頂点から底面と交線の交わる点までのベクトル) とします。
このとき、平面上で、l に対して球の中心が円錐の軸側にあれば交差と判定します。
それ以外の場合、線分 l と球の中心との距離を求め、
球の半径よりも小さければ交差と判定します。
距離計算
- 2 つの図形の距離計算のアルゴリズムをまとめます。
-
- 点と点
-
- 2 点間を結ぶベクトルの長さです。点 a, b に対して
|a-b| が距離になります。
-
- 点と直線
-
- 直線の方向ベクトル (長さ1) を v とします。
直線上の一点から点へのベクトルを p とすると、
p-(p・v)v で直線から点へ最短距離で結ぶベクトルが求まるので、
これが距離になります。
-
- 点と三角形
-
- 点から三角形の 1 頂点へのベクトルを v とします。
三角形の法線と v の内積が距離になります。
-
- 点と線分
-
- 線分を v とする。線分の始点から点まで伸びるベクトルを p とする。
v・p が 0.0 以上、|v|2 以下なら点から線分に伸ばした足は線分上に
存在し、その足の長さ (点と線分を含んだ直線との距離) が距離の値になる。
v・p が 0.0 以下であれば、線分の始点から点までの距離が、v・p が
|v|2 以上なら線分の終点から点までの距離が求めたい距離になる。
-
- 線分と三角形
-
- 線分を p+tl、
三角形を (1-u-v)q0+uq1+vq2
で表します (t, u, v は媒介変数)。
Tomas Moller のアルゴリズム
|
[-l (q1-q0) (q2-q0)]
|
|t|
|u|
|v|
|
= |
(p-q0)
|
を Cramer の公式で解きます。
0.0≦u, 0.0≦v, u+v≦1.0 なら交差しています。
|l|t で、p から交点までの距離が求まります。
-
- 半直線と三角形
-
- 線分と三角形の場合と同様です。
0.0≦t, 0.0≦u, 0.0≦v, u+v≦1.0 なら交差しています。
|l|t で、p から交点までの距離が求まります。
戻る