I have something to ponder.
The initial version (that btw.. compiled on Windows with only minor adaptations, thank you @Haystack) was based on a heighmap that is available in its entirety right from the beginning. I got away without any pre-processing of data, just load the texture image and start rendering.
I said I build a data structure of aabbs of given node_size that are used to select what needs to be rendered this frame. For that, I need the horizontal extent which is trivially known by the node's x/z position in the quadtree. And the minimum and maximum height, either thoroughly looked up from all the node's height values which is slow but accurate or estimated for instance from lookups of corner points and centre or any selection of values inside of the node. More formally: a node's aabb at position x, z in the raster of the quadtree has the coordinates
minimum = (x, minimum height of node's area, z)
maximum = (x+node_size-1, maximum height of node's area, z+node_size-1)
Savvy so far ? π΄ββ οΈ
I did this to have optimal flexibility, as everything terrain renderer related could be recalculated on the fly.
These days seem to be over when I expand this to something that doesn't fit into memory any more. The quadtree is generated as a whole, but heightmap tiles will be loaded on demand. So he horizontal extent of a node is still there as it only depends on the quadtree, but the node's height values are not yet in memory.
I could
- (a) just ignore them and use an aabb of magical height for the selection.
- (b) pre-calculate minimum and maximum values.
- (c) look them up each frame during node selection.
- (d) insert them into the nodes' aabbs on tile loading.
(a) Not feasible. In steep terrain nodes will be missed.
(b) Possible. Needs a pre-calculation step that extracts minimum and maximum values when the heightmap images are generated. Or I would have to offer a tool. Disadvantage: I loose quite some flexibility as the node size must be known when a heightmap is generated. This means people should know what area and spatial extent a heightmap is meant to be for when they make one.
(c) Possible for small heightmaps, but quickly slows down the algorithm because of cache misses.
(d) Possible, but would probably lead to some popping and actually I wanted to avoid this type of artefact
But it would be slow as I'd have to traverse the tree to find each node and assign the minimum and maximum values. It'll also significantly slows down the loading process for a tile.
Maybe I have not thought of something.
I tend to (b), create a min-max-map and sacrifice flexibility. Creating such a map would be a nice finger exercise for an aspiring C++ newcomer. I'll help :-)