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.
Search Nedrilad ::

Custom Search