Graphics Reference
In-Depth Information
V3,V2,V4
E3,E7,E4
F1,F4,F3
V2,V3
E2,E7,E8,E1,E4,E5
F1,F2
V3
V5
E5
V2,V6,V5,V3
E7,E9,E6,E4
F4,F3,F2
E4
F3
E6
E1
E3
F1
F2
V1
V4
E2
E7
E9
F4
E8
V2
V6
Figure 12.6 Adjacency information associated with each vertex, edge, and face facilitates
instantaneous access to their adjacent vertices, edges, and faces.
Although it is possible to work directly on this basic representation, doing so would
not be very efficient. To efficiently clean up the mesh geometry, removing degeneracies
and other things that could cause problems for collision detection code, additional
adjacency information must be computed.
Having full adjacency information allows retrieval of all adjacent vertices, edges,
and faces of a given vertex, edge, or face in constant O (1) time. Full adjacency
information for some features of the mesh from the earlier example is provided in
Figure 12.6.
However, storing a full set of adjacency information for every feature of a mesh
is prohibitive in terms of memory requirements. A good compromise between fast
adjacency queries and minimal storage is to store only some adjacency information,
enough to allow other needed adjacency information to be derived in a fixed amount
of time.
Several data structures, primarily for manifold solid models, have been suggested
for storing partial adjacency information. The winged-edge [Baumgart75], half-edge
[Mäntylä88], and winged-triangle [Paoluzzi89] data structures are examples of such
representations (Figure 12.7).
The winged-edge and half-edge data structures are “edge-based.”In the winged-
edge representation, references to the vertices of the edge, the two faces connected
to the edge, and the next and previous edges for both connected faces are stored
for each edge. In the half-edge representation, each edge is treated as consisting of
two half-edges: directed edges between the same two vertices, pointing in opposite
directions. Each half-edge holds references to its “twin”half-edge, the face the half-
edge is part of, the next half-edge of that face in counterclockwise order, and the vertex
the half-edge originates from. In both schemes, vertices and faces have references to
an incident (half-)edge.
Search WWH ::




Custom Search