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?

• Jimmy, I edited out the stuff about shadow volumes and changed the title, since it didn't seem relevant and was potentially confusing - the question is actually just about building adjacency data, even though your ultimate purpose is to use it for shadow volumes. – Nathan Reed Sep 12 '13 at 17:32

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.

• Cool, searching for edges with the opposite order was a key piece of missing information; works a champ; +1 and accepted. – Maximus Minimus Sep 12 '13 at 18:37

Look at the half-edge data structure.

The idea roughly is that you store a list of half edges, e.g. the half of a particular edge attached to a particular face. This structure then also stores information about the corresponding half-edge for the adjoining face.

The data structure makes queries about connectivity, adjacency, and so on very efficient. There are algorithms to generate the data efficiently, though not necessarily "game run-time" efficiently (you'll probably want to do this offline in your asset pipeline).

See also these blog posts. I believe the structure and algorithms are also in Real-Time Collision Detection, but I don't recall for sure and dont' have a copy at the office.

• -1, sorry, but that didn't give any info I didn't already have, and was oriented around usage on the CPU rather than building a list with adjacency for use in a GS. – Maximus Minimus Sep 17 '13 at 16:41