Quad isn't the best?

While reading some articles over the internet I am deeply starting to thing, that the quad-based LoD algorithm wasn't the best idea. I think so mainly because using such technique on a rather flat surfaces I still will have a lot of unneeded detail.

To demonstrate what I mean, I have found some pictures on the internet.

The picture to the left illustrates something like a hill near the flat ground. The hill itself is more "extruded" from the surface, and it needs more vertexes to represent all it's slopes and caves. It's more logical to add extra detail to the hills, and do not extra detail where the area is completely flat. This is the algorithm I need to implement if I want more complex terrain look more natural. This algorithm is called Optimally Adapted Meshes (OAM).

Unlike previous picture, this one exactly represents the technique I use at the moment. It can be seen with naked eyes that there are way more vertexes used on the areas, where you actually do not need them.

The OAM algorithm, or it's implementation to visualize terrains in realtime (Real-time Optimally Adapted Meshes, or ROAM) uses a height map to determine for each vertex it's error value - the heights around it so see if the area around it is flat or it needs more detail. Based on error value it determines where the extra detail should be added and where it's ok to leave the same amount of vertexes at the moment.

I also need to think in parallel the scaling problem, and implement it inside.

Links

Roam info & papers: 1, 2, 3, 4

 

When to split & when to combine

Today I have almost finished my LoD algorithm. For now I just use simple "divide to 4" technique, and later I will probably use some other, more efficient one, like true ROAM, but for now it's ok.

In the heart of it lies one big question - when to split node to add more detail, and when to combine 4 nodes to one, so to remove unneeded detail. My first thoughts were to make some kind of table with the dependency of distance to node to necessary LoD level, but it was rejected soon because of planet sizes, which varies a lot. For example, using this approach my big planets will be less detailed, rather than small ones because of node's size - it will be bigger for big planets.. like the side of a big cube is bigger that the side of a small one.

Then I tried to calculate the ratio between the distance to node and node's size, and this gave a better result. 

The idea is simple. First I calculate the factor (F) which equals to distance to node (actually the it's the distance to closest vertex of a node) divided by node's size. Then I analyze this like so:

1. If F is less than some number (Kmin), which means that camera is close to node, then extra detail should be added (the node should be split on 4 smaller nodes). Of course here the check should be added if the detail level is at it's maximum.
2. If F i greater than some number (Kmax), which means, that camera is far enough from the node, then extra detail should be removed. And of course here the check should be added if the detail level is at it's minimum.
3. And finally, if F is between Kmin and Kmax - do nothing.

Something like this. In this picture I have chosen Kmin to be 2, and Kmax to be 3, but it's obvious, that this is the place to experiment.

This logic needs to be integrated in the procedure that scans all the quadtree, and decides if the leaf should just be rendered, or divided/combined.