Given a mesh face, find its neighboring faces

Question

I'm trying to efficiently find all neighboring faces of a given face. I'm taking a sly approach, but I wonder if can be improved upon.

The approach I've taken so far is to create a data structure after my mesh geometry is created. I build a hash of arrays to map vertices to the faces that are comprised of them:

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);
    }
}

Now that I have the hash of arrays, I can retrieve a given face's neighbors:

var neighbors = [];

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

This works fine, but I'm wondering if its over-kill. I know that each face in geometry.faces contains members a,b,c that are indices into geometry.vertices.

I don't believe the reverse information is stored, although, tantalizingly, each vertex in geometry.vertices does have the member .index, but it doesn't seem to correspond to faces.

Am I missing something obvious?

Thanks/.

dgmz dgmz · Accepted Answer · 2017-03-16T17:29:46

I think that

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

should be changed to

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

since otherwise, it seems that there won't be enough elements in vertexToFace if the number of vertices is greater than the number of faces. You can also simplify a bit with

vertexToFace[fx] = [];

Given a mesh face, find its neighboring faces

2 Answers