Game Development Reference

In-Depth Information

The representation of the mesh as triangles is optimal for the graphics hard-

ware and the rendering process, but it is unsuited for our algorithms because the

neighborhood of a vertex cannot be determined efficiently. If the overhead can be

afforded, neighbor lists for all vertices can be created at the beginning:

for
each triangle t
{

for
each pair of vertices v i, v jint

{

v i.neighborsAdd(v j); v j.neighborsAdd(v i);

}

}

This provides very fast access to the neighborhood of a vertex, but on the

downside, it takes a lot of extra memory that can become unacceptable. Since

neighborhood access is unlikely to become the bottleneck here, it is advised that

we trade some of the access speed for memory—there are way more efficient data

structures for this purpose [Campagna et al. 98]. Here, the
DirectedEdge

data structure is used:

struct
DirectedEdge
{

int
vertex;
int
neighbor;
int
next;
int
prev;

}

;

This data structure represents every triangle as three directed edges (see
Fig-

ure 14.3)
, where each edge has a reference to the vertex it is directed to, as well as

references to its previous, its next, and its “neighbor” edges, saved. When we now

give each vertex the reference to just one of the edges that head away from itself,

we can restore its whole neighborhood just with the
prev
and the
neighbor

references by the following algorithm:

Figure 14.3.
A directed edge (dashed) and its previous, its next, and its neighbor edges. To

retrieve the whole neighborhood information, we just need to have a pointer to the previous

and the neighbor edges of each vertex.