Behind the Scenes – Planet LOD

Hello! I've been working on a level of detail (LOD) system for the procedural planets series. It's still a ways away from completion, but I thought I'd update you on my progress.

The first thing I wanted to get working was a 'spherical quadtree' (SQT) – essentially just 6 quadtrees making up a cube, which can then be mapped to a sphere.

I began by creating an SQT and Quad class. Quad implements a fairly standard quadtree, while SQT is responsible for creating 6 of these quadtrees, and storing which direction they face in 3d space (to form a cube). To verify everything was working correctly (and also with idea of using as a visual aid in the eventual tutorial series) I created a little scene editor where I could click on the faces of a cube and it would update and draw the SQT.

The next thing I wanted was to be able to calculate the 4 neighbouring quads of any given quad. This is because I wanted to enforce adjacent quads to never be more than one division bigger or smaller. This will make it much easier to fix the cracks that will occur between adjacent meshes of a different LOD (something I learned from this KSP Unite talk).

As a starting point, I found this article which described a nice algorithm for finding neighbours on a single quadtree. I just needed to extend the search across adjacent faces for edge/corner quads.

Once implemented, I could right-click on any quad and it would highlight its four neighbours. (Red = North, Orange = East, Yellow = South, Green = North).

However, as you can see from the gif above, neighbours are sometimes incorrect across adjacent faces. This is because (for example) the North edge of the Right face is adjacent to the East edge of the Top face (should be South). This inconsistency between the coordinate systems of different faces is what was messing the algorithm up.

My current solution is to create a 2d array in the SQT that stores the necessary information to convert between the coordinate systems of any two adjacent faces:

Neighbours now work correctly across all adjacent faces. This allows me to keep all adjacent quads within one division level of each other.

The next task will be to spawn meshes based on this SQT, and fix the cracks that occur between them. I'll keep you updated :>