Speed issues with btHeightfieldTerrainShape

[TheJosh]

Hi,

I've been working on a zombie game, and recently noticed very low frame rates when the number of zombies went above about 20.

I used Valgrind/Callgrind to investigate the issue. I ran the game for 30 seconds, enabled Callgrind, ran for another 30 secs then disabled again.

btHeightfieldTerrainShape::processAllTriangles is taking up 90.35% of CPU time, which makes me wonder what's going on there.
Screenshot: http://chaoticrage.com/valgrind/screens ... -01-15.png

My engine has a btHeightfieldTerrainShape for the main terrain, and a KinematicCaharacterController (+ Ghost) for each player and for each zombie. I get all of my collision callbacks using the chost objects (I don't even iterate over the dispatcher manifolds).

Any ideas?

[xexuxjy]

I tend to get similar results with heightfield terrain shape in my c# version of bullet. Looking at that profile data it looks as though most of the calls are in GJKPairDetector::getClosestPoints and btConvexShape::getLocalSupportingVertex, which kind of makes sense as all the terrain shape is doing is finding a bounding box for the characters movement and calling an triangle v shape test on every triangle thats included in that box. I've found that if you're doing long diagonal movements on the terrain shape then you have a pathological case where you potentially end up testing a lot of triangles.

What resolution is your height grid, and how fast are the entities moving (i.e. how big is the test on the grid) ?

[TheJosh]

What resolution is your height grid, and how fast are the entities moving (i.e. how big is the test on the grid) ?

The height grid has tiles of 1m x 1m, and the entities move at 10 - 20 m/s. I now understand why that is using so much CPU, bit it's pretty annoying.

I might try a lower-res grid, see if that helps.

[STTrife]

would it be helpful to divide your grid into multiple instances of btHeightfieldTerrainShape of much smaller chunks of your terrain?

Then the system only has to check a small part of your height field and the rest can be dismissed based on bounding box.

[TheJosh]

I was going to try that next, see if that helps. I'll post back here when I have some results.

[STTrife]

if for some reason bullet doesn't do this well, then it shouldn't be too hard to implement this yourself I think. I assume your heightfield doesn't rotate so checking the axis aligned BB's should do the trick..

[xexuxjy]

I had a patch for btHeightFieldTerrainShape that built an optional finer grained quadtree on top to help with situations like that. (submitted as issue : http://code.google.com/p/bullet/issues/ ... %20Summary ) . I've also seen people suggest a form of bresenhams line drawing in the calculation of the squares to test which I think may be a better option but I haven't seen code for it.

[STTrife]

Thanks for sharing that xexuxjy, I'll try it out as soon as I get to that point.

Oh and TheJosh, how large are your grids now, I mean in terms of number of raster lines?

[TheJosh]

In terms of raster lines? I'm not sure. Most of my maps are 200m x 200m with a 1m sized grid square (so 200x200 sized heightmaps). I'm guessing because it's all one rigidbody, it hits the AABB broadphase every time, so the narrowphase has to look over 200x200 (400,000) grid squares, which would be 800,000 triangles I'm guessing, does this sound about right?

[xexuxjy]

no, it's not that bad.... it will take your start and end movement points and calculate the set of possible overlapping triangles, not the whole heightfield shape. it just that if you're doing diagonal movements then that box is larger then it would be otherwise.

If your zombies are only moving slowly then they probably won't be testing many triangles, so it shouldn't really be much of an issue. even in my c# version which is a lot slower then the c++ one I can comfortably have 512 x 512 terrain shape, in fact the actual size of the terrain isn't really that important as it's a regular grid and the triangles are derived from that for the test. it only gets bad when you're testing a collision over a large area.

how many zombies do you have moving each time?

[STTrife]

yeah that would seem to be the case. I think you can pick your grid size based on sizes of your other objects. It would seem kinda odd if your grids are smaller then the objects falling on them.

But maybe 32x32 or 64x64 grids would be better

the octree would even work better I think, then you have to worry much less about grid sizes. but again, if your objects falling on the grid are really big, it will have to check a lot of triangles always ...

edit: was typing this at the same time as xexuxjy was writing a reply. His answer seems plausible but then again if you report slow behaviour with slow moving zombies on a 200x200, that seems different from what xexuxjy says...

[TheJosh]

So I should be trying lower-res terrain instead of terrain slicing into multiple heightmaps? I've got some weapons which do terraforming (drilling holes and the like), and I'm worried If I decrease my res it won't look as nice, although I might be able to fix it with rendering the high-res version, but only giving bullet the low-res version somehow. Also, I tested on a map with a lower res heightmap (50x50), and it's better, but not excellent.

And I have all 20 or so zombies moving at any one time. They aren't moving heaps fast, about 10 m/sec. The player is like 15 m/sec and I have some "fast zombies" moving 20 m/sec.

I guess if I'm running at 60hz, it's 16.6ms per tick. 10 m/sec = 1m/100ms, so 1/6m per tick, so it should be hitting the same triangle most ticks, yeah?

I think I'll give the QuadTree a try, and maybe try to get the Zombies to halt every so often.

[TheJosh]

Okay so I found a few things helped:

1. I made the size of my units smaller. They were actually too large (about 2.2 m tall), so it was a good idea anyway.
2. My zombies are actually a Lua script which calls a function to update movement direction. I made it only update the KinematicCharacter when the direction changes,
   not every tick.
3. I made zombies stop moving when far from the character (50m is the current distance but I might make it larger). This made a big difference.
4. I realised that dead zombies still had their character (and ghostobject), even though the Lua state was being nuked. I now replace killed entities (which stay around for a while so you get a dead body lying on the ground) with a 10cm3 static cube. Obviously a static runs quicker than a dynamic.

I have profiling data if anyone is interested.

I might also try some more things, although my performance is getting close to acceptable;

1. Reducing the res of my heightmaps too, but I can't do that on all maps yet because some maps use heightmaps instead of walls.
2. I might also try the QuadTree

[xexuxjy]

Yep would definitely be interesting to see your new profile data.

I doubt you'll get much benefit from quad tree , if your zombies are/were 2.2 m and moving at 10m/s then you're probably only testing 4-8 triangles per entity anyway which shouldnt be excessive, am surprised that with only 20 entities you were hitting issues. You could reduce your grid resolution but 200 x 200 with 1m intervals isn't bad by any means.

possibly obvious question but are you testing in debug/release for bullet?

[DannyChapman]

I've also been seeing big slowdowns when my object is moving close to the heightfield. Actually - I typically just have one object and one heightfield (http://www.rowlhouse.co.uk/PicaSim/) - the reason it's hurting me is my plane is a compound with about 11 shapes, and I have to simulate at a very high frequency (e.g. 600Hz) to keep the aerodynamics calculation stable (until I find a way of changing the integration scheme). Otherwise the simulation tends to flip out about around 300 mph (for a R/C glider - this kind of thing: http://youtu.be/rfoxjNg-eg0).

One thing I noticed is that the comment in btConvexTriangleCallback::processTriangle

//aabb filter is already applied!

is incorrect in that the aabb test has only been done against the heightfield's aabb - not against the triangle. I've put in a quick temporary hack and this provides a huge speedup when my plane is within the heightfield's aabb, but is still above the ground:

Code: Select all

void btConvexTriangleCallback::processTriangle(btVector3* triangle,int partId, int triangleIndex)
{
  btCollisionObject* ob = static_cast<btCollisionObject*>(m_triBody);

  // Quick check on AABB
  const btTransform& tr = ob->getWorldTransform();
  if (
    triangle[0].getZ() < m_aabbMin.getZ() &&
    triangle[1].getZ() < m_aabbMin.getZ() &&
    triangle[2].getZ() < m_aabbMin.getZ()
    )
  {
    return;
  }

I don't know if this is a bug, or just really low hanging fruit for optimisation! Obviously the check could be made more efficient too (e.g. by doing it one level higher up on the 4 vertices of the quad, to avoid repetition and a function call).