GJK 算法中的支持函数

Question

我正在尝试实施 GJK 算法，但我立即陷入困境。

问题是实现不是 O(n^2) 的支持函数。

现在我正在计算完整的 Minkowski 差异，然后执行 GJK 算法真的没有意义。（或者是吗？）

我所说的 Support-function 是返回 Minkowski 差分中在指定方向上最远的点的函数。我认为这不应该是 O(n^2)，因为它在我当前的实现中。

Answer 1

最简单的支持函数是 0(n)，即在一个方向上找到最好的点积。

    public Vector3 MaxPointAlongDirection(Vector3 directionToMove)
    {
        float max = float.NegativeInfinity;
        int index = 0;
        for (int i = 0; i < vertices.Length; i++)
        {
            float dot = Vector3.Dot(vertices[i], directionToMove);
            if (dot > max)
            {
                max = dot;
                index = i;
            }
        }
        return vertices[index];
    }

对于三角凸包，另一种更快的方法是爬山。1 计算每个点的邻接信息。2 从一个随机点开始，找到所有相邻点的最佳点积。3 使这个新点成为当前点重复步骤 2 4 当没有找到更好的产品时停止（这将是有效的，因为对象是凸的，因此没有局部最大值）

或 Dobkin-Kirkpatrick 层次结构。

在对象正在旋转的情况下，可以相对于旋转对象转换 directionToMove 向量（仍在处理此问题）。从而不需要旋转所有点。