检查凸形固体是否完全位于另一个凸形固体内部的最快方法是什么？

Question

我有我需要检查有关其位置的三个不同状态的两个不同的凸对象：

1. 固体不碰撞
2. 的固体部分碰撞
3. 一个固体的完全是内部的其他

我使用GJK算法来检查实体是否碰撞，以便消除1状态。现在的问题是，GJK无法判断我是否有部分碰撞，或者其中一个物体是否完全位于另一个物体的内部。什么是检查第三种状态的最快方法？

Answer 1

1. 为两个对象创建一个AXIS对齐边界框（AABB）。
   • 如果他们（AABB's）没有发生冲突，那么他们的身体在外面/不会碰撞。
2. 如果AABB的DO：
   • 相交的所有面/一个与其他机构的边面/边缘（你可以再次消除与AABB非collissions如上的每一张脸，脸对等）
   。
3. 如果没有别的，他们是在另一个之内。

以下演示文稿是相当不错的资源。我推荐阅读：http://www.sccg.sk/~durikovic/classes/CGAnim/ca10_lesson04.pdf

Answer 2

建立第一个实体的所有面的取向平面方程（取每个面的三个顶点），并检查第二个实体的所有顶点位于平面的正侧。

针对N个面和M个顶点需要时间O（N.M）。