btDbvtBroadphase very slow on sweep/ray testing

[Dragonlord]

The implementation of btDbvtBroadphase seems to have a serious performance issue. To see the problem create a simple work with btDbvtBroadphase. Add a few objects in it. Now try to make a convexSweepTest with a small sphere (for example 0.01 radius for example) or a rayHits test with a distance vector of length 500.0 . This is right, use a long ray or sweep distance. The call in bullet takes easily 300ms or more although you have next to no objects in the world. Reduce the length of the test ray ro 200, 100 or 10 and see how the speed gears up.

So in a nutshell if the test distance increases to larger numbers (for example up to 500) the rayHits testing in btDbvtBroadphase climbs up to 300ms or more for the same collision world.

I suspect the class incorrectly bloating up internal state outside the used for space but covered by a long ray. I see no bug tracker or bug forum so I post it here.

[lunkhound]

It sounds like a serious bug.

There is an issue tracker here:

https://github.com/bulletphysics/bullet3/issues

[Dragonlord]

It sounds like a serious bug.

There is an issue tracker here:

https://github.com/bulletphysics/bullet3/issues

If I'm not mistaken this bug tracker is for bullet v3 but this problem affects bullet v2.

That said I've tracked down the problem to btHeightTerrain. It's testing every single triangle in the entire AABB covered by the swept shape. Remedied the problem by adding an own class and patching into bullet additional calls processAllTrianglesConvex and processAllTrianglesRay called appropriatly able to optimize the calls. Brings 300ms down to ~1ms for regular cases and a bit more for unfortunate cases.

[lunkhound]

If I'm not mistaken this bug tracker is for bullet v3 but this problem affects bullet v2.

Even though the repo is called "bullet3" it actually contains bullet v2 as well. And both versions are being actively developed there. So I'm pretty sure the issue tracker is for both bullet versions also!

That said I've tracked down the problem to btHeightTerrain. It's testing every single triangle in the entire AABB covered by the swept shape. Remedied the problem by adding an own class and patching into bullet additional calls processAllTrianglesConvex and processAllTrianglesRay called appropriatly able to optimize the calls. Brings 300ms down to ~1ms for regular cases and a bit more for unfortunate cases.

Nice! Good to know you found it.

[dern23]

Any chance you could share your solution? I encountered the same problem a couple of weeks ago and diagnosed it in the terrain's AABB as well; but since the ray-casting is a rarely used feature in our software, fixing it was deemed low priority so I moved on to other things. This is the kind of fix that should be integrated back into the trunk as the fix for the similar performance problem in the terrain's AABB collision calculation was.

[Dragonlord]

The optimization on the height terrain testing itself I can't share since it ties directly into my engine code and objects. The missing call-in point though can be patched with the patch file. It affects ray casts and convex casts but not the calls inside btCollisionWorld physics simulation due to the function calls being static instead of virtual (could be fixed though too).

Just implement processRaycastAllTriangles and processConvexcastAllTriangles in btHeightTerrain subclass with the optimization matching your system. If left unimplemented it reverts to processAllTriangles as before so it's backwards compatible.

[dern23]

That's excellent, much appreciated! It might also be desirable to create an issue for this at https://github.com/bulletphysics/bullet3 as well, Erwin seems to check that more often these days than this forum. He might be able to assist in any possible refactoring required to integrate the patch into the trunk.