Spiritus Astrum

I believe I have managed to get multiple detail levels working.

I have not yet implemented the code to add each detail level to each tier of the quad tree successfully, but I have produced a pointslist which I believe contains all detail levels up to and including the max detail level specified by the used.

So, if the user specifies a detail level of 1024, the pointslist will contain a spherical terrain with a resolution of 1 node, 4 nodes, 16 nodes, 64 nodes, 256 nodes, and 1024 nodes. Each node has four points, which will have two more points added to allow them to be rendered, as I discussed previously.

The images below seem to show the multiple levels of detail all rendering at once, which is correct at this point. However, I will not know if this system is working correctly or not until I load the nodes into the quad trees properly. I will then need to modify the rendering function to render only specific levels of detail, to test this code.

If it works, I can move on to the final step in the prototype, which is the distance based optimisation algorithm.

I have finally implemented quad-based rendering!

The images below show the terrain looks identical to what it used to look like before all of this work, however, there have been massive changes made to how it all works.

There is still some relatively minor distortion, which seams to be occur only along the seams of the quad spheres faces. This, I believe, is due to vertices and/or faces on both sides of the quad sphere boundary being duplicated. Since both faces occupy the same space, distortion occurs, due to Z-fighting.

There may also be some issues with collision detection in certain parts of the terrain, but I can address these issues later.

In addition to extensive bug fixes, optimisations, and improvements to the algorithm, each node in the quad tree now contains six points, which are used to draw two triangles, or one quad, per node. This is a vital step, because in order to subdivide the terrain based on the distance of the player, each of the quad trees nodes needs to be able to, essentially, render the entire face of the terrain.

This means that from an extreme distance, the terrain will render using only a handful of quads, and as the player gets closer, it will subdivide only those quads close enough to the player, producing a highly optimised, but also a high quality terrain mesh.

The next step is to implement the “Levels of Detail” that I require for this to work. At the moment, I am creating a list of terrain vertices at the most complex level of detail, and rendering all of them. I now have to generate a list of terrain vertices for each level of detail in the quad tree. For example, I will have a list of points generated for just one node, and for 4 nodes, then 16, then 64, then 256, then 1024, etc.

Once all of these points are generated and stored in their respective quad trees (each face has it’s own quad tree now, and I have to generate a list of points for each face separately), I can write a distance-based optimisation function which only subdivides a higher level node if it is close enough to the player. If this works, I should essentially have a spherical terrain implementation. There will still be a lot of work to do with optimisations, texturing, and scaling (I want to be able to scale the terrain to realistic planet sizes, that will be another challenge!) but the prototype should be done.

I have fixed the minor bug that was preventing the last face from drawing, and I have copied the changes to the second of the six faces that form the quad tree.

So far, the new system seems to be working very well, but I won’t know if it has worked for sure until I can get all six of the faces rendered, and the perlin noise applied.

I am confident that this new approach will work, however. There are no visible issues with the two sides of the quad sphere that I have added so far.

I have finally made a breakthrough with regards to the quad rendering.

As can be seen from the images below, I can now render an entire face of the quad sphere in quads, as opposed to tris.

The solution I used was to add six points to each node, instead of four, in order to draw two triangles, forming the quad. Using an index buffer would have been more efficient, and I may implement this technique in the future, but the system seems to work quite well as it is for now.

I used to have two loops in the code to create the geometry: One to create the list of points for each face, and another loop that would iterate through that list of points and rearrange them so that they had the correct “winding order” to be drawn.

This was obviously very inefficient, however, since this was being done only once (on loading the game) it wasn’t a major problem. I have since fixed this however, making the code much more efficient.

There is one minor bug in the code, and that is that the very last face of the quad sphere is not showing up. The loop seems to terminate one step too soon. The cause of this is rooted somewhere in the quad tree initialisation functions, and may take a little time to track down, but it should not be too difficult.

Once I have that bug fixed, I can copy my code changes to the other 5 faces of the quad sphere, and I should then be ready to move on to the next major step of the project: Generating multiple detail levels.

I have succeeded in drawing my first quad!

This may seem like a trivial matter, but it took considerable effort to get this far. In addition to the extensive modification and bug fixes that I wrote about before, I also had to modify the entire algorithm that creates the data points, to ensure they are compatible with the new system.

