gjk 算法 c++

GJK算法（Gilbert-Johnson-Keerthi算法）是一种用于求解凸体相交的算法，其用途广泛应用在物理引擎、碰撞检测和计算机图形学等领域。

GJK算法的基本思想是通过迭代逼近的方式，在高维空间中找到两个凸体是否相交的最近点对，从而确定它们是否相交。具体来说，GJK算法分为三个主要步骤：

1. 初始化：选择两个初始点，一个位于第一个凸体上，一个位于第二个凸体上。这两个点可以是凸体的顶点、边界上的任意一点。

2. 迭代逼近：根据Minkowski差集（两个凸体的差集）形成的新凸体，找到离原点最近的点。该最近点必然位于Minkowski差集的边界上，可以通过求解凸包或者线段相交等方法来寻找。

3. 更新凸体：如果最近点距离原点足够小，说明两个凸体相交；否则，将最近点加入到Minkowski差集，进行下一轮迭代逼近。

由于GJK算法通过在高维空间中进行求解，虽然只需要两个凸体的形状信息，但能够得到相交的最近点对，进而支持接触深度、碰撞法向量等额外的信息。此外，GJK算法具有高效、可扩展性好等优点，因此被广泛应用于各种实时计算几何问题中。

总之，GJK算法是一种高效的求解凸体相交的算法，通过迭代逼近的方式找到相交的最近点对，其具有应用广泛的优势，可用于物理引擎、碰撞检测和计算机图形学等领域。

相关问题

三维场景GJK算法C++

GJK算法是一种用于计算两个凸多边形之间最短距离的算法，可以用于三维场景的碰撞检测。

以下是一个简单的C++实现：

struct Vec3 {
    float x, y, z;
};

struct SupportPoint {
    Vec3 point;
    int index1, index2;
};

Vec3 support(const Vec3& dir, const std::vector<Vec3>& shape1, const std::vector<Vec3>& shape2) {
    Vec3 p1 = supportInDirection(dir, shape1);
    Vec3 p2 = supportInDirection(-dir, shape2);
    return p1 - p2;
}

SupportPoint supportInDirection(const Vec3& dir, const std::vector<Vec3>& shape) {
    float maxDot = -FLT_MAX;
    Vec3 maxPoint;
    int maxIndex = -1;
    for (int i = 0; i < shape.size(); ++i) {
        float dot = dotProduct(dir, shape[i]);
        if (dot > maxDot) {
            maxDot = dot;
            maxPoint = shape[i];
            maxIndex = i;
        }
    }
    return { maxPoint, maxIndex };
}

bool gjkIntersection(const std::vector<Vec3>& shape1, const std::vector<Vec3>& shape2) {
    SupportPoint a{ support(Vec3{ 1.0f, 0.0f, 0.0f }, shape1, shape2), -1, -1 };
    std::vector<SupportPoint> simplex{ a };
    Vec3 d = -a.point;
    while (true) {
        SupportPoint b{ support(d, shape1, shape2), -1, -1 };
        if (dotProduct(b.point, d) < 0) {
            return false;
        }
        simplex.push_back(b);
        if (doSimplex(simplex, d)) {
            return true;
        }
    }
}

bool doSimplex(std::vector<SupportPoint>& simplex, Vec3& d) {
    int n = simplex.size();
    switch (n) {
    case 2: return doSimplex2(simplex, d);
    case 3: return doSimplex3(simplex, d);
    case 4: return doSimplex4(simplex, d);
    default: return false;
    }
}

bool doSimplex2(std::vector<SupportPoint>& simplex, Vec3& d) {
    Vec3 a = simplex[1].point;
    Vec3 b = simplex[0].point;
    Vec3 ab = b - a;
    Vec3 ao = -a;
    if (dotProduct(ab, ao) > 0) {
        d = crossProduct(crossProduct(ab, ao), ab);
    }
    else {
        simplex[0] = simplex[1];
        d = ao;
    }
    simplex.erase(simplex.begin() + 1);
    return false;
}

