geometry - 船体和箱体之间的最近距离

Question

找到凸包和轴对齐框之间最近距离的最佳方法是什么？最近距离是指船体和盒子上彼此最接近的一对点。我们可以假设我们知道我们知道船体和盒子不相交。

船体由面、顶点给出，如有必要，我可以对面进行三角剖分。

Answer 1

此处的论文给出了一种算法，用于在两个凸包之间找到最接近的对。 http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf

有一段时间，我认为可能是 AABB 的船体之一会使该算法变得不必要。不幸的是，我发现那不是真的。

此算法背后的想法是您采用两个船体的 Minkowski 差异。最近的对将是这个 Minkowski 差异中最接近原点的点。 Cartheodory 定理说，在 d 维空间中，您只需要 d+1 个点来表示船体中的一个点。所以基本上你选择 d+1 大小的 minkowski 差异集并找到它们到原点的最近距离。通过迭代算法找到离原点最近的点。