Sign in to follow this  

building a global edge list from a mesh

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this