Planet Renderer – Week 3.5: Terrain LOD

This is a bit of a delayed update, mainly because my computer broke down and I needed to reinstall all software.

Regardless I modified what I had in week 2 to display terrain with level of detail. You can see the results here for yourself:

Apart from that, I also added textures and text rendering with sprite fonts.

Right now, the LOD method uses the most naive approach, which is rebuilding the entire geometry every frame. I plan on caching the geometry so that only the parts that changed need to be rebuilt, possibly with a combination of techniques from algorithms such as ROAM for its split queue or chunked LODs for its patches in order to increase the framerate. For now the focus was on finding a good splitting heuristic though, which should be easily transferable to those other algorithms.

The subdivision code has stayed rather similar to the last post, so I will not go over the details of how this works. The most interesting part is the splitting heuristic: It is a method that determines if a triangle should either be culled, split or rendered as a leaf.

So the first step is performing some form of culling, which I will detail in a later post, but the idea is finding a good method to prevent generating and rendering geometry for invisible terrain, such as terrain that is on the other side of the planet or not visible in the cameras view frustum. If the culling test is positive, subsequent steps wont be calculated anymore and the heuristic returns a CULL command.
If the triangle passes the culling test, it is checked if it should be split (subdivided) based on its position and the cameras position. If this test is positive, the heuristic returns a SPLIT command, otherwise it will return LEAF.

In the recursive subdivision method, this information is used to either discard the triangle, recursively subdivide it or add the triangle positions to the vertex buffer.

For the distance check, at first I used this rather simple formula:

if(distance*subdivisionLevel > magicNumber)return SPLIT;

Using this approach I was already able to get some results:

This is already a quite promising result, but it has one problem, which is that the detail level does not appear uniform on the screen size. At a large distance the level of detail is to small and the planet seems really low poly, and at a short distance the level of detail is way to high and causes an uncomfortably small framerate.

Ideally, you would want the triangles to be all be roughly the same size on the screen, regardless of the distance. The naive version of implementing this would be to calculate the surface area in screen space, but that would be extremely expensive since it would require transforming all triangles with the WorldViewProjection matrix, which is a rather slow process when done of the CPU.

Luckily, I was able to find a good alternative, which is calculating the triangles maximum size based on the size of its sides, its distance from the camera and the field of view of the camera. The idea is that the angular size according to the angle of a triangle made from the camera position to two points on the triangle needs to be smaller than a predefined value:

The size of a triangle at a certain subdivision level can be precalculated. Since I am using an icosahedron as a base shape, all triangles will be roughly equilateral. The base size (level 0) is the distance of two arbitrary corners of an arbitrary triangle of the icosahedron, and the size of every level is half the size of the previous level. All of those triangle sizes can be placed in a look up table, for which any array will do, where the index is the subdivision level:

triLevelSizeLUT.clear();
triLevelSizeLUT.add(distance(baseIco[3] – baseIco[1]));
for (i = 1; i < maxSubdivLevel; i++)
{

triLevelSizeLUT.add( triLevelSizeLUT[i-1]/2 );

}

This is precalculated along with the maximum percentage the triangle angle can be of the cameras FOV angle every frame:

maxScreenSizePercentage= maxTrianglePixels/ WINDOW.Width;

The angular size of a triangle at a certain subdivision level and distance then can be calculated similar to how the near clipping plane is calculated with the usage of an inverse tangent

angSize = arctan(size[subdivLevel]/distance);

And this information can be used to determine a subdivision:

if(angSize/cameraFOV > maxScreenSizePercentage) SPLIT;

In order to make all of this more performant, the camera is transformed into the object space of the planet.

Another optimisation would be precalculating the splitting distances into another look up table, so that the inverse tangent calculation could be omitted. This look up table would contain the split distance with the subdivision level as parameter, and would need to be recalculated every time the FOV, the base triangle size, the maximum triangle pixels or the screen width change.

As can be seen in the video above, this method gives some quite nice results for the detail level at any distance.

Once I had all of this implemented I added texture support and equilateral texture sampling to the planet shader. Here is what the result looks like with a moon texture:

To make debugging and performance assessments easier I also implemented text rendering for the framework. This implementation is not really relevant to the project, but for anyone interested, I use sprite based font renderering with textures and metrics generated with BMFont. Here are the necessary source files:

• Text Shader: GLSL
• Sprite Font: Header – Source
• Text Renderer: Header – Source

This concludes my update for the third week, although I will make another post about frustum culling tomorrow for the fourth week 🙂