Box2D Forums

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.

I wrote a little constant-size container to replace the vector, use "lvector<int, nParticles>" instead of "std::vector<int>":

The exceptions are all strings, which could be much improved, although it shouldn't matter because the vectors shouldn't overflow.
Also, instead of just use and remove the delete, to avoid allocations.
The "neighbors" array can also be kept in the class instead of allocated on the stack each time it is needed, although I don't know if this gives an improvement.
In any case, applyLiquidConstraints() runs twice as quickly with these changes applied.

Ok, seeing the previous post I decided to actually look at your code, rather than give general hints.

I'm basically having a hard time believing that any sort of custom class is going to be better than std::vector. The given one is basically a wrapped array, you might as well just be using the array?

Anyway, given what you said about perfomance, I see two main problems with your code, that I don't think you would have fixed given the previous advice.

Firstly, you have this:

This is no good. Because you've declared neighbours inside the loop, it will be destroyed and recreated each time, and adding a capacity will not help. You want:


Secondly, as goffrie points out, you are allocating vlen every iteration too. I'd replace it with std:vector as well:



NB: Apparently Visual Studio de-allocates on a .clear(). If you are testing on this platform, you should check for that, as it will negate any benefits.

All of your points are valid and useful, Boris. I'm working on the code as we speak, and I'd spotted some of these, but not all of them. I'm definitely in agreement, having looked into it further, that the STL is pretty close to being as optimal as I'd thought it was, and that the performance problems are stemming from me using it wrongly.

My main line of inquiry at the moment (on top of all the stuff you mentioned) is that as well as neighbours and vlen being clumsy in their scoping, I'm not convinced that building that neighbours list for every particle is such a great idea in the first place, at least not in the way I'm building it at the moment. It makes life easier to iterate through the neighbours list for the bulk of the algorithm, but it's expensive to build the list in the first place - I'm spending a lot of time just grabbing ints from cells in the hashGrid and push_back'ing them into neighbours. I'm looking at a few options, but my main hunch right now is that if I can build this using linked lists (stl::list, presumably) rather than vectors, I can get basically the same outcome by just fixing up a few pointers rather than constantly copying values from one vector to another. I need to try a few things out, but I will keep people updated on my progress, if it's of interest.

This is not technically valid C code, as stack-allocated array sizes must be compile-time constants.

However, I'm pretty sure gcc allows it (not sure about Microsoft's compiler), so you might get away with it anyways.

I didn't know that; gcc does allow it. (Compiling with -pedantic-errors, I see that it complains about it not being ISO C++)

Okay, so I've played with a few more optimisations, but it's becoming clear quickly that currently the big performance hit is in the custom hashGrid broadphase stuff, and there's no easy way to solve it. I've considered a few techniques (and tried a couple, without much success), before I realised that I've been barking up the wrong tree, because really that custom broadphase is the thing we're wanting to remove anyway, and replace with the one that's running in Box2D already. I'm prepared to give this a go, but I'm so inexperienced with the internals of Box2D that I'm not even sure which questions I should be asking to get started. I'll have a go, though, and see if anyone can provide food for thought

Earlier in the thread, ewjordan talked about how he imagined these fluid particles might work in the engine:



This sounds quite complex, but I'm not 100% convinced about how much of it is necessary. It seems to me that having something that behaves like a sensor shape (representing the neighbour range, but otherwise not doing any rigid body collision) is a reasonable starting point. With regards to the specifics of the SPH fluid constraint solving stuff, I'd be happy as a first pass to stick with something external to the core of the engine for now, so that there can be some flexibility in how users work out the specifics of the maths to tune things for the right behaviour. Perhaps eventually we can work out some universal system for solving the SPH and just allow the user to tweak a few values based around ranges, density, viscosity, etc, but for now all I'm thinking about is how these particles should behave with regards to the broadphase.

So, what would we need to do for basic stuff like flagging a shape in a way that says "this is a sensor, but it's one I'm using for a fluid particle?". The main thing as far as I can see is simply that a "fluid sensor" should register contacts with other fluid contacts as normal, but:

1 - Should possibly ignore contacts with shapes which aren't flagged as also being fluid sensors (not sure of exactly how we'll handle interactions between fluids and non-fluids yet, so I don't know how applicable this is)

2 - Should avoid creating a pair when it detects a contact with another fluid sensor. The fluid simulation doesn't need or use pairs, and given the high amount of overlap between particles, this is the first thing that makes Box2D assert when dealing with any notable number of particles.

Now, I don't really understand yet how fundamental pairs are to the engine. So I don't know if just turning off the bit of code that generates pairs for fluid sensors is a reasonable thing to do. Is anyone able to explain how the Box2D broadphase works, exactly? How and why it generates pairs, and what they're used for? Whether it's reasonable to just not generate pairs for certain types of shapes if we know we won't need them, or whether that's nonsensical - and if it is nonsensical, why?

As I understand it. Pairs are created whenever two proxies (shape AABBs) overlap. If the shapes are filtered, then a pair is still generated, but it's the null pair. I think in principle it's possible to avoid this overhead, but it isn't done yet.
I'd keep particles separate from the engine for now, but you can reuse the broadphase code quite easily by creating a new broadphase, and passing it proxies wrapping each particle.

You should probably expect a lot of your processor time to be spent in the broadphase, this is fairly unavoidable.

I'm not sure what you mean by a "null pair". Certainly by (for instance) taking the sensor test, making the balls also be sensors, and turning on "draw pairs" in the debug stuff, it still draws the pairs. Perhaps the pairs are not used for doing any rigid body collision response, but they're still generated.

What's involved in creating a new broadphase, and is there any overhead for doing so? Right now, the code runs two collision systems (Box2D's one, and the grid-based one bolted onto the top, which may or may not be considered a broadphase depending on your definition), and it seems strange to pay the price for both of them.

For the record, I'm currently paying something in the region of 35% of the processing time in the Box2D broadphase (mostly processing particles which get handled in the custom code anyway), but I'm paying at least another 35% on top of that trying to manage the hash grid for the SPH processing. Trying to find a way to turn off the Box2D stuff I'm not using seems counter-intuitive. It would make much more sense to use Box2D to tell me which particles are close to any given particle, rather than waste CPU time trying to figure that out myself. It's just that if I try to do so, those pairs are a killer.

You know, I think simply using sensors for the fluid particles could work just fine. Looking back, the main reasons I didn't do this were:

1) With the JBox2d testbed's software renderer, it's way too expensive to draw all the sensors (like, 10 fps vs. 50 fps expensive). The solution here is easy, though I didn't try it at the time (I forget why, esp. since I ended up doing this with the solid particles anyways) - just turn off drawing of the entire sensor and replace it with a specialized fluid rendering step.

2) Fluid-solid interactions need to be handled properly if the particles don't have solid cores.

3) There are a lot of pairs, so the maxPairs setting needs to be set pretty high (not a problem at all).

4) Sensor processing was a major hassle back when I wrote that code, something which is vastly easier now thanks to all of BorisTheBrave's work. Now it's a simple matter to read off a list of currently touching particles (at least in the C++ engine).

But I think just taking a sensor based approach could work very well, and that might be the best way to avoid broadphase duplication. What you'd do is just make the sensors have half the size of the neighborhood that you're looking at. Storing some of the SPH fields on each particle might help, too, as the pressure calculation step could then proceed pair-by-pair instead of particle-by-particle (which doubles the number of operations, hitting each pair twice). There might even be some things that could be stored away to make this all more cache friendly, but that would be a later optimization.