# building a global edge list from a mesh

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

## Recommended Posts

I am building a global edge list of all the unique edges of my mesh. I am using the winged-edge data structure for my edges which I store in this list. I'd like to know if my algorithms are well enough thought out to implement it now (i.e. if I understand it) and I've listed my steps below so if someone could look at them and tell me if it's solid, it would be much appreciated. I only have one question about it which is in parenthisis in step 4 using an undirected graph. --- Construct a global edge list (contains all unique edges from the mesh). --- 1) Construct an empty region list (global edge list). 2) Choose a starting triangle (now the current triangle) from the mesh list. Create 3 winged-edge data structures. 3) Initially, assign two of them as frontier edges (local edge 0 and 1). a) Initially, both will be unmarked as this is first triangle. So do basic operation #2 (shown below) to close the sequence of frontier edges. 4) Now I walk around the frontier edges in order and add or substract one vertex from the frontier. (At this point, do I construct an undirected graph to walk around the edges and test? If so, how so?) a) Test 2 edges at a time. Is edge operation #1, #2, or #3 (shown below). If operation 3 is used, then all edges found and goto step 7. 5) Populate winged-edge data structure for new edges and add edge to list. 6) Set new frontier edges or boundaries (in the undirected graph?). Continue walking around frontier borders and pick next two and goto step 4. 7) This list is now done (should have come from step 4a) and region is complete. 8) Set this region list aside. If there are still triangles left in mesh list, create a new region list and goto step 1. --- basic operation --- Operation #1: 2 consequtive edges of the frontier shared by one "outside" triangle. --> Handle that triangle, replace the two edges by that triangle's third edge, shortening the frontier polyline by one edge. Operation #2: A frontier edge not sharing "outside" triangle with either of its neighboring frontier edges. --> Handle that triangle, replace the edge by the two other edges of that triangle, thus lengthening the frontier by one edge. Operation #3: Only 3 fontier edges left, sharing the same outside triangle. --> Handle that triangle, then the process is DONE.

• ### What is your GameDev Story?

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

• 13
• 9
• 9
• 34
• 16
• ### Forum Statistics

• Total Topics
634124
• Total Posts
3015661
×