Storing connectivity without linked lists

Suppose you had 100 people. Some of those people held hands. Some, didn't.

QUESTION: How many arrays would it take to store the connectivity information?

ANSWER: ONLY 1.

This beautiful idea probably stems from graph theory, but I've seen an implementation of something similar when storing edge to edge connectivity information in one of Eric Lengyel's implementation of finding unique edges. The reason this works is you invert the concept of an array. Instead of using the index of an array to store a value, the index of the array IS the value. In this case, the index of the array is the person, and the value is the next person your connected to.

So suppose you had 5 people, 0..4, and person 0, person 2, and person 3 were holding hands, and person 1 and person 4 were not holding anyone's hands.

The array would look like this { 0x02, 0xFF, 0x03, 0x00, 0xFF }. This means person 0 is holding hands with person 2, person 1 is holding hands with nobody (0xFF means end of the chain), person 2 is holding hands with person 3, and person 3 is holding hands with person 0, and person 4 is again, holding hands with nobody. Now in this case, this is circular connectivity. But suppose you only wanted to keep track of who on the left was holding your hand. Also assume that person 0 is holding the next person in their left hand. Then the array looks like this: { 0x02, 0xFF, 0x03, 0xFF, 0xFF }. The cool thing about it is the minute you find someone who is holding hands, you can instantly traverse the array and find all the other people holding hands. In this example, the connectivity goes in one direction.

This similar concept explains how Eric Lengyel's code works: http://www.terathon.com/code/edges.php

Simply stated, any time you discover a unique edge, you can use this algorithm to associate the connectivity of multiple edges with one edge. And no matter what which link ("hand") of the chain your in, you can always find the end of the chain (0xFF) because the connectivity goes in one direction. Since the connectivity goes in only direction, you only ever need one value for every one unique element. This means that, in the people example, as long as you only need to know who is holding your left hand, then the array will never need to be bigger than the number of people total.

With the edge concept, it is slighty different. You can, at most, have 3 * triangleCount individual edges, but some of those edges may not be unique. Generally, triangles are considering sharing an edge if, given triangles T0 and T1, there exists an edge such that edge index 0 < edge index 1 on T0, and edge index 1 < edge index 0 on T1. However, it is still possible that MORE than 2 triangles can share an edge. Let's say 3 triangles T0, T1, and T2 share an edge E, so that the actual geometry looks like a flattened mercedes logo. Then while there will be three triangles all sharing one edge, in this case there will only be two *unique* edges, E0 and E1, where E0 shares faces with T0 and T1, and E1 shares faces with T1 and T2.

In order for this algorithm to handle these cases, we want to store the connectivity of all the edges that are not unique. To do this, we define a semantic such that the first edge (defined by 2 indices) you encounter where triangle indices i0 < i1 starts the chain. And any subsequent edge with the same semantic i0 < i1 continues the connectivity chain. Using this semantic allows us to use connectivity when required, but NOT when we are dealing with normal edges that only are sharing two faces (triangles) per edge. Please see the code for more details :-)