algorithm - Building triangle adjacency data

Given a list of triangle indices, how exactly does one go about converting that to a list of indices with adjacency for a geometry shader?

Note that we're strictly talking about indices here - vertices are present, but we're going to focus solely on indices, because we can use them to match duplicate vertices without having to get into floating-point comparisons and epsilons - that work has already been done.

I know that for any given triangle in the list, indices {0, 1}, {1, 2} and {2, 0} (or {n, n+1}, {n+1, n+2}, {n+2, n} if you prefer) of it form it's edges; the index list is well-formed and respects winding order correctly.

I know that for any given such edge, we can search the entire list for another triangle that uses two of those indices, and the third index of that triangle is the one to use for completing the adjacent triangle for that edge.

I know that in the adjacency list each original triangle is represented by 6 indices, the original indices go into slots 0, 2, 4; the new indices to complete the adjacency go into slots 1, 3, 5. The index to complete for edge {0, 1} goes into slot 1, the index to complete for edge {1, 2} goes into slot 3, the index to complete for edge {2, 1} goes into slot 5.

What have I tried?

I've tried brute-forcing it, and yes, that will work, but I'm after a more elegant approach.

I've tried Eric Lengyel's edge list builder, but (1) it doesn't seem to respect the original triangle order, (2) it doesn't seem to respect winding order, (3) it's as clear as mud where to go next after you've built the edge list, and (4) I've a suspicion of sample code that has such obvious glaring errors as "triangleIndex" versus "faceIndex" - did the author even compile the code, never mind run it to verify it?

So -- any suggestions or pointers from here on?

Answer

I would try using a hash table for this (for instance, std::unordered_map if you're in C++). Build a hash table that maps from a half-edge (expressed as a pair of indices, in order) to the third index of the triangle the half-edge belongs to.

This can be built by simply iterating over the triangle list and adding each triangle's three half-edges to the hash table. If your initial index list had a pair of adjacent triangles, (0, 1, 2, 2, 1, 3), you'd end up with a hash table containing:

(0, 1) -> 2
(1, 2) -> 0

(2, 0) -> 1
(2, 1) -> 3
(1, 3) -> 2
(3, 2) -> 1

Note that edges (1, 2) and (2, 1) both appear in the table, representing the two sides of the edge, and pointing to the third vertex of each of the two triangles.

Then, to build the adjacency data all you have to do is iterate over the triangle list again, and query each triangle's edges with the opposite winding. So when processing triangle (0, 1, 2) you'd query edges (1, 0), (2, 1), and (0, 2). This will find the opposite vertex of each edge, if it exists.