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[1] on and this spherical hexagon+pentagon map generation project[2] (both of those pages have fantastic screenshots). I decided ProcJam 2018[3] would be a good time to learn this.
I’m doing all of this for the 9-day ProcJam[4], so I’m trying to reuse my existing map generation code that works with Vladimir Agafonkin’s Delaunator[5] 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.
1 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:
[6]I’m using a Fibonacci Sphere instead. There are two algorithms listed on this archived wiki page[8], which was linked from stackoverflow[9], and there are some improvements in this notebook[10]. The layouts of the points are slightly different:
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.
Related: The Tammes problem[11] in math is about fitting circles onto a sphere to maximize the distance between the closest pair of circles. We don’t need anything this fancy for this project, as we don’t need something optimal, merely nice looking.
2 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.
- Project the points from the sphere onto an infinite plane using a stereographic projection[12]. 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.
- 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.
- 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[13] (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[14] 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:
- Rotate all the points so that the last point in the array is on the south pole. (see stackoverflow[15] for math details)
- Run Delaunay without that point, because the stereographic projection will project that point out to infinity.
- 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:
Instead of implementing this yourself, I recommend using Philippe Riviere’s d3-geo-voronoi[16] library. I didn’t end up using it because my mapgen4 code runs on the data structures from Delaunator[17], 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.
3 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[18] 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).
For most of my Voronoi map generation projects, I don’t actually use Voronoi, but something similar. Voronoi places the vertices at the circumcenters of the Delaunay triangles; I’m instead placing the vertices at the centroids of those triangles. 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[19].
4 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.
5 More#
Delaunay and Voronoi are calculated with Delaunator[20]. Graphics are rendered with regl.js[21], 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[22].
- There’s an interactive video explanation of stereographic projection[23] from 3blue1brown and Ben Eater!
- For point selection, also see Mike Bostock’s version[24], based on this wonderful article[25], which proposes an improvement over the Fibonacci approach. I haven’t implemented it.
- Also for point selection: https://www.jasondavies.com/maps/random-points/[26]
- For point selection on a sphere, also see this paper from Matt Zucker and Yosuke Higashi[27]. I used the Fibonnaci approach because it seemed easier but I may want to switch to something better at some point.
- Philippe Riviere has lots of cool Observable notebooks showing Voronoi on a sphere https://observablehq.com/collection/@fil/voronoi[28] ; he also developed a library called d3-geo-voronoi and a map projection[29] that uses this.
- Jacob Rus’s notebook[30] shows various methods for picking random points on a sphere.
- D3’s stereographic projection[31] shows what the projection looks like; note that they cleverly place the “infinity” point in the middle of the Pacific Ocean, so that no land gets the infinite distortion.
- Mikola Lysenko tells me that the Delaunay triangulation on a sphere is equivalent to calculating the convex hull of the points on the sphere.
- https://papers.otfried.org/2001-47.pdf[32] - paper describing Voronoi on spheres
- https://www.cis.upenn.edu/~cis6100/convex8.pdf[33] (section 8.5) - also describing Delaunay+Voronoi on spheres
- This page was unexpectedly posted on HN; see the comments[34].
I’m doing all of this for the 9-day ProcJam[35], so I’m intentionally not making it perfect, but instead stopping at “good enough”.