## Creating a Planet : Geometry

I have wanted to expand on my previous post regarding ‘Cube to Sphere Projection’ for a while now, so in this article I am going to cover how I define the spherical geometry of the planets in more detail.

You can read the previous article here.

To be honest, I wasn’t very happy with details of the last post and I’ve wanted to expand on it ever since. The idea was to give people who wanted to work on a planet renderer enough information to make a start on their own project with ideas for the basic planet geometry. As previously mentioned, my planets are based on quad trees which are orientated around the planet center to form a cube (therefore 6 quad trees are required, one for each cube face). My LOD is then based on the distance of the camera to the particular node. This is slightly contrary to ‘traditional’ quadtrees which are usually split based on a number of objects assigned to a particular node.

There are many different implementations for both flat and spherical terrains (more information), but I find this method my favorite because of the ease of working with the different nodes of the quad tree; knowing that the size of a node is n^2+1 means texturing is easily accomplished and finding specific vertices in the grid becomes trivial. In this article I’m going to cover the planet geometry again, albeit in more detail.

Quad trees can be a huge help in optimizing terrain rendering. The basic idea is that we want to define a series of bounding boxes which contain parts of the terrain at different scales, which get progressively smaller (each node will be 1/4 the size of its parent node). We can use the bounding boxes to check which parts of the terrain are visible, starting at the root (the largest BB) and recursively calling the children all the way down to the tree leafs where all our geometry and sceneobjects lie.

Implementation :
We start by defining the root node of the tree which encompasses the entire area of the terrain (remember we are working with a 2d plane now – so this can be done the XZ axis). Each node has four child nodes (which can be null in the case of the leaf nodes) and a bounding box volume which defines the extents of the node along each of the two axis. It can also be beneficial to store the center point of each node, which I’ll come to later.

The general flow goes like: starting with the root node, subdivide it to produce 4 children of equal size which fit within the current BB and pass in the new bounding information from the root node to each child. This subdividing of nodes happens ‘n’ number of times. n can be either a predefined depth variable for how many levels the quadtree will have, or a minimum amount of objects allowed in a node. Once we subdivide down to this depth level we have reached a leaf node. The leaf node should contain the terrain geometry and possibily a collection of sceneobjects within its bounding volume.

One representation of a quadtree would be:

Rendering this terrain now only requires one call the draw function on the root node, where a bounding box check will be done with the camera view frustum. If the BB is within or even partially within the frustum we call the draw function of each of the children in the tree. This happens right down the tree until a leaf node is reached. Once at the leaf node, we know it is visible by the camera and so we can render the terrain mesh and the sceneobjects attached to the node.

This can save a lot of work; imagine that for a high level node which isn’t within the camera frustum, we can immediately cull this along with all its children saving all those draw calls. You can also further benefit for the fact that if a particular bb is fully within the camera frustum, you can go straight to the leaf nodes and draw them, saving on furter BB.Intersection() calls.

Using quadtrees can also narrow down the amount of work needed between scene object interactions because each scene object is assigned to the node within whos bounds they lie. When it comes to doing things like collision checks then you only need check each object with the other objects in the same node.

Storing the scene objects and the terrain mesh in the leaf node isn’t the only way to do this as you could also store them in each of the nodes at different depths (like chunked LOD). But as there are many ways of doing this, your implementation will depend greatly on what you want to achieve.

Defining the Planet Geometry
The above example of the quadtree works quite well for traditional terrains but for the purpose of creating a planet we need to actually define the spherical geometry based on a cube. This means defining the cube first and then transforming the vertices to form a sphere. In order to do this and make sure the LOD is sufficent to get down to one meter at surface level we need to calculate the size of the cube.

This is done using a binary logarithm of the radius of the planet, taking the gridsize of each node into account. A binary logarithm will tell you by what power or exponential you need to raise a base number to get the desired number. (or simply put, how many times must I subdivide a number to get to two). This is easy to work out:

```float _iRadius = 32;
int _iMaxLOD = (int)Math.Log2(iRadius * 2.0f);
```

This function will tell us that we need to subdivide a cube of size 64 (radius = 32), six times to get to a resolution of two (meters);

