Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
How important is the exact topology of the map, as opposed to just letting actors go in one direction and eventually end up where they started? The simplest and most efficient representation would be a torus/donut. –  congusbongus May 27 '13 at 6:41
    
Yes, I mentioned spherical mapping and the problems it has with the poles. I want to store values around the surface so I need a mapping from 3D surface point to array index with as little stretching as possible. –  DaleyPaley May 27 '13 at 6:47
    
You could try to subdivide a tetrahedon to create a sphere. It consists of equally sized and distributed triangles. –  thalador May 27 '13 at 7:03
    
@thalador Thanks for the suggestion. Not sure but I think icosahedrons are better than tetrahedrons if I go the triangular route. But anyway, the tesselation is not the problem. It's the efficient array indexing that's bothering me. –  DaleyPaley May 27 '13 at 7:40
    
Additional read: gamedev.stackexchange.com/questions/10249/… –  Krom Stern May 27 '13 at 8:16

4 Answers 4

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.

icosahedron subdivision

share|improve this answer

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:

enter image description here

(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):

enter image description here

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.

share|improve this answer
    
That is indeed a very nice representation. My main concern with triangular methods was with maintaining triangular arrays and all the stitching. There is still a tiny bit of stitching here but the arrays are rectangular. Thanks, very good to know –  DaleyPaley May 28 '13 at 23:33

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

share|improve this answer
    
Ah, a truncated icosahedron. Yes, that is exactly what I need. Thanks. Also, while I never used winged edge, I have used half edges a lot for mesh manipulation so I am well versed in that area. Cheers, I am near a solution. –  DaleyPaley May 28 '13 at 0:21

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.

share|improve this answer
    
I had never heard of the hairy ball theory, it's quite interesting. Have to stop myself from making puerile jokes. I have distributed points on spheres before like that, but the problem is that polygonising it is far slower than subdividing a polytope. Also, the shapes and valence of the cells will be too non uniform for my liking. But thanks anyway. –  DaleyPaley May 29 '13 at 6:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.