Hydraulic erosion between chunks

[stephen-hqxu]

Current state

• Random raindrop is spawned within the chunk.
• Raindrop is descending until it has evaporated or it flows over the edge.

Bug caused

• Some raindrop exits their lives much earlier than normal, causing the terrain to be eroded unevenly.

Suggestions

• Sync the raindrop to the next chunk when it flows.

Possible implementation

• Make a copy of all neighboring chunks and send all of them to computation.
• It requires some more works on synchronisation, other threads can't use the chunk that has been copied and hasn't returned.

[stephen-hqxu]

Hydraulic erosion between chunks is definitely not something easy to implement. In the future we will refer it as free-slip hydraulic erosion.

Here's some dev notes.

General approach

When rendered chunks are requested to be loaded, all visible chunks are checked for completeness. If not, for each of those chunks, the program will also check for its surrounded chunks. If any of the surrounded chunk is not found, it will be inserted and computed for heightmap. Whenever it's computable, all neighbour chunks are locked such that no other threads can copy them until it's released, and make a copy of all heightmaps, sent to device.

For all chunks, the simulator will only spawn rain drop at the center chunk, while the neighbour chunks will hold rain drop that flows out of the boundary of the central chunk.

For simplicity, central chunk is contained in neighbour chunks

Global-Local index table

When we copy neighbour chunks, chunks are aligned linearly, called local index, where the index of the next free-slip chunk starts at the end-index of the previous chunk+1. When chunks are eroded, the rain drop system uses global index system, where index is continuous within a row of a free-slip range, such that the index of the first element of each row of the chunk is the index of the left-hand side element+1.

For more information please refer to the documentation in the source code.

Instead of arranging the chunk into global index system, we use some math formula to convert the index during erosion. To make things more efficient, we pre-compute a lookup table for such index.

What's going on?

Currently we can confirm that water droplet can freely slip to the neighbour chunks. There are a few bugs in the current release, and possible solution for each.

• Sometimes chunks are funky looking, feels more like the heightmap is not generated and some garbage memory data is rendered. It's due to the fact that newly created chunk is not locked before dispatching heightmap compute.
• Seam can be seen between chunks, due to the fact that erosion change the height value of the map. To align them back, a simple approach is to make the edge value equals to each other.
• Erosion brush generation should take free slip range instead of map size.
• We notice that seam exists even with the post-erosion edge correction. It's caused by the fact that we only update the original 32-bit heightmap, but for the formatted 16-bit map it's untouched when chunk is not a center chunk. To solve this we need to update normal map and formatted map for every neighbour after each erosion of the central chunk.

[stephen-hqxu]

Some more suggestions

• Merge heightmap with normalmap. Currently the alpha channel in normalmap is not used. Consider moving red channel in heightmap to alpha channel in normalmap, which can cutdown memory usage and make formatting easier.
• Cut down memory copy. Use mask with heightmap. Performing erosion right after heightmap is generated. To generate chunk that doesn't have heightmap only, set the mask = 1; otherwise mask = 0.
• Format all chunk maps in one kernel launch instead of copying the result back to the host and then copy back to device and do the formatting one kernel launch by one. Provide a list of pointers to formatted maps similar to heightmap.

[stephen-hqxu]

We introduced a new algorithm for generating an interpolation table instead of using the previous interpolation method which used a plenty of branches to check for areas required for interpolation.

Official release will go live soon, hopefully. We are still working on host side codes to ensure data coherence.

Interpolation index lookup table.

The lookup table uses thread ID as index, and lookup for the coordinate (x,z) for required for interpolation. Compared to out old brute-force search method, it not only cuts down the number thread required for such operation, but also utilises all threads.

Checklist Item	Brach Checking (Old)	Specialised Table (New)
Type	Conditionals	Mathmatical formulae
Number of thread lauched	freeslip^2 * dimension^2	(dimension - 2) (2 freeslip * (freeslip - 1)) + (freeslip - 1)^2
Thread utilisation	~1% depends on freeslip and dimension, smaller utilisation when both are greater	Always 100%
Data security	Required even more branches to make sure threads don't cross over to other working areas	Interpolation areas are predefined in the table and only simple branches are needed to distribute working threads

The old algorithm:

if (pixel_requiring_interpolation) {
   perform_interpolation();

} else {
   return;
   // Threads that are not in the interpolation pixel will be killed
}

void perform_interpolation(float* maps) {
   // A lot of braches to determine how to do interpolation...
}

How does the table works

We classify interpolation into 3 types:

• Edge interpolation
  • Column edge interpolation: Interpolation patch has size of 2 * (dimension - 2)
  • Row edge interpolation: Interpolation patch has size of (dimension - 2) * 2
• Corner interpolation: Interpolation patch has size of (dimension - 2)^2

Patch will not cross over to other patch nor the edge of the freeslip map so the current freeslip chunks can still connect to adjacent area that are not presented. Bits are inserted into the MSB of (x,z) coordinate of the interpolation pixel, and we use combination of both bits to determine what type of interpolation it's, and three simple branches are used for each type.

For more information please refer to the documentation within source code