# search mesh topology

This topic is 4898 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've posted this before, but still can't find a solution. I'm trying to search the topology of a mesh to find regions. So what I'm doing is trying to find all the triangles and put them in a winged-edge data structure. By searching the mesh topology, I figure all triangles that have neighboring triangles will give me a region because they all run together. So, if I have a sphere, it will show me all the elements (tri's) on the inside as one region, and all the elements on the outside as another region. But I'm having a hard time in figuring out how to search the mesh. Here's what I've come up with so far using the winged-edge data structure, but somehow I don't think it's correct.
processCurrentTriangle() {
(loop through edges) {
edge gives me 2 vertices (start, end)
left traversal gives me pred and succ edge
right traversal gives me pred and succ edge
edge gives me 2 faces (which means one new neighboring triangle)
mark new triangle as found (neighbor).
}

After all edges searched, add to region list.
Delete current triangle from mesh list list.
}

To find the neighboring triangles of the triangles in the model, do I loop through the edges of my first triangle to find it's neighbors? If so, then which of the neighboring triangles do I choose to make the next current triangle once I've found all the bordering neighboring triangles? Or do I just choose one edge of the original first triangle and make that neighboring triangle the new current triangle? Will that eventually take me down a path where I box myself in and find no more neighboring triangles, yet still leave me with unfound neighbors from the very beginning? (in other words, what if I chose triangles to the left somehow where it eventually took me in a circle of triangles, then I find no more left because I've sort of boxed myself in). I hope that made sense. Any help much appreciated. Or if someone can post some links that talks about searching a mesh topology, even better.

##### Share on other sites
I'm not even sure what you mean by "regions". Do you have a set of triangles and you want to find the connected components of the complement of the union of those triangles? For instance, if given a mesh that describes an icosahedron, the algorithm would identify two "regions" (inside and outside); if given a single triangle, the algorithm would identify a single region (everything but the triangle).

Or is this something completely different?

##### Share on other sites
Quote:
 Original post by alvaroI'm not even sure what you mean by "regions".

Here's a link to a previous discussion that might help on what I meant by regions. These guys really helped me understand what I needed to do, but I'm sorta stuck on how to actually search the mesh topology.

http://www.gamedev.net/community/forums/topic.asp?topic_id=339474

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634134
• Total Posts
3015744
×