Monday, April 25, 2022

VRAGE: Volumetric Water

 SUMMARY:

  • Research on our new VRAGE 3 engine has started
  • VRAGE Water
    • Planetary scale (or small pond)
    • Volumetric 3D (no 2D plane or height field)
    • Flow simulation, arbitrary gravity
    • Buoyancy, pressure, surface tension and more
  • Overview of existing technologies 
  • Examples of work-in-progress experiments & next steps


Guest post by Petr Minařík, Senior Lead Programmer at Keen Software House

Hello, Engineers!

VRAGE™ is an in-house game engine developed by Keen Software House. VRAGE stands for “volumetric rage” and/or “voxel rage”.

VRAGE’s core feature is volumetricity within the environment. Volumetric objects are structures composed from block-like modules interlocked in a grid.

Volumetric objects behave like real physical objects with mass, inertia and velocity. Individual modules have real volume and storage capacity and can be assembled, disassembled, deformed and destroyed.

For our next generation of the VRAGE engine (VRAGE 3.0) we have started research of water and its simulation. Our expectation is that water will become a major part of available gameplay features in our future games. Our current research goal is to support the realistic behavior of volumetric water, while maintaining good performance and visual quality.

For a more detailed look at our research on VRAGE “Volumetric Water”, please watch the video below:


Feature requirements

Any kind of simplification like plane or sphere approximation is a no go for us. Any simplification like that reduces player possibilities of interactivity.

Volumetric water must be simulated with all possible natural phenomena, on planetary scale, creating flows like rivers and waterfalls, all while still being interactive and allowing players to to fully interact with and manipulate it.

These are the features we consider as a top priority:

  • Volumetricity - fully 3D simulation, no 2D planes or height fields
  • Flow simulation - with an arbitrary gravity, throughput based on hole size, mass conservation
  • Buoyancy - Archimedes principle, hole detection, ship sailing
  • Scale - from a small pond to a water planet
  • Pressure - level equalization, high hydrostatic pressure at high depths
  • Surface tension - water creates globules in zero gravity

There are many features we might consider, like air pressure simulation, inner flows, vortices, viscosity, water color, gas / air tightness, lava, acids, moving sands, siphoning, AI simulation, and many others.

Existing technologies

There are basically two main approaches used for liquid/fluid simulation. Both of them attempt to simulate water based on famous Navier-Stokes equations describing flow of incompressible liquids.

Smoothed particle hydrodynamics (SPH)

Based on simulation of a high amount of small particles. By their interaction with each other the effect of flowing liquid is created.

Source: Github - SPlisHSPlasH

Pros:
  • Physical behavior (velocity, gravity, collisions)
  • Realistic visuals
  • Lots of existing GPU implementations
  • Better suited for exact simulations

Cons:
  • Computationally extensive
  • Unstable - more sensitive attributes
  • Difficult to scale
  • Surface tracking



Cellular automatas (CA)

Grid based simulation where there is a mass and physical properties in every cell. Every cell interacts with its direct neighbors and this creates the effect of a “flow”. 

Source:.jgallant - 2d-liquid-simulator-with-cellular-automaton-in-unity

Pros:
  • Fast & simple, stable
  • Easy to parallelize
  • Already used in games (Minecraft, Ylands)

Cons:
  • Axis aligned - Water surface & vertical gravity immutable
  • Sand like issues - “Water piling”
  • Complicated collisions with dynamic objects


Combinations of particle and grid based approach

Unfortunately, all the above research tends to simulate either fast limited fluids, or slow high-quality simulations. Although they look great, they focus on offline rendering (movies, static images) and a limited scale of simulation (basins, aquariums). Large scale simulations are simulated with approximation approaches like height cells or shallow water simulation. 
  • PIC - Particle in cell
  • FLIP - Fluid implicit particle
  • MAC - Marker and cell grid
  • MLS MPM - Moving Least Squares Material Point Method
Source: Redsharknews

