我正在实施 Expanding Polytope Algorithm,我不确定如何从 minkowski 差异上的一个点推导出接触点

I'm implementing the Expanding Polytope Algorithm, and I am unsure how to deduce the contact points from a point on the minkowski difference

我一直在从多个来源阅读有关 EPA 的信息,但在找到与原点的 minkowski 差异的最近点后,它们似乎都突然停止使用。他们中的大多数人都说了类似 "With this information, we can then generate the local and global contact points and contact tangents," 的内容,但我不明白这怎么可能,更不用说如何去做了。我看不出有人如何仅从差异中得出被减数和减数,而且肯定不会在合理的时间内得出。这个问题的标准解决方案是什么?

我希望在 3D 中实现此算法,如果这会改变答案的话。谢谢

此处为博客 post 的 OP。

post实际上说的是EPA算法第8步计算接触点的方法:

Project the origin onto the closest triangle. This is our closest point to the origin on the CSO’s boundary. Compute the barycentric coordinates of this closest point with respect to the vertices from the closest triangle. The barycentric coordinates are coefficients of linear combination of vertices from the closest triangle. Linearly combining the individual support points (original results from individual colliders) corresponding to the vertices from the closest triangle, with the same barycentric coordinates as coefficients, gives us contact points on both colliders in their own model space. We can then convert these contact points to world space.

请允许我在这里改写一下。

令 Ca、Cb 和 Cc 表示 CSO 三角形的三个顶点,其中包含 CSO 边界上到原点的最近点,表示为 Cp。

计算 Cp 的三角形的重心坐标 (x, y, z)。

x Ca + y Cb + z Cc = Cp

请注意,我们需要将用于获取 Ca、Cb 和 Cc 的两个对象 (A & B) 的原始支持函数结果保存在全局 space 中。设Aa、Ab、Ac为对象A的原始支持函数结果。设Ba、Bb、Bc为对象B的原始支持函数结果。

Ca = Aa + Ba
Cb = Ab + Bb
Cc = Ac + Bc

利用之前得到的重心坐标(x, y, z)将物体A和B的原始支撑函数结果线性组合,我们可以计算出两个物体上的接触点,记为Ap和Bp:

Ap = x Aa + y Ab + z Ac
Bp = x Ba + y Bb + z Bc

我希望这能为您阐明计算过程。