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.

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?

Quote: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.

[link]
http://www.gamedev.net/community/forums/topic.asp?topic_id=339474
[\link]