Source: UCLA Mathematics

VRAGE Water - Our solution

We would like to present you our solution, which is based on ongoing research and prototypes we have created. It is far from a final implementation but it already contains some expected behavior and it is even fun to play with.

Combination of particle and grid based approach

We use Center of mass (COM) in every cell, which can also be seen as one particle per cell. These are main properties of our system:
  • Grid based simulation
  • Velocity introduced to the cells to increase realism
  • Center of mass (COM) introduced to avoid unwanted diffusion
  • Compatible with voxel approach used in current VRAGE engine 

Every cell has these physical properties:
  • Mass
  • Velocity (calculated from forces)
  • Center of mass (COM)
We found this technique to be so far the great compromise between features we need and a performance of the algorithm.

Example: Cells with indicated center of mass and velocity

Fluid simulation forced to behave as liquid

These principles are similar to those used in fluid simulation. We use proper forces to keep the “fluid” liquid and simulate water behaviors.
  • Gravity + tension forces can keep the fluid in a liquid state
  • Pressure forces adjust water compression (Water Pressure)
  • Surface tension to create nice globules
  • Constant expansion/diffusion. If not limited, liquid can spread around.
  • No maximum mass cell limit

To be able to correctly simulate surface equalization with pressure, we had to make our water compressible. That means the deeper the cell is, more water is stored in the cell.

Basic algorithm steps

First cell velocities are calculated from forces applied to cells. Then an advection step is executed where diffusion for every cell is applied. After these calculations, new values are copied to the content buffer.


VRAGE Water - Forces

To simulate the basic natural phenomenons we use these forces:
  • Gravity 
  • Pressure
  • Surface tension
There is an indefinite amount of other forces possible, like friction/viscosity, thruster forces, wind, pumps, turbines.. Each of them adds more immersivity and natural behavior to the water, on the other hand it increases the performance cost of the algorithm.

Example: Interaction with mouse cursor - attracting and distracting force

Gravity

Gravity is a point centric force with different direction per cell. We need to consider all special cases which can appear in our games, thus our requirements for gravity are very similar to natural force.
  • Gravity is dynamic and is different at different positions in the world
  • It is non-linear and not aligned to any axis
  • There can be no gravity at all
  • Gravity center can be inside of a water pool
Example: Water follows gravity center and creates a globule around it

Example: Velocities aligned along gravity force

Pressure

Pressure force determines water volume distribution, it tries to keep the amount of water in every cell the same. The result of this force is that water is not squeezed into several cells and it fills empty spaces much quicker, including situations like U-bend etc.
  • Pressure distributes liquid in cells to keep same threshold
  • Pressure helps liquid to get into places where water should naturally flow
  • If there is no pressure, all water is compressed into several cells
  • This force is not a hydrostatic pressure
  • Air pressure is not considered
  • Our water is compressible
    • + it gets to proper level very fast
    • - it takes a huge amount of water in depth
Example: Water equalization in an U-bend

Surface tension

Surface tension is a force pushing against the water surface to keep the water in the globule shape. This effect is the most visible in zero gravity, where it creates nice dynamic blobs.

Source: NASA

With surface tension the behavior can sometimes also mimic water blobs on the window glass.

Example: Surface tension creating globules in zero gravity

Example: Velocities aligned to surface tension force

VRAGE Water - Diffusion

Thanks to grid based algorithm it is very easy to find neighbors to every cell. Every iteration the water is spread to these neighbors by an amount given by diffusion radius. With diffusion we can easily simulate phenomenons like mist, steam or gas. The principles of diffusion are:

4 Directions (Up, Down, Left, Right)
If not limited, water always evaporates into mist
Expansion only to direct neighbors
Amount is determined by diffusion radius

Example: Diffusion with no velocity

The spread area center is given by COM and the cell velocity, where COM is the start of the vector and the end of the vector is the center of diffusion area.

Example: Diffusion with velocity

Example: Water drop expands to empty area, as no forces are applied

