Monday, November 28, 2011

Sprinkle behind the scenes

This summer me and a friend released a physics puzzler for iOS and Android based on fluid simulation. It started as a really small project almost a year ago, but grew along the way and has been really well received on both platforms.

Last year i posted movie clips from a fluid simulator I was working on, and the fluid in Sprinkle is basically the same algorithm, but in 2D and with lots of optimizations. The simulator is particle-based, but not traditional SPH. Instead, the pressure and velocity is solved with a regular "sequential impulse"-solver. It's quite a mindjob to work out the constraint formulation, but it's worth the effort, since you get unconditionally stable fluid that is reasonably fast and interacts seamlessly with rigid bodies.




The most compoutationally intensive operation is neighbor finding. I'm using a pretty standard spatial hashing technique, with a twist. Each particle gets assigned which quadrant within the cell it belongs to, and a table is used to search neighboring cells, so only four cells need to be searched for each particle instead of nine. For this to work, the cell size needs to be at least four times the particle radius. I also do all neighbor finding on quantized 8-bit positions within each cell, and cell positions are also 8-bit quantized. This is to reduce data size and cache impact.

The fluid step does two iterations per frame to get the desired incompressibility, but neighbors are only computed once. There is also a maximum number of neighbors per particle, and all pair-wise information is stored directly in each particle, duplicated per pair, so it can be traversed linearly. Particle positions are stored in a separate list to minimize cache impact when updated.

For rigid bodies, the excellent Box2D engine is used, and was loosely integrated with the fluid. Box2D is also setup to do two velocity iterations per frame, but the rigid/fluid solver only kicks in once per frame, so the overall update goes something like: rigid -> rigid -> fluid -> fluid -> rigid/fluid. Ideally I should have integrated the fluid solver more tightly, so the update loop would be rigid -> fluid -> rigid/fluid -> rigid -> fluid -> rigid/fluid, but it turned out to be unnecessary for the type of scenarios we wanted to create.

There is a maximum of 600 particles simulated at the same time, so there is a life time on each particle of about 3.5 seconds, then they disappear and gets recycled. An important part of levels design was of course to create levels that drain naturally, and do not rely on pools of water.


In addition to the 600 simulated particles, there is 240 simplified particles, which only follow ballistic trajectories until they hit something. These are rendered separately in a brighter color to look more like foam and splashes. I spawn these "decoration" particles based on certain criteria, for example when fluid is hitting something, or is moving upwards. Full collision detection is still being done on these particles, in very much the same way as the regular particles, but they are instantly removed as soon as they hit something. The particle collison detection is performed first on the fluid cells, using standard Box2D queries and then for each particle using custom methods. Each rigid body shape has a dual representation used only for fluid collisions, and internal edges between convexes in a concave shape are filtered out in a preprocessing step to avoid "edge bumps". This was really crucial for any level that includes a ramp or a slide, which are highly concave.

For rendering, a dynamic particle mesh is built on the cpu every frame and rendered by the GPU using a simple refraction shader. On Android, I use double-buffered dynamic VBOs to update the particle mesh, while on iOS it seems faster to just use a vertex array. I guess for these shared memory architectures most of the old graphics wisdom is no longer applicable. Particles are stretched, aligned, resized, colored, etc based on their physical properties, so it's quite sophisticated for being a particle renderer. If there is one thing that really stands out about Sprinkle I'd say it's how smooth the water looks, considering it's only 600 simulated particles.

The fluid simulation is done on a separate thread, and so is the particle mesh generation, so it scales quite well onto multiple cores. For Tegra 3, which is a quad-core architecture we also added a smoke simulation on a separate thread, but that will be another blog post.

Getting the game to run at 60 FPS on a mobile device was really quite a challenge. The 0.8-1.2 GHz ARM processors found in mobile devices today are indeed quite fast, but if you compare to a regular desktop PC, it's actually still quite far away. For a frame time of 16 ms on an iPad 1 I had to target about 1.5 ms on my desktop PC, so it's roughly a factor of 10x.

