Box2D Forums

Delaunay triangulation?



sounds great

I meant Delaunay, not Voronoi

Hi guys!

I'm developing a little game and an accurate water simulation is very important for its gameplay.

I checked Jos Stam work and it looks interesting, but a little too hard to code (at least for me): http://www.dgp.toronto.edu/people/stam/ ... /GDC03.pdf

There is also a chapter in GPU Gems 3 that describes how to implement Stam's method entirely in a pixel shader.

After reading that I heard about SPH and found a nice demo from Danny Champman:
http://www.rowlhouse.co.uk/water/index.html

There is also available a video of the demo:
http://www.youtube.com/watch?v=T0E6e7viXyc

Danny's code is pulicly available, clearly written and it's based in a very easy to understand paper:
http://www.matthiasmueller.info/publications/sca03.pdf


I hope that this information is useful for someone. I personally believe that SPH method is easier to understand and code, but I fear that it will not be fast enough...

Sorry if it's bad etiquette to revive this thread after so long, but did anything come of this work, ewjordan? I'm about to embark on coding up some kind of fluid simulation myself (it's going to be a pretty major feature of the game I'm working on, if I can get it to perform well enough), but it looks like you've already got this into a reasonably advanced state and it'd be a shame to have to reinvent the wheel.

Well, apart from the hacked up demo that I put together somewhere earlier in this thread, no, I never got this fully integrated into the engine. I took a look at what it would take a while back, but time constraints never allowed me to actually do it, simply because it requires touching a lot of code to make it so that the proximity detection and force applications happen inside the engine instead of externally (the ideal would be for fluid stuff to be handled as another contact type).

Unfortunately I can't commit to doing this right now, since I'm in the home stretch of a project that's somewhat urgent for the client. I should be done with this fairly soon, though (within a couple weeks, or else I'm in trouble!), so when that's done I can certainly help advise you or even help with the code.

This is a feature I'd really love to have in the engine, esp. if it could be done in a user friendly and fast way (i.e. integrate SPH on the surface, height field water underneath, and BorisTheBrave's buoyancy code all into one seamless package where you'd just say something like LiquifyBody(myBody) and be done with it - the main problem with something like Phun's water system is that if you really fill up large amounts of space with water, SPH uses up way too much processing to be feasible, so you really need some sort of dynamic transitioning between less accurate height-field methods for large near-static bodies of water and the SPH stuff where it's needed).

I've looked into SPH a bit and found a couple of naive-looking (but reasonably easy to understand) code implementations, so I'm going to start plugging away at this. Help is likely to be much appreciated when you've got the time, but I completely understand what it's like being faced with project deadlines

I imagine I can get a rough, slow implementation together over the next couple of weeks, but a tiny bit more information (if you have the time to give it) might help me get moving faster.

1 - As I understand it, the bulk of the speed hit in these systems is processing the particles interaction with its neighbours (or, in fact, keeping track of who the neighbours are). The example code I've got splits the screen up into square regions and processes those for neighbours, but I gather that Box2D's broadphase stuff is likely to do a better job of this. Unfortunately, I know almost nothing about those parts of the Box2D internals. Where would be a useful place to start with getting Box2D to quickly tell me what all of a particles' neighbours are?

2 - Are the particles in your test solid? That is, do they collide with other, non-fluid, rigid bodies, and use the normal Box2D contact solver stuff, or do you have to deal with the interaction between fluids and solid bodies in some specialised way?

3 - Following on from 2, and assuming that each of your particles is a b2Body with a b2Shape attached rather than some other non-Box2D representation (is it correct to assume this?), which stuff do I need to turn OFF for these bodies and shapes - what things are a waste of time for Box2D to even consider processing for the particles?