VRAGE Water - Work in progress

All presented content is work in progress and subject to change. Currently our goal is to scale up water simulation to planetary level. For the prototype we use accelerated octree structure for solids and manual level of details (LOD) for the water.

Example: Comparison scale on planetary level

Example: Manula water LOD switching

During the development there are also some unexpected situations where you introduce not planned behavior. Check out the most interesting ones!

Example: Viscous water - lava, honey, melted iron...

Example: Boiling water

VRAGE Water - Next steps

We continue improving large scale water simulation, which includes more sophisticated methods of LOD switching, arbitrary grid resolution etc. It is possible to combine more water optimization techniques together. Next priorities for us are:
  • Lodding, large scale simulation, concealment
  • Surface generation / marching cubes
  • Buoyancy
  • Moving to 3D space

Follow our social media to get the latest news!

We are always impressed by the innovation of our modding community! We would like to thank the Space Engineers community for continuing to inspire us through their ideas, suggestions, and hard work.

Hiring

If you’re interested in working on awesome games like Space Engineers, we’d love to hear from you!
Check out the open positions at Keen Software House and don’t forget to send us your English CV/resume and cover letter.

Remote collaboration is possible!

Our team is global.

Finding the best candidates to join Keen Software House means exploring every possible solution, including remote work. While we strive to provide team members with the best possible work-life balance here in Prague at our incredible Oranzerie offices, we understand that it is not always possible to transition, therefore we are very remote friendly. Here’s a map of where our teammates live.

 

Thank you for reading this blog!


Best,
Petr Minařík
Lead Programmer at Keen Software House


For more news:
Vrage Engine: www.keenswh.com/vrage/
Space Engineers: www.SpaceEngineersGame.com
Keen Software House: www.keenswh.com
Medieval Engineers: www.MedievalEngineers.com
GoodAI: www.GoodAI.com
General AI Challenge: www.General-AI-Challenge.org


Personal bio:

Petr Minařík is lead programmer at Keen Software House, an independent game development studio best known for its best-seller Space Engineers (over 4 million copies sold). Petr is a former leader of the team who successfully developed and released Space Engineers, and who developed the most important parts of its codebase.
 
Petr has been interested in programming since his childhood, when he earned money by gathering old paper and bought Didaktik Gama, national clone of ZX Spectrum. He spent three years in 2K Czech working on Mafia 2 at various programming positions until the game was released. Then he started to work in Keen Software House with Marek Rosa on his game Miner Wars and during the last 11 years he has helped make Space Engineers unforgettable and the company famous. Petr loves solving challenging problems, especially those which everyone says it is impossible to solve.
 
At this time, Petr is working on the next generation of VRAGE engine, focused on liquid and fluid simulation.

