Implementing Free-slip Hydraulic Erosion

[stephen-hqxu]

This pull request deems to officially resolve #1.

Free-slip hydraulic erosion is a technique, that allows out-of-chunk-boundary raindrop to "free-slip" to neighbour chunks instead of ending the lifetime early. This significantly improve eroding efficiency of every raindrop and gets the same erosion detail as of previous algorithm with fewer number of erosion iterations.

Approximately 20k iterations now gives same LoD as 80k iterations before.

Main academic reference: Ondˇrej Št’ava, Bedˇrich Beneš, Matthew Brisbin, Jaroslav Kˇrivánek: Interactive Terrain Modeling Using Hydraulic Erosion. In Eurographics/ACM SIGGRAPH Symposium on Computer Animation (2008)

Boundary conditions are implemented using so called ghost cells that contain a copy of their neighbors and act as a free-slip boundary where no water can run out of the simulation domain. However, water movement along the border is not restricted.

Checklist

Main free-slip hydraulic erosion feature

• [x] Implementing global-local index lookup table.
• [x] Rain drop can freely rolled over to neighbour chunks.
• [x] Implementing post erosion edge interpolation lookup table.

Releated improvements addressed in this release

• [x] Erosion brush radii and indices are readjusted for free-slip logic.
• [x] Flag heightfield generator so heightmap generation and erosion can be separated.
• [x] Evolve multithread and memory model for better neighbour synchronisation.
• [x] Merge heightmap and normalmap rendering buffer into a single texture and remove dedicated storage for normalmap.
• [x] Batch all format operations into one kernel to reduce program complexity.
• [x] Checkers to avoid reloading rendering buffer every frame.
• [x] Cache repeated global memory accesses with shared memory.
• [x] Terrain model is seamless.
• [x] Effectively disable free-slip hydraulic erosion.
• [x] Other misc improvements discussed in #1 and release notes for v0.3.0-preview.x.
• ~Normalmap is seamless.~

[stephen-hqxu]

How it works

The main idea is requesting all adjacent chunks of the current chunk we are working on, make a copy of them and combine all chunks into a large texture, erode them as usual, break the large texture back to chunks and finally store them back.

Data safety is guaranteed. Chunks have been copied must not be used by any other threads until they are returned and released, it can be achieved by a simple lock.

There are 2 main technical difficulties:

1. When combining all neighbour chunks into a large texture, the index used to reference this texture is different from the one used when they are separate. In other words, this is the difference between first index in chunk i = last index in chunk (i-1) + 1 and first index in chunk i = 0.
2. Prior to erosion, heightmap generator deliberately offsets index by 1 to make sure the value at the edge of this chunk is the same as the adjacent's, so two disconnected meshes don't leave any seam. Yet after erosion it's no longer guaranteed, we need to manually normalise the pixel at the edge to align them such that the terrain becomes seamless. How to interpolation edges for the best performance is challenging.

A brief comparison

Figure 1: Showed erosion

• Old model: High frequency simplex noise "spike" artifact can be seen around the edge, due to the fact that raindrops are deleted when they flow out of bound, such that edge areas are eroded less often than others. A thick border "stripe" can be seen.
• New model: Erosion marks are smoother and more evenly distributed towards the flow direction. Chunk border is more continuous.

Figure 2: Showed deposition

• Old model: Area around the edge is shape, since out-of-bound raindrop may still carry some amount of sediment, and it's no able to deposite sediment to fill in uneven surface.
• New model: Spikes are flattened by deposition.