Spherical map representation

Question

My latest game will take place on a small planetoid. I am looking for good data structure for representing cells on the surface of a sphere. Triangles, squares, pentagons, hexagons? Which one minimises stretch the most and creates the best tiling?

Spherical mapping is the easiest but the stretch at the poles is unacceptable. Cubemapping is also fairly easy but there would still be considerable stretch near the cube corners. Subdividing an icosahedron seems the best in terms of stretch but there is the problem of indexing many triangular arrays and finding neighbouring cells at the boundaries would be difficult.

I guess I could use a single linear array of points representing N-gons, each with an array of N neighbour indices, but that seems like a huge waste of space.

The game has RTS elements so I will be storing things like influence maps and performing A* pathfinding and convolution, so the representation has to be efficient.

Answer 1

Okay, for anyone interested in this topic I will now detail the solution I have chosen. Thanks to every one who replied and gave me ideas.

First, for the 'best' tesselation, I will choose the truncated icosahedron as a starting point. Subdividing it leads to a very nice tesselation of hexagons with 12 pentagons providing the curvature. Also, continuing the subdivision on its dual will give me a very good triangular mesh for rendering with nice properties. Regarding the 12 pentagonal cells: I can ignore them, make them special (like the only places bases can be constructed), or I can hide them under scenery.

The hexagonal and pentagonal cells will be stored in a half edge data structure for easy access to neighbours and fast traversal. The only tricky part is finding which cell a given world point is in, but that can be done by starting at a random cell and walking towards the point through neighbours.

I hope someone finds this information useful. I have learned a lot and am looking forward to getting some results.

Edit:

Here is an image showing the result of my icosahedron subdivision and dual mesh switching using half-edge data structure.

I may do a few iterations of relaxation to get the cell areas even more uniform.

Answer 2

There is a way to do this rather elegantly based on subdividing an icosahedron, as you suggested in your question. An icosahedron is made of 20 equilateral triangles, and these triangles can be grouped into 5 sets, where the 4 triangles in a set form a parallelogram shape:

(The groups of four triangles with a squiggle drawn through them are the parallelograms I'm talking about. The arrows say which edges would be glued together to fold this up into an icosahedron.)

If these triangles are subdivided into smaller triangles, the whole parallelogram can be indexed like an n by 4n rectangular array (n = 4 in the example):

The numbers in each cell are the column numbers of the rectangular array. The rules for finding neighbors within the array are fairly simple: the horizontal neighbors are just plus or minus 1 column, while the vertical neighbor is either minus one row and plus one column, or plus one row and minus one column, depending on whether the column number is even or odd, respectively.

However, you still have to write some special-case code for finding neighbors that cross the boundary from one parallelogram to the next. It's a bit tricky since in some places, the top or bottom of one parallelogram will be connected to the side of another, or the top and bottom will be connected with a horizontal offset between them, etc. Possibly a half-edge structure or similar for the parallelograms would be useful here. However, at least the relationships are symmetrical amongst all 5 parallelograms: they all follow the same pattern in which side is connected to which other side of their neighbors.

Answer 3

Hmmm - the comments about stretch indicate you're moving between spherical and planar mapping, that's what leads to the distortions at the poles

If you want the tiles to be flat and uniform, you're correct that a icosahedron, specifically a truncated icosahedron is pretty common

You can find all of the different mappings here - Spherical Polyhedrons on wikipedia

As far as maintaining the relationships between the faces, that's a topology problem - you might find either winged edge or quad edge helpful (and you get the wonderful opportunity to meet a whole new form of algebra) Winged Edge

Answer 4

I guess I'm coming a little bit late to the party, but here's a possible solution that can be used to maintain a spherical world of arbitrary size and uniform appearance.

The key thing to understand here is that the world isn't flat, and therefore a 100% uniform tiling would be impossible (this follows from the so-called Hairy Ball Theorem). Some irregularities have to be allowed, and the best we could hope for is to spread those irregularities evenly around the surface, making each as small as possible.

It's actually quite easy to do in non-deterministic way. First, choose N random points uniformly around the surface. Make sure those points are actually uniform (see Sphere point picking, formulas 9-11). In second step we make those points less random and more uniform: assume all those points have negative electric charge so that they repel each other. Simulate the movement of the points for several steps, until they converge into an equilibrium state. This final configuration of the points will give you a mesh which is nearly uniformly distributed around the surface of the sphere.