🔴 OPEN BUG: Terrain Octree

Eggheads talking about bytes and stuff.
Post Reply
User avatar
Site Admin
Posts: 1470
Joined: 2022-Jan-09, 00:59

🔴 OPEN BUG: Terrain Octree

Post by Krishty »

The main reason for draw distance limits is TFXplorer’s “flat” terrain data structure. All terrain tiles are thrown into one large array for rendering, collision, etc.

At the current viewing range of up to 49 tiles, up to 5000 terrain tiles must be processed for gameplay, rendering, contrails.

When the viewer moves to a new terrain tile, ca. 100 tiles need to be thrown away (they get out of range) and another 100 must be loaded (as they enter visible range). Of the 4800 tiles that remain resident, several hundred may change their LoD because their distance to the viewer changed.

Unfortunately, there is zero order in the process. In a flat array, fetching/removing entries happens semi-randomly depending on where the viewer is and where he goes. GPUs rely heavily on batching, but no batching can take place with semi-random changes: you either have to create 5000 tiny batches (useless) or a large one that you throw away and rebuild in its entirely when something changes (also useless).

This is the reason for these CPU spikes as you move through the terrain:
image.png (267.64 KiB) Viewed 1258 times

We need a hierarchical data structure that allows batching + caching on different hierarchy levels. Since the terrain is 2D, an octree is the novel solution: Tiles at the lowest level. Blocks of 2×2 tiles above that. Then Blocks of 4×4 tiles; 8×8; 16×16; etc. As the viewer moves, in 75 % of cases you only need to rebuild a 2×2 block. 4×4 blocks in 25 %; 8×8 in 6.25 %; etc.

This should remove our restrictions on draw distance and greatly improve our ability to pump polygons to the screen.
Post Reply