在 3D 空间中实现扩展多面体算法

Question

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

考虑这个单纯形：

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

原点是红、绿、蓝轴助手。没有边缘连接的白色球体代表我需要将多面体扩展到下一个的点。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

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

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