Tessellations and Quadtrees

To model the surface of a planet, we need to break the visible part of it up into a sheet of polygons (specifically, triangles) which can be fed to the 3d engine. It is convenient to first choose a mesh of polygons that tiles the surface (exactly covers it) and then generate the terrain in terms of that mesh. Any local mountains or valleys will be represented as variations in the height of polygon vertices, rather than worrying about the spherical coordinate system.

There are many ways we can map (distorted) polygons onto the surface of a sphere, or tessellate the sphere. One way is to inscribe a regular polyhedron (for instance, a cube) into the sphere, and then project the facets of the polyhedron onto the sphere. In the case of a cube, we will divide the sphere into six four-sided regions. Note that these regions won't be squares like the faces of the cube, they will have curved sides and 120-degree angles inside the corners.

Tessellations using an inscribed cube and an inscribed icosahedron

We'd like to eventually divide the surface of the planet into a lot more than six polygons. We will impose some finer mesh on the individual faces. It is easy to construct meshes that, when applied to a regular polygon, divide it into many identical polygons. The simplest example is putting a square grid on one of the square faces of the cube.

I would say that the best coordinate system from a user's point of view is latitude and longitude. This recommends the inscribed-cube tessellation: if we define an arctic and antarctic face, we are left with 2/3 of the globe covered with a coordinate system that is a squarish mesh aligned close to the latitude and longitude lines, and the remainder can be mentally mapped as latitude lines being concentric squares in the north and south polar faces.

When we project that square grid onto the surface of the sphere, we run into a problem: the grid squares are no longer all identical. The ones in the middle of the face are nearly square, but the ones near the edges are more oblong and the corner grid "squares" have a 120-degree internal angle. If we apply some terrain generation algorithm that expects a uniform mesh, we will get distorted terrain away from the centers of the squares. Here's a picture of a cube with sides projected outwards onto a sphere:

The way I fixed this was to switch from using an underlying cube to an underlying icosahedron (20-sided polyhedron, with equilateral triangles for sides). Each vertex of an icosahedron has five triangles around it, so when it's projected out onto a sphere the internal angles will be 1/5 of 360 degrees, which is 72 degrees, and which is only a 20% distortion of the ideally-60-degree angle instead of the 100% distortion I got with a cube. This switch also entailed going from Cartesian coordinates to non-orthogonal coordinates on the faces. This unfortunately removes any ability to mentally convert between face coordinates and latitude/longitude - but it has turned out that I don't do mental conversions like that anyway. Here's a picture of the icosahedron I'm using now with sides projected out onto a sphere - note how the triangles are less distorted that the squares are in the cube, above.

(I cut out some of the away-facing sides for clarity):

Subdividing the faces

The polyhedra shown above form a framework on which to build a planet, but the faces must be subdivided into many polygons to produce an appropriate amount of detail (if the planet is going to be more than a few pixels across, anyway). I produce this extra detail by breaking up each face into a grid of squares (for the cube) or equilateral triangles (for the icosahedron). I have found that putting a 4x4 grid on each face is a good starting point; here are pictures of that for cube and icosahedron faces:

Once the viewpoint gets close enough to the planet, even this set of polygons won't produce enough detail. I can't increase the level-of-detail of the whole grid indefinitely, because I would quickly find I have too many polygons to render in a reasonable amount of time. Instead I must increase the detail locally, so there can be very dense polygons around the viewpoint but sparser ones further off, like this:

(Here the red dot indicates the viewpoint).

This "expansion" lends itself to storage in a tree. Specifically, since each triangle splits into four smaller triangles, (and each square can easily be split into four smaller squares), it can be stored in a "quadtree" where each node of the tree, representing a triangle or square at some scale, has four children (or no children if it hasn't been expanded.)

I've made a Java applet that illustrates the quadtree expansion and collapse algorithm. This dates from when I was using a square grid, but the algorithm is still very similar on the triangular grid.


Another possible expansion which has been used in some terrain engines is the "bintree" where triangles/squares are split by successive divisions into two. For square cells, a bintree expansion would look like this:

I exclusively use quadtrees; for more information on a type of bintrees used for terrain generation called "BinTriTrees", see Seumas McNally's page on BinTriTrees.

Home | Terrain Generation