Implement water flow analysis

[mariuszhermansdorfer]

Start brainstorming about how to best approach water flow analysis on the mesh.

Inspiration and another one

[mariuszhermansdorfer]

Possibly use the flow accumulation algorithm described in this paper: http://skl.iswc.cas.cn/zhxw/xslw/201811/P020181116568187439544.pdf

[mariuszhermansdorfer]

Experiment with cellular automata: http://www.jgallant.com/2d-liquid-simulator-with-cellular-automaton-in-unity/

[BarusXXX]

Hi Mariusz, you can assign me this. I will work with dummy data since I do not have a kinectv2 to test the setup with.

[mariuszhermansdorfer]

Perfect! In the master branch there is a MockMesh class, which we use for benchmarking without having to fire up Rhino and plugging in the Kinect. You might want to use this to generate your data.

[mariuszhermansdorfer]

this thread on Rhino forums is somewhat related and might serve as inspiration.

Other than the actual logic on how to calculate flow direction and accumulation there is a question of morphology. Is our water simulation visualized through changing respective vertex colors of the terrain mesh? Or should we rather draw separate objects such as lines, particles, cellular automata etc. which would represent water flows?

I’d tend towards the latter, since it might give us more flexibility both in the computational logic and in visualization.

[mariuszhermansdorfer]

@BarusXXX, check out this PR #34 and the comments we posted there. I wrote a D8 approach, which takes only 2 ms to run on the whole array. I agree with you that this shouldn't be recalculated for the water flow part. While we are at it, maybe we should create a flow direction matrix for your water flow part?

Here is a good explanation of what I mean. Then each particle would only lookup the direction of flow in the flow direction matrix and grow in this direction. Sort of like the old Nokia snake did.

[BarusXXX]

Implemented a D8 runoff method. b9022ba07fe728579ff5e79b5692f194c6499099

• Currently the outer edge is assumed to be an absolute water drain.

• There are some white artefacts that seem to occur in a regular pattern.

• [ ] It would be cool to implement perlin/simplex noise generated clouds alongside a regular grid.

• [ ] @philipbelesky flowlines could be implimented somewhat similar as pixel trails rather than geometry. If we wanted to be able to bake flow line geometry, could we have a little method that draws flowlines from a pixel array when a radio button is pressed?

[mariuszhermansdorfer]

Thanks @BarusXXX! It's a good start, but since it doesn't produce convincing results just yet, I moved the whole logic to a separate branch: https://github.com/mariuszhermansdorfer/SandWorm/tree/feature/WaterFlow

Let's stick to this for the future as well - each feature gets its own branch and once we're happy with the outcome, we merge them together via PRs. @BarusXXX Agreed!

[BarusXXX]

I didn't realize Pixel Array was inverted wrt elevation, now it works much better, pushed to the WaterFlow Branch.

[BarusXXX]

Tested it in the setup works quite well. Could be improved by using shaders and/or parallelising the execution into parts and using Fourier to bring the parts together.

[mariuszhermansdorfer]

Nice @BarusXXX! Looks much better now! Rather than treating this as another type of analysis, I think we could try and generate a separate water surface mesh. This would allow us to control its transparency and raise individual water cells to the actual flooding level, to better visualize which parts of the terrain would be under water. I have a few ideas on how to approach this and could tinker with your branch next week.

In the meantime I experimented a bit with a polyline-based approach. It has a lot of rough edges still, but the initial take is quite promising. Live in this branch

The general idea is, that with the Rain density slider users define where rain drops should hit. Then each drop follows the steepest gradient downhill and draws a flowline. Right now these drops are not too smart. They first grow and then shrink for 50 frames each but this could be improved. Starting points for these polylines could also be randomized a bit, such that they don't always fall at exactly the same spot.

@BarusXXX, @philipbelesky, do you see value in continuing both approaches (polylines & water flow mesh) or should we just decide on one. I feel, that they kind of give different insights and there is value in keeping both, but would like to hear your opinion.

