P-152: Virtual World Concept Update 93: Chunked Levels of Detail Using Quad Trees Part 60: Proof of Concept

I believe I have finally achieved some preliminary proof of concept on this project. I still have a lot of work to do, and I have added a lot of hacks and temporary code to the system to get the proof that I need, but I do think that I am at the point where my solution can work, it’s just a matter of continuing with it.

The final piece of the puzzle that I needed was found HERE.  One blog, the author creates a system similar to the one that I am trying to create, however, they made a slight change to what I am doing. We both started with a “view distance” within which the player should be seeing all nodes, (which, coincidentally, was 50 meters for both of us!) however, they doubled the view distance for each tier, so the lowest (most detailed) tier had a view distance of 50, then 100 for the next tier, and 200 for the next.

I wasn’t doing this, I was keeping the distance at 50 for all tiers, and so some of the upper tiers were not being subdivided (because they weren’t close enough). Increasing the view distance of the higher tiers, seemed to fix this.

The following is some output from my project. I have edited it slightly to make it easier to read, but the data itself is the same.

I am using a very simple 4×4 grid for my lowest tier, so I have a root node at the top node, then 4 nodes beneath that, then 16 beneath that.

PATTERN: 0 46.818398 120

PATTERN: 1 60.809765 60
PATTERN: 2 18.453243 60
PATTERN: 3 87.349358 60
PATTERN: 4 63.461105 60

PATTERN: 9 28.831198 30
PATTERN: 10 27.726509 30
PATTERN: 11 27.210642 30
PATTERN: 12 26.627022 30

EXECUTIONS: 9

The base view distance is 30. At the top of the tree, the view distance is 120 (30*4). The distance is 46.83 (between the player and the node center, I didn’t use projection or anything complex like that, just a basic 3D distance function). 46 is less than 120, so this node is subdivided.

At the next tier, the distance is 60 (30*2). 3 out of the 4 nodes in this tier fail the distance check (Node 1, 3, and 4 all have distances greater than 60). So, only node 2, with a distance of 18, should be subdivided, and it is, the ONLY nodes to be processed from the final tier are nodes 9,10,11, and 12. All other nodes were excluded without being processed. Since all nodes in the final tier are less than 30, all nodes render, giving 4 visible nodes, and a total of 9 executions (compared to 21 if all nodes were processed).

PATTERN: 0 44.358543 120

PATTERN: 1 53.603680 60
PATTERN: 2 20.225315 60
PATTERN: 3 84.271286 60
PATTERN: 4 66.791267 60

PATTERN: 5 67.052711 30
PATTERN: 6 72.205887 30
PATTERN: 7 41.021362 30
PATTERN: 8 44.516945 30
PATTERN: 9 24.109743 30
PATTERN: 10 26.365093 30
PATTERN: 11 30.481152 30
PATTERN: 12 33.372673 30

EXECUTIONS: 13

The story is similar with this output. The visible distance is the same (30). 44 is less than 120, so the root node subdivides, but this time, two of the nodes in the next tier are less than the view distance, nodes 1 and 2, the others are excluded. In the final tier then, nodes 5,6,7,8 (children of node 1) and 9,10,11,12 (children of node 2)are subdivided. Of these, just two are close enough to be rendered, for a total of 13 executions.

I still have a lot of work to do. The main thing is to modify the points generation algorithm to remove my hardcoding and hacking, and allow for the use of much higher resolution terrains. I also need to test the code with all 6 of the faces of the spherical terrain. Currently, I am using just one face for testing. I then need to add textures, and find a way to scale the terrain to realistic planet sizes.

However, for now, I think what I have done is enough for a basic concept test. I will continue working on this, although other projects will likely be put to the forefront for a while.

I may post a video of the prototype working at some point, I haven’t decided on that yet.