Quad sphere subdivision algorithm

Question

I like to generate some planets like Kerbal Space Program does. By some videos of the developers I know that they use a quadsphere, which consists of six “entities” as a minimum. These are all plane meshes, which get subdivided the closer you get. This allows a ground to orbit level of detail. However, I have some problems understanding this subdivision algorithm:

1. Since I have six separate meshes, how do I know where I have to subdivide them, if they are all separate?

2. If I always just subdivide the quad the camera is over and I end up with something like this:

even though I want something like:

.

So how can I ensure a sense full 2:1 subdivision with neighbour quads?

Answer 1

Implementing LOD subdivision on terrain is quite complicated, I rather recommend to use a library or something. But if you prefer to learn the hard way here are the principal steps you need to do:

First, unlike your assumption, you do not start with 6 meshes like the most zoomed out version, but you define your geometry at highest resolution (most zoomed in version). So if we assume you implement 4 levels (0: lowest, 3: highest) you start with a sphere consisting of 4³ * 6 = 384 meshes that is the entire sphere at level 3. Then you need the meshes for the lower levels. There are 4² * 6 meshes for level 2, 4¹ * 6 for level 1 and 4⁰ * 6 for level 0, the simple cube. That gives you in total 510 meshes for all levels.

At runtime, you just determine the distance of each of your 384 level 3 meshes to the camera (you may check only a subset). If the distance is long enough you render it with a lower level (notice that you always join 4 predefined higher meshes into one lower level mesh). That's a basic LOD implementation.

Once you have finished this, you'll notice that the meshes at the border from one level to another are not properly connected and expose artifacts (graphical glitches). To solve that too, you need stitching. The real pain of this topic (interestingly your sphere image does show stitching already). So for stitching, you need extra border meshes for each level and side and corner which gives you an additional 8 fold mesh count ⇒ ~4590 meshes in total.

Actually, it's better you do not use something like generic meshes but using directly OpenGL (or whatever). Which gives you additional flexibility (maybe some of those mesh implementations offer it too). In OpenGL this would result in just 384 buffer objects (sort of mesh container) and ~28 index buffers (sort of mesh layouts) and those can be combined at runtime to all the necessary 'meshes'.

As I said, it is rather an advanced topic, you'll better searching for a guide to follow, or if you lost your need for pain, take a library already implementing it.