I eventually arrived at a situation where I had four points for each node that I wanted to render, which is what I wanted. I then needed to render these four points as a quad, which I assumed would be a simple task.

In actual fact, it turned out to be quite complex. Everything in computer graphics in rendered with triangles, which require three points. So, to render a quad using two triangles, I would need six points, not four, with two points being reused.

I looked into a few different ways of solving this problem, including using GFXTriangleLists as a rendering method, and using an index/primitive buffer.

I am confident that the index buffer idea would have worked, but it would have required even more changes to the codebase to implement that. I decided for now to just create four points, as normal, then, when I am loading the points into the quad tree node, I will duplicate two of them, so I will have six points stored per node instead of 4. During rendering, I should then be able to draw those six points as two triangles.

I don’t know if this is going to work yet, but I am reasonably confident.

There is still a lot of work to be done on this, but I feel I am making significant progress.

I have made a lot more progress in investigating the problems I have been having with the spherical terrain.

Firstly, I now believe that these problems are actually preexisting. Below are some screenshots that I took with the old codebase, which I believed was working correctly (using triangle based rendering).
However, there are some missing polygons, and some visible graphical distortion occuring at the edges of the quad spheres faces.  I hadn’t paid much attention to these before, I assumed they were simply minor bugs that could be corrected later, but I now believe that these are actually more serious issues with the underlying algorithms.

I have, after much effort, managed to get the points to be generated in groups of four. What was happening is that the loop I was using to generate the points was incrementing and decrementing in the conventional way, like this:

for(int i = 0;i<maxvalue;i++)

{

for(int j= 0;j<maxvalue;j++)

{

}

}

This produced the correct number of points, but, each group of 4 points was arranged in a line, not a quad, (since it was being incremented by 1 at a time).

I have now modified this algorithm to produce points in contiguous groups of 4. This is significant progress, however, I have still not completed the quad rendering. I have had to completely re-evaluate and modify the existing spherical terrain system, including the rendering. I am confident that I will solve this issue, and I feel that I could be relatively close, but I am not quite there yet.

I have put a lot more work into this project that I have had time to post here, these are just snippets of what I have actually done. I feel that, even though this has taken a lot of time, I have a much greater understanding of how this whole system fits together now. So much so that I have been able to make complex optimisations to the code as I am working through it, removing older code that I had added when I clearly didn’t fully understand the workings of the system. I have even removed an entire loop from the codebase, which was used to rearrange the order of the vertices so that they rendered correctly. I have now incorporated this into the first loop, which generates the vertices.

I have also completely refactored most of the other code in the spherical terrain generation functions, improving and optimising it. I had quite a bit of redundant code in there that has now been removed, and other code that worked in some cases, but failed for others. This would no doubt have resulted in irritating bugs at some point, if I hadn’t dealt with it now.

Since the terrain system needs to be fast and reliable, this time has certainly been well spent.

Unfortunately, I have not solved the quad rendering issue, as I had hoped. I am not certain how exactly to solve this problem.

The code changes that I implemented worked for low resolutions of the spherical terrain, but produced the same pattern of gaps when I increased the resolution.

I had assumed that the problem was with the creation of the points for the spherical terrain. Upon investigating this, I discovered that these points seem to be correct.

I plotted the points in gnuplot (one or two faces at at time) and, as the below graphics show, there they seem to be correctly lining up, with no seaming.

I have found several errors in my implementation of the complex algorithms underpinning the spherical terrain, and I have corrected these. This hasn’t fixed the issues, but it has made my code more efficient, and should make debugging much easier.

I believe the issues must have something to do with the fact that I am trying to render faces in quads (4 points) rather than tris (3 points), since the terrain system seems to work ok with the previous system, which used tris.

I have finally solved the problem that I was working on!

There was a bug in the code that offsets the vertices and projects them onto a sphere. I don’t know why this wasn’t showing up before, it was only noticeable when I tried to render the terrain using quads.

I now seem to have a sphere generated from a series of points, using quads. I can now quickly add the perlin noise back to the system, and move on to the next step, which is to populate the other tiers with lower resolution versions of the terrain.

I can then implement the actual optimisation and CLOD rendering system.

I am slowly getting to the point where the terrain system is ready. Once that is done, I hope to move a lot faster in implementing the rest of the virtual world.