Discrete fluid "filling" algorithm for a height map

Question

I am looking for an algorithm that will describe the transient behaviour of a fluid as it spreads across the surface of a height map. My starting conditions at t=0 are:

• A 2D matrix of height values (H) of size [x, y]
• A 2D matrix of fluid height values (F) of size [x, y]
• A metric of the area of each point in the matrix (a), i.e. each location is 1 cm^2
• A viscosity value for the fluid (u)

What I want is an algorithm that can calculate a new value for the fluid height matrix F at t'=t+1. At any point I could calculate the volume of fluid at a given point by v = a * (F(x,y) - H(x, y)). Desirable properties of this algorithm would be:

• It does not need to consider the "slope" or "shape" of the top or bottom of the fluid column at each point. i.e. it can consider each value in the hieghtmap as describing a flat square of a certain height, and each value of the fluid height map as a rectangular column of water with a flat top
• If a "drain" (i.e. a very low point in the height map) is encountered, fluid from all parts of the map may be affected as it is pulled towards it.

A simple example of what I'm looking for would be this:

• A 5x5 height map matrix where all values are 0
• A 5x5 fluid height map matrix where all values are 0 except [2, 2], which is 10.
• An area per point of 1 m^2
• A viscosity of u

The algorithm would describe the "column" of fluid spreading out over the 5x5 matrix over several time steps. Eventually the algorithm would settle at a uniform height of 10/25 in all locations, but I'm really interested in what happens in between.

I have attempted to search for this kind of algorithm, but all I can find are equations that describe the behaviour of particles inside of a fluid, which is too granular for my purposes. Does anyone know of any good sources I could reference for this problem, or an existing algorithm that might serve my needs.

Answer 1

O is your starting fluid-column
o are diffusing columns
************************
X  X  X  X  X

X  X  X  X  X

X  X  O  X  X

X  X  X  X  X

X  X  X  X  X  
************************
--Get the Laplacian of the heights of each neighbour and accumulate results
in a separate matrix
--Then apply the second matrix into first one to do synchronous diffusion
--go to Laplacian step again and again


************************
X  X  X  X  X

X  X  o  X  X

X  o  O  o  X

X  X  o  X  X

X  X  X  X  X  
************************


************************
X  X  .  X  X

X  .  o  .  X

.  o  O  o  .

X  .  o  .  X

X  X  .  X  X  
************************
************************
X  X  .  X  X

X  o  o  o  X

.  o  o  o  .

X  o  o  o  X

X  X  .  X  X  
************************


************************
X  X  .  X  X

X  o  o  o  X

.  o  o  o  .

X  o  o  o  X

X  X  .  X  X  
************************

************************
X  .  o  .  X

.  o  o  o  .

o  o  o  o  o

.  o  o  o  .

X  .  o  .  X  
************************
************************
.  .  .  .  .

.  o  o  o  .

.  o  o  o  .

.  o  o  o  .

.  .  .  .  .  
************************
************************
.  .  .  .  .

.  .  .  .  .

.  .  o  .  .

.  .  .  .  .

.  .  .  .  .  
************************
************************
.  .  .  .  .

.  .  .  .  .

.  .  .  .  .

.  .  .  .  .

.  .  .  .  .  
************************
sorry for very low height-resolution

Laplacian

Laplacian's place in diffusion

Diffusion's place in Navier-Stokes equations

Discrete Laplace Operator

Simple algorithm (in pseudo):

get a cell's value in a.
get neighbour cells' values in b(sum of them)
put b/4.0 in c(getting 4 cells' values)
add a to c
build a matrix with this algorithm
apply the matrix onto old one
goto step 1

Harder algorithm (in pseudo):

apply discrete-Laplacian-operator on all neighbours(finite-differences thing)
put solution in c height-map
subtract or add c to/from starting height-map
goto step 1

Jos Stam's fluid-solver has a similar thing for the diffusion part.