Dev notes: Creating Worlds, pt. 3

In the last part we left off with a quad that can be subdivided as needed, so there will always be a sufficient level of detail at the spot where the camera is positioned, and depending on how high above the terrain the camera is.

The next step is to create six quads like this and assemble them into a cube. And finally, extrude the quads outwards so the cube will turn into a sphere.

We have a bunch of twodimensional quads. Let’s say the middle is at (0,0) and the four corners go from (-1,-1) to (1,1). To keep it simple, our cube is going to have the same corners, just in 3D, so there’s 8 corners that go from (-1,-1,-1) to (1,1,1).

Let’s solve this with cheap tricks

All we need to do is to translate the twodimensional coordinates to threedimensional ones. The easiest one is the top face of the cube. Technically speaking, we’ve already been translating those 2D coordinates before so it would show up in 3D space on the screen, by adding a “height” (Y in 3D) coordinate to the width (X) and depth (Y in 2D, Z in 3D).

So now our height is just going to be 1 because it’s on top of the cube, and we end up with the corners (-1x,1y,-1z) to (1x,1y,1z). The bold Y is the new part we just added. It’s just as easy to add a bottom side to the cube by repeating the same thing, but using -1 instead of 1 as the height value.

But what about the sides? Let’s look at the right side of the cube. We already know that all four points are going to end up at the right – that means, the X coordinate will be 1. Which only leaves us the Y and Z to worry about. Well, just plop in the 2D coordinates and call it a day. So the right face translates from (-1x,-1y)-(1x,1y) to (1x, -1y,-1z)-(1x, 1y,1z). The bold parts are the new ones.

There’s another translation to do, though – testing which part of the quad is going to be subdivided, depending on the camera position. We can do this easily for our 2D quad – and the 2D quad is basically the top side of the cube, right?

Well, to put it simple – just flip the camera over. Let’s say the camera is right at the middle of the right side of the cube, and one unit away: (2, 0, 0). Flip it over to (0, 2, 0), and do the subdivision algorithm for the right side just as you would do if it was the top side.

Of course, the camera in the sketch isn’t even close to the middle of the quad, because I didn’t think this through when I made it. But I hope you get the idea. There might be more elegant solutions to this problem, but this is the “braindead simple” variant. Which is usually a good place to start at.

On a sidenote, this is one of the problems where the “inheritance model” of object oriented programming really shines. Of course, you could implement six completely seperate variants of the quads, one for each side. But most of the functions are exactly the same, and repeating yourself is a big no-no! So, a nice way to solve this is to have one abstract “parent” quad that has all the functions except for the translation functions that flip the coordinates over. Then you add six “child” quads and let them inherit from the abstract “parent”. Because they’ve inherited from the parent, each child can now do what the parent can do. Each child gets their own set of translation functions. This way, you only have to implement the shared stuff once.

We want spheres! We want spheres!

Now we’re half an article in and I’m still talking about flat quads. Let’s get on with the sphere show! Now, if only there was a magical function to turn everything into a sphere…

But wait! There is one! Our old friend Normalize().

As you might remember from the article “About Shading“, the Normalize function takes a vector and resizes it, so its length will be exactly 1. For example, normalize(2, 0, 0) and normalize(0.5, 0, 0) will both return (1, 0, 0).

And as it just so happens, for a sphere with a radius of 1 unit, every single point on its surface will have a distance of 1 from the middle.

That means: With a cube that’s centered on (0,0,0), you can simply normalize any point of its surface, and it will turn the cube into a sphere. If that doesn’t qualify as magic, I don’t know what does.

I should mention that, in order for this to actually turn into a sphere, you’ll have to subdivide the surface of the cube into many little pieces, like, for example, a grid… oh wait, that’s exactly what we’ve already done :-)

Once you’ve normalized a vector, you can add some fractal noise to its length, but just a tiny bit. Use the normalized vector components as input values to get a deterministic output.

You might have noticed that the grids are slightly distorted because of the curvature. If you use the grid points before they’re normalized as the input for the simplex noise, your terrain will be stretched as well. However, if you use the normalized output instead, the distortion will disappear and everything will render correctly.

And that’s it! Now we have a procedurally generated, spherical world with adaptive level of detail!

Of course, there’s still a lot more to do – this doesn’t really look like a planet yet. There’s still grass to plant, oceans to fill and mountains to sprinkle over the terrain. But let’s save that for next time.