Next: Splines Up: Polyhedral Data Structures Previous: Euler's Formula

# Winged Edge

• Operations:
• Want to traverse
• Neighboring faces of a face/vertex
• Neighboring vertices of a face/vertex
• Edges of a face
• Want to modify (add/delete) the polyhedron
• Key ideas of winged-edge:
• Edge is important topological data structure
• Also, separate topology from geoemtry
• Edge is the primary data structure

• Pictorially:

• Data types:
```struct he {
struct he* sym;
struct he* next;
struct he* prev;
struct vert* v;
struct face* f;
void* data;
}
struct vert {
struct he* rep;
void* data;
}
struct face {
struct he* rep;
void* data;
}```
• Example: Neighboring faces of f

(picture)

```struct face* f;
struct he* e;
struct he* s;
struct he* fl[LOTS];
int i;

s = e = f->rep;
i = 0;
do {
fl[i++] = e->sym->f;
e = e->next;
} while (e != s);```
• Example: Removing an edge

```RemoveEdge(struct he* e) {
/* fix edge->edge pointers */
e->prev->next = e->sym->next;
e->next->prev = e->sym->prev;
e->sym->next->prev = e->prev;
e->sym->prev->next = e->next;

/* fix edge->face pointers */
ee = e->sym->next;
while (ee != e->sym) {
ee->f = e->f;
ee = ee->next;
}

/* fix face->edge pointers */
e->f->rep = e->prev;

/* fix vertex->edge pointers */
e->v->rep = e->sym->prev;
e->sym->v->rep = e->prev;

DeleteFace(e->sym->f);
DeleteEdge(e);
}```
• Variations:
• Some operations simplified by splitting edge into half-edges
• Uses a lot of space. Time-space trade-off.

• Manifolds with Boundary
• Half-edge allows representation of manifold w/boundary

Set sym pointer to NULL

• Allows for lone face

(picture)

• Makes some constructions easier
• New Euler formula

where B is number of boundaries

• Duality
• Faces and vertices are dual

Representations and rolls are identical

• Can replace each face with a vertex and each vertex with a face

(picture)

• If boundaries, then dual may not be manifold
• Evaluation
+
Faces with arbitrary number of sides

Vertices with arbitrary number of neighbors

+
Iterate over everything
-
Not space efficient
-
Painful to write/debug code
**
Simpler data structure better unless you need to modify, iterate

• API
• Discussions in papers use low level operators
• Better if user of package does NOT manipulate pointers
• Higher level ``safe'' operators, iterators:
• ForeachMeshVertex
• ForeachFaceVertex
• Split 3-1
• RemoveEdge
• Example: Split all faces 3-1
```ForeachMeshFace(m,f) {
p = SplitFace3to1(f);
SetPosition(P,x,y,z);
}```
• Which operations should we provide?

CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab

cs488@cgl.uwaterloo.ca