Author Topic: How does the erosion in WM work behind-the-scenes?  (Read 4381 times)

0 Members and 1 Guest are viewing this topic.

csp256

  • World Machine Veteran
  • ***
  • Posts: 19
    • View Profile
How does the erosion in WM work behind-the-scenes?
« on: October 21, 2014, 05:24:55 PM »
Remnant, I sent you a private message but you never responded. Maybe you will see this? :)



I am moving forward with expanding my previous efforts to simulate low-gradient fluvial erosion (river meanders, billabongs, etc). I think I have figured out a way to alter my previous fluid simulation to capture the relevant dynamics. I am participating in a 48 hour competition this weekend and will be working on this problem.

I've poured over the relevant literature and found no other attempts to simulate these sorts of processes from a computer graphics stand point (all other attempts were computationally prohibitive, merely generated passable fakes, focused on different time or spatial scales, or were similarly unsuitable), but admitably I was not looking at high-gradient, particle based simulations. However, I would like my technique to play-nice with the erosion in World Machine (which obviously does a very good job on more mountainous terrain), and it could help to know more about how WM does it.

Does anyone have any references to literature which describes how these sorts of operations are performed? Or is it more of a trade secret? I'd really like to show these two erosion techniques working together in concert on a single terrain, if possible.

WFab

  • World Machine Guru
  • ****
  • Posts: 361
    • View Profile
    • Blog
Re: How does the erosion in WM work behind-the-scenes?
« Reply #1 on: October 22, 2014, 01:07:28 AM »
I've been waiting for your next post, to see if you went forward with your idea or not. Patience well rewarded I'll say!  :D

Hotshot

  • World Machine Guru
  • ****
  • Posts: 237
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #2 on: October 22, 2014, 05:20:11 AM »
Can it also be applied on Lava?

csp256

  • World Machine Veteran
  • ***
  • Posts: 19
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #3 on: October 22, 2014, 09:25:08 AM »
Lava? There is no way to know. Probably? If it works at all, it should work for that as well.

Let me publicly collect my thoughts. Maybe there is interest, or suggestions...

What I am going to attempt has several problems. First, the model I have implemented is for two dimensional fluids: this implies infinite depth, not infinite shallowness. Second, it is only physically accurate for microscopic scales. Third, the simulation blows up if there are high ratios between fluid densities (areas with lots of fluid, and areas with very little fluid).

Thankfully, the fluid depth should not change things too much, because I am only intending this to work under constrained conditions, and fluid depth matters less in those conditions. And we do not really care about physical accuracy, just something that looks believable that can be quickly, iteratively tweaked by an artist.

The density ratio thing is a real problem though. In this model, every cell (pixel on the heightmap) has 9 numbers associated with it, that add up to about 1. This sum represents how much total fluid there is in that cell. There is one number representing how much fluid goes into each neighboring cell (including how much fluid stays in that cell). All of these numbers are then transmitted to the neighboring cells. Each cell then updates its numbers (think of it like moving them towards a weighted average).

The problem is if one neighbor gives you a value of 10,000 and another gives you 0.0001... the update rule simply breaks. There are ways of improving this, which rely on physical theory I don't understand, but I think I can fake it. Here are some of the not-physically-accurate alterations I intend to try:

