Advertisement Jump to content
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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 this post

Link to post
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 this post

Link to post
Share on other sites
Original post by alvaro
I'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.


Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!