P-152: Virtual World Concept Update 50: Chunked Levels of Detail Using Quad Trees Part 18

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.