Godot Physics performance drop on ConvexPolygonShape RigidBody contact

[fathonyfath]

Godot version

v3.4.2.stable.official [45eaa2d]

System information

Windows 11, GLES3, RTX3060TI [511.23]

Issue description

At the moment the rigidbodies contact, suddenly the performance going bad with the physics process takes 200ms.
It also looks like the rigidbodies stick to one another.
This doesn't happen when I'm using Bullet physics.

Steps to reproduce

Project default settings is using Godot physics.

1. Run the project
2. Press space to start spawning rigidbodies
3. On my machine, as the third rigidbody made a contact with already falling rigidbody, physics process getting slower

Meanwhile switching to Bullet physics on the project settings, it can handle the physics process more stable.

Minimal reproduction project

physics-benchmark.zip

[Calinou]

Related to #48587.

I can confirm this on 3.x 49df809.

The RigidBody's convex collision shape is made of 78 points, which I feel is fairly high for an object with such a simple shape:

However, performance dips as soon as the first RigidBody touches the StaticBody, so this is unexpected.

Replacing the convex collision shape with a BoxShape solves the performance problem, even when there are dozens of RigidBodies. Collisions won't be as accurate, but for the mesh provided here, it gets close enough.

Minimal reproduction project with BoxShape: physics-benchmark-box.zip

I ran a profiler on a 3.x debug build, here are the results:

Top functions (inclusive)

Top functions (self)

Flame Graph

Flame Graph (bottom-up)

perf data: perf.data.zip

[gg312]

Same issue on master 4dc8214

[TideGear]

Still an issue on v3.4.4.stable.official [419e713].

[brundonsmith]

I'm seeing this issue in v4.0.alpha13.official [59dcddc45]

[Calinou]

I recommend testing #63702 locally to see if it fixes this issue.

[fathonyfath]

It looks like that fixes the issue, however, now the bodies jitter and seems cannot go to its resting state. But I think that is out of the scope of this issue. Thanks!

I made new project for the 4.0 for the testing. On unrelated notes, the 4.0 default graphics already looking really good. Kudos to the team!

physics-benchmark-2.zip

[Calinou]

however, now the bodies jitter and seems cannot go to its resting state

See #62819 and #61827.

[fathonyfath]

however, now the bodies jitter and seems cannot go to its resting state

See #62819 and #61827.

Noted, since that is already tracked on a different issues, it means we can close this issue, right?

[Calinou]

Noted, since that is already tracked on a different issues, it means we can close this issue, right?

This issue should be kept open, as this is a different issue from #48587 (which is for kinematic bodies) and the linked PR hasn't been merged yet.

[peastman]

In this case, the jittering might be partly the fault of #63702. The MPR algorithm doesn't precisely determine the separation axis, and hence the collision point. It creates a portal defined by three directions and iteratively refines it. The way it was described in the original article, it stops as soon as it can prove there's a separating axis somewhere inside the portal. The article suggested a way to estimate approximate collision points. That's what I originally tried, but I found it didn't work with the collision resolution code in Godot. The collision points were too unstable, causing things to jump all over.

When I implemented it in Simbody we used a different approach. We needed very precise collision points for a variety of analytic shapes. So we used MPR to estimate the collision points, then followed with Newton iteration to refine them to numeric precision. But that requires colliding shapes to provide extra information that isn't available in Godot, like the radii of curvature at an arbitrary point on the surface.

So instead I settled on having it continue iterating with MPR until the portal is sufficiently small to give an accurate estimate of the axis. I empirically chose some criteria that seemed to work in my tests:

if (extra_iterations == 5 || (dir1.dot(dir2) > 0.995 && dir2.dot(dir3) > 0.995 && dir3.dot(dir1) > 0.995)) {

It's possible they're still a bit too loose. Try increasing the threshold on the dot products a bit, maybe to 0.999. You might also need to increase the limit on extra_iterations a little.

[Regrad]

Our team is porting the game from Godot 3.5 to Godot 4. We have discovered a huge physics issue in Godot 4. When a character collides with a concave body, there is a catastrophic performance degradation. This is especially pronounced when colliding with sharp corners.
You can watch it on video. I checked many times that the problem lies precisely in physics. Godot 3 Bullet didn't have this problem.

https://youtu.be/brtjvycMPFs

[peastman]

Can you create a minimal test scene that demonstrates the problem? I can profile it and see where the slowdown is coming from.

[Regrad]

Certainly. Now we have night, but tomorrow I will definitely assemble and send a project with a test scene where this bug can be observed. I'll add this fountain and a simplified version of the character there as an example.

[Regrad]

Test scene
test_level.zip

Test video showing how to get catastrophic performance degradation. To get the effect, you need to go into the wall in the indicated areas. Any monster stuck in such places makes the game impossible to play.
https://www.youtube.com/watch?v=-sA7heYETgg

[peastman]

Profiling shows that it spends about 90% of CPU time in gjk_epa_calculate_distance(), which is called from GodotCollisionSolver3D::concave_distance_callback().

Here is what it looks like to me. To find a collision between a concave mesh and any other shape it calls GodotConcavePolygonShape3D::cull(), which recursively searches the bounding volume hierarchy to find faces that might intersect the object. When it finds one it calls gjk_epa_calculate_distance(). That's a good method for complex shapes, but in this case it's two very simple shapes: a capsule and a face. GJK is a really inefficient way of detecting collisions in simple cases like that.

I think this relates to an issue we've discussed elsewhere, that test_body_motion() always uses GJK. I believe @reduz has been working on a new implementation that should be much faster. I'm not sure of the status of that.

A related note: for capsule-face intersections, SAT will probably be faster than GJK, but I think we can create an analytic implementation that's even faster (see https://wickedengine.net/2020/04/26/capsule-collision-detection/).

[akien-mga]

We're running out of time to solve this properly for 4.0 (release imminent), but this is high on the priority list for 4.1, together with various other physics issues.