The only problem now is that 6 will subdivide the cube down to a resolution of 2 – but what if the patch grids have a size of 32^2? This would mean the resolution of the vertices on the surface would actually be a lot smaller than our desired 1 meter. To correct this we simply take the binary logarithm of the gridsize (n^2) and subtract it from _iMaxLOD. Luckily, these LOD functions only need to be called when initialing the planets, so we don’t really need to worry about performance.

Defining a cube of vertex Grids:
Defining a cube using quadtrees isn’t particually hard once you get used to it, but it can be a pain getting the orientation of the cubes quite right. Each of my terrain patches has a buildMesh() function which, when called, generates a grid of vertices around a center position on a given plane. The individual planes are very important as they will define which quadtree belong to what cube size. The function looks similar to:

```private void BuildMesh(Vector3 centerPos, Vector3 axisX, Vector3 axisZ)
{
// temp array for demonstraion
VertexPositionTextureNormal[] vertices = new VertexPositionTextureNormal[width*height];

int index = 0;
for(int u = 0; u < height; u++)
{
for(int v = 0; v < width; v++)
{
vertices[index].Position = new Vector3(centerPos + (axisX / width) * (v - width / 2) + (axisZ / height) * (u - height / 2));

index++;
}
}
}
```

Calling this function 6 times passing in the correct local orientations should produce a cube made up of 6 grids of vertices like this, where the red denotes the local X axis and the blue denotes the local Z axis. The back faces are missing in the diagram:

Based on the size of the cube which we calculated above, you should ensure that when defining a quadtree cube face, at least one component is equal to CubeSize / 2, and that the other two components are CubeSize. This will help created a closed cube.

Making the World Round:
Projecting the vertices from a cube out to a sphere is very easy. Consider the following diagram and the instructions to see how to do this:

1) Center the cube on zero (0,0,0).
2) Normalize each vertex in the grid. This will create a unit sphere.
3) Multiply the vertex position by the radius of the planet + the height of the terrain at this point, which will scale the sphere to the desired dimensions of your planet.

and all this convets to a simple function:

```private Vector3 GetWorldSpaceCoordinate(Vector3 cubePos, float height)
{
cubePos.Normalize();
return cubePos * _fRadius + height;
}
```

The height above can come from a variety of sources. I use 3d perlin noise in a number of shaders which render the heightmaps for each patch to several rendertargets of varing sizes. I then use the corresponding texture values are coord U,V to get the height for the terrain grid at X,Y. As long as the size of the rendertarget matches the patch nodes this seems to work fine.

Following the above instructions, you should be able to generate spheres which resemble the following image:

LOD Selection:
As with everything else, there are numerous methods for calculating when to split each quadtree node into smaller pieces. I don’t think this has to be particularly complicated to get good results. One thing I would suggest though is splitting the nodes of the quadtree based on the distance from the camara to the center of the closest edge on the bounding box. Using calculations which depend on the distance of the camera from the center of the node can cause huge differences at higher LOD levels when the camera is stradling the borders of nodes.

Other Little bits:
Of course this article only outlines the way I have defined planet mesh geometry and there are still many things left to do after this. Here are a few of the many things needed to get this geometry resembling a planet:

CPU heightmaps – I wrote this article to describe how to generate heightmap textures using the CPU.

GPU heightmaps – the same again, just adapted to work on the GPU

Real Scales and Imprecision – If you want to create realistically scaled planets, you will inevitably encounter issues with 32-bit imprecission which I discuss a little in this article.

Depth Buffers – This is another important issue when using realistic scales because all that distance between planets wont fit correctly into a 16-bit / 32-bit depth buffer.

1. #1 by Gahme on May 27, 2010 - 9:11 am

This is great, thanks for this “advanced” version of the first article. This should really help people out.

2. #2 by Philippe Da Silva on May 27, 2010 - 1:44 pm

Hi,

This is really definitivelly interesting and it may bring other game developers working on such game features.

By the way, did you ever thought of providing your planet rendering/scene management systems as a binary library that you would licensed to developers?

Philippe

3. #3 by Lintfordpickle on May 27, 2010 - 3:03 pm

@Phillipe, I have thought a little about releasing a binary library and also releasing the full source under an open source license in the future (which I still plan on).

