Spiritus Astrum

I have devised an algorithm to solve the integration problems with between the spherical terrain and the quad tree.

Basically, it works like this.

The size of the quad tree is the primary determining factor, this would be chosen by the user, and all other values regarding resolution and size are based on this.

So, if the user specifies a size of 4096 for the terrain, this means that the quadtree will have 4096 spaces.

However, 4096 is not evenly divisible by 6, so I cannot directly plug that into the spherical terrain algorithm. I first need to divide 4096 by six: 4096/6 = 682.666. Then I cut off the decimal point to give just 682 (It is impossible to have .6 of a vertex). This means that each face of the quad sphere has a maximum of 682 vertices. Now, to satisfy the final condition, I need to take the square root of 682, which is: sqrt(682) = 26.115. Again, I cut off the decimal point, which gives 26. This is the critical number, which tells me the length of the axes on each face of the terrain. This allows me to construct a spherical terrain which will fit into the quad tree leaving as little wasted nodes as possible.

Working forward from 26 it is possible to calculate the efficiency of the algorithm:
If the x and y axes of each face of the quad sphere are 26, 26*26 gives the number of vertices in a single face, this is: 676. 676*6 gives the number of vertices in the entire quad sphere, which is: 4056.

The quad sphere has 4096 spaces, 4096-4056 gives 40, so 40 spaces are wasted. This gives an efficiency of 99.99% The efficiency actually increases as the size of the quad tree increases.

I am still having an issue with rendering. With the new algorithm, only part of the terrain is being rendered. I am in the process of solving this problem.

I have made some progress with the quad tree.

The main issue is still in generating the vertices for the spherical terrain in a way which is compatible with entry into the quad tree.

I have made progress with the spherical terrain code and the quad tree code, but they are still not compatible.

Ideally, what I need to do is generate multiple spherical terrains, each at a different detail level, and each containing a power of 4 number of vertices, 256, 1024, 4096, etc. These can then be loaded into the quad tree as they are. I can then parse the quad tree quickly, producing a list of vertices using the different detail levels (higher detail for closer vertices, lower detail for more distant vertices). These vertices would then be loaded into a vertex buffer for rendering.

However, I cannot generate power of 4 spherical terrains, since my spherical terrain are generated from a quadrilateralised spherical cube, or quad cube, which has six sides, meaning the number of vertices needs to be evenly divisible by 6.

My proposed solution is to use the same general technique, but instead use a power of 6 number of vertices that is as close to a power of 4 as possible, and then populate the rest of the quad tree tier with blank values. So, instead of using 4096, I would use 4092 (682*6 = 4092) and fill the 4 spaces with blank values. I would do this for all tiers. The blank spaces shouldn’t make a difference when I parse the quad tree, so it should work.

I am still having issues with this implementation, which are mostly due to changing the resolution of the terrain at each tier, and therefore, changing the number of vertices.

I am still working on the quad tree implementation.

I have spent a considerable amount of time on working on this, but have not been able to successfully integrate the quad tree with the spherical terrain yet.

The spherical terrain algorithm that I have implemented is very complex, and changing the number of vertices used to generate the terrain to a power of 4 is proving to be difficult.

The terrain uses noise generation for randomness, which involves creating a vector with a specific number of vertices. In addition to this, the code for the vertex buffer that I am using to store the vertices also needs to be changed.

I am restricted by the limitations of the quad sphere algorithm to having the world divided into six planes, which is where most of the difficulty is, but I am confident I will be able to solve this issue eventually.

I am still working on the integration of the quad tree optimisations with the spherical terrain code.

I have uncovered a problem with this implemention. The quad tree requires the data to be a power of 4. Each tier is 4 times more complex than the last, so the first tier has 1 element, the second has 4, the third has 16, the fourth has 64, and so on.

However, the existing spherical terrain implementation does not follow this pattern. It is divided into six sections, with each section corresponding to a face of the quad cube. These sections have a non-power of 4 value.

I will need to recode the algorithm to produce a vertex list that is both power of 4, for the quad tree, and is also evenly divisible by 6, to allow it to be broken into six equal sections for the quad cube.

I have recoded the rendering pipeline for my spherical terrain. Instead of rendering the spherical terrain directly to a vertex buffer (which is very slow) it instead renders it to a data structure that I have created. This data structure is then copied to a vertex buffer for rendering onto the screen.

I now need to replace this data structure with the quad tree containing the different levels of detail (or “tiers”) of the spherical terrain. I can then use a fast distance-based algorithm during the rendering pass to extract only the visible pixels from the quad tree and add them to the vertex buffer for rendering.

So far, the process seems to be working out ok, but I am still not certain if the overall concept will work.

My Quad Tree test program is progressing well. I have a fairly good idea now about how to use Quad Trees in a spherical terrain implementation. What I intend to do with my project is:

First, create several different versions of the spherical terrain, at different levels of detail (For example, 256*256, 512*512, 1024*1024, etc). This data will likely be stored temporarily in vectors.

Then, a single quad tree will be created, which will store the terrain information for all LOD’s in it’s hierarchy of nodes.

I can then quickly parse the quadtree, using a distance based calculation (based on the players position) to decide if a particular node should be returned at it’s current resolution, or subdivided into a lower resolution. I will also need some way to group or “chunk” together several nodes surrounding the player.

Early tests indicate that the quad tree design that I have created does, indeed, perform much better than brute force (manually parsing all terrain pixels). One preliminary test resulted in my quadtree program processing just 12 terrain vertices, where a brute force algorithm faced with the same problem had to process 84 verts. This is a 7-fold performance improvement, and it seems that as the terrain becomes more detailed, the performance gains are even higher.

I have returned to this project to implement the next step, which is optimisation of the rendering system. At the moment, all of the terrain vertices for the spherical terrain are being loaded into a single vertex buffer, and then rendered. This obviously leads to massive performance problems for even small terrains

In order to create highly detailed terrain which can be rendered in real time, I need to optimise the way the terrain is rendered. I have chosen to use a Chunked Level of Detail,or CLOD algorithm. This basically creates several versions of the terrain, at different levels of detail, from very low to very high resolution. The idea is that the terrain far away from the player will be rendered  in a much lower resolution, while the terrain close to the player will be rendered in a much higher resolution. Since the low-resolution terrain is far from the player, it won’t be noticed.
The most authoritative author on the subject that I have found is HERE.

I have done extensive research on the subject, and I have decided to create a self-contained test program first, to experiment with QuadTrees and how they would be used to create a CLOD solution.

I have made some progress with researching CLOD. It seems quite tricky to implement, but essentially, the data is stored in a quadtree. This quad tree is created at design time, and does not need to be recalculated every tick.

The algorithm then selects patches from the quad tree based on an error calculation. Patches further from the player are at a lower level of detail, while patches close to the player are in full detail.

I understand the basic concept, but before I can implement this, I have to figure a few more things out. For example, are the different LOD’s of the mesh stored in different quadtrees? Or are they somehow combined into the same quadtree? Does each patch get it’s own vertex buffer, or are they combined into one?

I will need to continue my research on this.

I have been researching the next stage of the spherical terrain. I need to implement some kind of optimised paging system. Rendering an entire planet-sized terrain at once is, obviously, impossible, so I need to find a way to page the terrain to ensure it can be represented in the game.

The two most common techniques that I have seen that are capable of this are geomipmapping and chunked levels of detail. I am researching both options at the moment, and I am currently leaning towards the CLOD implementation.

Once this is done, I should be able to render massive worlds with little difficulty.