My experiment and suggestion for a chunk LOD system

[MirceaKitsune]

An idea has been floating in my mind about an easy and effective LOD system for chunks. Back when I attempted a basic Minecraft like engine in Godot, I have used this technique and surprisingly got it to work quite well: It was only for terrain as I haven't gotten around to adding more, but I know it provided surprisingly accurate results. I will explain my technique below and exactly what I suggest implementing: If there's no strong disagreement or blocker I may even post this as an issue in Github later.

Like virtually any engine, the performance goal in Minetest is to get as much draw distance as possible without losing performance. While performance has greatly improved in recent years, you still need to keep the world foggy if you have a 144 Hz monitor and would like Minetest to run at your Vsync of 144 FPS. For this reason a LOD system for rendering distant chunks would be useful to consider: Long ago we did in fact have such a thing, however it was never used as it was glitchy and merely produced ugly polygons trying to mimic the terrain. My suggested implementation is much cleaner and should not have this issue.

What I did: When the origin of a chunk is past a certain distance from the camera, the chunk is drawn at a larger scale by treating groups of voxels as one voxel. This means that when generating the visual mesh of that chunk based on its contents, you don't create 1x block for each voxel, but a single 2x block for the average of voxels in that 2x2x2 area: This results in less faces by essentially halving the resolution of the chunk at the price of accuracy. The further the chunk is from the camera the more we increase the skip... this must be done up to a common sense limit as going too far will eventually result in ugly gigantic cubes, in my case I only allowed up to 4 steps / meters so 3 just LOD levels. As the faces become larger, the texture is mapped at opposite the scale and repeats accordingly as to create the illusion of nodes being at the same size. Nodes that aren't cubes (meshes or nodeboxes) are dropped and treated as empty space. The LOD meshes of each chunk should be generated when that chunk is loaded and stored in memory until that chunk is dropped, at least in Godot I found that keeping them is cheap given their low resolution and avoids delays when LOD levels are changed as the player moves.

Example: Let's say the top-left corner of a chunk contains the following 8 voxels in a 2x2x2 area: 4x cobblestone, 1x dirt, 3x air. The algorithm determines cobblestone is the predominant node, and proceeds to draw the whole set as a single cobblestone block of double size. When two or more different nodes exist in equal proportions in an area, pick the first in a predictable way so the decision is consistent across neighbors... for maximum efficiency air could be preferred if in equal quantity to a solid node.

Needless to say this is a LOD system which implies loss of detail: It will look ugly and inaccurate, but will allow you to see something from far away which may be better than a low draw distance. For instance the trunks of trees will always disappear as they're 1 nodes thick so the algorithm will always detect more air in any given 2x2x2 area... terrain on the other hand shouldn't see much of a difference, it will just appear a bit larger but still seem fairly okay. This effect should thus be used very far away, in my experiment I think I set it to start beyond what in Minetest would be 256 nodes / meters. With this optimization we may be able to safely support draw distances of 500 to 1000 nodes now which seems optimal for realism and beauty, granted we can also boost the distance limit at which the server sends chunks to clients which is itself very low and greatly limits draw distance. What do you think?

[Blockhead]

I think this LODing from a client would ramp up client CPU usage. I know having the client chunk mesh cache can ramp it up already, this would add more load. It might add CPU bottlenecks for performance back to Minetest, which is already kind of infamous for being too CPU heavy for what it achieves graphically. But you never know without code I say.

[MirceaKitsune]

I think this LODing from a client would ramp up client CPU usage. I know having the client chunk mesh cache can ramp it up already, this would add more load. It might add CPU bottlenecks for performance back to Minetest, which is already kind of infamous for being too CPU heavy for what it achieves graphically. But you never know without code I say.

The performance gain would have to be calculated by the user when enabling it: There may be a little bit of extra CPU usage as chunks load, in exchange for better FPS for longer draw distances from there on. I'm not too worried here since remember that lower LOD levels are also easier to compute given they're much simpler.

[freshreplicant]

I can't attest to the technical soundness of your imagined implementation, but an LOD system for Minetest would be great. I suppose it could be toggleable by the user, same as the other fancy graphical features.

[MirceaKitsune]

I can't attest to the technical soundness of your imagined implementation, but an LOD system for Minetest would be great. I suppose it could be toggleable by the user, same as the other fancy graphical features.

My Godot based project still suffers from slow loading times so it's hard to retest exactly what I did: Will see if I can fix it and get a few screenshots for reference, at the moment I'm busy working on a new little mod for Minetest. I only remember that it did look right in the end: The only issue was you could get cracks between connecting chunks, but again it's LOD and only meant to appear at high distances it's not bad practically.

