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

I have given some thought to how I am going to parse the quad tree when I have complete the implementation.

Quad trees provide massive performance benefits  compared to iterating through each node in a list. They accomplish this by essentially eliminating entire “branches” of the tree without the need to parse individual nodes.

In order to use this in a spherical terrain implementation, I will have to use the players position to include or exclude branches in the node tree. I will not be able to compare the position of the player to the position of the node, since that will require checking each node, as if I didn’t have a quad tree at all.

I propose to parse the quad tree by implementing a coordinate system for each node, and then translating the players position into that coordinate system. I could then mathematically determine whether a given node should be subdivided further (due to it’s proximity to the player) or discarded (too far away to be rendered). This should work ok.

I have not implemented Levels of Detail in the algorithm yet, I am only dealing with whether to render or not render the vertices, instead of rendering several sets of vertices of differing resolutions. This should avoid the problem of having to stitch the edges together, however, I may also have issues with the player being able to see the edges of the visible terrain. I may not be able to render enough of the terrain at the highest resolution to avoid this.

Another issue is what to do if the player is standing at the edge of several nodes of the quad tree. I will likely have to process all of those nodes, which could cause performance problems. In theory, the player could be standing on the intersection of four nodes, which would mean four times more processing would need to be done.