Speed issues with btHeightfieldTerrainShape

[TheJosh]

Sorry about the late reply; had a big weekend.

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

I'm on release (CMAKE_BUILD_TYPE=RelWithDebInfo)

Profiling (valgrind) data can be downloaded here:
http://chaoticrage.com/valgrind/

You can also read my notes and the process I used to get this data. I can provide screenshots if required.

The second two (#3 and #4) didn't have a huge impact in my tests, but my testing is on a smaller map with bigger tiles than most of the maps I play on. Also, while testing I don't move the character, so the benefit of only moving zombies which are close-by isn't apparent because they are all close by on this map.

All game source can be grabbed from here:
https://github.com/TheJosh/chaotic-rage

Interesting bits:
https://github.com/TheJosh/chaotic-rage ... p.cpp#L595 (world set up, heightmap creation is a little below)
https://github.com/TheJosh/chaotic-rage ... it.cpp#L48 (unit creation; unit is the base class for Player and NPC)

[TheJosh]

I know it's been a while, but I'm profiling my engine again, and can't get past the massive amount of cpu time the btHeightfieldTerrainShape is using, so I'm doing more investigating.

I've been looking at the number of calls to and from the method btHeightfieldTerrainShape::processAllTriangles. From what I can see, looking at the code, it iterates over all triangles between two btVector3s, checking for a collision.

The first profile I did, there was 10,188 calls to processAllTriangles, and it called processTriangle a total of 113810 times, which is on average 11.17 calls per call (if that makes sense).

That number seemed a little high, so I made my much bigger, like 6m x 6m cells, and turned on debug drawing so I could see the edges of the cells. I then ensured my character was entirely within a single triangle before I turned on the profiler. On that run it was averaging 7.7 calls to processTriangle per call to processAllTriangles, which still seems high; I would expect it to be more like an average of 2 calls (of course I don't expect it to always be 2 calls, but I would hope it to be closer than 7.7 calls).

Does static geometry have collisions with the height field? I would hope not, but I might test it with all my static geometry removed.

[TheJosh]

So it appears that even with static geometry gone, it still runs with a high call-in to call-out ratio.

I did another test; again I positioned the character in the middle of a triangle (with debug draw on), and then toggled debug draw off, and started the profiler.

11,680 calls to btHeightfieldTerrainShape::processAllTriangles

23,360x calls to btTriangleConvexcastCallback::processTriangle
70,080x calls to btConvexTriangleCallback::processTriangle

23360 + 70080 = 93440
93440 / 11680 = 8

Interestingly, with this test, there is exactly 8 calls to processTriangle for each call to processAllTriangles; I was expecting 2 calls (two tris per tile), but if it was processing 1 extra tile on each axis, there would be 4 tiles total, which would be 8 calls. I might look into this further.

[STTrife]

Maybe you should check

Code: Select all

  359         for(int j=startJ; j<endJ; j++)
  360         {
  361                 for(int x=startX; x<endX; x++)

in the cpp source file to see the values of startJ, endJ, startX and endX. If your character is smaller than 1 tile, then it should be:

endJ=startJ+1
endX=startX+1

or else it will be processing more tiles than neccesary, and there might be something wrong in the switch-cases stuff that sets up these limits above.

[xexuxjy]

not sure if it's confusing your tests but debug draw will also be calling process all triangles with it's callback to show the heightmap

[TheJosh]

in the cpp source file to see the values of startJ, endJ, startX and endX. If your character is smaller than 1 tile, then it should be:
endJ=startJ+1
endX=startX+1
or else it will be processing more tiles than neccesary, and there might be something wrong in the switch-cases stuff that sets up these limits above.

I'll have a play with this.

not sure if it's confusing your tests but debug draw will also be calling process all triangles with it's callback to show the heightmap

Yeah I allowed for that. I've got hotkeys to turn debug draw on and off, so I turned it on, positioned my character, then turned it off and started the profiler.

[TheJosh]

I've done some more testing. I modified bullet to report what tiles it was checking as it checked them. Then I turned on debug draw (lots of data), positioned the character, took a screenshot, turned off debug draw, recorded the tiles being processed.

Test 1, fully within top-left triangle
http://chaoticrage.com/valgrind/try_two/screenshot1.png
0,8
0,9
1,8
1,9

Test 2, center of tile
http://chaoticrage.com/valgrind/try_two/screenshot2.png
0,8
0,9
0,10
1,8
1,9
1,10

Test 3, fully within bottom-right triangle
http://chaoticrage.com/valgrind/try_two/screenshot3.png
0,9
0,10
1,9
1,10

Test 4, On the boundary of four tiles
http://chaoticrage.com/valgrind/try_two/screenshot4.png
0,9
0,10
1,9
1,10

So it appears to over-test almost every case, except test 4 where the over-test is actually required.

[STTrife]

Code: Select all

 299         // expand the min/max quantized values
  300         // this is to catch the case where the input aabb falls between grid points!
  301         for (int i = 0; i < 3; ++i) {
  302                 quantizedAabbMin[i]--;
  303                 quantizedAabbMax[i]++;

First i think the above code could be removed, cause both min and max of the aabb will denote the cell they are in, and only the cells between those two have to be checked. However if you look at

Code: Select all

  239 static inline int
  240 getQuantized
  241 (
  242 btScalar x
  243 )
  244 {
  245         if (x < 0.0) {
  246                 return (int) (x - 0.5);
  247         }
  248         return (int) (x + 0.5);
  249 }

These are rounded up, it might be neccesary to swap the + and - here to make it floor, which would seem correct, because later on you can see that for for the cell that it checks it adds 1 to get the vertices.

Code: Select all

  367         getVertex(x,j,vertices[0]);
  368         getVertex(x+1,j,vertices[1]);
  369         getVertex(x+1,j+1,vertices[2]);

So for example if the local coordinate is 0.6 then it should floor it to 0 cause its in cell 0 and use vertices 0 and 1 to form the triangle to check.

Then

Code: Select all

  359         for(int j=startJ; j<=endJ; j++)
  360         {
  361                 for(int x=startX; x<=endX; x++)
  362                 {

(I changed < to <=) should check the correct cells.

With these changes i THINK it might work more efficiently and only check the triangles that need checking, but i have not tested this! (Actually it wil always check the whole cell, so always at least 2 triangles.)

You should try this in all situation where you know which cells should be checked and step trough it to see if the correct values are found for startx and endj and such, or if i made a mistake. Also check situations with bigger aabb's and not sitting on the edge of the heightfield would be recommended...

[STTrife]

Did you succeed in speeding up the collision checking in heightfields yet? If so could you share the solution?