C++ Gilbert-Johnson-Keerthi (GJK) 算法

2025年3月22日 | 7 分钟阅读

识别凸体碰撞的一种流行方法是Gilbert-Johnson-Keerthi (GJK) 算法。它在计算机图形学、物理模拟和游戏开发中非常有用，因为它高效且多维。该过程的目的是确定两个凸体是否相交。它以三位发明者 S. S. Keerthi、D. W. Johnson 和 E. G. Gilbert 的名字命名。他们于 1988 年首次提出它。

Gilbert-Johnson-Keerthi (GJK) 算法是计算几何和物理引擎中检测两个凸体碰撞的一种流行方法。它利用 Minkowski 差的思想来高效地确定两个凸体是否相交。

单纯形是由两个物体 Minkowski 差生成的几何图形（点、线、三角形或四面体）。GJK 算法迭代地构建一个单纯形。主要思想是，如果坐标系的原点位于 Minkowski 差内，则两个物体正在碰撞。

Gilbert-Johnson-Keerthi (GJK) 算法的关键特性

Gilbert-Johnson-Keerthi (GJK) 算法具有以下几个关键特性：

凸形状检测
由于 GJK 专门为凸形状设计，因此它能够有效地检测各种实际应用中的碰撞，包括机器人和物理引擎。
单纯形方法
通过使用单纯形概念（它是三角形的推广），该方法可以有效地计算两个凸体之间的最近点，从而降低问题的维度。
迭代过程
在确定是否发生碰撞之前，GJK 会使用迭代过程不断改进其对最接近的点的估计。通过使用单纯形概念（它是三角形的推广），该方法可以有效地计算两个凸体之间的最近点，从而降低问题的维度。
支持函数
该过程使用支持函数来生成正在评估的两个形状的凸包上的点。支持函数可以帮助找到给定方向上的最远点，这对于 GJK 计算至关重要。
健壮性
GJK 的鲁棒性和处理计算中可能出现的数值问题的能力使其能够受益于实时应用程序。
效率
该算法的典型复杂度为 O(n)，其中 n 是形状的顶点数。这表明该算法相当高效。与边界体积层次 (BVH) 等其他方法相比，这种效率尤其明显。

Gilbert-Johnson-Keerthi (GJK) 算法的优点

Gilbert-Johnson-Keerthi (GJK) 算法具有以下几个优点：

凸形状效率
GJK 特别适用于凸对象，能够快速计算它们之间的最小距离或确定它们是否相交。
迭代性质
对于计算效率高的实时应用（如游戏引擎或模拟），该技术通常可以在几次迭代中收敛。
概念简单
由于其基于基本几何概念（Minkowski 差、单纯形和支持函数），因此该技术易于理解，并可以使用基本几何库在C++ 中实现。
支持任意维度
GJK 无需重大修改即可在 2D、3D 或更高维度下运行。这种适应性对于需要多维碰撞检测的各种应用非常有用。
无需预处理
与某些其他技术相比，GJK 不需要对形状进行大量预处理。由于它直接作用于几何形状，因此适用于动态和实时场景，在这种场景下对象可能会发生变化。
支持非相交和相交的对象
当两个对象不发生碰撞时，GJK 可以测量它们之间的分离距离并确定它们是否相交。

Gilbert-Johnson-Keerthi (GJK) 算法的缺点

Gilbert-Johnson-Keerthi (GJK) 算法具有以下几个缺点：

对非凸形状效率低下
GJK 的设计专门针对凸对象。处理非凸形状会增加复杂性和处理成本，因为它们需要被分解成凸部分（例如，使用凸包）。
数值不稳定性
由于浮点运算的精度，GJK 与许多几何算法一样，容易出现数值不稳定性。大型或小型对象可能会因此遇到问题。
处理退化情况
在遇到边缘情况或退化情况（例如，未碰撞但非常接近的对象或精确接触的对象）时，GJK 可能会遇到困难。在这些情况下，需要格外小心以避免无限循环或收敛问题。
实现复杂性
尽管原理很简单，但单纯形技术和边缘情况可能会使实际实现变得困难。在 C++ 中管理内存分配、递归和浮点比较可能很棘手，并可能导致错误或效率低下。
支持函数实现
如果对象使用复杂或自定义的几何结构进行指定，那么为复杂形状实现支持函数可能会很困难，并且可能需要大量的代码。
不处理对象穿透深度
在发生碰撞的情况下，它不会立即计算穿透深度。处理穿透深度会增加额外的复杂性；需要像扩张多面体算法 (EPA) 这样的扩展。

Gilbert-Johnson-Keerthi (GJK) 算法的使用场景

Gilbert-Johnson-Keerthi (GJK) 算法的几个使用场景如下：

鲁棒的几何建模
GJK 可用于 3D 建模工具，以计算复杂凸多面体之间的最小距离或识别几何建模应用中的交集。
机器人运动规划
GJK 方法用于机器人领域，用于计算机器人部件之间或机器人与环境物体之间的距离。它有助于路径规划和碰撞避免。
物理模拟
GJK 有助于确定模拟中运动凸体之间的分离，包括刚体动力学，从而实现对碰撞的真实反应。
游戏开发中的碰撞检测
在实时物理引擎（如 Bullet、Havok 和 Box2D）中，GJK 算法经常被用来检测球体、盒子以及更复杂的多面体等凸对象之间的碰撞。
触觉反馈系统
GJK 有助于在触觉反馈系统中检测虚拟工具与模拟组织或器官之间的碰撞，例如虚拟手术模拟器。