Also: There's a simpler and more CPU effective way to go about my suggestion, albeit slightly less accurate. Instead of scanning the average quantity of voxels in a space, check only the top-forward-left corner and make the whole thing whatever you find there. This means that for LOD we simply loop through voxels in the chunk data in larger steps: Instead of "{x: 1, y: 1, z: 1}, {x: 2, y: 1, z: 1}, {x: 3, y: 1, z: 1}, ..." the scan will be "{x: 1, y: 1, z: 1}, {x: 3, y: 1, z: 1}, {x: 5, y: 1, z: 1}, ..." instead. Only issue is this makes it a matter of luck what will appear, voxels on even positions will be rendered at 2x size while those on uneven positions removed... it's LOD though so as long as it's efficient and accurate enough that you see something and it doesn't look wrong it's not that important.

[hex]

You're describing essentially an octree. I've thought of LODs a lot as well so let me add what I know.

First, textures currently mip out to basically a single color within the practical viewing range. (i currently consider 500 the new "okay" range)
This means that beyond some point, you shouldn't even think in terms of textures like "cobble" or "dirt" but rather single colors akin to the minimap color, which is derived from the tile and probably equivalent to its final mip.
Therefore, LOD systems would get most bang for buck by encoding color information only. Using color only means that you do not need to switch shader state. Color can be encoded in cheaper schemes than 16 bit, indeed, you could probably generate an optimized 256-color palette from all the registered node definitions. Some nodes would be "off" but you wouldn't notice it much.

Next, beyond a certain distance it no longer matters whether the nodes or chunks of them are actually cubic. They can very well be represented by a cloud of thick GL_POINTS. (This has been suggested by more than one person in the past.) Extensions to render points with a variable size are common, so your octree simplification could be used - it would simplify rendering a little, but what you really gain here is the much needed bandwidth increase to actually push terrain at that distance to clients.

Third, lighting information is probably unnecessary beyond a given distance. Light sources at huge distances can be represented as additive halo sprites. Screenspace ambient occlusion performed on the far chunks could approximate the flood GI relatively well.

Fourth, at extreme distances you do not really need the color either. You can just render solid matter as huge points, and if you want some anti-aliasing, you can alpha blend it using the node density (amount of nodes occupied in an area) as the alpha value. You can also experiment with subsampling beyond a certain distance - this can paradoxically decrease aliasing rather than increase it, especially if the subsample is anisotropic. Another thing you can do at thousands of nodes away is render to a cubemap texture and timeslice its updates, exploiting the fact that nobody is going to travel fast enough to notice. This approach also allows better anti-aliasing opportunities and is probably optimal for the maximum LOD level.

[Faustawk]

the minecraft mod farplane two uses a system that uses the world generator to guess what's in far-off areas rather than actually loading them from disk. Not sure if it would be possible in minetest (and wouldn't be for Lua mapgens) but if so it would provide a significant performance boost.

[MirceaKitsune]

Hex: Interesting approach, thanks for sharing. It would be interesting to see examples of how that looks in other engines. That approach though would be much lower quality: The one I'm going for is still a 3D mesh and textured as well as lit by the environment (sun / moon only), only the number of faces are reduced by 2x / 3x / 4x respectively which should mean they are that much faster to render... I think it would be higher quality than simple colors and no lighting, I imagine that may be difficult to get right.

the minecraft mod farplane two uses a system that uses the world generator to guess what's in far-off areas rather than actually loading them from disk. Not sure if it would be possible in minetest (and wouldn't be for Lua mapgens) but if so it would provide a significant performance boost.

I'm curious how it does that guessing. Based on the mapgen parameters? That's actually a very interesting idea, since this way you don't rely on the server sending you chunk data for far away things, it could work with my implementation idea also! But obviously it has the drawback that any large scale edits made by players will be missing, which for a little house might not matter but if you have a giant castle it will look odd that it suddenly pops out of nowhere from LOD areas once you get close enough.

[Blockhead]

the minecraft mod farplane two uses a system that uses the world generator to guess what's in far-off areas rather than actually loading them from disk.

This is the type of methodology the old 'farmesh' for Minetest used. I'm not sure whether sampling perlin noise at low resolution or loading blocks is slower; it may depend on the available server RAM cache, though CPU calculation can be faster than a RAM fetch. Conceptually I don't like it much because of how much players might have modified the terrain, though the benefit is that the terrain doesn't need to already be there - though it certainly makes things easier, which is why Veloren pre-generates the entire world to about 3 levels of detail.

[LMD]

Two observations:

