CODEWITHSUNDEEP
three.jsmesh
Jeremy Fischer
Jeremy Fischer

Reputation: 41

Given a mesh face, find its neighboring faces

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/.

Upvotes: 4

Views: 1928

Answers (2)

TomFree
TomFree

Reputation: 1389

To me it depends on your use case. If you wanna do this just once then to me it's indeed and overkill and I would just iterate through the faces to find the neighbours. Cost is O(#G) to speak in complexity terms #G being the number of faces. So not bad. The next time you do it cost will again be O(#G).

In your case cost is O(#G) to create the structure and then for retrieving neighbors it depends on array implementation but probably O(log(#V)) where #V is number of vertices. So first retrieval cost is O(#G+log(#V)) so > O(#G) Next retrieval however is again O(log(#V)) so in case you have lots of those retrieval operations it seems to make sense to use your way in most cases. However you will need to keep track when the geometry is changed as this would invalidate your structure. So as so often - it depends...

Just a side note - question is also what you consider a neighbor. One vertex in common or and edge... Just mentioning it cause I just had a case where it was the later.

Upvotes: 0

dgmz
dgmz

Reputation: 413

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] = [];

Upvotes: 0

Related Questions