1: I will keep the simulation stable by treating the fluid density & speed differently in different contexts. The fluid update rule will see the "real" value of the fluid, but the erosion algorithm will see a (possibly nonlinear) function of that. This is to say that a cell which has a total sum of 0.8 might be treated as having no or almost no fluid in it for purposes of the erosion algorithm. A cell with 1.2 might be considered more like a lake. You can imagine that if you were to threshold the flow in this video ( https://www.youtube.com/watch?v=TkiSO3uzs48&list=PLXpzskMR1uFv51vp2FVP4KRTec9akvE8F ) that you would see river-like structures.

2: I will add a sponge layer. This slows down the computation, slightly, and uses slightly more memory, but it makes it so that fluid flows off the edge of the map with much less bounce-back. It does this by adding extra cells on the side of the simulation where the laws of physics change the further off the simulation you go. If you watch the videos I posted ( https://www.youtube.com/watch?v=3zH_zYwwdTk&index=5&list=PLXpzskMR1uFv51vp2FVP4KRTec9akvE8F ) you will notice that there is an initial shockwave, and it bounces off the side of the simulation. The shockwave was because I was lazy, and the bounceback was because I did not use a sponge layer. Neither will happen now.

3: Any regions of excessively high (or low) density fluid built up in the sponge layer will be (gently) exponentially damped. This means that excess fluid will be created or removed off the sides of the sides of the simulation as necessary to keep things stable.

4: The height of the terrain in the sponge layer is antisymmetric to the terrain perpendicular to it. That is to say, that as you move the last few pixels to the boundary you see altitudes of 108, 104, 101, 100 then the sponge layer will take on values of 99, 96, and 92.

5: I will not rely on boundaries to induce flow. I will cause flow by either (A) adding a force dependent upon the slope of the terrain at that point or (B) causing some particles to bounce back from neighboring cells that are different heights. That is, if you are at a cell/pixel of altitude 100, and you try to send some fluid to a cell of altitude 105, then some of that fluid will bounce back, and some will spill over. If you try to send very little fluid, all of it will bounce back. If you try to send fluid to a cell of altitude 95, then all of it will flow into that cell.

6: Every time fluid flows into a cell or bounces back, it erodes that cell slightly. All sediment is evenly mixed in a cell. Bounce back causes more erosion than flow. I expect to use some nonlinearity here: flow that is twice as strong is more than twice as erosive. This might be exacerbated explicitly by calculating the rotation (curl) and explicitly eroding more on one side of the map.

7: Sediment is deposited... according to some rule I have not decided on yet. Let me know if you can think of a good one. The easiest way is to have some percentage be deposited every time step.

8: I will output maps of fluid density, erosion, deposition, velocity (and maybe rotation) in addition to the heightmap itself.

9: It will take inputs of a heightmap and a precipitation map (which represents how much fluid is deposited into every cell). I will assume the precipitation map is constant valued for now: every cell gets the same rain. I could foresee more complicated inputs being possible, but I am not in a rush to implement them.

10: I do not know how I will solve the problem of mountain-tops. These areas could naturally develop fluid densities of 0, as all the fluid would flow away and little if any would return from downhill. I anticipate that the easiest thing to do will be to add a constant amount of fluid to every cell every time step, and then multiply every density by a number a little less than 1. (or decreasing it as a function of how much more than 1 it is) This should prevent any cell from getting values too big, or values too small.

Let me be very clear: I do not know if this is going to work, and I am only attempting to alter this one model because it just happens to be the one simple fluid dynamics algorithm I know. This is just an outline of my idea. There is certainly a more clever way to approach this, but I do not know what that is.

Now that I think about it, I can imagine a way to simulate a lava source... that would be interesting.
« Last Edit: October 22, 2014, 09:27:31 AM by csp256 »

Remnant

  • Author
  • World Machine Guru
  • *****
  • Posts: 2311
    • View Profile
    • http://www.world-machine.com/
Re: How does the erosion in WM work behind-the-scenes?
« Reply #4 on: October 22, 2014, 04:07:41 PM »
Hi,

very cool work -- I'm excited to see what you can cook up.

Unfortunately, I don't know much in the way of any existing research to help you with -- as you said, the field is a mix of unsolved problems, computationally insane solutions, and hacks. Which is frustrating but also means there's fertile ground for actual new results!
-- Stephen Schmitt
- Creator of World Machine

csp256

  • World Machine Veteran
  • ***
  • Posts: 19
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #5 on: October 24, 2014, 11:54:34 AM »
The hackathon has started. First feature: sponge layers!

https://www.youtube.com/watch?v=eD5NJ4gAV2U&feature=youtu.be

For unknown reasons, there is some anisotropy in the simulation (it doesnt treat all directions the same). I am working on it... I will update this thread with my progress.

Hotshot

  • World Machine Guru
  • ****
  • Posts: 237
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #6 on: October 24, 2014, 12:49:25 PM »
Will it be a 2D plane flow map (2D Vector Field)? or 3D?
what about flowmaps?
https://www.dropbox.com/s/56ln2zarlqfq8e4/Water%20Flow%20For%20UDK.pdf?dl=0

csp256

  • World Machine Veteran
  • ***
  • Posts: 19
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #7 on: October 24, 2014, 01:13:57 PM »
Pure 2d. Ive tried hard to stay away from 3d.

As stated in a previous post, outputs will be density, velocity, deposition, erosion, and the heightmap itself.

Velocity implies directionality in addition to speed.

I'm not sure what you are trying to show me with that link.

I have a race condition somewhere. :(

EDIT: I had n>1 race conditions, and now I have n-1 race conditions.

https://www.youtube.com/watch?v=6rxxSv114_g&feature=youtu.be
« Last Edit: October 24, 2014, 03:00:21 PM by csp256 »

Tangled-Universe

  • World Machine Guru
  • ****
  • Posts: 66
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #8 on: November 02, 2014, 07:54:56 AM »
Hi Chris,

I have no idea at what stage you are, but here is a paper showing principle methods of fluvial erosion and thermal erosion.
http://www.cescg.org/CESCG-2011/papers/TUBudapest-Jako-Balazs.pdf
It's for GPU based applications, but the principle/math behind it is similar I suppose.

For the "bounce back" effects you describe; they sound like "shear stress" and there's quite some research done on this phenomena and a search for "shear stress river (flow)" gives results, but they may not meet your requirements. That's too technical for me to judge.

Regarding the issue with fluid density values going awry, and I may not be understanding this thing at all, but isn't it possible to release fluid based on the fluid vector? Hard to explain what I'm thinking, but it's like clamping of fluid input if the fluid vector is decreasing (fluid buildup).
The paper I posted above uses a similar cell approach (I think) so may contain pointers for you on how to approach this.

Frankly, by looking at the list of your thoughts, I think you'll need to start a bit more simpler/basic and iterate from there? However, I don't know your talent and intellect of course :) It sounds a bit too ambitious to me to achieve "at once" if you see what I mean :)
Following your posts with interest, so I'm looking forward to see/hear more!

Cheers,
Martin

TJTAS

  • Community Member
  • **
  • Posts: 4
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #9 on: November 09, 2014, 05:17:34 PM »
Do your cells have a velocity value?. That could be used for deposition with the value deposited being the inverse of the velocity(normalized).

csp256

  • World Machine Veteran
  • ***
  • Posts: 19
    • View Profile
Re: How does the erosion in WM work behind-the-scenes?
« Reply #10 on: November 16, 2014, 10:24:27 AM »
I had to drop it until the end of the semester. It is one of three-four projects I will be working on this winter break (beginning 1 month from two days ago).

Yes, I have (or rather, trivially calculate) a velocity vector. I also recover density and speed values. It makes no sense for deposition rates per cell to be the inverse of velocity. The most sensible thing is to be proportional to dissolved sediment density. There should probably be a term which is a function of both fluid depth and flow magnitude, though.

That paper looks very relevant. Thank you for linking it to me! That paper and its references should prove useful. That paper's methods are going to have problems capturing the specific dynamics I want because you can not properly capture the curl (rotation) of fluids with a 4 point stencil (but this is something that should be easy to fix).

Yes, the no-slip bounce-back conditions are approximately correct for rough stone... in the microscopic limit. It is probably more correct to use a slip boundary condition in this case.

I don't know what you meant about the fluid vector. You are probably misunderstanding something. If possible, try to differentiate between a vector and a vector field when necessary.

Only two of the topics I discussed are properly difficult: numerical stability and the erosion algorithm. One is solvable, and the other one is a matter of "faking it until you make it". The others I either did or will be trivial.

I think I will investigate direct shallow fluid solutions. A friend of mine has a shallow fluid simulator that I should be able to adapt.

I am going to abandon the GPU aspect for now and do prototyping on the CPU. Faster development times are key for me right now. Again, everything is on hold until the end of the semester.