Planet Renderer – Week1: LOD Terrain Research

I have put some time into researching the topic of generating terrain at the size of planets with level of detail dependant on the distance of the camera.

There are a lot of different approaches to solving this problem, and it is already clear that I won’t have time to test every one of them myself, but I have identified some reoccuring themes during my time scavenging the internet, and I willl put together a summary of that.

There are a few things that an ideal terrain algorithm would support, but it is probably not possible to meet all of the requirements with one solution, and the choice will need to be prioritized based on that:

• Avoiding cracks between LOD thresholds
• Avoiding jittering and z-fighting at planetary size terrain
• Finding a good balance between making the cpu and the gpu do work – depending on the type of application the renderer is used in the cpu may be needed for other tasks, or the gpu would need to render some heavy effects on top of the renderer.
• having a regular distribution of triangles
• culling triangles outside of the camera frustrum
• culling triangles occluded by already rendered geometry
• only recalculating data that needs to change when the camera moves
• minimizing the amount of memory usage
• being friendly to texturing and shading

Generally the procedure seems to go as follows:

• Create a basic shape
• Place parts of that shape in a tree hierachy
• subdivide and spheriphy the shape using an LOD algorithm (the choice may depend on the base shape)
• Add height to the geometry based on some kind of height information
• optionally refine rather vertical sections of the geometry

There seem to be two categories of basic shapes, which come with different approaches.

The first category is a spherified cube or quadsphere. A subdivision is grid based could look like this:

Benefits of basing it on a cube are the accesibility of using common terrain algorithms on the 6 faces and then simply spherifying every face. Also the quad base is likely to be efficient for memory usage. Typically a quadsphere uses a quadtree (for culling too) and an algorithm such as:

 

• Continuous Distance-Dependant LOD
• Geometry Clipmaps (GPU)
• Chunked LOD
• Geometrical MipMapping

Another advantage is the accesibility to texturing, while the main downside is the irregularness of triangle scale at corners vs in the middle of the face, and the extra step of triangulating the faces.

The other categury is using polyhedrons such as octahedrons or icosahedrons. Spheriphying those would look something like this:

 

 

 

 

 

 

They have different tree structures because of the shape of their triangles: Octahedrons have right angled triangles, which is ideal for a binary tree, as subdividing the triangle would use the process of splitting the triangle in two halves, resulting in two new right angled triangles.

Icosahedrons on the other hand consist of equilateral triangles and therefore best subdivide into 4 new equilateral triangles, and therfore would use a quaternary triangle tree. In both cases memory alignment should be achievable since there are no odd numbers used in either tree structure.

In both cases though the ROAM 2.0 algorithm seem to be most adequate for terrain LOD, since it is designed to handle planetary terrain. The downside of it is that it has a fairly high complexity and CPU workload (compared to most algorithms presented for the quadsphere), but that may in turn free up the gpu workload for other neat effects such as atmoshperic scattering etc.

In any case polyhedrons clearly have less problems with evenly distributing triangle scale, especially icosahedrons. On the other hand it might be more difficult to map textures, and it may also be more difficult to precalculate and store data such as vertices.

I am not sure yet which method to choose, so I will put some more time into researching all the LOD algorithms used. Once I have made the choice, the next step would be to implement a simple framework in opengl and c++ that allows testing these terrain algorithms. We will see how far I get towards the next blog update 🙂