2D场景实现GJK碰撞检测算法时如何计算链式叉乘求搜索方向
问题背景
我在参考GJK碰撞检测算法编码实现的相关文章做开发,目标是完成2D版本的GJK算法,而非文章中讲解的3D场景实现。
文中给出的3D场景下线段单纯形处理的C++代码片段如下:
bool Line( Simplex& points, vector3& direction) { vector3 a = points[0]; vector3 b = points[1]; vector3 ab = b - a; vector3 ao = - a; if (SameDirection(ab, ao)) { direction = ab.cross(ao).cross(ab); } else { points = { a }; direction = ao; } return false; }
原3D逻辑通过两次连续叉乘(向量三重积)求解下一轮迭代的搜索方向,需要明确该逻辑在2D场景下的实现方式。
AB、AO向量的几何关系参考示意图:
2D场景实现方法
首先明确3D代码中两次叉乘的几何意义:计算得到的方向是在AB与AO构成的平面内,垂直于线段AB、指向原点O所在一侧的向量,这就是GJK下一轮迭代需要的搜索方向,不需要硬套3D叉乘的计算逻辑。
2D场景下向量叉乘的结果是z轴方向的标量,不需要模拟3D叉乘流程,直接用向量三重积恒等式展开计算即可,公式在任意维度下都成立:
向量三重积恒等式:
(u × v) × w = v * dot(u, w) - u * dot(v, w)
代入原3D代码的计算目标(ab × ao) × ab,展开后得到:direction = ab * dot(ab, ao) - ao * dot(ab, ab)
该式只用到向量点乘、数乘、减法运算,完全适配2D向量计算。
配套的2D版本基础工具逻辑和3D完全一致:
- 点乘计算:
dot(a, b) = a.x * b.x + a.y * b.y - 同方向判断
SameDirection(ab, ao)等价于dot(ab, ao) > 0
最终2D版本的Line函数实现代码如下:
// 注:vec2为自定义2D向量结构体,包含x、y分量,支持加减、数乘基础运算 using Simplex = std::vector<vec2>; bool Line(Simplex& points, vec2& direction) { const vec2 a = points[0]; const vec2 b = points[1]; const vec2 ab = b - a; const vec2 ao = -a; if (dot(ab, ao) > 0) { const float dot_ab_ab = dot(ab, ab); const float dot_ab_ao = dot(ab, ao); direction = ab * dot_ab_ao - ao * dot_ab_ab; // 可按需对direction做归一化,不影响方向正确性 } else { points = { a }; direction = ao; } return false; }
补充说明:
- GJK算法只要求搜索方向的朝向正确,向量长度不影响support点选取结果,不需要强制归一化direction。
- 该实现和原3D逻辑的几何意义完全一致,没有精度损失,计算效率比模拟3D叉乘更高。
内容的提问来源于stack exchange,提问作者TOOL
相关产品推荐
相关产品推荐

