Dev notes: Creating Worlds, pt. 1

Ah, procedural landscapes! So much fun. And easy to program.

You start with a chessboard mesh and place it under the camera. The height of each mesh point is generated by a fractal noise algorithm (such as Perlin).

It would be great if you could just increase the resolution of the mesh until you can’t make out the single polygons anymore, but resources are limited!

So you implement Level of Detail (LOD) and increase the mesh resolution only in the middle, where the camera is. Now the outer parts of the mesh look rather crude, but it doesn’t matter, because they’re far away from the camera – and the closer parts of the mesh look nice and detailed.

Now it’s time to move the camera, since you want to be able to explore this landscape. But there’s a problem! You’ll have to recompute the mesh as you move, or you’ll quickly run out of terrain under your camera. Basically, you’re taking the ground with you as you move along (which is pretty much what tanks do, in a way).

You could recompute the entire mesh every time, but that would take a long time. On second thought, the parts below the camera are still good, so just add a bit of new terrain to the front of the mesh (and for every LOD submesh, of course – excuse the crappy illustration below, but you get the idea).

And while we’re at it, delete a bit on the back – you don’t need it anymore and this way you won’t run out of memory.

That’s all! Now you can compute normals and textures, add some water, grass and trees, and you can travel across your procedurally generated world until you have moved far enough that your floating point coordinates run out of precision. Here’s one of my later attempts.

This Earth is too flat

This approach works for many kinds of procedural world engines, but it does have three important characteristics: The generated landscape is flat, it’s endless, and the chessboard size is static.

That means that moving the camera back and forth works just fine, but when you move the camera up and down, you run into problems. The closer you get to the ground, the less detail you see. And if you move your camera high above the terrain, the illusion breaks down and it becomes obvious that there’s a highly detailed patch just below the camera, but the borders of the chessboard are much less detailed.

This problem might be solved by tweaking the LOD system. But wait, there’s more. “Flat and endless” is the opposite of this:

If you’re on a planet and keep moving along the surface, you’ll eventually end up in the same spot again. Can’t do that on an endless plane!

So if you’re planning on developing a space game with procedurally generated planets that you can land on, this approach doesn’t work. Non-spacefaring frog is sad.

sadfrog2

First, let us consider a spherical cow

Here is an approach to the spherical planet problem that I am working on right now. There’s no guarantee I will ever finish this or that I won’t switch to a different approach as I go, so I’m publishing this as a collection of rough ideas.

The typical approach to generating a threedimensional sphere with computer graphics is to start with one of the “Platonic solids“, subdivide the faces in regular intervals and extrude the resulting points so that each point has the same distance to the center of the body. Let’s go over this step by step.

platonic_solids

Why start with a platonic solid?

The big idea is to reduce a threedimensional problem to a twodimensional one. Platonic solids have the advantage that every face of a body has the same dimensions. So you can take multiple flat planes, cut each of them to the required face shape, piece them together and you will end up with a regular threedimensional body.

Subdividing and extruding

Each point on the surface of a sphere has the same distance to the center of that sphere. Each corner point of a platonic solid has the same distance to the center of that body. However, the points in the middle of a face are closer to the center of the platonic solid than the points at the corner of a face because they’re on a flat plane.

By subdividing the faces of a solid in regular intervals, we can add more points. And by extruding the points outwards so that every point has the same distance to the center, the body will become more and more spherical. Take a look at this Wikipedia article – “Geodesic Grid”.

subdivision

Which one of the platonic solids to start with?

The tetrahedron, the octahedron and the icosahedron are all made up of regular (equilateral) triangles, and once you start subdividing the dodecahedron, you end up with regular triangles, too. This brings along some disadvantages.

Regular triangles don’t map well to twodimensional data structures such as arrays, they’re complicated to measure distances on, and crossing over the edge onto the next triangle is tricky as well. The culprit is the alternating distance between the tip and the base points.

But all is not lost, thanks to the good old cube.

Mapping a sphere to a cube (also known as a “Quadrilateralized spherical cube“) makes life simple, since you’re essentially dealing with six curved squares.

The eight “poles” where the corners meet require some special attention, as the subdivided squares will be slightly diamond-shaped because of the distortion. But aside from that you get efficient data storage in twodimensional arrays, easy computation and easy movement and distance measuring.

This article will be continued in part 2.

by