Actually I’ve had quite a few emails asking the same thing but unfortunately I still don’t feel the quality of the code is good enough for releasing. Admittedly I haven’t spent all that much time on Britonia in the last few months (a few hours a week only) so I’d like to try and get some of the much needed core features in and working before I clean up and document everything.

All that said though, I don’t mind writing articles which explain a particular method that I’ve used to help people until the time comes that the game is ready 🙂

-John

4. #4 by MischaW on May 27, 2010 - 3:27 pm

Nice tutorial! Found out all that stuff by trial and error though… Probarbly took me a lot longer, than if i couldve read the article a few months ago!

There’s ONE thing that isnt clear to me though:

THE FRACTAL GENERATION!

I use fractals also, and use xyz on the planet as input to the function. This works GREAT up until a certain depth (18 or so). After that the fractal runs out of precision. Example at level20: point1.X = 0.123434 point2.X = point1.X = 0.123435. But do to fp32 precision this point gets:
point1.X = 0.12343 point2.X = 0.12344.

How do you solve that at deeper levels? i havent found an answer yet.

I experimented with a base and a detail map, but i cant get satisfactioning results: base map up until level 18, from then sample parent, and add fractal. But linear filtering just doesnt work + i get cracks where a deeper level has detail map, and the coarser doesnt!

How to fix this precision, i dont know. Do you know? It would be of great help!

5. #5 by Philippe Da Silva on May 28, 2010 - 9:30 pm

I would definitivelly be interested using such library just for the two main features that will be missing (for time reasons :p) from my current project: scene management for huge space distances & procedural planet rendering 😉

If you can/want to share such binaries, I’d be glad to use them :p

Philippe

6. #6 by Lintfordpickle on May 30, 2010 - 10:09 am

@ Phillipe, Hi,

I’m still not ready to release any code or binaries as the planet rendering is constantly changing (e.g. if I were to compile today, there wouldn’t even be planet textures).

As for the scene graph, this still is largely unfinished as I’m currently working on the distances since the game moved from the solar system level (~[-90AU, 90AU]) to the galaxy level (~[-50000LY, 50000LY]).

7. #7 by Lintfordpickle on May 30, 2010 - 10:23 am

hi MischaW,
My earth like planet has a quadtree depth cap at 17 levels, and like you stated this doesn’t appear to bad. a depth of 17 puts the width/height of a patch at ~48 meters apart if I’m not mistaken, with 32^2 vertice grid in this space. If I remove the cap then I also notice grainy terrain after level ~18.

I also noticed you posted the same question on the infinity board, so I’m also interested in if Flavien Brebion has managed to solve this.

I’ll have a look at this this week and see if I can get my quadtree to subdivide a lot higher and remove the grainy noise (which I haven’t triede yet).

-john

8. #8 by MischaW on May 31, 2010 - 2:46 pm

From one side: great to hear i’m not the only one with this particular problem.
On the other side: it might be real hard to overcome this precision issue, as it will be very hard to overcome with fp32’s on the gpu i guess. Maybe low level generation on CPU (after level 16/18) is a solution. Although that would be very slow…

I hope maybe you cán overcome what i couldnt 😛

9. #9 by Lintfordpickle on May 31, 2010 - 2:52 pm

Hi MischaW, I don’t know if you’ve seen this threa on Gamedev.net:

in which Flavien Brebion says he still has this problem. One way he deals with it (or plans to again in the future) is to use doubles on the CPU. I

I think I’m going to keep the height generation on the GPU for now though.

10. #10 by YellPika on June 1, 2010 - 8:36 pm

Hooray!!

Nice article. I’ve been developing some planets myself, but one of the things that keeps getting in the way is calculating what LOD to use.

What equation are you using to calculate LOD?

11. #11 by dartanham on June 12, 2010 - 7:37 am

Hi, it was a nice reading. I am curious, though, are you pre-building all lod levels at once? I must be missing something, because a detailed planet-size terrain won’t fit in ram, I guess. As to the heightmap part, I understand that it may be generated on the go, no problem. But what about the geometry, do you generate it when needed as well? Thanks.

12. #12 by dartanham on June 12, 2010 - 7:43 am

What I mean is, lets say you’re very far. Then you see just a coarse grid. Now, you approximate enough to split the tree one time, you have then some new nodes seen. More close to ground, you’ve split a lot then, what I don’t get yet is: have you created all these levels of geometry beforehand, or do you create them as you go (on a separate thread, maybe)? Thanks and congratulations for your great work.

