javascript - 在 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()功能，它现在可以工作了。