GJK算法在三维碰撞检测中通过迭代计算Minkowski差中离原点最近的点，判断原点是否在其内部以确定两凸多面体是否相交；它不依赖顶点数量，仅需可靠的支撑函数，适用于球、胶囊体、OBB等任意凸形，性能稳定但要求物体严格凸且输出无直接法向或穿透深度。
什么是GJK算法在三维碰撞检测中的实际作用
GJK（Gilbert–Johnson–Keerthi）不是直接判断“两个凸多面体是否相交”的黑盒函数，而是通过迭代计算Minkowski差中离原点最近的点，来判断原点是否落在该差集内部。如果原点在Minkowski差内，说明两物体相交；否则不相交。它不依赖顶点数量，只依赖支撑点（support point）函数，因此对任意凸形（包括凸多面体、球、胶囊体、OBB等）都适用，且性能稳定。
关键前提是：两个物体必须是严格凸的，且能提供可靠的 support() 函数——即给定方向 d，返回物体上沿该方向最远的点。
怎么为三维凸多面体实现正确的 support() 函数
凸多面体的支撑点必然是其顶点之一，所以 support() 本质是遍历所有顶点，点积比较：
Vector3 support(const std::vector<vector3>& vertices, const Vector3& d) {
float maxDot = -std::numeric_limits<float>::max();
Vector3 result = vertices[0];
for (const auto& v : vertices) {
float dot = dot(v, d);
if (dot > maxDot) {
maxDot = dot;
result = v;
}
}
return result;
}
</float></vector3>
注意三点：
- 输入
d必须是单位向量，否则点积结果不可比（GJK内部会归一化方向，但自己实现support()时若不预归一化，可能因浮点误差导致选错顶点） - 若多面体由面/边定义（如Half-Edge结构），不要试图用面法向投影——支撑点只取决于顶点集合，暴力遍历顶点最稳妥
- 不要缓存顶点索引或提前排序：支撑方向每次不同，无法预优化；现代CPU下百个顶点的线性扫描开销可忽略
为什么直接套用二维GJK代码在三维会失败
三维GJK的单纯形（simplex）可能是点、线段、三角形或四面体，而二维最多到三角形。漏处理四面体情形会导致：
- 单纯形退化（如共面三点+原点在平面外），算法卡死或返回假阴性
-
closestPointToOrigin()计算错误，误判原点距离
标准流程中，每轮需根据单纯形顶点数分支处理：
- 1点：直接返回该点
- 2点（线段）：检查原点是否在线段垂足范围内，否则退化为端点
- 3点（三角形）：检查原点是否在三角形所在平面的正面/背面/投影内，用重心坐标或平面方程判定
- 4点（四面体）：检查原点是否在四面体内部——需对4个面分别做平面侧性测试（
dot(normal, origin - vertex) ），全部满足才在内；否则找出离原点最近的面，将单纯形收缩为该面+新支撑点
很多开源实现（如Bullet的早期版本）曾因四面体投影逻辑有符号错误，导致穿透几帧才检测到碰撞。
怎么把GJK结果用于实际碰撞响应
GJK本身只输出“相交/不相交”布尔值和最近点对（在Minkowski差中），不提供碰撞法向、穿透深度或接触点。要获得这些，需额外步骤：
- 若GJK判定相交，运行
EPA（Expanding Polytope Algorithm）从最终单纯形出发，细化Minkowski差表面，得到精确的最小分离向量（即法向+深度） - 或者，在GJK收敛后，用最终单纯形的顶点反推原始空间中的两个点（通过顶点索引映射回A/B物体），再用它们拟合一个分离轴（粗略法向），但精度有限
- 实际引擎中（如PhysX、Bullet），GJK通常只作快速剔除，真正需要响应时切换到更重的算法（如SAT on clipped faces 或 full EPA）
别指望单次GJK调用就能拿到 normal 和 penetrationDepth——那是常见误解。GJK的强项是快和稳，短板就是无几何信息输出。
GJK在三维里最易被忽略的细节是四面体退化判定和支撑方向归一化；一旦这两处出问题，表现就是“明明穿过去了却不报碰撞”，或者“抖动时频繁闪退”。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
