Jump to content
  • Advertisement
Sign in to follow this  
_V_

Winged-edge structure implementation

This topic is 4236 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

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 this post


Link to post
Share on other sites
Advertisement
Ok, I've thought about this a little bit more...

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!