Geometrical Robustness - Real-Time Collision Detection - page 482

each vertex can reference one (or all) of its incident edges. This addition would allow
all adjacency information to be accessed in O (1) time using any feature (vertex, edge,
or face) as the indexing element.
12.2.3 Testing Connectedness
As an example of what can be accomplished using adjacency information, consider the
problem of determining whether all faces in the face table are connected through an
edge to another face. If the faces are not all connected, the number of connected com-
ponents and a face of each component should be output. The example is presented
for triangles only.
To be able to know which connected component a triangle is part of, a label
field is added to each triangle data structure for holding the component number.
Initially triangles are labeled as not being part of any component. Then, all triangles
are looped over and for each unmarked triangle encountered the running component
number is increased by one, the triangle is tagged with this component number and
all neighboring triangles of the triangle are recursively visited and marked with the
same component number.
If all components are connected, the recursive procedure will end up visiting and
marking all triangles with the initial component number. When returning to the outer
loop, no unmarked faces will be found and the procedure will exit, saying there is
only one component. If there are multiple components, the recursive routine will
fail to visit some faces, which are eventually encountered by the outer loop, which
in turn increments the component count before recursively visiting the faces of the
next connected component, and so on. The following piece of code implements this
procedure.
// Unlabel all triangles
for (i = 0; i < numTris; i++)
tri[i].label = 0;
// Loop over all triangles, identifying and marking all components
int componentNumber = 0;
for (i = 0; i < numTris; i++) {
// Skip triangles already labeled
if (tri[i].label != 0) continue;
// Mark this triangle with the current component number
tri[i].label = ++componentNumber;
printf("Component %d starts at triangle %d \ n", componentNumber, i);
// Recursively visit all neighboring triangles and mark them with the same number
MarkAllNeighbors(i, componentNumber);
}