1

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

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

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

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

4

2 回答 2

5

最简单的支持函数是 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 向量可以相对于旋转的对象进行变换（仍在研究中）。因此不需要旋转所有点。

于 2010-05-04T21:43:08.743 回答
3

好吧，GJK 会给你 Minkowski 和的最接近原点的点。如果没有其他东西移动，那么您的 Minkowski 和将是相同的，并且最近的点也是。

通常人们认为身体可以自由移动和旋转。在这种情况下，结果一直在变化。

在翻译案例中，您应该能够重用您的 Minkowski 差异。在轮换情况下，您需要重新计算。对于许多实时应用程序来说，这将是一个问题。

如果您的算法通过支持函数隐式使用 Minkowski 差异，那么您无需重新计算任何内容。这是使用支持功能的优势之一。

有些形状具有非常简单的支撑功能形式。在这种情况下，你不需要计算任何东西。这是另一个优势。最后，您可以添加支持函数以形成 Minkowski 和的支持函数。一个很棒的属性，因为这样你可以使用基元形成一个形状族，并让 GJK 处理它们。

如果您在平面上有一个 n 个点的凸包，则可以通过查找包多边形的边缘并对法向量的角度进行排序来预先计算支持函数。船体上的每个顶点都有两条法线。只需按顺序查找您的方向是否在这些法线向量之间。那会给你O（n）。

您还可以更改比较顺序并将其设为 O(log(n))。

于 2010-03-16T21:31:38.897 回答