Creating an organic grid on a sphere

I recently created a tweet about creating an organic looking quad grid on a sphere and it got rather popular.

Since I got some feedback and people asking me how to do this, I decided to give some more context. However, don’t expect a full-on tutorial for the engine of your choice. Instead, this is supposed to give you some more background on how to implement something like this and explain some of the theory behind it. I will attempt to cover the grid generation itself as well as give a brief introduction to tile placement and marching squares.

As is probably already clear to you, this is directly based on a grid generation algorithm that Oskar Stålberg posted on Twitter a while ago and which he uses in his sandbox town building game Townscaper. He has also written a very in-depth post on the process of building the tech behind Townscaper on imgur.

This was, however, only presented for a grid in a plane so far. What do we need to do to adapt it for a sphere (or even crazier shapes)?

The surprisingly simple answer is: nothing.

For the slightly more complicated answer, keep reading.

Grid Generation

To summarize the algorithm:

1. Start with a triangulation (in the tweeet above triangles in a hexagon)
2. Remove random edges triangles to create quads (we will now have a grid consisting of mostly quads but also some triangles)
3. Subdivide all quads and triangles into new quads
4. Relax the grid to make it look more natural

Step 1: Triangulation

The first step of the algorithm requires a triangulation. What is a triangulation, you ask? Well, there are many definitions (including but not limited to tracking bad guys in police crime dramas) but in our case we will define it as surface triangulation which, with the words of Wikipedia, is “a net of triangles, which covers a given surface partly or totally”. Simply put, we split our initial shape into many smaller triangles. In the tweet above this is the triangulation of a hexagon but we can triangulate any surface, really.

A popular triangulation of the surface of a sphere is the so-called icosphere. It is, of course, not the only triangulation but it has some nice properties including the fact that all triangles have the same size.

Below is an image of our icosphere in Blender:

Step 2: Removing Edges

Removing edges is relatively straightforward. However, we need to be careful to keep track of which edges we have already removed as to not accidentally remove an edge of a face that is already a quad. The rule for this is simple: when we remove an edge between to faces, we can’t remove any of the remaining six edges of the two now merged faces anymore. I solved this by keeping track of a list of edges that are stil “available” and only removing edges listed there from the mesh. When I remove an edge from the mesh, I remove the now forbidden six edges from the list.

If we did everything right, our former icosphere should look something like this:

Step 3: Subdivide Faces

We are currently facing one problem: Our result should be a quad mesh. That is, a mesh consisting only of faces with four edges. But there are still some triangles left in our current mesh. Luckily, triangles can easily subdivided into three smaller quads as illustrated in figure 3. In the same way, the already existing quads can be subdivided into four smaller quads as well. By doing this, we thus end up with a mesh consisting only of quads.

Done correctly, our mesh now looks like this:

Step 4: Mesh Relaxation

We are now almost where we want to be but the mesh does not look very organic yet. This is where the mesh relaxation comes in. For me, this was the trickiest step since it involved some experimentation to get it to look just right.

In the simpler case of a grid in a plane, there are some ressources available which outline possible relaxation methods, like this article from andersource.dev, but most of them seem to involve letting each quad force its vertices into a square shape.

I see no reason why an approach like this shouldn’t work on a spherical mesh as well. However, I approached the problem from a slightly different angle and started with (a restricted version of) Laplacian smoothing which is generally used to smooth meshes. In the end I needed to augment this by adding forces which try to prevent too small/large and thin quads as well. There are probably many good ways too relax the mesh but some good guidelines should be:

• each quad should be as square as possible
• all quads should have approximately the same area
• or any similar criteria

Using my approach, the final result looks like this:

Bonus: Tiles and Marching Squares

Deforming the Tiles

So now we have our mesh. But what can we actually do with it? I decided to go for a very minimalistic Townscaper “clone” which uses the sphere mesh for tile placement. Call it SphereScaper or an equally creative name.

One advantage of a quad mesh is that we can place deformed square tiles at each face. The math for this is relatively simple. We only need to deform from our mesh’s \(x\)- and \(y\)-coordinates (assuming \(z\) is up) since we can just extrude the \(z\) component along the face’s normal vector.

Now let’s assume that our tile’s corner points are \(\vec{a} = (0, 0)\), \(\vec{b} = (1, 0)\), \(\vec{c} = (0, 1)\) and \(\vec{d} = (1, 1)\) (that is, our tile is defined inside a unit square). An arbitrary quad face on our mesh is defined by four corner vertices in 3D space, let’s call them \(\vec{a}'\), \(\vec{b}'\), \(\vec{c}'\) and \(\vec{d}'\).

Each coordinate \(\vec{p} = (x, y)\) in the original tile can be described by the bilinear parametrisation

We can easily transform this to the new quad:

where \(\vec{p}'\) is the resulting coordinate inside the quad.

We can also easily rotate tiles by reordering the new quads’ corners.

var mdt = MeshDataTool.new()
...
var v = mdt.get_vertex(i)
...
v = a + v.x * (1.0 + v.z) * (b - a) - (1.0 - v.x) * v.z * (c - a) - v.x * v.z * (d - a) + v.normalized() * v.y
...

A Brief Introduction to Marching Squares

The most straightforward way of placing tiles on a grid or mesh is to assign values to each face of said grid and then draw the corresponding tiles. For very simple cases, this may work. However, you will quickly run into problems when you want to draw transitions between tiles, for example a shoreline between water and land. A very popular way of solving this is to use marching squares.

In marching squares, values are not assigned to the individual faces but to the mesh vertices instead. For each quad face we then read the values of its four corner vertices and choose the corresponding tile. In case of a simple configuration with two values like “land” and “water” we need to check for a total of 16 cases per cell. Since many of these are just rotated versions of other cases we only need to create a total of 6 different tiles to make marching squares run. (There are other algorithms which use more diverse tilesets as well like the blob tileset but most of them boil down to the same concept.)

Despite its name marchings squares works without modifications on any quadrilateral mesh so there is no downside to using it on an irregular grid. It even allows building non-rectangular structures with ease since the vertices do not neccessarily need to have exactly four neighbours. In my oppinion, this improves the organic feeling a lot.

I don’t want to delve much deeper here but in case you want to know more about marching squares, I found the Wikipedia article to be surprisingly helpful and there are lots of tutorials explicitly on the topic out there.

Thanks for Reading! 🎉

If you have any questions or feedback, feel free to contact me on Twitter: @CaptainProton42.