示例

让我们通过一个示例来说明 C++ 中的 Gilbert Johnson Keerthi。

 
#include <iostream>
#include <vector>
struct Vector2 
{
    float x, y;
    Vector2(float x = 0, float y = 0) : x(x), y(y) {}
    Vector2 operator-(const Vector2& v) const {
        return Vector2(x - v.x, y - v.y);
    }
    Vector2 operator-() const {
        return Vector2(-x, -y);
    }
    float dot(const Vector2& v) const {
        return x * v.x + y * v.y;
    }
};
// Find the farthest point in a shape along a direction
Vector2 support(const std::vector<Vector2>& shape, const Vector2& d) {
    float maxDot = shape[0].dot(d);
    Vector2 furthest = shape[0];
    for (const auto& p : shape) 
    {
        float dotProduct = p.dot(d);
        if (dotProduct > maxDot)
        {
            maxDot = dotProduct;
            furthest = p;
        }
    }
    return furthest;
}
// Check if the simplex contains the origin
bool containsOrigin(std::vector<Vector2>& simplex, Vector2& direction) {
    Vector2 a = simplex.back();
    Vector2 ao = -a;
    if (simplex.size() == 3)
    {
        Vector2 b = simplex[1];
        Vector2 c = simplex[0];
        Vector2 ab = b - a;
        Vector2 ac = c - a;
        Vector2 abPerp = Vector2(-ab.y, ab.x);
        // Perpendicular to ab
        Vector2 acPerp = Vector2(-ac.y, ac.x); 
        // Perpendicular to ac
        if (abPerp.dot(ao) > 0) 
        {
            simplex.erase(simplex.begin()); 
            // Remove C
            direction = abPerp;
        }
        else if (acPerp.dot(ao) > 0)
        {
            simplex.erase(simplex.begin() + 1);
            // Remove B
            direction = acPerp;
        } 
        else
        {
            return true; 
            // Origin is inside the simplex
        }
    } 
    else
    {
        Vector2 b = simplex[0];
        Vector2 ab = b - a;
        direction = Vector2(-ab.y, ab.x); 
        // Perpendicular to ab
        if (ab.dot(ao) < 0) direction = -direction;
    }
    return false;
}
// GJK algorithm for collision detection
bool gjk(const std::vector<Vector2>& shapeA, const std::vector<Vector2>& shapeB)
{
    Vector2 direction(1, 0); 
    // Start with an arbitrary direction
    std::vector<Vector2> simplex;
    Vector2 point = support(shapeA, direction) - support(shapeB, -direction); // First support point
    simplex.push_back(point);
    direction = -point;
    // Update direction toward origin
    while (true)
    {
        point = support(shapeA, direction) - support(shapeB, -direction);
        if (point.dot(direction) < 0) return false; 
        // No collision
        simplex.push_back(point);
        if (containsOrigin(simplex, direction))
        return true;
        // Collision detected
    }
}
int main() 
{
    std::vector<Vector2> shapeA = {{0, 0}, {1, 0}, {0, 1}};
    std::vector<Vector2> shapeB = {{0.5, 0.5}, {1.5, 0.5}, {0.5, 1.5}};
    if (gjk(shapeA, shapeB))
    {
        std::cout << "Collision detected!" << std::endl;
    }
    else
    {
        std::cout << "No collision!" << std::endl;
    }
    return 0;
}   

输出

 
Collision detected!

说明

此代码实现了用于两个凸形状之间 2D 碰撞检测的 Gilbert-Johnson-Keerthi (GJK) 算法。每个形状都表示为由 Vector2 点组成的向量。support() 函数用于查找形状沿给定方向的最远点。gjk() 函数从一个方向开始，计算 Minkowski 差，然后将支持点添加到单纯形中以不断完善搜索。containsOrigin() 函数根据需要修改方向，以确定原点是否位于单纯形内部。该过程将迭代进行，直到检测到碰撞或未找到碰撞。

下一个主题检查 C++ 中给定的数字是否为 pronic 数

C++ Gilbert-Johnson-Keerthi (GJK) 算法

Gilbert-Johnson-Keerthi (GJK) 算法的关键特性

Gilbert-Johnson-Keerthi (GJK) 算法的优点

Gilbert-Johnson-Keerthi (GJK) 算法的缺点

Gilbert-Johnson-Keerthi (GJK) 算法的使用场景

示例

说明

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Gilbert-Johnson-Keerthi (GJK) 算法

Gilbert-Johnson-Keerthi (GJK) 算法的关键特性

Gilbert-Johnson-Keerthi (GJK) 算法的优点

Gilbert-Johnson-Keerthi (GJK) 算法的缺点

Gilbert-Johnson-Keerthi (GJK) 算法的使用场景

示例

说明

相关帖子

C++ 中 std::lock_guard 与 std::unique_lock 的区别

C/C++ c32rtomb() 函数

C++ 中的 std::codecvt

C++ 不同子序列

C++ 中的粒子群优化

C++ 中 tellg 和 tellp 的区别

C++ 中的 std::to_address

C++ 中的奥尔数

C++ 与 C# 的区别

C++ std::start_lifetime_as, std::start_lifetime_as_array 函数

订阅 Tpoint Tech

联系信息

关注我们

教程