Astral Realms

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.

I now have working player collision! This took a lot longer than I expected, and there is still quite a bit of work needed to clean this up, but it is working well.

The problem was that a variable was not being updated on the server, only on the client, and so the server didn’t have access to the polylist for the collision calculations. This is now fixed.

I can now begin work on large terrains, and optimisation of the collision system and rendering. I need to implement a system which only renders and collides with the polygons close to the player, and then updates these polys as the player walks around the surface of the planet.

I also need to deal with the famous 10,000 unit problem in Torque. Torque uses 32-bit floats to store position transforms, and when the player gets to about 10,000 units from the origin, these 32-bit values lose precision, and this causes a noticeable “jitter” effect. To deal with this, I would either have to replace all of the 32-bit floats with 64-bit floats, which would require major reworking of the engine, or, implement a system where the player actually remains at the origin, and the world moves around them.

This system is the one that I used in my Icarus Rocket Simulator, and it works quite well. This project is multiplayer however, which does make things more complex, since I will need absolute coordinates on the server (in the database) and I will need to translate those to local coordinates for each player (centered about the origin).

I have made quite a lot of progress with the collision issues that I have been having, although player collision is still not working. I now believe that the issue lies in a particular variable not being updated on the server.

What I think is happening is that the collision is being detected on the client, and the list of collision polygons is being generated on the client. However, that list of polygons is not being sent properly over the server, and so the server doesn’t have anything to collide with, resulting in no collision.

The collision with objects of the item class probably works because it’s collision system is different, and simpler.

I am currently implementing a solution which I believe will fix this issue.