Geek asks and answers

Discrete fluid “fill” algorithm for height map

I am looking for an algorithm that describes the transient behavior of a fluid as it spreads over the surface of a height map. My initial conditions at t = 0:

  • Two-dimensional matrix of values ​​of height (H) of size [x, y]
  • Two-dimensional matrix of liquid height (F) values ​​of size [x, y]
  • The metric of the area of ​​each point in the matrix (a), that is, each place is 1 cm ^ 2
  • The viscosity value for the liquid (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 fluid volume at a given point via v = a * (F (x, y ) - H (x, y)). The desirable properties of this algorithm would be:

  • There is no need to consider the “slope” or “shape” of the top or bottom of the liquid column at each point. those. he can consider each value in hieghtmap as a description of 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 “leak” (ie a very low point on the height map) occurs, fluid from all parts of the map can be affected when it reaches for it.

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

  • 5x5 DEM matrix, where all values ​​are 0
  • The matrix of the map is 5x5 in height, where all values ​​are 0, except [2, 2], which is 10.
  • Area per point 1 m ^ 2
  • Viscosity u

"" , 5 × 5 . 10/25 , , .

, , , , , . - - , , , .

+5
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

-

( ):

get a cell 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

( ):

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 .

+5

More articles:


All Articles