bool doSimplex3(std::vector<SupportPoint>& simplex, Vec3& d) {
    Vec3 a = simplex[2].point;
    Vec3 b = simplex[1].point;
    Vec3 c = simplex[0].point;
    Vec3 ab = b - a;
    Vec3 ac = c - a;
    Vec3 ao = -a;
    Vec3 abc = crossProduct(ab, ac);
    if (dotProduct(crossProduct(abc, ac), ao) > 0) {
        if (dotProduct(ac, ao) > 0) {
            simplex[0] = simplex[2];
            d = crossProduct(crossProduct(ac, ao), ac);
        }
        else {
            simplex[1] = simplex[2];
            d = crossProduct(crossProduct(ab, ao), ab);
        }
    }
    else {
        if (dotProduct(crossProduct(ab, abc), ao) > 0) {
            simplex[0] = simplex[1];
            simplex[1] = simplex[2];
            d = crossProduct(crossProduct(ab, ao), ab);
        }
        else {
            d = abc;
        }
    }
    simplex.erase(simplex.begin() + 2);
    return false;
}

bool doSimplex4(std::vector<SupportPoint>& simplex, Vec3& d) {
    Vec3 a = simplex[3].point;
    Vec3 b = simplex[2].point;
    Vec3 c = simplex[1].point;
    Vec3 d = simplex[0].point;
    Vec3 ab = b - a;
    Vec3 ac = c - a;
    Vec3 ad = d - a;
    Vec3 abc = crossProduct(ab, ac);
    Vec3 acd = crossProduct(ac, ad);
    Vec3 adb = crossProduct(ad, ab);
    Vec3 ao = -a;
    if (dotProduct(abc, ad) > 0) {
        if (dotProduct(acd, ao) > 0) {
            simplex[1] = simplex[3];
            simplex.erase(simplex.begin() + 2);
            d = crossProduct(crossProduct(acd, ao), acd);
        }
        else {
            if (dotProduct(adb, ao) > 0) {
                simplex[0] = simplex[3];
                simplex.erase(simplex.begin() + 2);
                d = crossProduct(crossProduct(adb, ao), adb);
            }
            else {
                simplex[0] = simplex[2];
                simplex[1] = simplex[3];
                simplex.erase(simplex.begin() + 2);
                d = abc;
            }
        }
    }
    else {
        if (dotProduct(acd, ab) > 0) {
            simplex[0] = simplex[1];
            simplex[1] = simplex[3];
            simplex.erase(simplex.begin() + 2);
            d = crossProduct(crossProduct(ab, ao), ab);
        }
        else {
            if (dotProduct(adb, ac) > 0) {
                simplex[1] = simplex[2];
                simplex[0] = simplex[3];
                simplex.erase(simplex.begin() + 2);
                d = crossProduct(crossProduct(ac, ao), ac);
            }
            else {
                simplex.erase(simplex.begin() + 1);
                simplex.erase(simplex.begin() + 1);
                d = -abc;
            }
        }
    }
    return dotProduct(d, ao) < 0;
}

float dotProduct(const Vec3& a, const Vec3& b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

Vec3 crossProduct(const Vec3& a, const Vec3& b) {
    return { a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x };
}

其中，`support`函数用于计算在给定方向上的支撑点，`supportInDirection`函数用于计算在给定方向上的支撑点和其在两个形状中的索引，`gjkIntersection`函数用于判断两个凸多边形是否相交，`doSimplex`函数用于根据简单形状的类型来执行相应的操作，`doSimplex2`、`doSimplex3`、`doSimplex4`分别对应2个、3个、4个支撑点的情况，`dotProduct`和`crossProduct`分别计算两个向量的点积和叉积。

需要注意的是，这个实现中使用了一些辅助函数，如`dotProduct`和`crossProduct`，需要根据具体情况进行实现。此外，还需要实现`supportInDirection`函数来计算支撑点。