LODding Terrain for 3D in Godot

Haystack

Pixophir I don't see a makefile, or CMakeLists.txt, or similar to describe the source dependencies. Do I need to make one?

Pixophir

Yes. You can use whatever build system you like or your IDE supports (even Scons 😜 ). I just use the Eclipse-cdt built-in.

I set include paths to the src/ and extern/ subdirectories. All includes should be relative (sometimes Eclipse gets in the way and renames them). Refer to the readme.txt for other dependencies. Link against the dynamic loader and pthread. Well, you'll see :-)

I am not into the make family because they drop their files in every directory.

Pixophir

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 :-)

Megalomaniak

IMO, Either b) or d) or if you can afford to implement both, option e) "choose your poison", let the game designer choose which works best for them.

But if only one, keeping in mind that

Pixophir actually I wanted to avoid this type of artefact

I'd also go for b)

Tomcat

Pixophir 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.

I guess when the user creates a landscape, they assume what terrain they want — mountainous, hilly or plain.

Probably need to distinguish between generators and pseudo terrain generators.

Pixophir I need some ~~realistic~~ values suitable for a game environment for testing.

I will show it with my own example. I need a terrain generator, first for a small village-farm, which could then grow into a city: a river or lake nearby, a forest of small hills.

For example for archaeologists, you need accurate reconstruction of terrain on the map — for the reconstruction of ancient settlements. But an element of randomness is desirable for the game.

Specifically, here is a desirable example of terrain:

This, the ancient Russian city — the Lord Great Novgorod. The last democratic state of Russ.

It is a swampy land, it is not always clear which rivers are natural and which are artificial. But to develop the city you need the ability to change the landscape: cut down trees, block the river in one place and dig canals in another. Fill in and tear down hills.

Pixophir

That would be possible to do both methods, it is not a big deal logic wise, just diligence.

Currently doing a small generator (diamond square) for terrain at higher resolution than I can do with real world data. I need some ~~realistic~~ values suitable for a game environment for testing.

Pixophir

@Tomcat Looks nice, I genuinely love archaeology.

I herewith lift you in the rank of chief terrain generation algorithms officer (CTGO). Your task is to search and find (and optionally implement) algorithms suitable for the purposes you want in a game :-)

A quick and dirty diamond square with fixed values is just 150 lines of code, including writing images to file, which is more than half of that ...

Tomcat

Pixophir Your task is to search and find (and optionally implement) algorithms suitable for the purposes you want in a game

Greatest regrettably, creating the terrain is only part of the project. There's a lot to be realized: the changing of the seasons, the growth of vegetation, the social behavior of people… I think I'll stop there. Right now I'm trying to figure out what can be implemented fairly cheaply in the first phase to proof-of-concept, and what should be put aside for later.

Haystack

Option (e): instead of a quadtree, use an octree, where each octant in a given LOD is the same size.

Pixophir

But that doesn't help me with the problem that the height data is not available at the time the spacial data structure is built.

(b) is the way for height maps that are already defined before the program starts. Needs some pre-processing, but is fast.
(d) must be done when height data is generated procedurally, like not stored at all. Performance needs to be monitored.

Haystack

It does help. With an octree, you don't have care about the min/max height of the source terrain data, b/c each octant is always the same size. If the terrain data exceeds the bounds of the current octant (above or below), that portion of the terrain data is put into a sibling octant (i.e. the octant above or below the current octant). This way your LOD switching distances are constant for a given LOD.

Pixophir

I had to pause for almost a month, but this weekend managed to implement the independent scaling of linear flat worlds. This means, one passes in the heightmap und a constant metric distance between posts and the renderer takes care of the scaling.

Haven't yet finalized the double precision rendering, so for now there is jittering when close to terrain of "actual size", but I got a roadmap for that.

Next asynchronous loading of heightmap patches, henceforth named tiles.

Maybe I should start to learn how to do videos ...

Megalomaniak

Pixophir Maybe I should start to learn how to do videos ...

OBS

Pixophir

Well, I was thinking about a recorder for my own renderer, but I think that'll do for now :-)

I still believe, that if I integrate this into the Godot scene tree, it'll be a huge node that brings all with it that is needed for rendering the world, terrain, scatterings, sky, shadows. And visitable places in there may be other scenes.

« Previous Page