物理引擎学习03-GJK碰撞检测算法基础

admin1

[code]bool GJK(Shape shapeA, Shape shapeB)
{
        // 得到初始的方向
    Vector2 direction = findFirstDirection();
    // 得到首个support点
    simplex.add(support(direction));
    // 得到第二个方向
    direction = -direction;
    while(true)
    {
            Vector2 p = support(direction);
        // 沿着dir的方向，已经找不到能够跨越原点的support点了。
        if (Vector2.Dot(p, direction) < 0)
            return false;
               
        simplex.add(p);
        // 单形体包含原点了
        if (simplex.contains(Vector2(0, 0)))
            return true;

        direction = findNextDirection();
    }
}
————————————————


Vector2 support(Vector2 dir)
{
    Vector2 a = getFarthestPointInDirection(shapeA, dir);
    Vector2 b = getFarthestPointInDirection(shapeA, -dir);
    return a - b;
}

Vector2 getFarthestPointInDirection(Shape shape, Vector2 dir)
{
    var vertices = shape.vertices;
    float maxDistance = float.MinValue;
    int maxIndex = 0;
    for(int i = 0; i < vertices.Count; ++i)
    {
        float distance = Vector2.Dot(vertices[i], dir);
        if(distance > maxDistance)
        {
            maxDistance = distance;
            maxIndex = i;
        }
    }
    return vertices[maxIndex];
}
————————————————
public Vector2 findNextDirection()
{
    if (simplex.count() == 2)
    {
            // 计算原点到直线01的垂足
        Vector2 crossPoint = getPerpendicularToOrigin(simplex.get(0), simplex.get(1));
        // 取靠近原点方向的向量
        return Vector2.zero - crossPoint;
    }
    else if (simplex.count() == 3)
    {
            // 计算原点到直线20的垂足
        Vector2 crossOnCA = getPerpendicularToOrigin(simplex.get(2), simplex.get(0));
        // 计算原点到直线21的垂足
        Vector2 crossOnCB = getPerpendicularToOrigin(simplex.get(2), simplex.get(1));
        // 保留距离原点近的，移除较远的那个点
        if (crossOnCA.sqrMagnitude < crossOnCB.sqrMagnitude)
        {
            simplex.remove(1);
            return Vector2.zero - crossOnCA;
        }
        else
        {
            simplex.remove(0);
            return Vector2.zero - crossOnCB;
        }
    }
    else
    {
        // 不应该执行到这里
        return new Vector2(0, 0);
    }
}
————————————————











[/code]