I made quite some progress on my water simulation. As well as plenty of other “behind the scenes” things like threading (managed to get average increase of ~20fps), saving/loading level to file and plenty of other small tweaks and changes.

Inner Workings of the simulation

Let’s start with the basics: liquid is represented as an integer number and at the moment any block can have from 0 to 15 units of liquid (which is water at the moment, but I plan to have more types, one of them obviously being lava). I use integer numbers because of couple reasons, even though floating point number would be better and simulations would be a lot more physicaly accurate if used with Shallow Water Simulation Model (See this paper for more info), it has its disadvantages: at the moment I use only 1 byte for liquid per block and using floats would need 4 times that, also due to the nature and precision errors in floats in many cases it would take a long time for larger bodies of liquid so reach stable state where no simulations would be needed. Integer numbers also have problems obviously, main one being that distributing 7 units of water into 2 blocks is quite hard, and if flow is prevented when difference between neighbours is only 1 unit, cases like 5|4|3 will appear, creating this ramp/stair effect which would imply that liquid has very high surface tensions which is not true for water.

The most basic liquid simulation using cellular automata would be something along those lines: check if liquid can flow straight down, if it can, perform flow operation and then if there are liquid left, or flow down was impossible, perform spread out operation which would distribute liquid to all the neighbours until most balanced state is reached (It is very easy to do using float numbers, however integers have problems there). Of course this has all the problems mentioned before, as well as some other related problems, one of them being Waterfall problem – when falling water creates a pillar and in some cases full amount of liquid can flow down so it spreads out in mid air, causing wider stream, as well as creating a large ramp if large amount of liquid is used.

In my implementation liquid is simulated in three stages:
First Stage – flow directly down, if any amount of liquid can flow down, perform flow and skip other stages until next simulation frame. This slows down the liquid flow speed, however if helps to deal with waterfall problem, it does not solve it completely, but it looks a lot better.
Second Stage – flow to the sides, this stage is only reached when conditions of stage one were not met, if possible in this stage liquid tries to flow to four sides, to the blocks with lowest amount of liquid. I test all 4 neighbours and pick the one with lowest amount of water, then flow 1 unit of water to it if possible (main block has at least 2 units more liquid, so it balances out 7 5 to 6 6), this operation is repeated until no more flow is possible.
Third Stage – this stage is only executed if no flow happened in stage two. In this stage path finding is used to search small area around the main block for possible outlets in a similar fashion as described in Here (I suggest to read the whole article, it is an interesting read). Path finding creates a list of all blocks that have space for liquid, then this list is sorted based on the distance to the original block, and flow is perform in that order until either there is no more liquid to flow, or all of the blocks in the list cannot accept any more. If that happens, outflow block is marked as static so no more simulations are performed unless it is woken up by other blocks. This also creates a limited liquid pressure.

Having three stages allows to distribute work better over multiple frames. Performing all the stages or even just stage three for each block would take a lot of time, even threads are used, it would cause problems where liquid would be simulated only in small areas because by the time it would be finished, the next stage would be triggered and it would need to perform simulation again from the start so simulation would not reach block segments (world is split up into small cubes for frustum culling, and other octree based optimizations) which are at the end of the queue until stable state is reached etc. At the moment my implementation has quite a few limit on how many stage threes can be performed in a single frame, before it quits simulation early, which helps to keep frame rate stable and makes sure that all block segments which need to have liquid simulated get at least some processing done. That means the overall liquid flow will be slower, but this will not cause any excess lag in other aspects of the game.

There are plenty of other smaller things I did not cover like: removing requirement for back buffer, exact details of path finding and so on, if you are interested in any specifics feel free to ask!

Video

Finally an update! I was busy with university stuff, so my project was on hold. However now that it is all done, I have more time to spend on it.

Video is at the bottom of this post if you do not want to read all the stuff :| .

Deferred Shading

