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

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.