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

 

Glitches

I have realized, that something needs to be changed in my code. I did some tests trying to see how program responses to big numbers. I have created a planet with the size exact to Earth's, and tried to fly here and there to see the performance, and then I ran to some unpleasant glitches.

This is taken from the stationary orbit at 1100 km from the surface of the virtual Earth. Strange thing that this artifacts not always appears (maybe I should call them UFO? :) ). It seems that this happens when some other processes run in background and use CPU resources a lot. I haven't tested it on other computers, maybe it's hardware specific.

I also noticed, that memory allocation and garbage collection isn't quite good, because the project constantly drains memory while runs. The problem is in LoD code, definitely.

Scales again

I've been thinking a lot about scales recently, once again, and those thoughts driving me nuts slowly.

Space is a very very very large thing. Our planet is about 6'300 km in radius, that is 12'600 km in diameter, and that is 12'600'000 meters, 8 digits. Assuming one world unit in the close distance is 1 meter of the planet, I have only 100 more sized object to be able to handle in close distance. So if I will be crazy enough to fly close to the sun (so that is should be rendered in real scale), I would have an float overflow because the radius of the sun is abou 110 times bigger, that the Earth's radius. We can ask why do we need such big numbers to store if we are 10 meters from the surface? Well, even if the part of a surface if 10 meters from you, you still have to take in mind that the center point of an asteroidal body is way far away from you and it is needed to make a proper curvature of a planet. To solve this somehow I have only 3 options in my mind:

1. Store vertex coordinates in doubles and apply exponential space transformations before converting them to floats.
2. Store vertex coordinates in doubles and cull vertexes that are very far away.
3. Make up something else.

And in my opinion, the only reasonable option is the last one..

There are couple of planetary engine demos around the web, I wonder how they solve this problem.

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. 

Deciding what to render

For the last two days I was thinking about my quadtree of nodes. Quadtree-based structure is used to store terrain nodes at different level of detail, based on the camera distance to them - more closely is the camera, then more detailed should be terrain. I will later write some text about my quadtree implementation, but for now I want to be detailed in explaining the scheme, which is essential to selecting the quadtree nodes, that needs to be rendered.

The quadtree consists of 2 core elements - node(s) and leaf(s). As I mentoned before, if a node have no child node(s), then this node is a leaf, and it should be rendered (if visible, but for now I do not make any checks on visibility). Each node may be only in two states: a leaf, or a node with 4 children (in that case such node is called a branch). This is the basics of quadtrees.

So, the core problem is to decide what quadtree elements needs to be rendered. This means that  there should be some kind of procedure, that runs via quadtree's nodes, and decides what to render and what to not.

Lets assume we have a quadtree like this. This quadtree have 3 "level of detail" levels (LoD levels, to be more shortly), and a lot of branches and leaves. Green circles are leaves, and brown ones are branches. Despite the visibility factor it's logical, that every leaf should be rendered, so that we could see the final terrain.

No matter how deep is the quadtree, the procedure, that finds all leaves in the quadtree so to render them later should scan all the quadtree's levels, and choose only those nodes, that are leaves. It should start from the very top of the quadtree, see if this node has any children. If it has, then "descent" down by one level until it finds the leaf. After the leaf is found it should "ascend" up to check other branches by going down. It should repeat this steps until all elements of quadtree are examined. It is clear, that if we have a rather big quadtree, it will take a lot of time to scan all its elements. Assuming that in this procedure we do not check for leaf's visibility, then yes, it will take some time to scan all the quadtree. Later on, when visibility check will be performed, the amount of nodes, that needs to be checked will decrease a lot. It can be easily understood if we assume that on the picture above, the third node from the left if no visible - then there's no need to scan its children.

Without visibility checks, the block scheme of such procedure can be the following.

Each node have the levelCheck variable, that is by default equals to 0 and is used to store in quadtree the child node number that has been scanned already. If it is equal to 4, that means that on this level we have scanned all children, so we should go up a level. And the lines "this.levelCheck=0" is used to reset the counter after all children of current node are scanned, so that next time when we will need to scan the quadtree, all nodes have this number reset back to zero.

Texture coordinates

Last two days I was trying to figure out what are texture coordinates. It's name sounds pretty obvious, but in real code it was confusing for me what exactly are texture coordinates and texture buffer, and how they should be properly defined.

I have found a nice picture, that have everything to understand once and for all what they are.

According to OpenGL documentation each texture must have like 2Nx2N for better memory allocation and computation. Each object's vertex should be “bound” to some point on the texture so that when the texture is applied to the object, the graphics card will know how to “wrap” an object with a texture. To do it properly, the corresponding position of each vertex on a 2d texture should be defined. This is called texture coordinates, and they should be defined as [0;1] numbers.

For example, if we have a 3x3 square mesh, that consists from 9 vertices with any dimensions in 3d (lets say 10 by 10), the scheme of defining texture coordinates (and texture buffer lately) should be like this (texture coordinates are always 2d and in range of [0;1] for each vertex):

Black text represent 3d vertex coordinates, and red text - 2d texture coordinates.

Wierd things

Last night at about 1 a.m. I was trying to put some tests to reveal the difference in calculating floats and doubles. The idea was simple - fix a time when the test stars, put in a loop for 1 million times some equations like multiplying and finding a square root of the number, and then fix the end time so do subtract it from the start time.

In first test floats were used. The number like 123456.78 was multiplied, divided, square rooted and etc. for fixed amount of iterations. And then, using doubles (big numbers from previous post) the same type of test was performed.

I was shocked that rather small float numbers had a higher results than doubles!

This is truly the result that let me think more closely to use doubles instead of floats without any doubts regarding performance.