Delaunay+Voronoi on a sphere

from Red Blob Games
19 Oct 2018

Table of Contents

I usually work with 2D map generation, in part because it’s easier, but also in part because I enjoy games with flat worlds + heightmaps more than I like games with sphere (curved) worlds. I’ve wanted to learn how to work with spheres so that I could make maps of entire planets, like I saw in this spherical voronoi map generation project on and this spherical hexagon+pentagon map generation project (both of those pages have fantastic screenshots). I decided ProcJam 2018 would be a good time to learn this.

I’m doing all of this for the 9-day ProcJam, so I’m trying to reuse my existing map generation code that works with Vladimir Agafonkin’s Delaunator library. I will try easy solutions first instead of optimal solutions, and then go back and improve things later.

There’s an interactive demo at the end.

#Points

The first step for a Voronoi Planet is to pick the points. I would like evenly spaced points to start with, and then I can add some jitter to make them less even. The standard approach is to use a subdivided icosahedron:

Subdivided Isocahedron (Wikipedia)

I’m using a Fibonacci Sphere instead. There are two algorithms listed on this archived wiki page, which was linked from stackoverflow. The layouts of the points are slightly different:

Two algorithms for generating points

Although these look pretty nice, there’s a downside: the patterns at the poles is different than the pattern elsewhere. I think a subdivided icosahedron wouldn’t have this problem.

#Delaunay Triangulation

The second step is to construct a Delaunay Triangulation on these points on a sphere. A standard Delaunay library works on points in a 2D plane. Surprisingly, we can use existing 2D Delaunay libraries to run on points on a sphere. The key idea is to transform the data before running the algorithm.

  1. Project the points from the sphere onto an infinite plane using a stereographic projection. This maps the northern hemisphere onto points inside the unit circle, and the southern hemisphere onto points outside the unit circle. There’s a proof that this projection produces a correct Delaunay Triangulation on a sphere; links at the end of the page.
  2. Run the unmodified Delaunay triangulation library on the points on the infinite plane. This general idea is useful — instead of modifying an algorithm, you can often modify the input data, run an unmodified algorithm, and then modify the output data.
  3. Wrap the results from the infinite plane back onto the sphere.

There will be a hole left over. The outer boundary of the Delaunay Triangulation is the convex hull of those points. That convex hull ends up wrapping into a small polygon near the south pole of the sphere. See this animation I made (also available in animated GIF and Quicktime movie formats).

The convex hull will wrap into a hole at the south pole:

We need to complete the mesh in this hole. It turns out I already implemented this for my dual-mesh library, for different reasons, and I reused that code here. Place a new point on the south pole, then add triangles to connect the edges of the hole to the new point:

This works but it ends up with one extra point that wasn’t in the original set. An improvement, which I haven’t implemented yet, would be to instead reuse an existing point:

  1. Rotate all the points so that the last point in the array is on the south pole. (see stackoverflow for math details)
  2. Run Delaunay without that point, because the stereographic projection will project that point out to infinity.
  3. Stitch that point back in as shown above.

I should implement this rotation step at some point, but it’ll have to be later. Without that step, it’s good enough for now. I expect to have half a million points so adding one extra at the south pole won’t be a big deal, I think.

Here’s the resulting Delaunay Triangulation:

Delaunay Triangulation on the sphere

Instead of implementing this yourself, I recommend using Philippe Riviere’s d3-geo-voronoi library. I didn’t end up using it because my mapgen4 code runs on the data structures from Delaunator, and it was going to be more work to adapt it to use d3-geo-voronoi than to implement the projection and stitching myself. The projection is around 10 lines of code, and the stitching I already had implemented. His is probably more robust than mine.

#Voronoi Regions

Once we have the Delaunay Triangulation on a sphere, we need the Voronoi regions. This is fairly simple. The Voronoi regions are formed by connecting all the triangle circumcenters for the triangles touching one of the input points.

But how do you computer a circumcenter for a triangle on a sphere? I found a solution on stackoverflow and implemented it.

The circumcenters all end up slightly inside the sphere. It’d probably be slightly better if the circumcenter was moved to the surface of the sphere. To do this, take (x, y, z) of the circumcenter, calculate the distance d = sqrt(x² + y² + z²), then move the circumcenter to (x/d, y/d, z/d).

Voronoi regions on the sphere

For most of my Voronoi map generation projects, I don’t actually use Voronoi, but something similar. I move the points from the circumcenters to the centroids. Not only is this cheaper to calculate, it ensures that all the region edges have a reasonable length. With Voronoi, some of the edges have small or zero length, and that makes it harder for me to place roads and rivers using those edges. I have written more about this topic here.

Centroids instead of circumcenters

#Demo

The demo was a lot of fun to play with. It’s a little slow when you increase the number of points to the maximum (100,000).

Draw:
Select points using:
Number of points on sphere:
Jitter:
Sphere rotation:

Slightly messy source code is here.

#More

Delaunay and Voronoi are calculated with Delaunator. Graphics are rendered with regl.js, which makes it much easier for me to use WebGL than if I had tried using WebGL directly. I also use a little bit of glMatrix.

I’m doing all of this for the 9-day ProcJam, so I’m intentionally not making it perfect, but instead stopping at “good enough”.

Part 2 is about elevation, biomes, rivers.

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