Graphics Reference
In-Depth Information
The analog of a triangle mesh in space, taken one dimension lower, is a collec-
tion of line segments in the plane. (The space in which we work is one dimension
lower, and the objects we're working with are one dimension lower: line segments
instead of triangles.) We'll discuss these briefly as an introduction to mesh struc-
tures. We'll call one of these a 1D mesh.
A 1D mesh (see Figure 8.3) consists of
vertices
and
edges,
which are line
segments joining the vertices. Because the line segment between two vertices is
completely determined by the vertices themselves, we can describe such a struc-
ture in two parts.
• A listing of the vertices and their locations. Typically the vertices are
denoted by small integers; their locations are points in the plane.
• A listing of the edges, consisting of a collection of ordered pairs of vertices.
The following tables describe a simple 1D mesh:
Vertices
Edges
1
(0, 0)
1
(1, 2)
2
(0.5, 0)
2
(2, 3)
3
(1.5, 1)
3
(3, 4)
4
(0, 2.0)
4
(4, 1)
5
(3, 0)
5
(5, 6)
6
(4, 0)
This data structure has an interesting property: The
topology
of the mesh (which
edges meet which other edges) is encoded in the Edges table, while the geometry
is encoded in the Vertices table. If you adjusted one of the entries in the Vertices
table a little, the number of connected components, for instance, would not vary.
One might argue that if you moved the vertices enough, then two edges might
intersect when they didn't intersect before. That's true, but such intersections can
be removed by adjusting the vertices; the fact that the edge
(
1, 2
)
intersects the
edge
(
2, 3
)
cannot be altered by moving the vertices.
Indeed, one can treat the edge table (together with a listing of the vertex
indices, in case some vertex is not in any edge) as describing an abstract graph
(in the sense of graph theory). From this one can compute things like the Euler
characteristic, the number of components, etc.
(a)
(b)
(c)
(d)
Figure 8.3: A 1D mesh consists of a collection of vertices and straight-line edges between
them. The ones that most often interest us (shown in (a) and (b)) have one or two edges
meeting each vertex, and no two edges intersect except at a vertex. But there are also
meshes with more than two edges at some vertices, like (c), and ones where edges do inter-
sect at nonvertex points (d).