[mariuszhermansdorfer]

Gaussian blur in the post processing tab helps achieve more meaningful aggregate flowlines:

[BarusXXX]

that with the Rain density slider users define where rain drops should hit. T

@mariuszhermansdorfer Great work! I think both approaches have promise, but for these to be more useful both of them would benefit with a direct way of controlling:

• How much rain is falling in the area.
• Where it is falling, is this a rain event or a large volume flood event from a particular area?
• Less obvious patterning of rainfall, we can look at implementing Perlin/Simplex Noise to deliver a water payload to a desired area without it seeming like a superimposed pattern.

And a direct way of sensing via:

• defining probe points for analysis
• live labelling of the points for direct user feedback

[mariuszhermansdorfer]

Made the polylines smarter. Now, they are randomly distributed across the terrain in a continuous fashion. Kind of like real rain drops would. They traverse the mesh until they get 'stuck' for 5 frames in a row. Then, they start shrinking and eventually get removed. They also can't exceed a certain length. Once reached, they will continue their traverse like a snake without growing or shrinking any more.

This really has to be seen live since a still image doesn't do it too much justice.

The max length parameter is now exposed to users as well:

[BarusXXX]

ndomly distributed across the terrain in a continuous fashion. Kind of like real rain drops would. They traverse the mesh until they get 'stuck' for 5 frames in a row. Then, they start shrinking an

@mariuszhermansdorfer Great work! Are the predominant SW diagonals symptomatic of the concurrent cell by cell execution (without a buffer of the previous state) or is the topography heavily inclined in that direction?

[mariuszhermansdorfer]

Ah, the diagonal SW-NE direction is because I am testing it from home and point the Kinect at a wall with a slight tilt. Thus the resulting flow patterns are very boring, It should look much better with a proper sand model and some interesting topography.

[mariuszhermansdorfer]

Flowlines are multithreaded now. It results in a roughly 2-3x speed up.

Single threaded tons of flowlines: 55ms

Multithreaded same amount of flowlines: 25ms

