堅牢な衝突検出アルゴリズムを探していて、Christer Ericson によるRealtime Collision Detectionという素晴らしい本を見つけました。特定の点が凸多面体の内部にあるかどうかをチェックする特定のアルゴリズムを使用しようとしています (3D 空間では、これらは四角錐、立方体、および四面体 (別名、すべての辺が三角形であるピラミッド) です)。私の場合、四角錐があります。ポイントの検証は、指定された数の半空間の交差ボリュームを使用し、多面体の側面によって張られるすべての平面の前または後ろにポイントがあるかどうかを判断することによって行われます。n特定の多面体の半空間の数を表す引数 (以下を参照) の使用法を理解するのが困難です。
// Test if point p inside polyhedron given as the intersection volume of n halfspaces
int TestPointPolyhedron(Point p, Plane *h, int n) {
for (int i = 0; i < n; i++) {
if(DistPointPlane(p, h[i]) > 0.0f) return 0;
}
return 1;
}
DistPointPlane(...)与えられた点と平面の間の距離を計算して
float DistPointPlane(Point q, Plane p) {
return Dot(q, p.n) - p.d;
}
3D空間で平面をPlane表す構造であること
struct Plane {
Vector n; // Plane normal. Point X on the plane satisfies Dot(n, X) = d
float d; // d = dot(n, p) for a given point on the plane
}
Plane ComputePlane(Point a, Point b, Point c) {
Plane p;
p.n = Normalize(Cross(b - a, c - a));
p.d = Dot(p.n, a);
return p;
}
アルゴリズムが行うことは、基本的に次のとおりです。
- 与えられた点について、凸多面体の各平面までの距離を計算します
- 距離が負か正かをチェック
- 距離が負の場合、ポイントは平面の法線の反対側にあるため、その後ろにあります。
- それ以外の点は平面の法線と同じ側にあるため、その前にあります
- 指定された多面体のすべての平面の後ろを指している場合は内側にあり、そうでない場合は外側にあります
四角錐に関して言えば、私が知る限り、3D 空間を 2 つの半空間5 planes * 2 = 10 halfspaces( 私が得られないのは、n上記のアルゴリズムのコードでの使用です。Planeインスタンスの配列を反復するループの終了条件として使用されます。ただし、前述のように、半角スペースは 10 個あります。
掘り下げて考えたことの 1 つは、2 つの平面の交点が線 (ピラミッドの端) であるという事実です。Wolfram Mathworldをさらに引用
線を一意に特定するには、線上の特定の点も見つける必要があります。これは、両方の平面上に同時にある点を見つけることによって決定できます
任意の 2 つの辺 (底面を含む) について、ピラミッドの 2 つの頂点の間にある線を取得するため、ピラミッドの各頂点はこの要件を満たします。したがって、交差に関しては 5 (底部に 4、頂点に 1) ありますが、本のテキスト (関数の実装の上のコメントを含む) は曖昧であり、それを読むと間違った考えが得られる可能性があります (少なくともそれは私の場合）。
私の考え方は真実に近いのでしょうか、それとも数学の知識に関して大きな部分が欠けているのでしょうか?
私はコードを Python 3 に移植し、アルゴリズムを変更して、追加の引数を取らずに平面のリストだけをループして (私の考えが正しければ、基本的に元のものと同じです)、 でプロットしましたmatplotlib。それは完全に正常に動作しますが、私はそれを正しく理解しているかどうかを知りたいです:
