给定一个网格面，找到它的相邻面

Question

我正在尝试有效地找到给定面的所有相邻面。 我正在采取一种狡猾的方法，但我想知道是否可以改进。

到目前为止我采取的方法是在创建网格几何体后创建一个数据结构。我构建了一个数组散列，将顶点映射到由它们组成的面：

    var vertexToFace = [];

    function crossReference(g) {

        for (var fx = 0; fx < g.faces.length; fx++) {
            vertexToFace[fx] = new Array();
        }
        for (var fx = 0; fx < g.faces.length; fx++) {
            var f = g.faces[fx];
            var ax = f.a;
            var bx = f.b;
            var cx = f.c;

            vertexToFace[ax].push(fx);
            vertexToFace[bx].push(fx);
            vertexToFace[cx].push(fx);
        }
    }

现在我有了数组的哈希值，我可以检索给定面的邻居：

    var neighbors = [];

    neighbors.push( vertexToFace(face.a), vertexToFace(face.b), vertexToFace(face.c) );

这工作得很好，但我想知道它是否过度杀戮。我知道geometry.faces中的每个面都包含成员a、b、c，它们是geometry.vertices的索引。

我不相信存储了反向信息，尽管令人着迷的是，geometry.vertices 中的每个顶点确实都有成员 .index，但它似乎与面不对应。

我错过了一些明显的东西吗？

谢谢/。

Answer 1

我认为

for (var fx = 0; fx < g.faces.length; fx++) {
        vertexToFace[fx] = new Array();
}

应改为

for (var fx = 0; fx < g.vertices.length; fx++) {
        vertexToFace[fx] = new Array();
}

否则，如果顶点数大于面数，则

vertexToFace

中似乎不会有足够的元素。您还可以简化一点

vertexToFace[fx] = [];

Answer 2

对我来说，这取决于您的用例。如果你只想这样做一次，那么对我来说这确实是多余的，我只会遍历面孔来找到邻居。用复杂度来说，成本是 O(#G) #G 是面的数量。所以还不错。下次你这样做的成本将再次是 O(#G)。

在您的情况下，创建结构的成本是 O(#G)，然后检索邻居的成本取决于数组实现，但可能是 O(log(#V))，其中 #V 是顶点数。所以第一次检索成本是 O(#G+log(#V)) 所以 > O(#G) 然而下一次检索又是 O(log(#V)) 所以如果你有很多这样的检索操作，它似乎会使在大多数情况下要使用你的方式。但是，您需要跟踪几何形状何时更改，因为这会使您的结构失效。就像很多时候一样 - 这取决于......

旁注 - 问题还在于您如何看待邻居。一个共同的顶点或和边......只是提到它，因为我刚刚遇到了后者的情况。