16 comments:

  1. This all looks quite intriguing!!

    What's the solution for small holes and LODs? Say the player builds a pump and walks away from it. Now the cells are too large to recognize parts of the pump as holes/viable routes to flow through. What's the solution to this??

    Overall though, this looks incredibly promising and I look forward to seeing what comes of it!!

    ReplyDelete
  2. Hello,
    there is no final decision on this problem yet. We will decide according to user feedback and priorities, so far there are two possible solutions:

    1. If the pump is static (const input and output), then we are able to simulate water even without flow simulation, just analytically based on source/sink sizes. Otherwise such case will not be simulated (concealment).

    2. For player structures, we can reduce maximum LOD around to allow water machines still work and water flow as needed.

    Best!
    Petr

    ReplyDelete
  3. Do you really need to consider zero gravity scenario? How are you going to use that in game?

    ReplyDelete
    Replies
    1. Brother, my dearest friend, it is for a space game

      Delete
  4. Greetings, Peter! Could you give me some directions for implementing it? I really liked what you showed on your stream, and I would like to make a demo like yours just to play with.I did successfully implement a system using my own reasoning, but I am having trouble implementing your approach. I would also like to know how you implemented sleeping clusters. I suspect it has something to do with that quadtree. I was able to create a "stilling" system which skips processing of individual cells, but it cannot skip large regions. It also is... not consistent. I did, however, optimize it a bit by separating cells into different sets. The collections are also tightly packed structs so I got good cache performance.
    Thank you for your time and your great work on SE.

    ReplyDelete
  5. Hello Anthony, what exactly you have problems with? Regarding clusters, they operate on a grid level, not cell level. Whole connected areas of grids with changes below treshold then can be put into a sleeping state, which saves a lot of performance.

    ReplyDelete
  6. Hello Petr,
    I wasn't able to fully grasp what you explained.
    I believe that the velocity part will calculate the future position and then transfer the liquid to that cell (or the closest cell along the path). Diffusion will distrubute liquid to all 4 cells (presumably, it will distribute it's liquid / 4 * some coefficient)
    I am not sure how to calculate the correct center of mass.
    Surface tension would check all 4 neighbors and, if they are a liquid, it will add some velocity to them, towards the cell.
    I am not sure how pressure would work.
    Regards,
    Anthony

    ReplyDelete
  7. Hello Petr,
    I started working on velocity diffusion. How did you calculate the new center of mass, and how did you select the quantity of fluid to transfer, based on diffusion radius?

    ReplyDelete
    Replies
    1. Hello Anthony,
      the quantity of fluid transfered to neighbour cell is determined by area of diffusion radius covering the neighbour cell. The bigger area is, more fluid is transfered. The same applies for the fluid what stays in the source cell.
      For computing velocity or COM of neighbour cell use a weighted sum, where amount of fluid is a "weight".

      All features like pressure, gravity, surface tension etc. are just forces, which means you calculate velocity changes per cell to achieve the effect. The effect of a pressure is to keep fluid level same across all cells with fluid amount above the treshold.

      Delete
  8. Hi Petr,

    I got part of the algorithm to work.

    My cell structure contains an amount (a float), cell type (wall or liquid), a delta (float), a COM (vector), initialized (bool). When I add fluid to the simulator, I set the COM to grid coordinates plus 0.5 and amount to 1. "Initialized" is used when getting a neighbor cell. If it is false, we calculate the COM to be grid coordinates + 0.5, then set it to true (I don't like this very much)
    To do diffusion, I iterate trough the cells. If the cell is not liquid or is empty, I skip it. Otherwise, I calculate a diffusion area. It is a rectangle centered at the cell's COM, with a width and height equal to diffusion radius * 2. I use a diffusion radius of 0.6.
    I then calculate rectangles for T/B/L/R and the source cell. Then I calculate the area of intersection between those rectangles and the diffusion area. I then calculate the sum of these areas. I then normalize the areas using this sum. I then calculate amounts to transfer (normalized area * the source cell's amount). I then add these to the neighbor's deltas. I subtract the sum of these 4 normalized areas from the source's delta.
    I am not sure how to calculate the new center of mass using a weighted sum. I only know of linearly interpolating a vector to another vector using a coefficient. I also don't know how I would defer these changes.

    Finally, I iterate once more, add the cell's delta to the cell's amount, and set the delta to 0. Maybe I could calculate a COM here.

    This is the diffusion part of the algorithm:
    https://pastebin.com/566C0FVU

    Thank you for your patience. I am getting closer to solving this.

    Anthony

    ReplyDelete
  9. Hi Petr!

    I have some forces working!
    This is the force algorithm:
    https://pastebin.com/qsedQrsQ

    U, D, L, R are the neighbors, and data is the current cell.

    It actually looks... good in a way.
    Using a small surface tension creates a thick stream of water falling down, but increasing it makes it thin. I guess that is correct?

    With 0 gravity, it does look kind of... right. Here is a video demo (uses 1 for the surface tension coefficient):

    https://streamable.com/3qo1hd

    But I don't like how it only forms small blobs. I believe you actually made neighbors come towards the cell. I made the cell go towards the neighbors. Is this correct? This could also be because my "brush" (cursor) only edits a single cell instead of a large circle.

    Also, how did you calculate the pressure force? I tried doing it based on amounts in neighbor cells and a threshold, but it looked choppy (hovering around the threshold).

    On another note, the code linked above is executed in the same pass as diffusion. You probably have multiple passes, like in the diagram. To do this, I need to add a velocity vector to my cell data. I will then iterate once, to accumulate velocities in the vector, and a second time, to apply diffusion (and a third time, to apply deltas).

    In the code linked above, I also clamped the velocity to between -1 and 1, because high values broke the diffusion algorithm (I calculate the center of diffusion by adding the velocity vector to the COM)

    You mentioned computing COM and velocity of neighbor cells. This leads me to believe you did not store COM and velocity in cells, and you calculate them when applying diffusion. That would be great, it would reduce memory access time. I am still looking for a good way to calculate COM.

    Also, does the simulator "propagate" velocities? I.E if you apply a force to a cell, does that affect the velocities of neighbors?

    Anthony

    ReplyDelete
    Replies
    1. Hi Anthony,

      regarding surface tension, calculate the force per direction and add the force calculated from difference between the neighbour and the cell itself. Then it will start to create bigger blobs and attract smaller to bigger blobs.

      It is very similar to pressure force calculation, just use compression treshold as a trigger and reference amount to push forces.

      Do it in two passes - as it is in my diagram, each block is one pass. In the first pass just calculate velocities (keep them per cell) and in the second pass do the diffusion. We also keep COM per cell and calculate new COM for cell during the diffusion pass.

      Velocity clamping is correct, it is needed. We dont propagate velocities, new velocity per cell is also updated in diffusion pass.

      Hope it helps! :)

      Delete
  10. Greetings, Petr!
    I have the "full-scale" algorithm working (pressure and surface tension). It is not as fluid, realistic or stable as yours, though. Would love to hear how you did them. I will e-mail you my algorithm soon.

    Here is a demo, with a little planet, gravity, and an ocean:
    https://streamable.com/djzgv2

    Also, I still don't have COM figured out. The current algorithm uses the cell's grid position, plus 0.5.
    The renderer is not optimized (it is a primitive batcher, it builds the render list every frame, even for the static terrain), but the simulator does have some tricks. It deletes clusters which have too little fluid and no walls. This prunes some instability related to excessive diffusion (gas-like behavior, even when under force). Red clusters are active, while gray ones are not.

    I am curious about your accelerated quadtree for solids. It would be quite useful to have (the solids waste a lot of memory and processing time (memory access time). I assume your solids are totally separate in the quadtree, and your cluster collection only houses liquid). I did not do this originally because I am unfamiliar with spatial indices.
    Also, how did you do LOD? A naive idea I had was to get the liquid from a 4 cell square, rebuild the grid (make it 2x smaller on each dimension) and transfer the quantity in 4 old cells to 1 new, larger cell.

    On another note, thanks for all the help. My simulator is pretty fun to play with, even in its current state.

    ReplyDelete
    Replies
    1. Very cool simulation Anthony👍

      Delete
    2. Hi Anthony,
      it is really good progress! Have you also implemented some kind of stabilization/optimization?

      Keep the solids outside the water, in separate structure. For our 2D water I have used simple octree - that way you can render huge square areas of cells as single big squares. In the water cell I just keep info, if the cell is solid or not.

      I have used COM mainly to have nice flow on diagonals. I believe a proper COM will also improve the round shape around the gravity center.

      The lodding itself is quite more complex, especially tweaking the pressure and forces generally per different lod size and their edges.

      Feel free to contact me directly on email/discord and we can discuss the algorithm in more details.

      Best!
      Petr

      Delete
    3. Thanks, Mr. Marek Rosa!

      Petr,
      I have sent you an e-mail with my Discord account. Looking forward to discussing with you!

      Regards,
      Anthony

      Delete