More accurate view distance based graph expansion

[Ralith]

After moving each character, Graph::ensure_nearby is used to expand the graph to contain all nodes whose centers lie within the view distance, and all neighbors of those nodes. Because chunks cannot be populated with terrain until the cell of the cubic honeycomb containing them has all incident nodes generated, this leads to characters being within view distance of chunks that lie within generated nodes but which cannot be populated as they have incident nodes which have not yet been generated.

To correct this without expanding the graph at an unsustainable rate, we need to use a chunk-aware traversal that populates nodes if they are incident to a chunk which is within view distance. To avoid requiring a hyperbolic cube vs. sphere intersection test, we can approximate chunk visibility by considering node vertex visibility or using bounding spheres, as in #49.

[Ralith]

This is the remaining substantial source of chunk pop-in.

[patowen]

Based on a rough sketch, I believe the radius of the bounding sphere should be twice the distance from the center to a vertex of a particular node (or in other words, double the maximum radius of a node).

(This would be if we used bounding spheres for entire nodes)

[Ralith]

That's extremely counter-intuitive. Are the vertices of the dodecahedron not the furthest points from its center?

e: oh, you mean the bounding sphere for when a node might be required for an in-view chunk. That makes sense.

[patowen]

I tried a simple implementation of this, but the view distance sacrifice requires feels too great. So far, I prefer the pop-in.

For concrete numbers, the default view distance from the origin would require 265259 nodes to be added to the graph to render the 21737 nodes that would actually have generated chunks in them. In contrast, the current implementation with the same view distance adds 16017 nodes to the graph to render the 1905 nodes that have generated chunks in them (although that is lower than necessary, given the pop-in, the difference is still quite striking).

The main problem is that the bounding sphere radius (with defaults) is 25.7 meters, so doubling it results in 51.4 meters, which is approximately how much we would need to reduce the view distance by to get the same numbers. That's more than half the default.

It might be best to keep this unfixed for now until world generation is better fleshed out (with non-intersecting megastructures, for example) and then greatly optimized.

[Ralith]

That's more than half the default.

From your numbers, it sounds like only 10% of the chunks in the default view distance are actually populated right now, so I'm not sure that's a fair comparison.

[patowen]

It's definitely not a fair comparison. I've been putting it off, but I should actually compute how many nodes and chunks intersect with a sphere around the player to see what the numbers would be in the ideal case.

[patowen]

Based on some additional testing, by using actual intersection computations, the minimum number of nodes that have to have at least one chunk rendered to support a view distance of 90 is 16133, so between 15917 and 21737 is a tradeoff between intersection computation speed and chunk-handling speed.

The number of nodes that need to be added to the graph to be able to generate all these nodes is 71687, so between 71687 and 265259 is the same tradeoff.

However, the 1905 -> 15917 increase in number of nodes rendered for a view distance of 90 is unavoidable, and 21737 doesn't seem that much worse.

Assuming we don't change the implementation of terrain generation, the 16017 -> 71687 increase is also unavoidable, but 265259 does seem significantly worse, so we might want to be smarter here.

Since we only need these extra nodes for terrain generation, it might be better to generate these nodes on the fly when we're about to use them for terrain generation rather than every frame. However, we'll need to move the ensure_nearby implementation to the client to fully support this (finishing up unfinished business from #309).

[Ralith]

I'm having a hard time following these numbers. What is the change in the number of nodes wrt. today that must be generated to fully populate the current view distance? What is the (approximate) view distance that, when fully populated, has the same number of generated nodes as we have today?

[patowen]

In short

The change in the number of nodes that must be (at least partially) generated to fully populate the current view distance is from 1905 to 15917 (or 21737 if we naively use node bounding spheres). To have the same number of generated nodes instead, we need to reduce the view distance from 90 to 68 (or 65 if we naively use node bounding spheres).

The change in the number of nodes that must be in the graph to generate the necessary chunks for the current view distance is from 16017 to 71687 (or 265259 if we naively use node bounding spheres). To have the same number of populated nodes instead, we need to reduce the view distance from 90 to 73 (or 60 if we naively use node bounding spheres).

In detail

The answer depends on where the player is, but I'll assume they're in the center of a dodecahedron (which likely will result in slightly smaller-than-average numbers).

The number of nodes that must have at least one chunk in it fully generated to fully populate the current view distance (of 90, or 4.2954593 in absolute units), is 15917. With default settings, nearby_nodes produces 1905 nodes, so this is an increase from 1905 to 15917. If we naively use the node's bounding sphere instead of getting an exact result, this number further increases to 21737.

The number of nodes that must be added to the graph for world generation to be able to generate all chunks within the render distance is larger because world generation requires querying data from neighboring nodes. With the current view distance, the answer is 71687. With default settings, ensure_nearby produces a graph with 16017 nodes, so this is an increase from 16017 to 71687. If we naively use the node's bounding sphere instead of getting an exact result, this number further increases to 265259.

The view distance that has approximately 1905 nodes in view is 68, or down to 65 if we use the bounding sphere instead.

The view distance that has approximately 16017 nodes that need to be in the graph for terrain generation to populate all the chunks in view is 73, or down to 60 if we use the bounding sphere instead.