Graphics Reference
In-Depth Information
H
N
E
E
12
T
1
E
11
V
3
V
1
V
1
H
T
H
F
F
2
E
T
F
1
T
3
V
2
T
2
E
22
E
21
V
V
2
(a)
(b)
(c)
Figure 12.7
Data associated with (a) the winged-edge
E
, (b) the half-edge
H
, and (c) the
winged-triangle
T
.
The winged-triangle data structure is “face-based.” Each triangle references the
vertices defining the triangle, as well as the three triangles sharing its edges. Vertices
have a reference to an incident triangle. Edges are not explicitly stored in the winged-
triangle representation. The definitions of these three data structures are as follows.
// Basic representation of an edge in the winged-edge representation
struct WingedEdge {
Vertex *v1, *v2;
// The two vertices of the represented edge (E)
Face *f1, f2;
// The two faces connected to the edge
Edge *e11, *e12, *e21, *e22;
// The next edges CW and CCW for each face
};
// Basic representation of a half-edge in the half-edge representation
struct HalfEdge {
HalfEdge *ht;
// The matching “twin” half-edge of the opposing face
HalfEdge *hn;
// The next half-edge counter clockwise
Face *f;
// The face connected to this half-edge
Vertex *v;
// The vertex constituting the origin of this half-edge
};
// Basic representation of a triangle in the winged-triangle representation
struct WingedTriangle {
Vertex *v1, *v2, *v3;
// The 3 vertices defining this triangle
WingedTriangle *t1, *t2, *t3;
// The 3 triangles this triangle connects to
// Fields specifying to which edge (0-2) of these triangles the connection
// is made are not strictly required, but they improve performance and can
// be stored “for free” inside the triangle pointers
int edge1:2, edge2:2, edge3:2;
};