(1) I think a "farmap" implementation would definitely benefit very much from good mapblock culling: Don't send invisible mapblocks. I think we already do this to an extent, but it could probably be improved.
(2) From a distance, you can only see the outside surface of a chunk. I'd expect sending just the surface to be vastly more efficient in the average case; you'd only have O(n²) - think something like 4 times 16² - rather than O(n³) many blocks - think 16³ - to send per chunk. (Then again, the "invisible" blocks like air or the stone beneath the surface usually compress well.)

[MirceaKitsune]

Very good points LMD: Another technique would be to only mesh the outside of a chunk past a certain distance, not making it convex per say but not allowing only a given degree of inner holes. And yeah entire chunks should be derendered if the geometry of a closer chunk is completely covering them, if that circumstance can easily be detected definitely do so!

Something worth noting about my suggested implementation: It can be used not only to generate the LOD mesh faster locally, but also send less data from the server potentially making the optimization network efficient too! We are decreasing the resolution of the chunk to double / triple / quadruple its voxel size, something we can just as well do on the server then send this reduced voxel data through the network. Doing so may allow boosting server-side draw distance too (how far from a player the server sends chunks) with less bandwidth requirements!

Of course this has a drawback: As the player gets closer to a chunk, the server needs to send it again at a higher resolution and eventually network the original chunk data if you get close enough... clients will also be stuck with the LOD model for longer till the new data makes it through the pipe, we need to think what happens with collisions and such if you can even walk into it (I'd block entry as is done for unloaded chunks). Of course if the player goes in one direction and not toward certain chunks, those chunks will never be viewed thus sent at their full resolution. So all in all this might result in slightly less data being sent overall.

There is of course a way to mitigate even this duplication, granted we go with my later approach of implementing the optimization by means of positional skipping rather than averaging (eg: "{x: 1, y: 1, z: 1}, {x: 2, y: 1, z: 1}, {x: 3, y: 1, z: 1}, ..." becomes "{x: 1, y: 1, z: 1}, {x: 3, y: 1, z: 1}, {x: 5, y: 1, z: 1}, ..." for each axis): The server remembers which positions were already sent to the client... as you come closer it only sends more position sets that you need to receive without re-sending ones that were already networked.

Yet another bonus: We can even use this to support faster world loading times in general, by allowing chunk data to appear faster even for close chunks, similar to how some png images first load blurry then their resolution increases! The server first sends the lowest quality layer to the client which renders the worst LOD level and applies it to all chunks, then the second best which is applied on chunks close enough to be using it... finally the chunk is sent and applied at its full resolution for ones close to the player.

Really wish I could get some thoughts from the developers on this: It's fun just thinking about those optimizations! I'll likely submit a modified copy of this on Github with all the aspects laid out in detail.

[proller]

https://youtu.be/trM2iTgLn_Y?t=192

[MirceaKitsune]

https://youtu.be/trM2iTgLn_Y?t=192

Yep, that's exactly what I was thinking of! Except with a much larger draw distance that would (ideally) be enabled by this change so the lower LOD levels only appear much further... even like that though it doesn't look bad at all, you see the snapping which could hopefully be smoothed somehow. Is that an engine fork, or a system that existed long ago and is no more today? I presume the LUA API doesn't have the ability to modify chunks in this way.

[proller]

still available around
https://github.com/freeminer/freeminer/ ... sh.cpp#L39
and still some holes not fixed on two levels joint
Also it was tried many years ago, now need to adjust settings for modern hardware

[proller]

https://youtu.be/Mtu3JyOiDCM
Also main problem is loading blocks from server and managing huge amount of them

[Astrobe]

Lossy compression for distant chunks?

[MirceaKitsune]

still available around
https://github.com/freeminer/freeminer/ ... sh.cpp#L39
and still some holes not fixed on two levels joint
Also it was tried many years ago, now need to adjust settings for modern hardware

Oh yes, I remember the Freeminer fork! Been a while since I last heard of it, wonder what the main differences today are. Any reason why vanilla Minetest wouldn't back-port this feature from it? Could that happen once it's good enough?

https://youtu.be/Mtu3JyOiDCM
Also main problem is loading blocks from server and managing huge amount of them

For a LOD system it looks really good and works just as I imagined it! The result is more aggressive in this video as the camera is in fly mode so you're moving fast and seeing a lot from above: When moving slowly at ground level it would probably be a bit more subtle, especially if it can be increased to act from further away.

As for optimizing data sent by the server, in case you're still working on that algorithm and can try the other half of my idea: Try making it so the server sends chunk data in steps, which would make the optimization also work as a form of faster loading and improve network efficiency apart from client-side LOD face reduction. The only disadvantage is clients will no longer be able to disable LOD as the system then becomes dependent on the server's settings on the matter, but if it looks alright I for one couldn't complain.

Example: Say the chunk is moderately far away so it's first being viewed at 2x LOD. The server only sends nodes at even positions to the viewing client, for example "{x: 0, y: 0, z: 0} = stone, {x: 2, y: 0, z: 0} = dirt", the client then interprets this data as "one 2x2x2 stone block at position 0x0x0 and one 2x2x2 dirt block neighboring it at position 2x0x0". If the client moves away from the chunk and never gets close enough, the server never bothers sending the other data for it. If instead the client moves toward the chunk enough to warrant loading it at its full resolution, the server sends the remaining positions (in this example "{x: 1, y: 0, z: 0} = stone") without sending the rest which the client already has... the client then recompiles the mesh at the higher resolution after receiving the additional data and mixing it in with the old one to form the whole picture.

Lossy compression for distant chunks?

That's pretty much my idea above: The system could work as both LOD for better performance on the client, and gradual data transmission for the server so it too has to network less to clients for distant chunks.

[MirceaKitsune]

A little addition to what I said above: Clients should give the server their maximum LOD level of choice mixed with their desired draw distance, the server then uses that info to provide the result closest to their decision. This means that if clients don't enable the new system, servers don't care and won't change anything from the current behavior... if the client indicates they're using chunk LOD, servers will then send chunks that are further away in stepped position intervals to allow for a greater draw distance than usual without too much extra networking. Separately and on top of that the client also changes chunk LOD based on draw distance and how the player moves... if a chunk for which it has the full data is now too far away it becomes a low-res mesh again for better FPS, but if you get close to it again before it unloads entirely the data won't be requested from the server a second time.

[Strength4549]

Does anyone know if the core devs ever said anything about LODs, or other performance improvements for that matter? Seeing that you guys seem to have already put this much thought into the matter, and even seem to have an MT fork with it, I just wonder why it isn't in the base game yet.

Is there some list of requirements that an LOD implementation would have to fulfill? Are the bottlenecks somewhere else?

Ive modified the client code a bit like MicreaKitsune suggested, to only render every nth node, to get a bit of a better understanding of the matter. So as long as you don't change your render distance or request more blocks from the server, this approach should have no performance or memory downsides.

As long as you still load the same number of blocks, you dont need any more ram, and it wouldnt take any longer to request the nodes from the server. It also doesnt put more load on the cpu, besides a couple extra ifs and multiplications per rendered node.

It should however speed up the mesh generation, since you only have to look at every 8th, 32nd, etc. node. And it could probably save a bit on vram since youre throwing fewer vertices at your gpu. Tho admittedly, those are just assumptions on my part. I have no clue if thats even how this works, or even if it is, if itd make a measurable difference.


Edit:
Implementing these LODs increased the fps on my laptop substantially when standing still in an empty dev map. Not sure how well that improvement would carry over to actual gameplay tho.
I just stood still for both of these, waiting for all the terrain to load. My laptop suffered greatly in both cases, but slightly less so in the LOD example.

Granted, it doesnt look good. Even for an LOD. But it kinda serves as a proof of concept that you dont need a perfect LOD system to improve the performance, and im sure that someone who whos familiar with c++ and the codebase could make something way better to convince the core devs in a reasonable amount of time.

[MirceaKitsune]

I was recently reminded this system already exists in a fork of the Minetest engine, though it still seems to need a bit of work from what the video showed. We just need the owner to make a PR for putting it in vanilla Minetest! I believe Paramat managed it, he could probably make a PR but I presume we'd need MT devs to confirm they're willing to integrate it.

[Blockhead]

The most active fork with an LOD system is proller's freminer with farmesh. It's been demoed before in posts like this one.

[proller]

Best actual newest code (but still unfinished) is here: https://github.com/proller/freeminer/tree/wip5.8.0
Add to config:

Code: Select all

world_merge=1 # To enable real world data
farmesh_quality=3 # if want better farmesh quality

Also available demo with very low farmesh quality https://servers.freeminer.org/ - all 'play' buttons

[proller]

current state : https://www.youtube.com/watch?v=tqSYzEMTwBE

[MirceaKitsune]

current state : https://www.youtube.com/watch?v=tqSYzEMTwBE

Looking very nice. Only issue I could personally notice is at least from some angles even farmesh won't load fast enough and there were missing chunks, at least in an older video where it was more obvious. Once it's stable this has the potential to be one of the biggest ever optimizations for Minetest!

[proller]

there is a lot issues for months of fixing..
Night version (with lights many kilometers away) https://www.youtube.com/watch?v=TzqoNShEJYA