How to index the faces of a Icosahedron?

Question

I'm writing a simulation that acts on a grid mapped across the surface of a sphere. The grid itself is a subdivided Icosahedron (The level of subdivision isn't known beforehand however)

With a grid of squares, it's easy to find adjacent cells because they'll be plus or minus 1 along either the x or y axis. But that isn't the case at all with these triangles, my mind is having a tough time visualizing a way to index the cells.

Is there any sort of coordinate system I could use for addressing the faces of the icosahedron, that at least makes it easy to get the 3 cells adjacent to any arbitrary cell in the icosahedron?

Answer 1

Essentially, you want to preprocess your geometry into a particular data structure which allows fast lookup of a triangle's neighbors.

If this is your only requirement, it is easy to "roll your own". For instance, for each triangle you would store its three edges, either as pointers to an edge structure or as indices into an edge table. Then, for each edge, you would store its two neighboring triangles (again either as pointers or as triangle indices).

This setup allows you to easily go from a triangle to each of its edges, and then to find from the edge structure the other neighboring triangle.

There are more advanced data structures for triangulated surfaces which allow more interesting operations to be done, for instance the doubly connected edge list or the winged edge data structure.

If you want to use a premade library, the GTS library will do what you need and much more.

Answer 2

For each side of the icosahedron, you can map the triangles to a grid, with each grid square divided in two, e.g. (hex numbering of the indices for formatting convenience):

 A
 +
 |\
 |0\
 +--+
 |\2|\
 |1\|3\
 +--+--+
 |\5|\7|\
 |4\|6\|8\
 +--+--+--+
 |\A|\C|\E|\
 |9\|B\|D\|F\
 +--+--+--+--+
B             C

For a side sub-divided n times, there are 4ⁿ triangles in the side, so you can create an array of that size for each side of the icosahedron to store any per-triangle data for your simulation.

A reference to a triangle can be stored as (side,row,column)

Row and column indices are 0-based. The column index is based on the number of triangles in the row (i.e. 2 per grid square).

If you have the side, row and column, you can calculate the index into the array for the side like this:

index = (row * row) + column

So you can store the data in a 2d array and access it like this:

value = data[side][(row * row) + column]

Adjacent triangles for a triangle with an even numbered column:

(side, row, column - 1)
(side, row, column + 1)
(side, row + 1, column + 1)

Adjacent triangles for a triangle with an odd numbered column:

(side, row, column - 1)
(side, row, column + 1)
(side, row - 1, column - 1)

This allows you to easily reference triangles in a subdivided triangle mesh without explicitly storing adjacency information.

The catch is when it comes to organizing this into an icosahedron. After computing the references to the adjacent triangles, you need to validate that the new reference is within the bounds of the side:

int rows = 1 << subdivision_count;
if(row >= rows)
{
    // compute (side, row, column) in adjacent side of icosahedron to B-C edge
}
else if(column < 0)
{
    // compute (side, row, column) in adjacent side of icosahedron to A-B edge
}
else if(column >= ((row * 2) + 1))
{
    // compute (side, row, column) in adjacent side of icosahedron to A-C edge
}

You'll have to store adjacency information for each side, and which type of edge it is (AB, BC, AC).

There will be 9 different possible mappings that you will have to figure out, one for each combination of edge type. For example, if the adjacent triangle crosses the AC edge, and this edge matches the AB edge of the adjacent side, then

side = adjacent side (from table)
row = row
column = column - ((row * 2) + 1)

etc

It's a more complex approach in some ways but simpler in others. The advantages of all this are:

• no need to store adjacency information for individual triangles, only for the icosahedron sides
• 3D triangle co-ordinates can be computed for the triangle given a (side,row,column) reference if you store the 3D position of A, B, C for each side, so no need to store those per triangle either