c++ - GJK从2D到3D的碰撞检测实现

Question

对于这个问题的长度，我深表歉意，并先发制人地感谢阅读本文的任何人!

因此，过去几天我一直在研究 GJK 算法。感谢 William Bittle 在 http://www.codezealot.org/archives/88 发表的精彩文章，我理解了它背后的一般概念，并理解了其在 2D 中实现的大部分细节。 .

我已经将他的伪代码(在文章末尾找到)实现到我自己的 C++ 项目中，但是我想制作一个 3D 实现。我的弱点在于使用点积来测试 voronoi 区域和 tripleProducts 来获得垂直线。但我正在尝试阅读更多相关内容。

我的问题归结为 containsOrigin 函数。我无法可视化和解释 z 轴添加的新 voronoi 区域。我似乎无法全神贯注于如何确定哪些区域包含原点。我假设有 4 个我必须考虑，每个都从构成单纯形四面体的 4 个面的三角形平面延伸。如果原点不在任何这些区域内，那么它就被包含在内，我们就会发生碰撞。

我如何着手测试它是否包含在特定的 voronoi 区域/哪个三角形面指向原点的方向？

当前的 2D 算法会检查是否形成了三角形，如果没有，则单纯形是一条线，它会找到第 3 个点。我假设 3D 算法检查是否制作了四面体，如果没有，那么它将检查三角形，如果为真，那么它将找到第 4 个点来制作四面体(我如何得到这个？使用方向法线起源？)。如果我没有创建三角形，它会找到第 3 个点来创建三角形(我是否仍然像在 2D 中那样使用三重乘积？)。

非常感谢任何建议、大纲、资源、代码扩充、评论。

Answer 1

根据您对 GJK 算法的期望结果，您可能希望查看来自 Molly Rocket 的精彩教程:https://mollyrocket.com/849

请注意他的实现只输出交集？是/否。但这可能是一个不错的开始。