Overall, with a reasonable amount of flowlines and an average CPU (I'm on a hexa-core 4 year old laptop) one can expect a very interactive experience with consistent 30 FPS:

[philipbelesky]

Looks great! A very hatching-meets-discrete aesthetic.

https://user-images.githubusercontent.com/495961/132116944-6079b150-c071-4aca-819c-ffa04b264562.mp4

[mariuszhermansdorfer]

Moved UI controls to a separate tab for clarity. Changed flow lines color to better match the water surface display:

Now, water surface is shown in blue by default:

[mariuszhermansdorfer]

Merged polyline flow into SandWorm2.0 branch.

[mariuszhermansdorfer]

Ok, I experimented a bit with a mesh-based approach to water flow. The logic is similar to what @BarusXXX proposed in his branch. Rather than simply changing vertex colors, in this case we generate a separate mesh simulating the water surface.

The first attempt is promising but I'm struggling with getting the simulation to progress in a meaningful way. It's not about the speed of execution, which definitely could be improved, but rather the increments between ticks. It takes thousands of iterations to resolve to a more or less steady state.

Here are a few screenshots of the progress:

Initial equal water distribution over the entire terrain:

Some time later:

The logic is fairly straightforward:

1. For each cell, check slopes to each neighbor
2. Starting with the biggest elevation drop distribute water
3. If there is still water left in the cell to distribute, check whether remaining neighbors can accept it

In theory it should converge much faster than what I see on the screen. Any ideas? @philipbelesky, @BarusXXX ?

The code lives in a separate branch, the relevant portion here: https://github.com/mariuszhermansdorfer/SandWorm/blob/0804f30b3ff0b8ce75ad2fed370a60a58bab2916/SandWorm/Analytics/MeshFlow.cs#L87-L126

[BarusXXX]

Ok, I experimented a bit with a mesh-based approach to water flow. The logic is similar to what @BarusXXX proposed in his branch. Rather than simply changing vertex colors, in this case we generate a separate mesh simulating the water surface.

The first attempt is promising but I'm struggling with getting the simulation to progress in a meaningful way. It's not about the speed of execution, which definitely could be improved, but rather the increments between ticks. It takes thousands of iterations to resolve to a more or less steady state.

Here are a few screenshots of the progress:

Initial equal water distribution over the entire terrain:

Some time later:

The logic is fairly straightforward:

1. For each cell, check slopes to each neighbor
2. Starting with the biggest elevation drop distribute water
3. If there is still water left in the cell to distribute, check whether remaining neighbors can accept it

In theory it should converge much faster than what I see on the screen. Any ideas? @philipbelesky, @BarusXXX ?

The code lives in a separate branch, the relevant portion here: https://github.com/mariuszhermansdorfer/SandWorm/blob/0804f30b3ff0b8ce75ad2fed370a60a58bab2916/SandWorm/Analytics/MeshFlow.cs#L87-L126

Hmm you don't seem to be working with buffers to capture the previous state, the direction of traversing the array effects (negatively) the outcome if you work on the same array simultaneously. Removing/Adding water from an adjacent cell and then calculating over that same adjacent cell results in the water head of that cell at a particular instant be erroneous.

Regarding speed we can think of parallelizing the water head calculation of each cell (similar to how you parallelized the slope calculation) to create part calculation of the water flow. Then we use some clever method to convolute the parts to calculate the resulting water head in each cell.

[mariuszhermansdorfer]

@BarusXXX My question is not really about the speed of execution, but more about how many iterations it takes for the simulation to converge.

Why is it that it takes so many ticks for water cells to arrive at the lowest parts of the mesh? Each cell checks whether there is a lower neighbor and if it has surplus water, it pushes it downhill. In theory, this should resolve in a few iterations. Currently it takes multiple thousand ticks to get there.

Use of buffers shouldn't matter because I first distribute rainfall across the whole array and then only push water downhill.

[mariuszhermansdorfer]

Ok, 2 insights so far:

1. Disposal of water on the borders needs to be done in a different way, than suggested here: https://github.com/mariuszhermansdorfer/SandWorm/blob/e34eb62d67282c040d4fe1118be18f7193902050/SandWorm/Analytics/RainDensity.cs#L67-L75 The above code only targets the corner points. I changed it to the following to get correct results: https://github.com/mariuszhermansdorfer/SandWorm/blob/635ec70045254350fb40b00c77a49eae6f403bcd/SandWorm/Analytics/MeshFlow.cs#L44-L55

2. What I am currently doing effectively only allows for disposing of one water cell per iteration. Once a cell is cleared of water, it becomes a sink and has the highest deltaZ to its neighbors. Thus forcing the neighbor to flow into it. Here are some values from one loop:

Cells 0-359 constitute our border and are set to 0. Cell 360 is the current cell

Now, 360 is empty and distributed its water head to the neighbors. Notice, that 359 got some of it.

Next, 361 gets empty, but 360 gets some of its water again.

That's why it takes forever to resolve. At each iteration very few cells actually drain to 0.

@BarusXXX , would your buffer approach solve this?

[mariuszhermansdorfer]

I did some tests with buffering the water head and this also doesn't work well. Imagine the following:

Cell A moves water to cell B. This action is stored in a buffer, but not directly shifted to cell B. Then cell C sees only the old state of cell B and tries to add its water to it. The buffer overflows and we end up with enormous amounts of water piling up very quickly.

@BarusXXX, I believe you haven't seen this issue in your code because you are clamping the color values to a predetermined max, hence it is not directly visible.

[mariuszhermansdorfer]

Ok, I'm finally getting some plausible results. Water mesh calculations are fairly interactive (around 20-30ms) and resolve in a reasonable time. I really like, how water reacts to changes in topography and either ponds or drains from the area. Flat areas still take relatively long to drain, which I'd like to address in the future.

[mariuszhermansdorfer]

Added temporary UI controls to toggle the simulation on/off. Fixed a few minor bugs and the simulation time is around 15ms now.

@philipbelesky, did you have a chance to work on the UI button element? Currently I'm hacking a checkbox to use it as a button, but ideally would like to replace it with a proper UI element.

Combination with flow lines:

[mariuszhermansdorfer]

@philipbelesky, @BarusXXX I used this feature as a playground to experiment with GPU acceleration using ILGPU. It took me a few hours to wrap my head around the basic concepts, but the results are sweet!

CPU multithreaded water flow on a full NFOV mesh: 25-30ms

GPU accelerated flow on the same mesh: 3-5ms

Most of this time is spent on data transfer between memory buffers of the CPU and GPU. Not everything makes sense to be accelerated this way, but I thought you might want to use this trick in some of your future work. For now, it only works with CUDA-enabled devices, but I will add support for Intel/AMD as well.

EDIT: latest commit is attempting to allocate computational resources to NVIDIA cards first. If it doesn't find any, it will resort to either another GPU or a CPU. The chosen device type is printed in Rhino's command line.

[BarusXXX]

in, which I'd like to address in the future.

@mariuszhermansdorfer Great work. Maybe for now you can add some infiltration amount to counteract water taking long to drain from flat areas? (Wouldn't infiltration and evaporation play more of a role in disposing of the water in shallow slope situations in any case?)

Also nice work with leveraging the GPU. Thanks for the heads up, definitely useful.

[mariuszhermansdorfer]

Thanks, @BarusXXX. Yeah, I added basic runoff coefficient implementation, just to get this off the ground. Having done more research, though, shallow water surface flow is a huge rabbit hole. Keeping it short, our D8 approach doesn't account for any momentum (i.e. every tick is recalculated without knowledge of any past velocity vectors). This results in unrealistic flow behavior, where steep areas take longer to drain than shallow ones.

I'm trying to wrap my head around some of the more complex approaches but the math behind it hurts my brain. I'm mostly trying to copy the CN approach described in this paper. I'll start a separate issue, where I'll document my progress and ask for help unpacking it, if you guys want to join.

[BarusXXX]

Thanks, @BarusXXX. Yeah, I added basic runoff coefficient implementation, just to get this off the ground. Having done more research, though, shallow water surface flow is a huge rabbit hole. Keeping it short, our D8 approach doesn't account for any momentum (i.e. every tick is recalculated without knowledge of any past velocity vectors). This results in unrealistic flow behavior, where steep areas take longer to drain than shallow ones.

I'm trying to wrap my head around some of the more complex approaches but the math behind it hurts my brain. I'm mostly trying to copy the CN approach described in this paper. I'll start a separate issue, where I'll document my progress and ask for help unpacking it, if you guys want to join.

Yes, D8 doesn't account for any momentum so flow behavior is unrealistic as you say, but why do steep areas take longer to drain? I was transferring water to adjacent cells apportioned in a ratio of slope (delta water head), this should account for steeper slopes or? Code I am referring to; https://github.com/mariuszhermansdorfer/SandWorm/blob/e34eb62d67282c040d4fe1118be18f7193902050/SandWorm/Analytics/RainDensity.cs#L102-L122

[mariuszhermansdorfer]

Cells push water downhill (in our case, where the water head is lower). They do so independent of each other, so it can happen that more than 1 cells discharge to the same downhill cell. In next iteration, this cell will have a higher water head than it's uphill neighbors who just got rid of their water and will push some of this water back. Effectively making the water flow uphill and not following the momentum of flow.

In short, we create tiny waves, but never let them continue and immediately dissipate their energy (water head) in all directions disregarding their desired direction of flow.

[mariuszhermansdorfer]

Short video showing flowlines in action and early attempts with mesh-based water flow: https://www.youtube.com/watch?v=9mYoyG-Oe-k