在 3D 中实现扩展多胞形算法 Space

Question

我正在尝试在 3D 中实现 EPA 算法space，但我似乎发现了一种情况，即凸单纯形可以变成凹形。

考虑这个单纯形：

而且因为很难看到这里发生了什么，所以它是动画的：

原点是红绿蓝轴助手。没有连接边的白色球体代表我需要将多面体扩展到下一个的点。 5 个黄色箭头是应该移除的面的法线，因为它们与新点的原点方向相同。有些面看起来不在同一个方向，但我已经验证它们是因为面法线和新点的点积是：

0.45396564417079877
0.9473689548609279
0.3346846050014339
0.09982613239032267
0.09982617482390854

所以 .gif 右侧的那两个面只是同一方向的大麦。

好的，EPA 算法说要删除这些面孔：

然后使用我们移除的面的剩余边构造到新点的新面。但是你现在可以看到凸单纯形变成了凹单纯形：

这显然是不对的，但我不确定哪里错了。在我看来，我删除了不该删除的面孔，但这些面孔与新点的方向相同。

这是我的代码：

var EPA = function(aWorldVerts, bWorldVerts, simplex) {
    var simplexFaces = [{a: 0, b: 1, c: 2},
                        {a: 0, b: 1, c: 3},
                        {a: 0, b: 2, c: 3},
                        {a: 1, b: 2, c: 3}];

    var ret = null;

    while(true) {
        var face = findClosestFace(simplex, simplexFaces);
        var point = support(aWorldVerts, bWorldVerts, face.norm);
        var dist = point.clone().dot(face.norm);

        if(dist - face.dist < 0.00001) {
            ret = {axis: face.norm, dist: dist};
            break;
        }

        simplex.push(point);
        reconstruct(simplex, simplexFaces, point);
    }

    return ret;
}

var reconstruct = function(simplex, simplexFaces, extendPoint) {
    //I do realize that this function can be done more efficietly
    var removalFaces = [];
    for(var i = 0; i < simplexFaces.length; i++) {
        var face = simplexFaces[i];

        var ab = simplex[face.b].clone().sub(simplex[face.a]);
        var ac = simplex[face.c].clone().sub(simplex[face.a]);
        var norm = ab.cross(ac).normalize();

        var a0 = new THREE.Vector3().sub(simplex[face.a]);
        if(a0.dot(norm) > 0)
            norm.negate();

        if(extendPoint.clone().dot(norm) > 0) {
            removalFaces.push(i);
        }
    }

    //get the edges that are not shared between the faces that should be removed
    var edges = [];
    for(var i = 0; i < removalFaces.length; i++) {
        var face = simplexFaces[removalFaces[i]];
        var edgeAB = {a: face.a, b: face.b};
        var edgeAC = {a: face.a, b: face.c};
        var edgeBC = {a: face.b, b: face.c};

        var k = edgeInEdges(edges, edgeAB);
        if(k != -1)
            edges.splice(k, 1);
        else
            edges.push(edgeAB);

        k = edgeInEdges(edges, edgeAC);
        if(k != -1)
            edges.splice(k, 1);
        else
            edges.push(edgeAC);

        k = edgeInEdges(edges, edgeBC);
        if(k != -1)
            edges.splice(k, 1);
        else
            edges.push(edgeBC);
    }

    //remove the faces from the polytope
    for(var i = removalFaces.length - 1; i >= 0; i--) {
        simplexFaces.splice(removalFaces[i], 1);
    }

    //form new faces with the edges and new point
    for(var i = 0; i < edges.length; i++) {
        simplexFaces.push({a: edges[i].a, b: edges[i].b, c: simplex.length - 1});
    }
}

var edgeInEdges = function(edges, edge) {
    for(var i = 0; i < edges.length; i++) {
        if(edges[i].a == edge.a && edges[i].b == edge.b)
            return i;
    }

    return -1;
}

var findClosestFace = function(simplex, simplexFaces) {
    var closest = {dist: Infinity};

    for(var i = 0; i < simplexFaces.length; i++) {
        var face = simplexFaces[i];

        var ab = simplex[face.b].clone().sub(simplex[face.a]);
        var ac = simplex[face.c].clone().sub(simplex[face.a]);
        var norm = ab.cross(ac).normalize();

        var a0 = new THREE.Vector3().sub(simplex[face.a]);
        if(a0.dot(norm) > 0)
            norm.negate();

        var dist = simplex[face.a].clone().dot(norm);

        if(dist < closest.dist) {
            closest = {index: i, dist: dist, norm: norm, a: face.a, b: face.b, c: face.c};
        }
    }

    return closest;
}

var support = function(aVerts, bVerts, dir) {
    a = getFurthestPointInDirection(aVerts, dir);
    b = getFurthestPointInDirection(bVerts, dir.clone().negate());
    return a.clone().sub(b);
}

var getFurthestPointInDirection = function(verts, dir) {
    var index = 0;
    var maxDot = verts[index].clone().dot(dir.clone().normalize());

    for(var i = 1; i < verts.length; i++) {
        var dot = verts[i].clone().dot(dir.clone().normalize());

        if(dot > maxDot) {
            maxDot = dot;
            index = i;
        }
    }

    return verts[index];
}

我知道支持功能与 findClosestFace() 和 edgeInEdges() 一样正常工作。此外，这应该无关紧要，但这是使用 Three.js 和 Javascript 实现的。也许我只是从根本上误解了算法的工作原理？

我做错了什么，我该如何解决？

Answer 1

经过几个小时的调试，我发现了我的问题。通过检查面的法线是否与新点的原点方向相同，找不到在将多面体扩展到新点之前要删除的面。许多关于这个主题的文章说你想删除新点可以 "see" 的面，我认为这意味着法线在同一方向。事实并非如此，因为您可以很好地使面法线与新点的原点方向相同，但是该面不能 "seen" 到点，因此删除它会出现问题，这就是我正在做。你基本上想把你的相机想象成新点所在的位置，环顾四周，你能看到的任何面孔都应该被移除。

要检查给定的面是否可以 "seen" 到新点，您要形成从所述面的顶点到新点的向量，并检查该面与面法线的点积。所以我在 reconstruct() 函数中用 if(norm.clone().dot(extendPoint.clone().sub(simplex[face.a])) > 0) 替换了 if(extendPoint.clone().dot(norm) > 0)，它现在可以工作了。

在 3D 中实现扩展多胞形算法 Space

Implementing the Expanding Polytope Algorithm in 3D Space

javascript

collision-detection