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
}
}
}
finding adjacent faces in mesh
Author
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.
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)
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]
Example a quad. 0, 1, 2 (lower right tri), 0, 2, 3 (upper left tri)
3----2| /|| / || / ||/ |0----1tri 1 lower right = E1 0->1, E2 1->2, E3 2->0tri 2 upper left = E1 0->2, E2 2->3, E3 3->0indices = [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]
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]
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]
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:
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...
Without storing additional info, you could also do something like this, using simple marker flags:
get verts of triA and triBfor (each vert of triA) set mark value(vert) = 1for (each vert of triB) set mark value(vert) = 0At 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 triBelse// if either vert has vert mark == 1, then that edge is not part of BMay 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...
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.
- 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
