Winged-edge structure implementation

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

Recommended Posts

Hi, I'd like to implement the winged-edge data structure and I was hoping to get some hints on how to go about it. My first issue is, how would I go about constructing the winged-edge structure out of a list of vertices and a list of faces which index into the vertex list? Something I can't quite wrap my mind around is how to determine the correct edges to set as next/prev CW/CCW edges. It isn't so hard to see what they should be when looking at a picture... What I've got so far is a face-to-vertex and a vertex-to-face table. Also, can anyone suggest some books/papers/material that I should look into for more detail on winged-edge and other b-reps. Thanks

Share on other sites

I can get the list of non-unique edges as follows:

Loop through all faces    Loop through all vertices        Add edge to table

The edge takes the the two endpoints as the current vertex and the next vertex in each face. If the current vertex is the last in the face, the other endpoint becomes the first vertex in the same face.

Note: winding is counter-clockwise.

Given the face/vertex list for a tetrahedron below

face1: 1 3 2
face2: 1 4 3
face3: 2 4 1
face4: 3 4 2

My winged-edge list so far looks like:

v1: 1, v2: 3 nccw_v1: 3, nccw_v2: 2 pccw_v1: 2, pccw_v2: 1 lface: 1 rface: 2
v1: 3, v2: 2 nccw_v1: 2, nccw_v2: 1 pccw_v1: 1, pccw_v2: 3 lface: 1 rface: 4
v1: 2, v2: 1 nccw_v1: 1, nccw_v2: 3 pccw_v1: 3, pccw_v2: 2 lface: 1 rface: 3
v1: 1, v2: 4 nccw_v1: 4, nccw_v2: 3 pccw_v1: 3, pccw_v2: 1 lface: 2 rface: 3
v1: 4, v2: 3 nccw_v1: 3, nccw_v2: 1 pccw_v1: 1, pccw_v2: 4 lface: 2 rface: 4
v1: 3, v2: 1 nccw_v1: 1, nccw_v2: 4 pccw_v1: 4, pccw_v2: 3 lface: 2 rface: 1
v1: 2, v2: 4 nccw_v1: 4, nccw_v2: 1 pccw_v1: 1, pccw_v2: 2 lface: 3 rface: 4
v1: 4, v2: 1 nccw_v1: 1, nccw_v2: 2 pccw_v1: 2, pccw_v2: 4 lface: 3 rface: 2
v1: 1, v2: 2 nccw_v1: 2, nccw_v2: 4 pccw_v1: 4, pccw_v2: 1 lface: 3 rface: 1
v1: 3, v2: 4 nccw_v1: 4, nccw_v2: 2 pccw_v1: 2, pccw_v2: 3 lface: 4 rface: 2
v1: 4, v2: 2 nccw_v1: 2, nccw_v2: 3 pccw_v1: 3, pccw_v2: 4 lface: 4 rface: 3
v1: 2, v2: 3 nccw_v1: 3, nccw_v2: 4 pccw_v1: 4, pccw_v2: 2 lface: 4 rface: 1

The left face is determined by the value of the outer loop above. The right face is found as the value of the outer loop when an edge with the same endpoints in reverse directions is found.

The problem then is, what more should be done when duplicate edges are found? There should only be unique edges in the winged-edge list so how do I point the next/previous links to the right edges?

Thanks.

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
14
5. 5

• 12
• 9
• 17
• 18
• 9
• Forum Statistics

• Total Topics
632597
• Total Posts
3007329

×