|
Zaphos
Guest
|
 |
« on: March 19, 2010, 09:14:06 PM » |
|
 You don't need encapsulation for l33t fluid dynamics skillz, you just have to be bat-shit crazy enough to spend months and months staring at white papers until you develop a deep Zen understanding of how the maths works, how you can reconstruct the code that the guys wrote for the paper ('cos they never open-source it, grr    ), how you can make it 50 times faster than what they did by throwing every "good" programming convention out of the window, and then you have to figure out how to carry on when an IGF finalist gets there first. I feel we may have hijacked this thread somewhat. What white papers did you look at? What techniques did you end up using? |
|
|
|
|
Logged
|
|
|
|
|
nikki
|
|
« Reply #1 on: March 20, 2010, 03:52:27 AM » |
|
maybe this can help you further |
|
|
|
|
Logged
|
|
|
|
|
|
|
|
|
drChengele
|
|
« Reply #4 on: March 20, 2010, 08:04:10 AM » |
|
I had a thought about using fluid simulation for a strategy game. You are very zoomed out, so an infantry batallion would be a single unit, presented as a patch of "fluid", each soldier a "particle". The fluid would be rendered using standard military colors (with a lot of contrasting pixels neighbouring one another I suppose) so that you would see an amorphous mass of green, grey, brown and skin-pink. I never really got around to it, but if I ever get good at fluid dynamics, I'm trying this. Imagine an artillery shell landing in the middle of the fluid and particles flying away leaving red trails behind them...  |
|
|
|
|
Logged
|
PraetorCurrently working on : tactical battles.
|
|
|
|
Zaphos
Guest
|
|
« Reply #5 on: March 20, 2010, 12:30:28 PM » |
|
Wow, thanks for all the links -- especially raigan, that's quite a comprehensive post!  I am actually familiar with some of the papers on fluid sim already, so I was mostly curious what techniques indies are using in practice on their games, and what tricks they needed to get a nice sim working interactively while still leaving cpu time for the rest of the game. It looks like everyone's going for SPH, pretty much? Also curious if anyone's tried any weird variants like sph coupled with shallow water -- it seems like it might be a good idea in some cases? |
|
|
|
|
Logged
|
|
|
|
|
|
|
LemonScented
|
|
« Reply #7 on: March 21, 2010, 07:05:29 PM » |
|
See, this is the part where I'm asked to reveal all my trade secrets and give someone else the opportunity to develop the technology quicker than me and release games heralded as awesome which my game will eventually get compared to.  When I first started developing my fluid sim at the start of last year I had a hunch that it would be the "next big thing" technologically, and now I'm running the risk of getting my game finished so late that it'll seem passe.  Grumpiness aside, I lean towards the "information should be free" school of thought. This is what my work is based on - "Particle Based Viscoelastic Fluid Simulation": http://www.iro.umontreal.ca/labs/infographie/papers/Clavet-2005-PVFS/pvfs.pdfAt it's heart, it's SPH, although it has some nice additional features. The integration method (a leapfrog Verlet thing), and the way that it deals with surface tension offer some nice optimisations on "classic" SPH. The fluid tends not to be as watery and splashy as SPH as a result, and appears a bit more viscous, but since I'm modelling paint then it works pretty well for me. Another advantage is that it incorporates a (hacky and not very stable, but workable if carefully controlled) method for fluid particles interacting with dynamic rigid bodies. I haven't bothered with the plasticity and viscosity stuff, since it's not relevant to my game. Some thoughts on what I've learnt over the last year or so: Work out exactly what your game needs, and do only thatFluid in games can be everything from a basic translucent quad right up to fullblown SPH, encompassing everything in between (heightmaps, spring/mass systems, you name it). At the top end of things, it can get incredibly computationally expensive and nightmarishly difficult to code and optimise. I've been coding games for 20 years and advanced fluid dynamics is the hardest thing I've ever had to do. Computing power just hasn't yet caught up with using stuff like SPH in a game unless the game is entirely based around fluid dynamics and you can afford to throw a huge percentage of a computer's horsepower behind it at the expense of other features you might want to put in. For my game it makes sense, but for many others I'd advise a simpler approach. Fake it only as well as you need to, and don't go any further, because right now this path leads to madness. Heightmap type approachesStuff like the video batelur posted. These are good for modelling the surfaces of large, mostly static bodies of fluid. You can fake a bit of pouring and splashing with particle effects, so used cleverly this can work pretty well. Variations on this are by far the most commonly-used approach I've seen in modern games, and there's plenty of information out there to pick an approach that will work best for the kind of effect you want and the kind of power you're willing to throw at it. Eulerian/grid based approachesI've looked into these but not implemented one myself (although they seem relatively straightforward). You're likely to take a performance hit, depending on the fidelity of the grid you choose, but it has the advantages of being an inherently stable approach, and seems great for stuff like smoke, fire, gases, and different types of fluid interacting (like dropping ink into water). Where it might get awkward is rendering the actual surfaces of liquids, and modelling fine-detailed stuff like splashing. Langragian/particle based approachesThis covers SPH and the Viscoelastic paper I linked to, and is what I'm doing. The results can be great, but optimisation is a nightmare, and stability can be a problem too. It can't model completely incompressible fluids, so you have to tune it carefully to get a balance between fluid which is "too springy" and varies wildly in the amount of volume it seems to take up, and fluid which is "not springy enough" which looks better under controlled cases but can explode wildly when stressed. Something as simple as a tall thin column of fluid particles can be very problematic, since as the column gets taller and thinner the pressure at the bottom of it reaches breaking point (at which point the simulation completely breaks down and particles fly around the screen at supersonic speeds - often, once this has happened, the fluid will never settle down again and is completely broken). Hybrid approachesI've not tried any of the hybrid approaches, although I know someone who has, and although the last I heard they were working towards decent-looking stuff, they warned me that this kind of stuff is especially hard to program right, even for people familiar with the other approaches. Also, as raigan points out, simulating the fluid with some of these approaches is only half of the battle. Rendering them is an entirely different kettle of fish  I hope this helps. Sorry if some of it sounds overly pessimistic, but given the amount of my time and sanity that have been taken up with playing with this stuff it seems only fair to let people know what they might be getting into, and advising some caution on their choice of method for approaching it. I think in a few years Moore's Law will take care of a lot of the processing power issues and we'll see a lot more of this stuff, but right now a lot of the fluid simulation methods still seem more suited to astrophysics than they are to games programmers. |
|
|
|
« Last Edit: March 23, 2010, 05:49:33 PM by LemonScented »
|
Logged
|
|
|
|
|
Zaphos
Guest
|
|
« Reply #8 on: March 21, 2010, 10:30:01 PM » |
|
Thanks LemonScented! I don't even have any clear game in mind yet so you probably don't have to worry about me at least Eulerian/grid based approaches
[...] Where it might get awkward is rendering the actual surfaces of liquids, and modelling fine-detailed stuff like splashing.
As I understand it, the other big problem is volume loss -- a lot of fluid will tend to just disappear over time if you're just using level set fluids. And also, coupling with rigid bodies and so on is even more painful than it is with SPH. Langragian/particle based approaches
This covers SPH and the Viscoelastic paper I linked to, and is what I'm doing. The results can be great, but optimisation is a nightmare, and stability can be a problem too. It can't model completely incompressible fluids,
There are some incompressible SPH techniques -- the most recent one I know of was at siggraph last year -- raigan actually linked it above, it's http://vmml.ifi.uzh.ch/files/pdf/publications/pcisph.pdf -- I don't know how much worse they are to implement though; I've prototyped normal SPH (following a paper by muller) before but none of the incompressible methods. I'm guessing it's even harder to make fast ... (at which point the simulation completely breaks down and particles fly around the screen at supersonic speeds - often, once this has happened, the fluid will never settle down again and is completely broken).
I think when you have large velocities / stiff situations you're traditionally supposed to take smaller time steps to avoid going unstable -- there's an early SPH paper that discusses adaptive time-stepping based on the CFL condition: http://www.geometry.caltech.edu/pubs/DC_EW96.pdfI'm guessing that's not really practical for you though ... what about just clamping particle velocities so they never travel further than your kernel width in one time step? I hope this helps. Sorry if some of it sounds overly pessimistic, but given the amount of my time and sanity that have been taken up with playing with this stuff it seems only fair to let people know what they might be getting into, and advising some caution on their choice of method for approaching it. I think in a few years Moore's Law will take care of a lot of the processing power issues and we'll see a lot more of this stuff, but right now a lot of the fluid simulation methods still seem more suited to astrophysics than they are to games programmers.
I think most of the best stuff from the graphics literature is aimed at movies, not games ... so, it's good as long as you can spend minutes per frame ... Now I'm tempted to do a grid-based method, with a really low resolution grid and rendered directly as the same low resolution grid. Just embrace an aesthetic that works with the limitations ... |
|
|
|
« Last Edit: March 21, 2010, 10:55:26 PM by Zaphos »
|
Logged
|
|
|
|
|
Zaphos
Guest
|
|
« Reply #9 on: March 21, 2010, 10:52:02 PM » |
|
Just a note -- looking through these links more carefully now, I would not recommend that mikeash link at all. He doesn't understand the code he's presenting, and it's pretty much just a copy of Jos Stam's GDC03 code. Relatedly: Jos Stam posted the GDC03 code (to go along with that paper) here: http://www.dgp.toronto.edu/people/stam/reality/Research/zip/CDROM_GDC03.zip |
|
|
|
|
Logged
|
|
|
|
|
LemonScented
|
|
« Reply #10 on: March 22, 2010, 02:05:37 PM » |
|
As I understand it, the other big problem is volume loss -- a lot of fluid will tend to just disappear over time if you're just using level set fluids. And also, coupling with rigid bodies and so on is even more painful than it is with SPH. I wasn't aware of the volume loss problem, although I could believe that it's an issue. As for the rigid body interaction, yes, that would be a massive headache, if it's possible at all. There are some incompressible SPH techniques -- the most recent one I know of was at siggraph last year -- raigan actually linked it above, it's http://vmml.ifi.uzh.ch/files/pdf/publications/pcisph.pdf -- I don't know how much worse they are to implement though; I've prototyped normal SPH (following a paper by muller) before but none of the incompressible methods. I'm guessing it's even harder to make fast ... Hadn't seen that paper. Filed for future exploration. As I say, optimisation is a huge part of the work with SPH approaches, so the devil is very much in the details with something like this. You never know, that approach might be faster or more open to optimisation than anything else, but until I've tried it you can colour me sceptical I think when you have large velocities / stiff situations you're traditionally supposed to take smaller time steps to avoid going unstable -- there's an early SPH paper that discusses adaptive time-stepping based on the CFL condition: http://www.geometry.caltech.edu/pubs/DC_EW96.pdfI'm guessing that's not really practical for you though ... what about just clamping particle velocities so they never travel further than your kernel width in one time step? Yep, the problem with multiple smaller timesteps is that you've got to run the maths multiple times per frame, which just exacerbates the performance issues. Currently I can get 10,000 particles at 30fps on my quad-core machine, but I can only do one timestep per frame, so I don't have much option but to try to balance the constraints to be as stable as possible and just design the levels to push the fluid sim hard but not TOO hard. Clamping velocities isn't much of a solution since it limits what the fluid can do in otherwise stable cases (firing it out of hoses would look pretty bad, for instance), and in cases where the stability has already begun to break down it's not much good at putting the genie back in the bottle, since even a clamped particle moving in a too dense/stiff cluster will propagate unrealistic amounts of energy around and set off other particles too - not to mention that testing and potentially clamping every single particle every frame doesn't do good things to the performance.  |
|
|
|
|
Logged
|
|
|
|
|
Zaphos
Guest
|
|
« Reply #11 on: March 22, 2010, 02:42:50 PM » |
|
Hadn't seen that paper. Filed for future exploration. As I say, optimisation is a huge part of the work with SPH approaches, so the devil is very much in the details with something like this. You never know, that approach might be faster or more open to optimisation than anything else, but until I've tried it you can colour me sceptical I think the paper says outright it will take more time per each time step -- the possible speed-advantage would be that you could take longer time-steps without going unstable. Yep, the problem with multiple smaller timesteps is that you've got to run the maths multiple times per frame, which just exacerbates the performance issues. Currently I can get 10,000 particles at 30fps on my quad-core machine, but I can only do one timestep per frame, so I don't have much option but to try to balance the constraints to be as stable as possible and just design the levels to push the fluid sim hard but not TOO hard.
One thing to note about the caltech paper -- they actually suggest stepping the particles at different rates. So, perhaps most of the particles would still step once per frame, but your high-velocity particles would take several steps. You could even try taking less than one time step per frame for the slower particles, and interpolating their positions ... not sure if that's a workable idea in practice or not. Also I'm curious -- how many particles do you find you need to get a good result with your fluids? Is 10,000 enough to fill the screen with decent-looking fluid? Or is it just a "more is always better" thing so you just do as many as you possibly can? |
|
|
|
|
Logged
|
|
|
|
|
LemonScented
|
|
« Reply #12 on: March 22, 2010, 04:10:56 PM » |
|
One thing to note about the caltech paper -- they actually suggest stepping the particles at different rates. So, perhaps most of the particles would still step once per frame, but your high-velocity particles would take several steps. You could even try taking less than one time step per frame for the slower particles, and interpolating their positions ... not sure if that's a workable idea in practice or not. Hmmm. Stepping more to increase stability (or less if you're confident about stability) would seem to me to be more of a function of pressure rather than velocity. Fast-flowing fluid is fine for me, the problem comes with deep, still bodies of fluid, which tend to oscillate worryingly at the bottom, where its densest. Unfortunately, these are the exact same particles which I can't afford to step more often because they're the ones that are already the slowest to process (because they interact with more neighbours than particles at the surface, or free-flowing ones). If I could somehow get away with updating those "deep" particles less often rather than more and still maintain stability, though, that would be a massive win. EDIT: I misread your/caltech's point, in that that's exactly what's being advoced. I don't know if that approach will work for my simulation but it's definitely got me interested enough to want to try it. Also I'm curious -- how many particles do you find you need to get a good result with your fluids? Is 10,000 enough to fill the screen with decent-looking fluid? Or is it just a "more is always better" thing so you just do as many as you possibly can? Again, it's a case of balancing and tuning. It's difficult to get an idea of volume in 2D but I'd say that a single particle is maybe half the size of the protagonist's head and 10,000 particles will fill - I dunno, an average-sized 2 dimensional house? Fine detail looks really cool but I also wanted to go for an oversized sense of scale. Actually I suppose it depends on how you position your camera as much as anything else. Spewer did puke simulation with maybe 100 or 200 particles (in Flash), and that was more than enough for that game because the levels were quite tight and intimate. I... I need more that that It goes back to what I said earlier about deciding what's right for your game. Even if you decide you definitely want to do something like SPH, you still need to make a call about what will constitute "enough" particles for you, and when you hit that number, I recommend putting down all the optimisation tools and getting on with the rest of the game. 10,000 was sort of my fantasy ideal-world number, and although I've hit it I'm not sure yet if the final game will go that high just because the necessary hardware specs to run it would limit my audience quite badly (and from what I gather, indie game enthusiasts with really beefy PCs are something of a rarity). |
|
|
|
|
Logged
|
|
|
|
|
Zaphos
Guest
|
|
« Reply #13 on: March 22, 2010, 05:52:46 PM » |
|
On time stepping -- I think one (hand wavy) way to think about their time-step restriction is that if you move a particle a distance larger than your neighborhood size in a single time-step, then you're potentially missing out on the influence of a whole bunch of particles that should have influenced you on that time step, and it's those 'missed influence particles' that would have slowed you down and kept you from going unstable. With that in mind, it makes sense that in the case where a bunch of fluid is moving fast *in unison* this turns out not to be a problem, because then neighborhood won't change much anyways. But in the cases where the fast motion is not in unison, the neighborhoods do change rapidly -- and that's what happens in the "deep still fluid" right as it goes unstable. This makes me wonder if you could distinguish the "fast but consistent" (and therefore stable) case from the "fast and inconsistent" (potentially unstable) case, and only do small time steps in the latter case ... I'm guessing that distinguishing these two cases may be too expensive in practice to be worth the bother, though! Again, it's a case of balancing and tuning.
It always is, isn't it ... still, it's nice to get some ballpark sense for what reasonable targets are! So, thanks again for this I do remember thinking Spewer could stand to use a few more particles ... |
|
|
|
|
Logged
|
|
|
|
|
LemonScented
|
|
« Reply #14 on: March 23, 2010, 05:48:22 PM » |
|
I've read the paper now, and its interesting (although not spent the hours needed to get the Zen-like understanding needed to actually implement it). I'm Still trying to figure out if it's usable or applicable. The main problem with SPH that it seems to be trying to fix is that you need small timesteps (and lots of them) to keep the simulation stable, and they're proposing a smaller number of larger timesteps (albeit ones with an iterative prediction-correction approach) to get equally stable results with less processing. So far so good, but I daresay that advocates of both camps would call me a lunatic for using timescales as big as 1/30th of a second, so only iterating once per frame, but I don't see any other way of cutting the processing down enough to get realtime results. If that approach could give me results that were as stable as I've got now (or better), but with timesteps of 1/15th or 1/10th (or bigger!) of a second, we'd be in business because I could update less than once a frame (and amortize the processing to keep it looking smooth), but I see no indication of the author's confidence about timesteps that big.
Also, although the number of iterations per step seems to be variable based on how quickly the prediction-correction converges on the correct result, those iterations seem to apply to all of the particles rather than just specific particles or groups. Perhaps that could be optimised away in the code, though. It's an interesting paper, and if it came with source code (they never do) I'd quite happily play with it, strip it down, speed it up and see how far it could be pushed, but for now I think I'll leave it to someone else to try it and see if it's applicable to games or if it's mostly just for making render farms for films run quicker.
|
|
|
|
|
Logged
|
|
|
|
|
Developer
