Graphics Reference
In-Depth Information
Another popular representation is the
quad-edge
data structure. See [Guibas85] for
details.
Data structures designed for nonmanifold geometry have also been suggested,
such as the
radial-edge
[Weiler88] and
star-edge
[Karasick89] representations. How-
ever, because nonmanifold geometry may have any number of faces connected
to an edge such data structures are more complicated than those for manifold
geometry.
To fill in an adjacency structure when the original data is given as face and vertex
tables, adjacency information must first be derived from the face and vertex tables. A
naive approach is to compare each face against every other face and write adjacency
information when two faces are found to share vertices. However, with an
O
(
n
2
) time
complexity this approach can handle only moderate-size meshes. The following two
sections show how adjacency information can be computed in
O
(
n
) time, which is
asymptotically optimal for the problem. The immediately following section describes
how to build a table for finding all faces incident to a given vertex. Section 12.2.2
shows how to compute an edge table, for looking up all faces sharing a given edge. The
same principles used in both sections can be applied to any similar table computation,
such as looking up all edges incident to a given vertex.
12.2.1
Computing a Vertex-to-Face Table
When a face/vertex table is given as input, the vertices of a given face can be imme-
diately located. However, locating the faces a given vertex is part of would require
an
O
(
n
) pass over all faces. To make this operation equally fast, a
reverse table
can
be computed: a table that for each vertex allows the immediate location of all faces
incident to the vertex. To simplify the presentation, it is here assumed that all faces
are triangles. The basic approach, however, is easily adapted to deal with arbitrary
faces. Given as input is a number of triangles,
numTris
, contained in a face table (an
array of type
Triangle
).
int numTris;
// The number of triangles
Triangle *tri;
// Pointer to face table array containing all the triangles
The
Triangle
structure is defined as:
struct Triangle {
int vertexIndex[3];
// Indices into vertex table array
};
Because each vertex might be part of a large number of triangles, the reverse vertex
table must maintain a dynamic, growable data structure associated with each vertex.
