Geometrical Robustness - Real-Time Collision Detection - page 480

Because edges are represented as a pair of vertex indices and this pair must be
used to index into a table, an open hash table (see Chapter 6) is employed instead
of a straight array. The hash key is computed from the two vertex indices. With
each key is associated a data block, containing the two vertex indices and the two
triangle edges the edge is connected to. This data block is realized by the following
structure.

struct EdgeEntry {
int vertexIndex[2]; // The two vertices this edge connects to

int triangleIndex[2]; // The two triangles this edge connects to

int edgeNumber[2]; // Which edge of that triangle this triangle connects to

EdgeEntry *pNext; // Pointer to the next edge in the current hash bucket

};

Assuming all edges are unique, the maximum number of edges, MAX_EDGES ,is
at most three times the number of triangles. The array edgeListHead is defined to
contain that many list-element pointers, corresponding to the pointers to the head
of each edge list. The hash key indexes into this array of list pointers. Again a second
array, edgeListEntry , of equally many elements is allocated as a pool, this time from
which to grab a list element each time a triangle is associated with a given edge list.

// If all edges are unique, there are at most 3 * MAX_TRIANGLES edges
const int MAX_EDGES=3*MAX_TRIANGLES;

// Hash table over edges, with a linked list for each hash bucket
EdgeEntry *edgeListHead[MAX_EDGES];
EdgeEntry edgeListEntry[MAX_EDGES]; // Entries of the linked list

To build the edge table, the main code loops over all triangles and all edges of
each triangle. If the edge does not already exist in the linked list of the computed
hash bucket, a new edge entry is linked into the bucket, specifying the triangle
from which the edge was taken, and the two endpoint vertices of the edge. If
the edge already exists in the hash bucket list, it has already been seen once and
thus the second triangle entry can be filled in with the index of the current trian-
gle. Here, it is assumed the function ComputeHashKey() implements the function
computing a hash key value that maps into the edgeListHead array. The main code
follows.

// Reset the hash table
for(inti=0;i<MAX_EDGES; i++) {