19 comments:

  1. "This summer me and a friend released"

    You mean "a friend and I"? ;)

    Great job on the game, Dennis!

    ReplyDelete
  2. Glad to see some things never change :)

    ReplyDelete
  3. It looks very nice indeed - especially getting good interactions between rigid bodies and the fluid. And keeping the simulation stable - I had troubles with that when I played with SPH a long time ago. Anyway, I hope it sells as well as it looks like it deserves!

    ReplyDelete
  4. Looks amazing! I don't believe that it's just particles with Newton physics. How did you do it? May be short tutorial next time :)?

    ReplyDelete
  5. looks great, any chance you could elaborate on why each cell is divided into quadrants?

    ReplyDelete
  6. Hi Dennis, very impressive game here.
    If you don't mind me asking, do you use any game engine (like cocos2D) to develop this game? Or is it only box2D and pure ios/android sdk?

    ReplyDelete
  7. Cool game! And awesome fluid simulation, the water is... well, so very fluid... :-)

    ReplyDelete
  8. Thanks for sharing your info. I really appreciate your efforts and I will be waiting for your further write ups thanks once again.
    youtube html5 player| html5 converter

    ReplyDelete
  9. This is an amazing game. Inspiring. Thank you for offering a free version. (I'll buy a copy at some point to support the developers)

    ReplyDelete
  10. Great game :)
    Can you tell what software did you use to compile the game ? I'm trying to make fluids with Unity3d but I don't get any good result.

    ReplyDelete
  11. Apparently you don't have much time to answer questions :) anyway: did you use some kind of CPU profiler for timing code on various target platforms (I'm especially interested in Android devices)? Or you just used PC profiling/rule-of-thumb-optimization and optimizations just transferred to other platforms?

    ReplyDelete
  12. Thanks for all the comments and sorry about being so slow to reply. The game does not use an off-the-shelf game engine. It's all homebrew code with some standard libraries like Box2D, ogg vorbis, etc. I just use xcode and the NDK (native activity).

    For profiling I use my own frame-by-frame profiler - it's actually the original software for RAD Game Tools "Telemetry" (previously called Dresscode), check out Telemetry if you want a good remote CPU profiling tool, it's well worth the money.

    trs79: I devide each cell into quadrants because it heavily reduces the number of neighbours to search. One could argue you get the same effect by using smaller cells, but it's not 100% correct, because searching more cells equals more cache misses.

    ReplyDelete
  13. Hi Dennis, you and your friend made an amazing game and your code optimizations for embedded system are very interesting! Thank you for sharing these informations.
    I'm curious to know how did you integrated Box2D with your particles system. Did you change the box2D original code or simply did you retrieve the box2D shape and solve the collisions by applying force to the fluid and to the box2D bodies?

    ReplyDelete
  14. Hej Dennis!

    Very cool game.

    Would be nice if you could answer the questions regarding your fluid simulation. How did you solve the problem.
    Would it be possible to do it using Box2D or any other 2D physics engine maybe ?

    Thanks

    ReplyDelete
  15. Alessandro, Brody, thank you for the kind words. I did not alter the Box2D code, but simply run the fluid as a separate simulation. They interact only once per time step through a velocity-based constraint, similar to a any regular rigid body constraint.

    ReplyDelete
  16. Hej Dennis!

    I don't know if you could answer this question but here it goes. Did you use any specific model to simulate the water, maybe SPH simulation, or did you use Metaballs ?

    Thanks

    ReplyDelete
  17. Hi dennis,

    I am Sameer an indie developer.
    I am implementing a 2D water simulation for a game.
    I need your little help with the stretching,aligning of the particles
    which you described in your blog i.e. tuxedoabs.
    As when my water particles separated from the main flow it looks like
    circles (as box2d circles).
    I tried implementing 2 FBOs and decreasing the opacity of the one fbo.
    but in Adreno GPUs, framebuffer switching is very expensive, I cant use this.
    Will you please help me implementing this?
    I just need little help from you.

    Thanks
    Sameer
    sameer_tripathy1988@yahoo.co.in
    skypeid: sameertripathy2

    ReplyDelete
  18. check our website and register now for play casino online
    goldenslot
    จีคลับ

    ReplyDelete