文章探讨了如何改进分离轴测试（Separating Axis Test），特别是在处理凸多面体碰撞检测时。通过叠加高斯映射图，可以高效地找到凸多面体的闵可夫斯基差的面，从而避免昂贵的计算。核心观点是，闵可夫斯基差的面要么是形状A的面，要么是形状B的面，要么是A和B边的叉积结果。这种方法显著减少了计算复杂度，提升了碰撞检测的效率。

文章《改进分离轴测试》主要探讨了如何优化分离轴测试（SAT）算法，特别是在处理凸多面体碰撞检测时的效率提升。以下是文章的主要内容总结：

1. 背景与动机：

   • 文章假设读者对窄相位碰撞检测方法和几何概念（如闵可夫斯基和）有一定了解。
   • 作者受到Dirk的演讲《凸多面体之间的分离轴测试》启发，开始思考如何通过高斯映射来优化分离轴测试。

2. 闵可夫斯基差的面：

   • 闵可夫斯基差的所有面要么是形状A的面，要么是形状B的面，要么是A和B的边的叉积。
   • 通过高斯映射，可以避免在第三种情况下进行昂贵的支持函数评估，因为已知一个顶点位于该面上。

3. 优化思路：

   • 作者提出了一种改进的分离轴测试算法，该算法只需进行一次完整的支持函数评估，而不是传统的FaceCountA + FaceCountB次。

4. 问题建模：

   • 文章将分离轴测试问题建模为一个优化问题，即在单位球面上最小化支持函数。
   • 对于凸多面体，支持函数的导数在有限数量的点上存在不连续性，这些点对应于多面体的面法线。

5. 算法实现：

   • 作者提出了一种基于图遍历的算法，通过遍历球面上的弧来更新支持点，从而避免重复计算支持函数。
   • 该算法使用半边缘数据结构来存储拓扑信息，并确保生成的凸包质量。

6. 性能提升：

   • 作者通过实验发现，这种图遍历方法在处理具有多个面的凸包时，比传统的分离轴测试快5-10倍。
   • 对于三角形与凸包的碰撞检测，速度提升约为1.2倍。

7. 总结与展望：

   • 文章强调，分离轴测试不仅可以看作几何算法，还可以视为球面上的优化问题。
   • 作者希望进一步了解该算法的历史，并欢迎读者提供相关信息。

文章最后提供了GitHub代码库链接，供读者进一步探索和实现该算法。

1. 关于测试案例的评论

   • 观点：评论1指出测试案例来自《光环2》中的“Ascension”地图，认为这是一个有趣的测试案例。
   • 引用：
     • "Hey that's Ascension from Halo 2. Cool test case!"
     • “这是《光环2》中的Ascension地图。很酷的测试案例！”

2. 关于非球形形状的讨论

   • 观点：评论2提出对于非球形形状的处理问题，认为在三角形级别进行碰撞检测会变得复杂，尤其是在处理大量顶点时。
   • 引用：
     • "What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost?"
     • “非球形形状怎么办？我们是否假设球形边界并接受成本？”
     • "Any optimization to cut down on ray tests or clip is going to be a win."
     • “任何减少射线测试或剪裁的优化都会带来好处。”

3. 关于数学命题的疑问

   • 观点：评论3对两个数学命题的等价性表示困惑，特别是对变量“d”的作用提出了质疑。
   • 引用：
     • "What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution?"
     • “‘d’是什么？如果d在实际最小距离的(x, y)处远大于|x-y|^2，而在其他(x', y')处等于|x-y|^2，那么(2)会不会得出不同的、错误的解？”

4. 关于分离轴定理的应用

   • 观点：评论4提到分离轴定理的简单性和其在面试中的应用，认为该算法易于向非技术人员解释。
   • 引用：
     • "If I have a flashlight and two objects, I can tell you if they're intersected by shining the light on it."
     • “如果我有一个手电筒和两个物体，我可以通过照射它们来判断它们是否相交。”

5. 关于优化问题和数值误差的讨论

   • 观点：评论5详细讨论了优化问题和数值误差的挑战，特别是在物理引擎中的应用，并提到近似凸分解的最新进展。
   • 引用：
     • "Closest points are vertex vs vertex, vertex vs edge, vertex vs face, edge vs edge, edge vs face, and face vs face."
     • “最近的点可以是顶点对顶点、顶点对边、顶点对面、边对边、边对面和面对面。”
     • "Approximate convex decomposition produces cleaner geometry."
     • “近似凸分解会产生更干净的几何形状。”

6. 关于链接提交的抱怨

   • 观点：评论6对提交到Hacker News的链接中频繁出现的Cookie弹窗表示不满。
   • 引用：
     • "I’m getting sick of the number of links submitted to HN blasting me with cookie spam bullshit."
     • “我受够了提交到Hacker News的链接中那些烦人的Cookie弹窗。”