Sphere HEALpix

from Red Blob Games
12 Aug 2019

Table of Contents

A few years ago I was looking at how to place a tile grid 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. I’m less concerned about equal area but reading about it made me want to play with that subdivision of spheres.

Imagine peeling a sphere into “orange slices”:

“Orange slices” view of a sphere

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? Distortion: 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:

Filling with tiles
Animate:

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 really. We’ve covered a distorted sphere with square tiles.

You may wonder, what’s the point?

Back to the original experiment: I wanted to create a flat grid of tiles with a sphere topology, instead of a game that works directly on a sphere. Many tile games allow you go to off the east side of the map and warp to the west side. This is a reasonable approximation of the behavior on a sphere. 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.

What happens with this distorted tile map?

The previous experiment had twelve discontinuities (pentagons) on a hexagon map, and two of them were at the poles. In this map there are eight discontinuities on this square map, and none of them are at the poles. Remember that the discontinuities have to handle 360° of distortion per hemisphere, so with twelve, we have 60° per discontinuity: missing one triangle of a hexagon, turning them into pentagons. With only eight, we have 90° per discontinuity: missing one square, meaning there are vertices with three squares instead of four. The distortion is more severe but it occurs in fewer places.

Like the previous experiment, in this map the weirdnesses happen when you are traveling around the arctic/antarctic circles. When you “warp” from one square region to the next, directions change. Let’s take a closer look at these. It’ll be easier if we rotate the squares by 45°.

Rotate:

The north pole is blue and the south pole is red .

Click on neighbor to move there

If you move around you’ll notice that you can get turned around. North isn’t always up. This means the game UI is going to be trickier.

 1  Related#

Note that this is equivalent topologically to a cube but the HEALPix mapping from the tiles to a sphere is smoother than with a cube. The regular cube mapping uses the 6 faces of a cube; HEALPix places the 12 regions on the 12 edges of a cube.

Rhombic dodecahdron http://www.cse.cuhk.edu.hk/~ttwong/papers/rhombic/rhombic.pdf[1] (and https://www.cse.cuhk.edu.hk/~ttwong/papers/spheremap/spheremap.html[2]) seems like it has the same overall pattern, but the mapping to a sphere is different. {I studied this a bit more and now believe they are the same structure.} 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. It probably doesn’t matter for the application I have in mind. In HEALPix the grid lines seem to stay straight when crosssing the region boundaries, but curve within the regions, whereas in rhombic dodecahedrons they turn at the boundaries, but stay straight within the regions.

https://healpix.jpl.nasa.gov/html/intronode4.htm[3] - there are global numbering schemes for HEALpix, so that each tile can have a global number instead of a coordinate relative to its region

HEALPix is designed to support fourier analysis[4], which is overkill for my needs.

The quincucial projections[5] seem worth exploring too. https://observablehq.com/@redblobgames/tissots-indicatrix-for-healpix[6]

https://github.com/substack/healpix[7] - javascript lib ; d3 also has this but has more dependencies

 2  Nice to have#

  1. Animate a sphere to the orange slice peels. Practical in SVG, or do I have to use webgl for this? I guess there are two animations going on simultaneously: the equator is becoming a line, and the north-south great circles are becoming lines. Here’s roughly what it would look like, but I need to fill in the polygons
Animate:

Email me at , or tweet to @redblobgames, or post a public comment: