Spiritus Astrum

I have come up with a solution for the node subdivision problem that I think will work quite well.

I know the node center points, the position of the player, and the view distance of the player. I also know the resolution of each terrain block, which I am calling the “blocksize” (If the max resolution of the terrain is 4096, and the current tier is 2, then each block is 2048×2048, therefore the blocksize is 2048).

I had initially planned take the node center point, and then add and subtract the block size from it, to get the extents of the block. I had then planned to use these extents to determine if the block intersected with the players view distance. This method could potentially have been more accurate than the method I ended up using.

However, I think I have come up with a much simpler idea. I have also determined that the blocksize value that I thought I had may not work, since the node positions are in world space, and the blocksize is not in that scale, so I will need to calculate an equivalent to the block size that works with the numbers that I have.

What I have decided to do is as follows.

Firstly, to get the new blocksize, I realised that the distance between each node center has to be the same. since each node is square, and each node is an identical size. If I assume that the distance between two node centers is “d”, then d divided by 2 is the distance from the node center to the edge of that node. This distance, d/2, is equivalent to the blockSize value that I was using in previous calculations.

Now, if I can assume that the nodes are circular, (or spherical) then I can create a vector from the node center to the players position, and scale that vector by d/2.  The point at the end of that vector will be the point closest to the player’s position, so, if the distance between that point and the players current position is less than the players view distance, that node is in view, and should be subdivided, otherwise, it is out of view, and shouldn’t be subdivided.

Assuming that the node is circular should work ok in most cases, the only time a problem could occur is if the players view distance intersects with the very edge of the corner of a node. This could be within the players view distance, but not within the circle described by my algorithm. I think this solution is definitely worth trying, if it doesn’t work, I can try something more complex.

I have done a lot more research into the problem I was having with the terrain system, and I believe that my initial thoughts were more or less correct.

The graphic below shows the issue:

Currently, the closest node, the one on the bottom right, will be subdivided. The other three won’t. However, the players view distance extends into the other three nodes, which means that the player will see visible gaps, since those nodes will not be subdivided or rendered. I am somewhat confident that this is the cause of the issue.

To fix it, I need to subdivide all higher level nodes that are within range of the players view distance. However,  I need to make this work on a per tier basis. In the above example, I want to subdivide all four nodes (since the players view distance overlaps with some part of each one of them). However, in the next tier, only the bottom right node will have all of its children subdivided, the other nodes will have only some children subdivided.

In this way, as the parsing algorithm moves through the tiers, it will behave in an efficient manner, only subdividing nodes when neccessary.

I am not sure how to solve this exactly, I will need to think on it some more. What complicates this issue is that I need to know if *any* part of the players view distance intersects with *any* part of the current node being parsed. I cannot use simple distance based checks. This is essentially a collision detection problem, I could learn a lot from current collision detection algorithms.

I have not spent a huge amount of time on this project this week, due to the work I have been doing on P136. However I have done some research into the final terrain paging and chunked level of detail issues that I have been having, and on the terrain resolution and performance.

There does seem to be a flaw in the algorithm that I am using for the terrain system. I believed originally that increasing the resolution of the terrain would fix the paging issues, by increasing the density of the terrain (and therefore reducing the size of the nodes).

This is because the issue is, I believe, caused by the node boundaries not being included in the subdivisions. I am only including the closest node in the search at the highest levels, so if the player is standing near a node boundary, the nodes across that boundary will not be subdivided.

To fix this, I will have to abandon the idea of searching though only the closest node at the highest tiers, and adopt a distance based system for all nodes, similiar to what I do for the lowest nodes.

If a node is within a certain distance of the player, it will be subdivided, regardless of how many nodes from that tier are already being subdivided. I think this concept should work, but it could take some time to implement and test it.

In addition to the issues with terrain paging, I have noticed problem with performance  at higher terrain resolution levels. As well as taking a long time to generate the terrain, the framerate is quite low, even at moderate detail levels. It is possible that this issue will be fixed when I fix the terrain paging issues, however.

This is a preliminary test of the optimised Quad Tree parsing system. The theory seems to be working ok, the terrain is being rendered more of less correctly.

There are some issues with gaps in the terrain, however. I believe these are to do with the the view distance of the terrain. Sometimes a player may be close to a node boundary, which means that both nodes (on either side of the boundary) should be selected. However, it is possible that the view distance only triggers one node to be selected, which results in a gap.

I believe that when I increase the resolution of the terrain (and therefore decrease the distance between the centers of the nodes, since there will be more of them) this problem shouldn’t be apparent any more.

There is some more debugging to do here, but I think I am almost there. The next step is to test the actual efficiency by increasing the resolution of the terrain. Hopefully, I will be able to increase the resolution far higher than I could before I implemented the Quad Tree system.

After that, I can begin work on the Terrain Texturing, and on scaling the terrain up to realistic planetary sizes.

I have implemented and tested the Quad Tree Parsing System. I am not yet rendering the terrain from it yet, I have just tested the actual functionality of the code.

