Geometrical Robustness - Real-Time Collision Detection - page 483

After this code has executed, componentNumber contains the number of com-
ponents in the mesh. The code relies on a recursive subroutine, which visits all
neighboring triangles of a given face.
void MarkAllNeighbors(int triIndex, int componentNumber)
{
int neighborIndex;
// Visit neighboring triangles of all three edges (if present)
for(inti=0;i<3;i++) {
neighborIndex = GetTriangleNeighbor(triIndex, i);
// If there is a neighboring triangle not already marked...
if (neighborIndex >= 0 && tri[neighborIndex].label != componentNumber) {
// ...mark it, and visit it recursively
tri[neighborIndex].label = componentNumber;
MarkAllNeighbors(neighborIndex, componentNumber);
}
}
}
The recursive procedure in turn relies on a subroutine, which given a triangle index
and an edge number queries the edge table for the other triangle sharing that edge,
returning the index of said triangle (or -1 if no such triangle).
int GetTriangleNeighbor(int triIndex, int edgeNum)
{
// Get vertex indices for the edge and compute corresponding hash key
int vi = tri[triIndex].vertexIndex[edgeNum];
int vj = tri[triIndex].vertexIndex[(edgeNum + 1) % 3];
if (vi > vj) Swap(vi, vj);
int hashKey = ComputeHashKey(vi, vj);
// Search hash bucket list for a matching edge
for (EdgeEntry *pEdge = edgeListHead[hashKey]; pEdge != NULL; pEdge = pEdge- > pNext) {
// ...
if (pEdge- > vertexIndex[0] == vi && pEdge- > vertexIndex[1] == vj) {
// Get index of the OTHER triangle of this edge
int whichEdgeTri = (pEdge- > triangleIndex[0] == triIndex);
return pEdge- > triangleIndex[whichEdgeTri];
}
}
// The input edge was a boundary edge, not connected to any other triangle
return -1;
}