Avoid holes in terrain while loading

[kring]

When moving around quickly in Cesium for Unreal (or presumably any engine using cesium-native), we often see "holes" where particular terrain or photogrammetry tiles are missing, and it looks bad:

These holes will not show up while the camera isn't moving; the selection algorithm is smart enough to avoid that. Also, with the default settings, if you wait a bit for all the tiles to load for the current view, then you can spin the camera around all you like and you still won't see holes. However, if you quickly move to a new area and then rotate, holes are almost inevitable.

The reason is that the selection algorithm prioritizes "showing the scene in the current camera view as quickly as possible" over "avoiding possible future holes." Let me explain.

The selection algorithm has just decided that a particular tile does not meet the required screen-space error (SSE). So it wants to REFINE: render the tile's four child tiles instead. Well, we already know the bounding volumes for those four tiles, so we know which ones are visible (inside the view frustum, close enough to not be fog-culled) and which aren't. The million dollar question is: do we 1) load the visible ones first and start rendering the visible children in place of the parent as soon as those visible tiles are available? Or do we 2) wait until all four children are loaded - including the non-visible ones - before we refine?

You'd rather do the first option, right? Me too. It makes a big difference, because when we're zoomed in close it's common for the coarse tiles in the tile hierarchy to have only one child visible. Why? Because toward the root of the tile hiearchy, the tiles get bigger while the area we're interested in remains the same. That means the area of interest in the levels near the root will tend to be only one tile.

So Option 2 doesn't require loading a "little" more data, it commonly requires loading 4 tiles when we really only "need" 1. Closer to our selected LOD (i.e. the high-detail tiles near the camera), the ratio of visible to non-visible tiles tends to be higher. But overall, it's not an exaggeration to say that waiting for all tiles versus only the visible ones requires waiting for double the tiles to load.

But if we don't wait for the non-visible tiles to be loaded before rendering the visible ones, now we have to worry about holes. The holes are those other three-ish tiles we decided not to load (or loaded with lower priority and didn't wait for). We can't eliminate the holes by "un-refining" the parent. If we did that, detail would blink out of existence with slight camera movement, which would look even worse than the holes.

In short, the holes are a direct result of loading faster. The only way we can truly eliminate the holes is by waiting longer to show content to the user. We can't render the tiles that should go in those holes because we don't have them yet. And if we wait until we have them, loading will be slower.

✨ But maybe we can fill the holes with something? Something we can create or load much more quickly than the actual tile content? ✨

But what??

Ancestor geometry, clipped in the fragment shader

One answer is that we can use a portion of a parent (or ancestor) tile to fill the space of a missing tile. The easiest way to do this by simply rendering the parent (or ancestor) tile in place of the hole, and rig up the fragment shader so that any fragments outside the bounds of the child tile get discarded (so that the parent geometry doesn't overlap the geometry of child tiles that are loaded).

Pros:

• Easy to implement.
• Little to no CPU time required.

Cons:

• Physics / collisions don't match what's displayed.
• Possible performance problems due to high fill rate on low-end GPUs. @kring previously saw significant problems with this in CesiumJS, but @jtorresfabra has used this approach in the past and didn't see any significant fill rate problems.
• Cracking at edges due to LOD differences. No good way to fill the cracks with skirts or anything else.
• When bounding volumes are not tight-fitting, parent geometry clipped to the missing child's bounding volume can still overlap the geometry in other child tiles.
• Ancestor geometry from several levels up the tree often aligns very poorly with the real geometry. For example, with Cesium World Terrain, if we have to go all the way to the root to find a tile with geometry, that geometry can be wrong by up to 77 kilometers! That's going to be very noticeable (nearly useless) when the camera is down at ground level. "But wait," you say, "there's no terrain on Earth that's 77km high or deep." You're right, from far away the Earth is very smooth. But the curvature of Earth means that the midpoint between two correctly-placed vertices in a level zero tile can be wrong by that much.

Ancestor geometry, clipped on the CPU

Similar to the above, except we actually clip the ancestor mesh at the child boundary, giving us a new mesh.

Pros:

• Almost as easy to implement as the GPU discard approach, since we already have mesh clipping code for other reasons.
• Physics / collisions reflect what's rendered.
• No risk of fill rate problems. Clipped tiles are cheaper to render than the real geometry would be.
• We can potentially use skirts to fill cracks between tiles, at least for 2.5D geometry.
• If we interpolate the edge vertex heights instead of Cartesian positions, the heights won't be as wildly wrong. The worst case will be the height of Mt. Everest or so (8-9km) rather than that 77km we mentioned before.

Cons:

• Up to 8-9km of height error is still wrong enough to be useless in many cases.
• More CPU time than the GPU approach. Probably measured in single digit milliseconds or so.
• We still have no good way to clip for non-tight-fitting bounding volumes.

Fill Tiles

The CesiumJS terrain engine solves this problem with something called "fill tiles". Fill tiles are completely synthetic geometry that perfectly fills the space of a hole and meets adjacent (real) tiles at their edges.

It works by looking at the adjacent tiles to every hole, and copying their edge vertices into a new vertex buffer. Then it sticks one more vertex in the center at the average height of all the edge vertices, and links all the vertices into triangles as a triangle fan. This is fast enough to generate that it's done synchronously at the moment we would otherwise have a hole.

Pros:

• Fast to generate.
• Fills the space perfectly, no cracks.
• No need to plan ahead; we can generate a fill tile when we realize we need it and not a moment sooner.

Cons:

• Probably impossible to generalize to more complicated geometry than 2.5D terrain.
• The geometry is totally fake. Mountains often pop up in the center of a fill tile once the real geometry is loaded.
• The fan shape of the geometry can be noticeable and look strange when lighting is enabled.

Other ideas??

Render some kind of blobby foggy thing rather than a hole? Use some kind of fancy stencil trick or somesuch to render parent tile geometry? Something else?

[kring]

Barring someone coming up with a better idea, I think the best approach for cesium-native will be the one described as Ancestor geometry, clipped on the CPU.

Clipping on the CPU will be too slow to do it synchronously during tile selection when we realize we'd otherwise have a hole (like we do with fill tiles in CesiumJS), but it should be plenty fast to do as part of the load process. Basically, our rule should be that we're only willing to refine a tile if all of its children have either been loaded or clipped from ancestor geometry. We can avoid "really wrong" ancestor geometry by limiting the number of levels we're willing to traverse to get to an ancestor with geometry available.

I don't really have a solution to the non-tight-fitting bounding volume problem. Options:

1. Clip to the child bounding volume, even though it doesn't fit tightly. There may be some overlap between the geometry from other children and from the clipped parent, but 🤷 we'll live with it.
2. Refuse to fill holes by clipping when bounding volumes aren't tight fitting. We can detect non-tight-fitting bounding volumes by looking for overlaps in child bounding volumes, or with an explicit, user-configurable property. When we refuse to fill holes by clipping, we're back to either living with the resulting holes, or loading slower in order to avoid them.