Graphics Reference
In-Depth Information
All triangles sharing a vertex specified by the index
i
can now be accessed as in
the following code.
for (TriList *pEntry = triListHead[i]; pEntry; pEntry = pEntry-
>
pNext) {
/* do something with triangle tri[pEntry-
>
triIndex] here */
}
A reverse vertex table of this type is often practical to have. One possible use is for
determining the neighboring triangles of a triangle
T
by computing the union of the
lists associated with the three vertices of
T
. However, for this particular application a
more efficient approach is to compute a table that directly associates with an edge the
faces connected to the edge. Then, given a triangle the neighboring triangles could
be immediately located by looking up the connected faces through the edge table.
The next section illustrates how to compute this type of table.
12.2.2
Computing an Edge-to-Face Table
As before, the input is assumed to be a face table indexing into a vertex table. This
time, the problem is to compute a table that associates an edge with the faces con-
nected to the edge. Again, to simplify the presentation the faces are assumed to
be triangles. Another simplifying assumption made here is that the input mesh is a
(bounded) manifold. Thus, no edge will be connected to more than two triangles.
Both assumptions can be lifted without much further work.
Because triangles, and faces in general, are given with their vertices in a consistent
ordering (conventionally counterclockwise when viewed face-on), an edge from some
vertex
A
to another vertex
B
that is part of two triangles will occur both as (
A
,
B
) for
one triangle and (
B
,
A
) for the other triangle. To view both (
A
,
B
) and (
B
,
A
)asthe
same edge, it is necessary to enforce an ordering of
A
and
B
. Because the vertices
are indices, the representative edge can simply be chosen to be the one that lists the
vertex with the smaller index value first; that is, the edge (min(
A
,
B
), max(
B
,
A
)).
In a case in which vertices are given as a triplet of coordinates instead of an index,
the vertices can still be consistently ordered by ordering the one with the smallest
x
, then
y
, then
z
component first. This is the
lexicographic ordering
of the vertices as
implemented by the following code.
// Compare vertices lexicographically and return index (0 or 1) corresponding
// to which vertex is smaller. If equal, consider v0 as the smaller vertex
int SmallerVertex(Vertex v0, Vertex v1)
{
if (v0.x != v1.x) return v1.x > v0.x;
if (v0.y != v1.y) return v1.y > v0.y;
return v1.z > v0.z;
}
