Box2D Forums

Yeah, the problem is that even if collision is filtered, overlapping AABBs still have to be resolved by the broadphase. Erin tried it the other way around, but it turned out to be cleaner this way. Even overlapping static shapes generate pairs.

I think it's more that we decided to be extremely (perhaps overly) careful about explicitly initializing everything because we had a lot of bugs from uninitialized variables when we were porting - maybe in the C++ version the center b2Vec2 is null until you set it?


Ah, I think I know what may be happening - without the fluid forces, since the fluid particles don't collide with each other, they're just all piling up in the same spot, giving that good old O(N^2) blowup in the number of pairs. At least until the fluid forces are figured out you might want to turn off the collision filtering, and just let them collide, that way each one will have at most six pairs that it's a part of.

FWIW, turning off the fluid-fluid collisions probably doesn't help the speed of my code very much, as once the forces are applied, these collisions are pretty rare anyways.

I had (in retrospect, naively) thought that just getting a bunch of particles pouring down the screen would be a good intermediate step towards getting stuff running, and I could add the constraints code later, but when I realised that Box2D was just going to explode with too many pairs until the constraints went in to seperate the particles I just went ahead and ported over the constraint code too.

I'm happy to say that I've now got what appears to be a fully running port of the Java demo It runs like a dog, even with the renderer fudged to draw points instead of circles. I'd expected the C++ version to run a bit quicker than the Java version, but if anything it's slower. I daresay this is down to my ham-fisted porting attempt (I'm really rusty with Java so I daresay I'm losing some efficiency by misinterpreting some of its nuances). Still, it works, and that makes me happy

I'll try to post up my code in the next day or two, for anyone interested. While I didn't find the Java version to be particularly messy to read, there are bits of my version which have come out as being a bit clumsy to read, so I'll try to tidy those up. At that point, I'll be looking forward to finding ways to improve on things. I think efficient fluids are a real possibility in Box2D, so long as we can find the right way to play to the engine's strengths.

EDIT: One thing I have noticed is that there appears to be the occasional "explosion" in the physics - you can see it in the Java version too, if you pull the camera back, hit reset, and watch what happens as the initial column of fluid falls. There's a point where the particles gravitate towards each other (because of surface tension?) and then suddenly explode and send a whole bunch of particles flying all over the screen. Does anyone know what could be causing that?

That one I do know - it's because the particles are all of a sudden hitting the rectangular region where the fluid force is actually applied, so when it turns on they experience very large forces from the fluid force. This could be avoided by placing the particles more intelligently so that they almost satisfy the fluid constraints rather than randomly spawning them.

Re: the speed issues, yeah, there's a lot of places where things could be going wrong. One thing I'd look for is how you translated the ArrayList stuff, I imagine that could cause some inefficiencies; apart from that, I can take a look at some point if you post the code, it probably should run faster in C++ if everything is done the right way, but it's hard to say exactly what might be wrong without seeing it.

Okay, so here's my rough port. It's pretty much my attempt to do a quick&dirty port of the Java. A few points of note:

- All of the constant variables currently live outside the class, because it was just easiest to get stuff working that way. I plan on encapsulating them properly, though.

- I haven't set the userData, since in C++ it wants a (void*) rather than an int (as a side-note, my preference for any testbed stuff which needs/uses userData would be to set up some kind of struct common to all of the tests, and put the relevant flags/data in there, to be used as applicable, rather than fudging stuff on a per-test basis. That's probably just me though). I've instead fudged my version of the debug renderer to just draw points instead of circle shapes for now.

- I've tried to make as much stuff statically-sized as possible, so the liquid array is set to be nParticles big at compile time, and all the stuff that did reference liquid.size now uses nParticles, since that number doesn't seem to change. In applyLiquidConstraint, neighbours is now an std::vector, and vlen is a dynamic array, both of which should be getting cleared up properly. I wonder if some of the fixed-size arrays are best converted to become members of the class, rather than creating and destroying them on the stack all the time.

- the ArrayList hash has been renamed hashGrid, and is a 2D array of std::vectors, since that seemed to be the closest approximation. I wrote my own little function (myMap) to replace PApplet.map, which seems to work. Either of these changes could be a potential source of slowdown, I suppose, given that I only have a very shaky grasp on what it is they're replacing.

- I wonder if the square root could be factored out, or moved somewhere it might be called less often, but I haven't tried that yet.

Progress, in case anyone is interested...

I've discovered a really cool performance profiler (http://www.lw-tech.com/ if anyone's interested) and found the bottlenecks in the code. The major problems seem to be with me using std::vectors as replacements for ArrayLists. Using them for the hashGrid stuff, in the grand scheme of things, is not too much of a problem, but the ones I use inside applyLiquidConstraint (particularly for building up the neighbour list) are shockingly slow (to me, at least - I expected more from the STL). I'm currently assessing the best way to sort this - probably I'm going to end up implementing some sort of mini memory manager for the code that manages the particles, but I'm not totally sure what form that'll take yet.

The overall plan goes something like this:

1 - Optimise the current code as far as it'll go without becoming too obfuscated to be readable. Do this without hacking Box2D (i.e. keep the hash grid for now)

2 - Have a serious look at the issues where particles collide with "normal" Box2D geometry, to see if that can be done in the "proper" way, to clean up those glitches. I'm hoping that this can also be done without fudging Box2D

