Sign in to follow this  
Wizumwalt

finding adjacent faces in mesh

Recommended Posts

Hey all, I'm having a problem finding the adjacent face of a triangle and would like to know if there are quicker ways. I guess it's kinda like I'm tracing the mesh, looking for adjacent faces of each triangle. The way I currently do this is to loop through my triangle list and grab a triangle, then I grab another triangle off the list to compare it to making sure I never compare one with the same.
triA = get triangle from List
triB = get triangle from List

if (triA != triB) {
    for (each edge of triA) {
        for (each edge of triB) {
            if start,end point of triA_edge == end, start point of triB_edge ... then triA and triB share edges and are adjacent
        }
    }
}
The problem is, for every triangle I pull off of the List, I have to loop through the List again (and looping through each edge of each triangle) till a match is found. This can be very time consuming. I hope that made sense and if anyone has ideas on how to do this better, much appreciated.

Share this post


Link to post
Share on other sites
The ways Ive seen resemble what your doing. I use an index list, say a triangle is made of vertices 0, 1, 2 CCW. A triangle adjacent (sharing) edge 0 -> 1, will have its indices arranged either as 0 -> 1 (maybe), or reversed 1 -> 0 (more likely), so for each edge of each triangle (Ex. above, E1 = 0->1, E2 = 1->2, E3 = 2->0) i try to find a triangle with an edge that is either the same or reversed, if found, the triangles share the same edge, and are adjacent. If I dont find it, I mark the adjacent triangle index for that edge as being -1, meaning the triangle edge is a non closed edge, a floating edge. This can take some time depending on the model, but store this list for later use.

Example a quad. 0, 1, 2 (lower right tri), 0, 2, 3 (upper left tri)


3----2
| /|
| / |
| / |
|/ |
0----1

tri 1 lower right = E1 0->1, E2 1->2, E3 2->0
tri 2 upper left = E1 0->2, E2 2->3, E3 3->0




indices = [0, 1, 2, 0, 2, 3], cast to a "triangle_t" type

struct triangle_t
{
unsigned int vindex[3]; // triangle made of vertex indices
};

now the indice list is triangle list [{0, 1, 2}, {0, 2, 3}], 2 tris (assuming "triangle soup", 3 indices is one triangle, 6 indices above / 3 = 2 tris, length of the "triangle_t" pointer indices was cast to. When you find the edge that matches, mark which triangle you found the matching edge in. E 2->0 of tri one above matches tri twos edge of E 0->2 (opposite winding probably). Then you can store this in a adjcency_t list, one oper triangle

struct adjacency_t
{
int tindex[3]; // triangle edges shared with "triangle_t" indices
};

triangle one (lower right) above would be adjacency = {-1, -1, 1}, in other words for a quad, edge 1 not shared(-1), edge 2 not shared(-1), edge 3 (internal edge of quad) shared with triangle 2 ( [1] )

[Edited by - NumberXaero on June 9, 2006 3:30:02 PM]

Share this post


Link to post
Share on other sites
Yes it is very time conusming(and will be).

To improve loop(if you haven't done this already):

Max adjacents per triangle = 3.
So you can break the loop when 3 are found.
Just need to have 3 indices(to adjacents) per triangle with a initial value(-1(not found)) and search only for adjacents that aren't found yet.
1 adjacent found = 2 adjacents found (obvious)

I don't know any better solution :p

[Edited by - ivarbug on June 9, 2006 4:51:58 PM]

Share this post


Link to post
Share on other sites
If you have a manifold geometry (simple closed mesh), you could represent the mesh as a Winged-Edge-Data-Structure (WEDS). This data structure is more expensive than a simple indexed mesh representation, but is very beneficial for searches such as this. Adjacent face information is stored on the edge, so that info is immediately known.

Without storing additional info, you could also do something like this, using simple marker flags:


get verts of triA and triB

for (each vert of triA)
set mark value(vert) = 1

for (each vert of triB)
set mark value(vert) = 0

At this point, verts of triA that are marked with value 1, cannot be part of triB. So, do the following:

for (each edge of triA)
if both verts have vert mark == 0, then that edge is shared with triB
else
// if either vert has vert mark == 1, then that edge is not part of B


May look like more code, but if you count I believe you'll find there are less operations.

You're going to have to store more information somewhere to get maximum speedup in general. WEDS is one way. Storing for each vertex the triangles that use the vertex is another way (walk through edges of triA, and if both verts also point to triB, then that edge is shared), but WEDS is faster. All of these acceleration techniques require some preprocessing, and the preprocessing can take a bit of time...

Share this post


Link to post
Share on other sites
I've also used winged-edge in the past, with good results. Currently though I'm using the following system:

- Edges are stored in their own indexed array
- Each edge indexes the vertices and faces that it touches
- Each face indexes the vertices and edges that it touches
- Each vertex indexes the edges that it touches, sorted by angle
- Adjacent faces of a face can be queried via face edges
- Neighboring vertices of a vertex can be queried via vertex edges

So far I haven't run into a query or operation that this doesn't support well, but there may be some. I use it for subdivision surfaces and other procedural mesh generation, and it seems to work well.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this