13. #13 by dartanham on June 12, 2010 - 7:55 am

I only see this way, generate while you go. First the coarse one, then when you zoom in, split and generate the children, etc. I will think about this specifically, but it would be nice if you detailed this part a bit more. I am thinking about trying this to see what happens, but on my mind I see some problems when close to ground, as many patches need to be created at once, or am I missing something here. Very thank you.

14. #14 by dartanham on June 12, 2010 - 8:30 am

Sorry for spamming your page! I understand perlin noise and quadtrees, but I still can’t understand when you zoom in and split a node in 4, you have to generate more detailed noise 4 times, then how can you do that without slowing down the entire thing? Please feel free to delete my other posts if you wish. Thanks.

15. #15 by dartanham on June 12, 2010 - 8:38 am

Ok I’m so sorry. I am going to implement it with what I have in mind. I will just generate more detailed noise where the tree splits and discard the old parent node. It must work great! Should not be a lot of regeneration, I guess, just the splits! I will regenerate on a separate thread and hope it’ll be fast enough then! Please tell me something, thanks. =) Oh and please forgive me for spamming so much, I’m just… excited.

16. #16 by Lintfordpickle on June 12, 2010 - 9:37 am

Hi Dartanham,

The LOD levels are not all precomputed at once because, as you said, this simply wouldn’t fit in the memory.

The Quadtrees are split and created (VB, heightmap, normalmap, diffusemap) at run time and each split requires 4 nodes to be generated. I have tried it using multithreading, whereby the node generation (x4) requests are queued and run on a second thread but to be honest, the generation is not too bad also when only using a single thread.

Another point you mentioned which is correct is that when the camera is close to the ground and you are flying very fast, a great many nodes are split which could be a cause for concern. The only way around this really is to limit the speed of the camera/player/ship based on the altitude, then it isn’t really a problem.

If you’ve got any more questions, just let me know.

-John

17. #17 by dartanham on June 12, 2010 - 9:02 pm

Very thank you for replying. Regarding the last point (camera close to ground), perhaps low priority generation of nodes ahead of time *could* possibly solve that — just a guess, though. Warm regards!

18. #18 by Jazz on June 23, 2010 - 7:38 pm

How do you solve culling when approaching the planet surface. Since the sphere radius is half of the cube size, you pass the bounding cube before reaching the surface.(unless you land on bounding cube center). Tried making the sphere radius distance of the cube center to cube corner. Didn’t work to well.

19. #19 by Lintfordpickle on June 27, 2010 - 6:27 pm

hi Jazz,

I’m not 100% sure what you mean by culling, but I assume you mean the sub-dividing down to the surface of the planet, and not the winding order or frustum culling.

If this is what you mean, then the distances for calculating the sub divide are both done in the ‘real’ world space, that is, where all the positions are double precision. This means basically that I calculate the surface position of the center of each cube where it would be on the planets surface, and compare this with the camera position.

If that isn’t what you meant, then just write back and i’ll have another stab at it 🙂

-John

20. #20 by Lintfordpickle on June 27, 2010 - 9:19 pm

Hi again Jazz, after your message on youtube, here is an update..

***
I create a bounding sphere for each quad tree node, again using the surface coordinates of each node (take the furthest vertex distance from the center of the node as the radius of the bounding sphere), and then I do a totally normal camera frustrum intersection test.

I remember that I also had a few problems with this culling a long time ago, but multiplying the radius by 1.1 to make it slightly longer seemed to solve this. I remember the problem I had was due to the very large distances (in-precision issues again).

Hope this helps.

-John

21. #21 by Eric Lee on July 10, 2010 - 1:41 am

Thanks for all the writing you do, it’s very helpful to those of us who are experimenting with the same stuff.

I found an algorithm at http://mathproofs.blogspot.com/2005/07/mapping-cube-to-sphere.html that does a better (more evenly distributed) job of converting a flat mesh into a spherical mesh. It’s involves a bit more CPU work but relative to the time spent generating the height values themselves, it’s not really noticable in my engine.

22. #22 by Jim on September 12, 2010 - 2:45 am

Do you have any source code in a complete porject for this by any chance? I understand better by line by line debugging.

-Jim