Advertisement Jump to content
Sign in to follow this  

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.

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

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.

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!