The system works by comparing the players position in 3D Space to the position of the center of each node in the current tier, then, the closest of the four nodes in that tier is subdivided. This means that in each tier, only one node is actually subdivided, and only 4 simple distance checks are performed. Currently, my terrain has a resolution of 4096, which means is has 7 tiers:

1,4,16,32,256,1024, and 4096.

This means that the number of tiers to be subdivided is 6 (the final tier cannot be subdivided) and the number of calculations is simply 4*7 = 28. The last tier needs distance checks to find the closest node to the player. In future, I will of course need to return multiple nodes to form an optimised renderlist to actually display the terrain. This is the next goal.

The main problem I had with this was getting the centerpoints specified correctly. I don’t have LOD’s, so only the final tier stores actual polygons, so I had to get the center of those polys and assign that value to be the centerpoint of the final tier. Then I averaged out the centerpoint of all four nodes to find the centerpoint of the parent node, and then did the same all the way back through the tree.

After much debugging, this is now working. I am not 100% satisfied with this system, but I think it should work. I will conduct proper performance analysis on it later, once I increase the resolution of the terrain.

The output of the test program is:

START
Subdividing Node ID: 0 At Tier: 0
Player Position: 0.000000 0.000000 109.447815
Node Center Point: -0.010743 0.145452 0.012632
Subdividing Node ID: 0 At Tier: 1
Player Position: 0.000000 0.000000 109.447815
Node Center Point: -0.106324 0.113596 0.668944
Subdividing Node ID: 1 At Tier: 2
Player Position: 0.000000 0.000000 109.447815
Node Center Point: -0.028212 -0.061257 0.918001
Subdividing Node ID: 2 At Tier: 3
Player Position: 0.000000 0.000000 109.447815
Node Center Point: 0.015407 -0.034157 0.906348
Subdividing Node ID: 2 At Tier: 4
Player Position: 0.000000 0.000000 109.447815
Node Center Point: 0.000000 0.066147 0.993855
Subdividing Node ID: 1 At Tier: 5
Player Position: 0.000000 0.000000 109.447815
Node Center Point: 0.000000 0.000000 1.000000
END

This shows the code parsing the tree, selecting the closest node at each tier, based on the player position. It also displays the centerpoint of the closest node.
This is another printout, showing the code with a different player position:

START
Subdividing Node ID: 0 At Tier: 0
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.010743 0.145452 0.012632
Subdividing Node ID: 0 At Tier: 1
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.106324 0.113596 0.668944
Subdividing Node ID: 0 At Tier: 2
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.456865 -0.086884 0.795397
Subdividing Node ID: 1 At Tier: 3
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.514364 -0.027944 0.759780
Subdividing Node ID: 2 At Tier: 4
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.558443 0.061092 0.811830
Subdividing Node ID: 1 At Tier: 5
Player Position: -54.272717 1.153820 82.365593
Node Center Point: -0.553337 0.000000 0.806620
END

As the player position changes, new nodes are parsed and new coordinates are returned in real time. The next goal, as I said, is to return a render list of polygons, which be be used to draw the terrain on the screen.

I am still working on the optimisation algorithm for the quad tree. I spent some time trying to implement a X and Y based coordinate system, before realising that this would not solve the problem that I am actually having. The X and Y coordinates would be specific to the quad tree, while the players position would be in world space, and three dimensional. There would be no way to determine the players position in the X and Y grid.

I have not implemented LOD’s for this project yet, so I only have 3D vertex position for the final tier, the actual tier of the quad tree that is rendered at highest detail, so I cannot use distance based checks on the higher tiers.

However, I have now implemented a system that I had devised previously, which is where I determine the centerpoint of each node by taking the average of the vertex position of it’s children. I start from the lowest tier, and then work backwards recursively, populating the higher levels of the tree. For example, to determine the centerpoint of a node on tier 2, I simple take the position of it’s 4 children (which will be tier 3) and take the average. Then, I do the same for tier 1, using the nodes from tier 2 which have now been populated.

This concept should work, but I am having some issues with setting the values of the tree. I am getting discrepancies between the debugger and my own quad tree printing function. I may have made a mistake with the tree printing function, or there could be issues with the algorithm that populates the tree with the centerpoint data.

I have made a major breakthrough with this project! I have finally implemented the terrain paging system. As seen in the below video, I can now page terrain polygons in and out of memory as the camera moves around the world.

In the below video, the player is stationary, and the code is using the camera position to perform the paging, but the concept is the same.

The code is, at the moment, not making full use of the quad tree. It is not performing an efficient search, accepting and rejecting branches of the tree, instead, it is performing a search of all of the nodes in the bottom tier of the tree, and rendering the ones close to the player. This obviously defeats the entire purpose of the quad tree, but this was done simply for debugging purposes.

The next step is to implement the quad tree parsing and optimisation program that I have devised, and hope that it works, and provides the significant speed improvements that I am hoping for (by massively reducing the amount of nodes that need to be processed).