You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

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向量的几何关系参考示意图:
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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.28 17:15:45