3 - Having done this, delve into Box2D's innards to see how it currently does things, and what could be tweaked to wire the fluid code more directly into the engine. At the moment I'm thinking that the LiquifyBody(myBody) idea is a bit too high level, but could possibly be added later as a sort of shortcut helper function. I'm more interested in controlling stuff at the individual particle level, either by having flags set inside shapes/bodies to identify them as being a fluid particle, or by defining fluid particles as entirely new types of shapes/bodies (I'm really not sure yet whether it's shapes or it's bodies we need to be dealing with). Box2D would skip the bits of the broadphase which aren't relevant for fluids, and then process any fluid particle interactions as a seperate part of the Step function. Once that's working, we can look at higher level stuff like liquefying bodies, or transitioning between fluid particles and buoyancy controllers, but I daresay that those sorts of details are likely to be specific to the games they're being used in rather than one-size-fits-all solutions.




EDIT: With regards to my current batch of optimisations, it would be really handy to know the maximum possible size of a neighbour list (i.e. the largest number of particles it would be possible to fit into 9 grid cells, given the size of the cells, size of the particles, and if it's relevant, the numbers used to calculate the forces to keep the particles seperate). Do you know if there's a way to calculate that, or would I just have to think of a suitably large number, load the code up with asserts, and hope for the best? Also, are you able to shed any light on the reasons for the SPH not being scale invariant?

Unfortunately that number is unbounded in theory, so I think the thing to do is just look at what you actually see and assume twice that size.

You may get some improvements in performance by pulling some of those list creations out of the inner loop - in Java it doesn't seem to make much of a difference, but in C++ you may see better performance from clearing a vector than creating a new one. From what I remember STL is not very careful about keeping memory and new object allocations down to a minimum, so it might do a lot of copying and whatnot.

Worst comes to worst, you may want to just create your own simple dynamic growable integer array class and use that instead - even in Java, that's what I should be doing, as the built in ArrayList class is slow as crap (not in the least because it autoboxes integer primitives into Integer objects...yuck). With all my "real" work that's how I always handle growable primitive arrays in Java these days (by doing them myself so I control everything), but I'm not sure if that translates as well to C++, maybe STL is already optimized to handle primitives fairly well? Sure doesn't sound like it, though, since if Java's crappy (for primitives, mind you - for objects they're pretty good) container classes perform better, that's some seriously inefficient C++ code...


I spent a bit of time trying to figure this one out when I noticed it, but I don't think I ever cracked it. Every single one of the equations looks like it should be scale invariant (i.e. if you shrink all lengths by a factor of 10, the equations seem like they should all scale appropriately, with no leftover length factors or anything like that). But if you play around with the parameters, it just isn't so, and things go unstable if the size gets too low. Interestingly enough, until you hit that threshold, the dynamics appear mostly scale invariant, but they eventually break down. It may be something I've done wrong - this isn't a true SPH implementation, and in fact I forget where I even saw this particular method. It may be worthwhile to try replacing the pressure/surface tension calcs with more standard SPH approaches, I think this one dumbs some of the steps down a little bit and that may be responsible for some of the weirdness.

I think I ultimately decided it was a precision issue, though I never finished tracking it down, and I remember being at least a bit dissatisfied with that answer. There could be a factor I missed somewhere that makes this explicitly scale dependent (maybe I didn't adjust pressures properly or something? It's been a while since I looked at this...). If you happen to discover the problem, please do let me know!

STL vectors copy the entire array to the new memory location when they are resized larger than capacity.
So you can significantly increase performance by:
a) Initialize the vectors with a largish capacity to ensure they do not copy as often. Say twice the average number of particles.
b) Yes, don't delete and recreate a vector, re use if at all possible. Why waste the effort de-allocating and re-allocating.
b) Store pointers instead of objects in the vectors, which will reduce the amount of memory to copy.

Just try a) as it's easy, and will have the most visible effect, I reckon.

For the love of god, don't throw asserts if you get an unusual fluid condition. As it would be impossible to ensure the assert is never thrown, this would render the code useless in production.

a) This is my short-term hacky fix - I set the neighbours vector to have an initial capacity of 256, which seemed like plenty to me - even then, pushing stuff onto the vector isn't as cheap as I'd like

b) I think I'm going to reuse a fair bit of the stuff that gets created in applyLiquidConstraint. There are a lot of temporary lists of things, and although it's a bit of memory hit to keep them around all the time, I suspect the performance increase would make it worthwhile.

c) IIRC (I can't look at the code right now), all the vectors are of ints, so storing pointers to them seems a bit redundant - there's no performance increase in copying pointers as opposed to ints (since they're both 4 bytes anyway, on 32-bit machines, at least), plus you've got the extra level of indirection when accessing them. For bigger objects, pointers would definitely be the way forward, though.



Every game I've ever worked on gets the asserts turned off in the final builds, so it shouldn't make a difference except for highlighting problems during production. That said, it's important to safely deal with the situations which cause the asserts, so that the game doesn't just crash if it encounters the unexpected stuff when the asserts have been turned off.

Really? I'm no performance expert, (or C++ expert), but I would have thought if you don't increase the capacity then nothing could be faster. I'd have thought it essentially boils down to
*end++ = data;


If you have lots of tempories, consider using b2StackAllocator, which was written for this. b2BlockAllocator may be helpful too.


Fair enough, I was assuming they were vectors of b2Vec2.