使用 GJK 的距离子算法找到最接近原点的单纯形上的点

Question

我正在尝试实现 Gilbert–Johnson–Keerthi distance algorithm (GJK)，但我在使用 "distance subalgorithm"（也称为 "Johnson's Algorithm" 时遇到问题，它用于确定指向最接近原点的单纯形。我得到的结果不正确，但我在我的代码中找不到任何错误，所以问题一定出在我对算法的解释上。

在 Johnson 算法中（如 Gino van den Bergen 的书 交互式 3D 环境中的碰撞检测 中所述），最接近单纯形 X = {yi : i ∈ Ix} 的仿射包上的点原点由以下公式给出：

其中 Δi^X 值是按照 X 的基数递增的顺序递归确定的：

... Δ^X 由下式给出：

对于二维，我使用以下方法找到离原点最近的点：

Point ClosestPointToOrigin(Simplex simplex)
{
    float dx = 0;
    for (int i = 0; i < simplex.size(); ++i)
        dx += dj(simplex, i);

    Point closest_point(0,0);
    for (int i = 0; i < simplex.size(); ++i)
        closest_point += dj(simplex, i) / dx * simplex[i];

    return closest_point;
}

其中Δi值由以下公式决定：

float dj(Simplex simplex, int j)
{
    if (j == 0)
    {
        return 1;
    }
    else
    {
        float d = 0;

        for (int i = 0; i < j; ++i)
            d += dj(simplex, i) * (simplex[0] - simplex[j]).dotProduct(simplex[i]);

        return d;
    }
}

对于一个单纯形X = {y1, y2} where y1 = (1,1),y2 = (1,-1),上面的代码returns(1.0, -0.333333),当最近点是,其实,(1, 0).

我一定是做错了什么，但我不知道那是什么。

Answer 1

你的错误是dj函数，也许你误解了dxi方程或者你没有写出你想要的。

我会尽力解释，如果你不明白的地方，请不要犹豫发表评论（我正在写伪 python 代码，但它应该很容易理解）。

假设我有以下单纯形：

S  = Simplex ({
    1: Point (1, 1) # y1
    2: Point (1,-1) # y2
})

我可以立即计算出 2 个增量值：

然后，我可以计算另外 2 个增量值：

希望现在您会开始发现自己的错误：Δ 值是基于索引的，因此对于维度 n 的每个单纯形 X，您有 n 个 Δ 值。您的错误之一是假设您可以计算 Δ^X₀ 和 Δ^X_i不管X的内容，都是false.

现在最后一个Δ:

注意：

一旦你在这里：

这里是用Python写的代码，如果你看不懂，我会尽量用你看得懂的语言写一个：

import numpy

class Point (numpy.ndarray):
    def __new__ (cls, x, y):
        return numpy.asarray([x, y]).astype(float).view(cls)

    def __str__ (self):
        return repr(self)

    def __repr__ (self):
        return 'Point ({}, {})'.format(self.x, self.y)

    x = property (fget = lambda s: s[0])
    y = property (fget = lambda s: s[1])

class Simplex (dict):
    def __init__ (self, points):
        super(Simplex, self).__init__ (enumerate(points))

    def __str__ (self):
        return repr(self)

    def __repr__ (self):
        return 'Simplex <' + dict.__repr__ (self) + '>'

def closest_point (s):
    dx = sum(dj(s, i) for i in range(len(s)))
    return sum(dj(s, i) / dx * v for i, v in s.items())

def dj (s, j):
    if len(s) == 0 or (len(s) == 1 and not j in s):
        print(s, j)
        raise ValueError ()
    if len(s) == 1:
        return 1
    ts = s.copy()
    yj = s[j]
    del ts[j]
    return sum(dj(ts, i) * (ts[list(ts.keys())[0]] - yj).dot(v) for i, v in ts.items())

S = Simplex([Point(1, 1), Point(1, -1)])

print(closest_point (S))

使用 GJK 的距离子算法找到最接近原点的单纯形上的点

Finding the point on a simplex closest to the origin using GJK's distance subalgorithm

algorithm

collision-detection

computational-geometry