I have implemented basic deferred shading, which seems to work well, but it still requires some extra work for specular settings (at the moment it is same for everything). I have implemented directional, spot and point/omni lights which look pretty good, but still need some adjustments for light emitting objects (when a small object encapsulates the light source, it is not lit since it is facing away from the light). Currently only directional light (sun at the moment) has shadow, which still requires additional work to make sure it properly covers visible area to maximize shadow coverage, which would allow to use smaller resolution shadow map or have higher quality shadows or improve distance from which shadows can be see. I have a plan how to do shadows for spot/omni lights as well, which should not be too hard since even though environment can be completely changed, it is easy to take only the blocks in range of the light, which should make rendering shadow maps quite fast.

Screen Space Ambient Occlusion (SSAO)

After implementing Deferred Shading, I have completely removed all baked lights (which I had 4 channels of) since now I can have any amount of any colour lights, that also removed the baked AO. However with new shading it makes easier to implement SSAO which has one big advantage, it works on any shape geometry, which means rebuilding terrain meshes is faster, also they take less memory since light data is no longer required (blocks themselves also take less memory now). It still requires some adjustments since at the moment it is too strong on light objects and too weak on dark ones.

Post processing

I have also added a simple bloom effect, which looks nice on sky however it does not bleed enough light to look the way I want it to look, but over all I am happy with it.

Water

Water… Still requires a lot of work since transparent objects are not supported in Deferred Shading, lights and shadows do not show up (since water is rendered after the lights pass, in a forward rendering part of the pipeline). However I think with the use of g-buffer it should be possible to create an easy refraction effect (maybe even reflection) to make the water look better, that of course goes for ‘static’ water at the moment.

I have been working on the liquid simulation a tiny bit once in a while, but now there is something that I can actually show. Water is simulated using Cellular Automata approach, which has its own advantages and disadvantages: it is fast to calculate, works with any type, since it requires only block itself and its neighbours also it reaches a stable state which is important since having water simulated all the time would probably kill the frame rate, however that comes with a disadvantage, since liquids are integer based for less memory usage, it is not possible to evenly split odd amounts of water to even amounts of blocks. Simulation needs to take that into consideration, which means there is a safeguard that does not allow liquid to flow if the water difference is only 1 unit, that results in a “Stair” problem when water is |5|4|3| when it could spread evenly to |4|4|4|. I managed to reduced the steepness of the stairs, but completely removing would require a lot more complexity (for example evaluating higher area around each block, using path finding to find possible outflow points). At some point I will try path finding based approach on a slightly higher area (well if it works for Dwarf Fortress it should work for me, right? — famous last words).

Next Steps

I am pretty happy with the graphical side at the moment, except the fact that Deferred Shading, SSAO, Post Processing highly reduces the frame rate and DirectX’s present() method blocks the loop for 8-12ms each frame, which I could spend simulating water, loading blocks, and doing other stuff (and the non blocking wait flag is not supported until DX11 and Win8 :( ). That means next I will be looking into threads… which I was avoiding since have bugs in a single thread is annoying enough and concurrent bugs are just some much more painful.

Also since graphics are now taking vast majority of the frame rate, priority queue for updating segments/blocks near the player is required. Or maybe even queue system overhaul and upgrade to thread support might be even better idea.

Oh yea I still need to implement better support for skylight and per column data (which requires a quadtree in addition to the octree), even though I am not using it for lighting the scene, it most likely will be required for game play mechanics.

Video

So I finally managed to make a short video, It’ does not show much, but I hope it you’ll see something interesting. If you have any questions about anything feel free to ask and I will make a blogpost or maybe even a video about something specific you want to know. In the future I plan to make some more videos where I focus on one or two things I make progress on, so I can cover them in more detail and I hope that will make them more interesting.

Hello everyone!

The time has come for me to start a dev-blog on my KipBGE Game engine. First videos and screenshots will be coming in the next 2-3 weeks!