Right, so this is really the main reason to prefer handling things inside of Box2d instead of just applying forces from the outside - I ran another broadphase in parallel with the Box2d one (exactly as you did, simple gridding), which is a waste of time since Box2d is already doing it. What I had considered before was creating a new type of shape that represented the neighbor range for a fluid particle, stored any dynamic SPH per-particle variables, and reported a special type of fluid contact which would be passed along to the SPH solver. If that's the route you want to take, you need to figure out a lot of stuff, for instance SPH "contacts" can't be solved pair by pair like normal contacts (pressures depend on all of a particle's neighbors, and pairwise interactions depend on pressures), so you've got to store away some of the data, figure out the best time to process the group, etc, or maybe decide to use the old values, or something like that. It gets a bit messy, esp. when you realize that you have to also integrate a whole new contact type, which means digging into the internals to figure out exactly what need changing.


In that demo (at http://www.jbox2d.org/liquid/, btw), I just used tiny circles so that they interact normally with the environment; in a real SPH sim, you want to handle fluid-solid contacts differently, because you get artifacts if you don't. You can see this in that demo as particles seem to act a little oddly near walls and corners, because they are only bouncing off of those whereas they are undergoing fluid interactions with the other fluid particles.

You'll probably have to look up exactly how to model fluid-solid terms; I think it's pretty simple, but I don't remember off the top of my head. If you use a have a circle representing the neighbor boundary, then you can use any contacts between that circle and a solid body to get the normal vector, which should be all you need for the calc.


Yup.

The broadphase is the main thing that's unnecessary. The rest is what's lacking, mainly the fact that the fluid constraints are solved totally apart from any other physical constraints (they happen completely outside the solving step, even), which may lead to poor quality interactions esp. with warm starting (not sure), and that the custom neighbor handling and broadphase don't allow an easy path to setting up reasonable interactions with solids (the neighbor "circles" have to be actual shapes in the system to use them to check for overlaps with polygons, and in my setup they were not).

As a first go, as you play with the SPH algorithms, you might see if you can get decent behavior using sensors, without worrying about potential inefficiencies in the broadphase or integrating with the solver - if you get the fluid-solid pressure terms right, you may not even need a hard core, though it might be worth doing a simple raycast check to make sure things don't tunnel (or you could use a point shape, though I don't think that's in any version but the Java one).

Also, (messy) code for what I got running is in the JBox2d testbed as LiquidTest.java (http://jbox2d.svn.sourceforge.net/viewv ... iew=markup).

The Java source is a great help to me. My current plan (if this is okay with you, it's your code I'm messing with after all) involves porting the code to C++, 'cos that's what I'm working in for my game, and then at some point in the future working with you to plan what could be the best way to integrate this into the engine better. It means I can prototype my game with the grid system so I can make progress with that, but if there turns out to be a good way to fold the progress back into the engine in a way that's useful to other users, I can maybe make some contributions to that as well. I'm a fan of learning to walk before I can run, so I'd rather see something up and running in the suboptimal way before trying to make informed decisions about what the better way would be.

It definitely seems to make sense in the medium-to-long term to try to work this into the engine better. In the short term, it's immediately obvious why the broadphase solver needs to be turned off. Just trying to set up the static geometry from your demo, and generate the 1000 bodies for the water (1000 round bodies just falling, I'm not trying to apply the constraints yet) immediately starts triggering asserts, even with the max proxies set to 2048, as in your demo. How do I turn this off for the water particles - by doing some contact filtering, or setting all the particles as a sensor, or what? It's not clear from the source; my best guess is that you've hacked the Box2d internals somewhere to test for LIQUID_INT and not attempt to process bodies with that set, but I don't know how to verify that.

Absolutely, I'm interested to see what comes of it.


Nope, the only thing LIQUID_INT is used for is inside the testbed it's checked so that the "water" stuff is drawn as colored points instead of circles (the circle code is not very fast in Processing and was bogging things down too much). No engine hacking that I can remember, at least.

You may want to check to make sure that you're spawning the particles in different locations, because it really should work if you've got enough proxies; also, make sure you've cleaned before rebuilding, you often have to do that after changing the proxy limit so that the settings file is recompiled. If that doesn't help, can you post which assertion you're hitting?

With b2_maxProxies set to 2048 (as it seems to be in your test), and b2_maxPairs becoming 16384 as a result, I get this:

b2Assert(m_pairCount < b2_maxPairs && m_freePair != b2_nullPair);

near the top of b2PairManager::AddPair, with a callstack which looks like this:



It used to do this on the first frame of the simulation, until I realised that it was odd to set up the mass data of the particles to have a mass and an I but no centre of mass (I presume Java guarantees that all vectors default to 0? Had to set this explicitly in my code). Having set the centres of the masses, my code will run for 6 or 7 seconds before hitting the same assert, although I'm not yet running the code to apply the liquid constraints so perhaps getting that working will help. I notice that Box2D is still adding pairs between touching/overlapping particles, even though (as I understand it) they should be collision filtered to not care about collisions with each other. Are pairs generated between collision filtered boides anyway, but just not acted upon? If so, what's the reasoning behind that? I would have thought that if two bodies won't respond to colliding with each other, it seems pointless to even detect the collision and generate the pair.