Astral Realms

I have made significant changes to the algorithms which I have been using to initialise and populate the quad tree. I now have the terrain successfully rendering using these algorithms.

Unlike the recursive system that I was using, these algorithms use “breadth first” or “level order” search, which means the first tier will be processes first, then the second, and so on. This is exactly what I want.

I am not certain how this will affect the efficiency of the system, but so far, I am only using the algorithms at load time, so it shouldn’t make much difference. I believe my current recursive algorithm should work for the run-time subdivision of the nodes.

I am currently rendering all nodes, for testing purposes, but I believe that I should now be able to run my optimised tree parsing algorithm without the difficulties that I was seeing before. I should be very close to proof of concept here, if everything has worked as I believe it has.

I believe I have correctly implemented the 3D to 2D projection code, however, it has not solved the problem.

After more research, I have discovered that there are two additional problems with the spherical terrain system. The first is that there is an issue with one of the nodes in each tier, I believe it is the first node. This node seems to have incorrect values, it seems to have the same values as the root node from the highest tier, meaning it is a single quad that encompasses the entire width and breadth of the terrain.

The below images show this quite well. The points themselves are being generated correctly, so the issue must be in how the points are being loaded into the quad tree, or more likely, in what order they are loaded.

The second issue is related. If the code was working properly, rendering the children from each node should produce a square, or a quad, shaped pattern. Ie, if I subdivide only one of the four nodes in the second tier, I should see it’s four children forming a square.

As the second set of images show, this is not what happens. I get four nodes rendering, which is correct, but they render as a line of three quads, and then another quad on another line. When I render all of the nodes, I get the correct spherical terrain output, but clearly, the nodes are being loaded in the wrong order.

This is almost definitely the cause of the render issues I was seeing. If the nodes are being loaded in the wrong order, then subdividing them based on distance will produce incorrect output. I hope that this will be an easy fix, and I will then be able to finally achieve proof of concept of this system.

I have been researching the current issues that I have been having with the Spherical Terrain in some detail.

I believe that, basically, what is happening is that the distances between the player and each node are wrong.

Due to the way that the different levels of detail of the quad tree are created, some of the nodes from different tiers overlap. However, for my current algorithm, I am splitting each node within range of the player into its child nodes, and then further subdividing each of those child nodes if their (the child nodes) distance is also within the players view distance.

Theoretically, this should work, however, since some nodes overlap other nodes of different detail levels, the distance values are not correct, sometimes, for example, a node’s distance will exceed the players view distance, and will not be subdivided, but it’s childnodes will actually be within the players view distance, and so, should be subdivided. This, I believe, is the reason for the missing nodes in the spherical terrain rendering (visible in the below images).

To fix this, I believe I can use 3D to 2D projection, or 3D Projection. This basically takes a 3 dimensional point and projects it onto a 2 dimensional plane, similar to the “window to viewport transformation” that is done in the rendering pipeline.

If I make sure to project each point (parent nodes, child nodes, etc) into the same 2D plane, then I should essentially be able to convert a 3D problem into a 2D problem, and then get the 2D distance from the player to the point or node in question. It then shouldn’t matter if there is an offset between the points in 3D space, since they will all be “collapsed” essentially into the same 2D plane, and only their positions in the other two dimensions will matter.

I have found what seems to be a fairly simple implementation here: 3D Perspective Projection, but I have to do a lot more research to properly understand what is going on here.

If this works, I should, finally, achieve proof of concept for the Spherical Terrain, and I can then add the next steps to it (Massive terrain, texturing, etc) before I move on with the project.

I have not been able to fix the current issue with the Spherical Terrain Project. I feel that I am very close, but I cannot seem to get the terrain to subdivide correctly.

The below video illustrates what I mean. As the camera moves further away from the terrain, the nodes at the back should stop rendering. This happens to most of the nodes. However, some of the nodes are rejected from the render list incorrectly, such as a node in front disappearing from view before a node behind it.

This is the problem that I am having issues fixing. I  will continue working on it for the time being, but I may not be able to crack this.

I believe I have figured out why the spherical terrain parsing system doesn’t work properly.

I have closely examined the nodes stored in the quad tree during the call to build the renderlist.

What is happening is that higher level nodes are being rejected because their distance is greater than the view distance, this is correct. However, it turns out that some of the child nodes of those higher level nodes have distances less than the view distance, which means that they should be subdividing or rendering, but they are not, because they have been excluded from the search.

This leads to not all of the nodes rendering correctly, which I believe leads to the striping effect that I am seeing.

If this is correct, then it should be fixable. I should be able to, for the moment at least, just find the closest point in the node to the players position, and if they is within the players view distance, I subdivide the entire node. This is a little messy and inefficient, since it involves additional distance checks for every point in the node, but it should work for now.

I have made some changes to the subdivision code which have addressed the optimisation issues.

I can now subdivide the terrain into without processing every node, but, in addition to some other logical issues, there is also a more serious problem.

It seems that when I parse the tree correctly (Subdividing only required nodes) the terrain does not smoothly fade in and out of view. It seems to render in strips, such as in the images below.

I am not certain how to fix this, or even if it can be fixed. I am concerned that this could be a serious logical flaw.

I am reasonably confident that this can be fixed however.

Upon further testing, it seems that my solution to the parsing and optimisation problem was not actually correct.

Even though it did work, when I analysed the number of calculations performed by the function I saw that there was one calculation for each node in the quad tree.

This means that it did not actually produce any noticeable benefit or performance boost. I do feel that I am very close to figuring this out, however, and I am currently in the process of refactoring the code to solve this.

Since the quad tree parsing algorithm uses recursion, this is not nearly as easy as it could be. I am looking into other parsing options (such as using a stack) as well as modifying the logic in my current code.

I believe I have finally achieved proof of concept with the spherical terrain using CLOD! After 82 posts, including 49 specific to CLOD, I think I am finally there (or almost, at least).

At the below video shows, I have successfully implemented a system whereby the terrain will dynamically change detail levels as the camera gets closer and closer to the world, and switch back again as it moves away.

The change is actually far more seamless than I thought! I was concerned that there would be problems at the edges, where the different levels of detail meet (for example, when the terrain close to the camera is rendering at a higher detail level than the terrain far from the camera), however this does not appear to be a major issue.

There is a visible border between the detail levels, which is to be expected, since I haven’t added any edge stitching yet, but in general the transition is very smooth.

Most importantly, the frame rate seems to be very consistent. I have not done full benchmarks at high resolution yet, but from the low resolution tests that I have done so far, the framerate does not seem to drop very much as the new tiers are paged in. This is all very encouraging.

There is still a lot of work to be done however. Firstly, at the moment, the transition is controlled by an If/Else statement with fixed distance variables, i.e, if the player is less than 5000 units away, display the lowest tier, once they are within 4000 units, transition to the next tier, etc etc. Obviously, this will not work for the final version of the terrain since I will not know exactly how many tiers they will be (the number of tiers will depend on the max resolution of that particular terrain) and in addition, I don’t want to hard code the distance values, these should be dynamic.

I also need to find a way to scale the terrain to realistic planet sizes. This will require finding a way to dynamically generate and add points to the quad tree, since generating enough points to render and entire planet cannot be done all at once. I will probably use my current code until the player gets close to the planet, and then begin generating points dynamically and adding just the points close to the player to the quad tree. This should allow far greater detail without having to load all points into the quad tree at once in the beginning of the simulation.

I also have to texture the terrain, and make sure that the terrain rendering and collision work at realistic sizes (this will involve dealing with 32-bit precision issues). I will also have to make sure the terrain works in multiplayer.