algorithm - GJK 算法中的支持函数

Question

我正在尝试实现 GJK 算法，但立即卡住了。

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

因为现在我正在计算完整的 Minkowski 差异，所以执行 GJK 算法真的没有意义。 (或者是吗？)

我所说的支持函数是指返回明可夫斯基差分中指定方向最远点的函数。我认为这不应该是 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 使这个新点成为当前点重复步骤 24 当没有找到更好的产品时停止(这将是有效的，因为对象是凸的，因此没有局部最大值)

或 Dobkin-Kirkpatrick 层次结构。

在对象旋转的情况下，directionToMove 向量可以相对于旋转的对象进行变换(仍在处理此问题)。因此不需要旋转所有点。