Sphere HEALpix

A few years ago I was looking at how to place a tile grid on a sphere. The goal was to have a game where in any local area, the player sees a flat top-down 2D grid world, but globally, the world has the topology of a sphere instead of a plane.

Many tile games allow you go to off the east side of the map and warp to the west side. This is what should happen on a sphere. But it’s rare for a tile game to handle the poles correctly. Some will allow you to go off the north side of the map and warp to the south side, but that’s not what happens on a sphere. I wanted to find an arrangement of tiles that would approximate the behavior on a sphere.

At the time I considered the Platonic solids: tetrahedron, cube, octahedron, dodecahedron, icosahedron, and ended up playing with a hexagon map on an icosahedron. The main idea is to subdivide each of the triangles of the icosahedron into tiny triangles, then take the dual of that mesh, turning it into lots of hexagons, plus 12 pentagons. Then I tried to hide the 12 pentagons by placing mountains or oceans in those spots so that you can’t walk there.

Platonic solids aren’t the only ways to subdivide a sphere. HEALpix is an approach that warps quadrilaterals into shapes that fit on a sphere. Their goal is to have each quadrilateral have equal area, and they also want to be able to calculate Fourier transforms and other mathematical operations. I think those things aren’t quite what I need but I wanted to dig into it a little more.

Imagine peeling a sphere into “orange slices”:

It’s messy to fill these curved slices with a grid of tiles. But what if we distort the slices a bit by turning them into angular shapes?

Cool, but even if we fill the middle part with square tiles, the parts near the poles don’t quite work because of the 45° angles.

The solution is to apply the 45° angle to the middle part too:

We now have twelve squares that we can cover with square tiles. We’ve now covered a sphere with square tiles! Except of course we haven’t exactly. We’ve covered a distorted sphere with square tiles, or maybe we’ve covered a sphere with distorted tiles. This might be good enough if the game UI focuses on the tiles and not the sphere.

What happens with this distorted tile map?

 1  Layout#

The previous experiment had twelve singularities (pentagons) on a hexagon map, and two of them were at the poles. In this map there are eight singularities on this square map, and none of them are at the poles. Remember that the singularities have to handle 360° of distortion per hemisphere^[1], so we have a few choices:

The more singularities there are, the smaller the distortion can be. The approaches with smaller distortions use triangles or hexagons, which is probably why we often see hexagons or triangles covering a sphere, but less often see squares. HEALPix is a variant of the cube approach, but with twelve half-sized squares instead of six full-sized squares.

Like the previous experiment, weird behavior happens when you are traveling around a singularity point. Let’s take a closer look at how regions are connected to each other. It’ll be easier if we first rotate the regions by 45°:

The north pole is cyan and the south pole is purple . Neither has a singularity. Arrows point north. The 8 singularities are yellow . These are “no go” zones. We need to keep the player away from them.

 2  Movement#

In a game we’ll want to move a character (or camera) from one region to another. Let’s try this. Try going north repeatedly. Try going in other directions. Try moving around a singularity. Try moving around a pole. Get a feel for how it works.

If you move around the equator, the north arrows stay facing the same direction. You only get turned around when you move past the poles. Once you do the north arrows change direction. That means north arrows don’t always point up, and the game UI is going to have to handle that. I think this is inevitable in a sphere map that is presented as a 2d planar game UI. You either need to rotate the player or you need to rotate the world.

 3  More#

Compared to the hexagon mapping of the sphere I had looked at earlier, I like that this approach works with square tiles, and that the poles are ordinary locations you can walk around. Things I still need to read:

1. Cube maps^[2] seem like a more straightforward system. Instead of twelve regions with two singularity corners each, there are six regions with all four corners as singularities. More variants: S2, Arvo, COBE, quadrilateralized sphere.
2. Rhombic dodecahdron^[3] (and here^[4] and here^[5]) has the same overall pattern as HEALPix, with a different mapping to the sphere. In HEALPix the mapping to a sphere is not the same for all the regions. Four regions along the equator have four concave sides; the eight polar regions have two straight sides and two convex sides. In contrast, rhombic dodecahedrons have twelve identically shaped rhombus regions.
3. Tetrahedrons have the most distortion at the singularities but they seem simpler to program. When you reach the north or south pole you flip the map upside down and shift it by 180° longitude. Could it be that simple?
4. Peirce and related conformal mappings? These preserve angles so if you are moving north you always move north but … I’m not sure if that’s relevant for this problem.

HEALPix seems cool but it’s also more complicated than what I need. For example there are global numbering schemes for HEALpix^[6], so that each tile can have a global number instead of a coordinate relative to its region. It’s also designed to support fourier analysis^[7]. I don’t need these features.

How much distortion does HEALPix create? Tissot’s Indicatrix is a visual way to understand distortion for maps. It places circles on the sphere, then shows you what they look like when distorted. I think HEALPix doesn’t look bad^[8].

I think it’s a neat approach, but I don’t know enough yet to recommend it. I think a proper evaluation would require me to:

1. Procedurally generate a map on a planet.
2. Draw the map on the twelve square regions.
3. Draw the sphere versions of the map. (HEALpix, COBE, rhombic dodecahedron, quadrilateralized sphere, etc.)
4. Walk around and compare the flat and the sphere versions of the map to see if they’re close enough for a game.

I haven’t done this, and it will have to wait for another time. I want to also consider the cube (quadrilateralized sphere) approaches. They seem to have more distortion but also seem easier to program. More papers I want to read:

• Dimitrijević, A., Lambers, M., & Rančić, D. (2016): Comparison of spherical cube map projections used in planet-sized terrain rendering^[9]
• Lambers, M.: Survey of Cube Mapping Methods in Interactive Computer Graphics (2019)^[10].

Also check out HyperRogue^[11], which explores all sorts of interesting geometries.

Meta: I think it’s good to collect techniques, especially between projects. When you’re next working on a project you’ll want to select from the techniques you’ve learned about. It’s like playing a collectible card game. You want to spend some of your time collecting cards, so that you have more abilities, and some of your time playing the cards, so that you can use the abilities you’ve collected. (Exploration/exploitation) This page is one of those techniques. I dug into it just enough to think that it’s promising, so that if I am in the future working on a sphere+grid project, I’ll have another technique that I can try.