ミンコフスキーの相違を原点からある方向に交差させると、どのようにして顔が交差するのが見えますか？

Question

基本的に私は2つの多面体のミンコフスキー差の船体に頂点のセットを持っています。私は原点から船体までの距離を任意の所定の方向に求めたい。 HERESに迅速な2Dスケッチ：

だから問題は線が交差して何が起こっているかの三角形の面/平面見つけることです。私はその飛行機を持っていれば、私は単にライン/飛行機の交差点テストをするだけです。私の問題は、正しい顔/面を見つけることです。何か案は？私がそれを決定するためにできるドットプロダクト/クロスプロダクト/トリプルプロダクトテストのいくつかのセットがありますか？それとももっと複雑なのでしょうか？

GJKアルゴリズムを使用して2つのオブジェクトが交差しているかどうかを判断するにはどうすればいいですか？衝突がある場合、特定の方向（物体の動きの方向）に侵入深さを見つけたいと思います。

Answer 1

多面体を光線の方向に投影すると、問題は2Dになり、どの三角形が原点を囲んでいるかを調べます。単一の三角形をテストするには、指定された線分（AB）が原点に対して時計回りか反時計回りかを検討します。これは、単純なクロス積の試験で決定することは容易である：それは反時計IFF X（Bから）です> 0

三角形の3つのすべての辺が同じ意味を持っている場合（時計回りまたは反時計回り）、三角形は原点を囲み、それはあなたが望む顔です。

EDIT：
あなたの多面体は、それが凸包である、そしてそれは凸状であるので、あなたが効率的な方法で表面を検索することができますので。非常に単純な「上り坂/下り坂を歩く」という方法でエッジを走査し、どちらの方向にも光線に沿って最も遠い2つの頂点を見つけることができます。それからポーロヘドロンを投影した後、これらの2つの点から出発して、起点に向かって同じように登ることができます。これはO（sqrt（n））になります。