P-152: Virtual World Concept Update 32: Chunked Levels of Detail Using Quad Trees

My Quad Tree test program is progressing well. I have a fairly good idea now about how to use Quad Trees in a spherical terrain implementation. What I intend to do with my project is:

First, create several different versions of the spherical terrain, at different levels of detail (For example, 256*256, 512*512, 1024*1024, etc). This data will likely be stored temporarily in vectors.

Then, a single quad tree will be created, which will store the terrain information for all LOD’s in it’s hierarchy of nodes.

I can then quickly parse the quadtree, using a distance based calculation (based on the players position) to decide if a particular node should be returned at it’s current resolution, or subdivided into a lower resolution. I will also need some way to group or “chunk” together several nodes surrounding the player.

Early tests indicate that the quad tree design that I have created does, indeed, perform much better than brute force (manually parsing all terrain pixels). One preliminary test resulted in my quadtree program processing just 12 terrain vertices, where a brute force algorithm faced with the same problem had to process 84 verts. This is a 7-fold performance improvement, and it seems that as the terrain becomes more detailed, the performance gains are even higher.