search

Hopson97 / open-builder

Open "Minecraft-like" game with multiplayer support and Lua scripting support for the both client and server
https://github.com/Hopson97/open-builder/projects/3
GNU General Public License v3.0
700 stars 80 forks source link

Suggestion: Don't use trilinear interpolation for terrain generation. #67

Open KdotJPG opened 4 years ago

KdotJPG commented 4 years ago

Suggestion Title Don't use trilinear interpolation for terrain generation

Describe your suggestion

Noticing commit c2b95e4c8a79ffbfe2a03d7a4c191e41bbf89dec from yesterday.

I would recommend not to use trilinear interpolation for terrain generation in this project, if you are able to consider such. Perlin and trilerp might be the biggest visual detractors to Minecraft's terrain generation. They are worth avoiding rather than emulating, in my opinion. I do see that you are using glm::simplex instead of glm::perlin for the 2D heightmap, which is great. But trilerp can tarnish the results of even the best noise generator or terrain formula, because it breaks the continuity of slopes and introduces a visible grid pattern. I think the community needs more counterexamples to trilerp, than they need more examples of it.

I put together a quick Minecraft mod a few days ago, to demonstrate a counter-example to the trilerp speed optimization. I haven't run performance metrics on it yet, but the approach doesn't feel any slower than Vanilla trilerp when generating or exploring worlds. The key optimization is to start with the height-based threshold, and any 2D noise that can be pre-generated per column. Then, generate the successive octaves of 3D noise only when you know that (current generated value so far) + (max range of the rest of the octaves including current octave) can possibly cause a cross between a positive and negative final value, i.e. block or no block. If it can't, stop generating noise at that block. Most blocks will get ruled out before any noise is generated, because the height-based threshold precludes noise from affecting the block state at all. Then many will get further ruled out after the first octave. The other difference compared to Vanilla MC is that 16 octaves was more than necessary. Only 4 or 5 octaves were really needed.

See code example: https://github.com/KdotJPG/Simply-Improved-Terrain/blob/af61d86022d48fd32fddbe05e87aabaffdc591b8/src/main/java/jpg/k/simplyimprovedterrain/world/gen/NoiseChunkGeneratorImproved.java#L403

The example at the link demonstrates this concept as adapted to Vanilla's terrain generation formula. It would be a simpler case to apply it to a single set of summed noise octaves.

Trilerp (Vanilla MC) image

No trilerp. I used a bi-spline for Vanilla biome grid interpolation because I had to interpolate it somehow, but the actual terrain is full-resolution noise. image

Hopson97 commented 4 years ago

Hello,

I see what what you mean, there are very obvious boxy parts on the "Trilerp" terrain that would ruin the aesthetics.

I will defintily be taking a look at the links posted here, and see what I can do based on what you have explained here.

Thanks!

(Shown to people on the Discord server too, they agree the trilerp is pretty bad compared to the spline)

KdotJPG commented 4 years ago

Sure.

I should clarify that the second image isn't a spline per se. The biome borders (including rivers) use a spline, because I adapted this to Vanilla MC's 4x4-spaced biome generation grid. Within the biomes, it's full-resolution 3D noise.

Either way, feel free to hit me up for pointers on the code I linked, or anything about noise generation in general. Happy to help in whatever ways. I'm K.jpg on your discord.