Kinematic/Character bodies cause slowdown/crash when colliding with convex collision shapes

[Zireael07]

Godot version:
Godot 3.3.

OS/device including version:
Linux Manjaro, Intel Kaby Lake

Issue description:
Noticeable slowdown when a kinematic body collides with stuff. I managed to "manage" most of it by a) optimizing the collision shape of the AI and b) reducing the number of "slides" attempted to 1. (I tried to change the physics to move_and_collide() but failed :( I am also looking at kinematic mode rigidbodies as a possible solution - I really like how smooth movement/AI code are with kinematic bodies as opposed to VehicleBody )

This is Bullet physics BTW - if you change to Godot physics and collide with a building, the game freezes, no output in log.

Cars: kinematicbody3d with a box collision shape
Ground: staticbody with a box collision shape
Buildings and some part of the road: convex collision, autogenerated (I will likely try replacing those with simpler shapes next)

Steps to reproduce:
Run the project, drive around. The fastest way to trigger AI crashing into stuff is to start a race (red flag on minimap, red marker on ground) because the AI crash into stuff after crossing finish line (unfinished [pun intended] AI handling xD)

Minimal reproduction project:
Not minimal, because it takes several AI going around and crashing into obstacles for stuff to happen, but:
https://github.com/Zireael07/FreeRoamRoguelikeRacerPrototype

master branch: drops to single digits when an AI or two crash into stuff
develop: drops to 20-ish fps

@Calinou and whoever else told me to make a new issue

[pouleyKetchoupp]

Does it happen with 3.2.3 as well, or just 3.3?

[Zireael07]

Looks like yes, it's the case in 3.2.3, too:

The freeze with Godot Physics is also present in 3.2.3.

[pouleyKetchoupp]

Note for junior job:
Fixing the issue might require experience with physics and could be difficult for a beginner, but if anyone is interested in learning the basics of debugging, helping with the first steps of investigation would be great.

Identifying the issue seems to be easier with Godot Physics, since it's a complete freeze (and it's likely to have a similar cause as Bullet). Here's what can help identifying the issue:

• Build the 3.x branch locally in debug configuration
• Use an IDE with a debugger like Visual Studio or VS Code
• Make sure the minimal project is set to use Godot Physics
  (Project Settings > Physics > 3D > Physics Engine > Godot Physics)
• Run the minimal project using a debugger and try to reproduce the issue
  (command line: --path c:/path_to_project_folder)
• When the game freezes, pause the execution in the debugger
• Check the call stack on the main thread and post it here

[Zireael07]

Note: for the freeze, it's enough for you (the player) to collide with a building, so it can be trivially reproduced. It doesn't appear to cause the slowdown the AI do cause, possibly because the player won't keep trying to drive ahead once crashed or possibly because there's only one of you the player around ;)

EDIT: I wish I knew how to compile Godot on Linux, because I have VS Code and could probably help out on one of the afternoons after the day job is done...

[pouleyKetchoupp]

@Zireael07 Thanks for the extra information!

About compiling godot: it's not too complicated. You would be very welcome to give it a try :)
https://docs.godotengine.org/en/stable/development/compiling/compiling_for_x11.html

[Zireael07]

Great, I managed to compile on first try (turns out I only needed scons, all the rest was already present on my Manjaro) and I managed to get VS Code debugger to work on the first try, too.

This is for the Godot Physics freeze.

[Zireael07]

So, whoa, 7000+ vertices in the convex hull for the building tell me some things a) I can't wait for the #48533 and b) I have to replace the convex hull with a box shape ASAP ;) and c) the godot remote tree DOES NOT tell me how many vertices are in autogenerated convex hull because if it did, this whole issue wouldn't have happened as I wouldn't have used convex in the first place and d) I think there's already an issue open about convex hull not simplifying?

[pouleyKetchoupp]

@Zireael07 Good job on finding the issue! In your specific case, since it's a building you can try to just use a concave shape instead, it handles large amounts of vertices much better in both Bullet and Godot Physics.

In general, I agree some extra information for this case would be useful. I think a warning on the tree node when using a convex hull with too many vertices could help, and possibly some read-only information in the inspector to see the number of vertices.

[Calinou]

I think a warning on the tree node when using a convex hull with too many vertices could help, and possibly some read-only information in the inspector to see the number of vertices.

What would be the maximum number of vertices to consider as "reasonable" for a single convex shape? Something like 200?

[pouleyKetchoupp]

I think a warning on the tree node when using a convex hull with too many vertices could help, and possibly some read-only information in the inspector to see the number of vertices.

What would be the maximum number of vertices to consider as "reasonable" for a single convex shape? Something like 200?

The best would be to test with both Bullet and Godot Physics, and maybe make the threshold dependent on the physics engine (at least for 3.x) since Bullet has a better algorithm for this case.

Godot Physics could also use some optimization for convex collision, because right now the performance cost probably grows linearly with the number of vertices.

[Zireael07]

Bullet definitely has a better algorithm, since all it did was slow down for that extreme collision shape xDDD

A drastic optimization of the collision shape (a box shape instead, or for future polygonal base buildings, possibly a hand-specified shape) fixed the issue, no more freezes, no more slowdowns <3

Leaving the issue open because Godot needs to warn/inform users of badly generated (overly complex, something like 200 vertices Calinou suggested or maybe 500 because it's a nice round number) convex shapes and because well, Godot physics shouldn't freeze even in such an extreme case (abort the loop after more than x iterations, maybe?)

EDIT to add: No, wait, one more thing - I am almost 100% certain remote scene tree does NOT display yellow triangle warnings, since it took me so many months to finally twig to the fact Plane shape is being deprecated, and since I've forgotten to add a static body and/or a shape resource for a collision shape several times, and all of those (collision shape without shape, collision shape without body, body without shape) produce yellow triangles in editor. (Most of the collisions are generated from script, either via node.create_convex_collision() or by manually assigning collision shape nodes and/or resources)

[pouleyKetchoupp]

EDIT to add: No, wait, one more thing - I am almost 100% certain remote scene tree does NOT display yellow triangle warnings, since it took me so many months to finally twig to the fact Plane shape is being deprecated, and since I've forgotten to add a static body and/or a shape resource for a collision shape several times, and all of those (collision shape without shape, collision shape without body, body without shape) produce yellow triangles in editor. (Most of the collisions are generated from script, either via node.create_convex_collision() or by manually assigning collision shape nodes and/or resources)

It's true editor warnings are not really useful for runtime-generated shapes. It would make sense to also have these warnings in the log when the shapes are created at runtime.

[peastman]

If it's ok, I'd like to investigate this and see whether I can make collision detection fast with large convex shapes. No promises, but I think there's a lot of room for optimization.

It looks to me like the problem is that project_range() and get_support() in GodotConvexPolygonShape3D are both implemented through a full loop over vertices. That makes the cost linear in the size of the mesh. By doing some precomputation, we ought to be able to avoid that. This paper suggests recording the neighbors of each point on the convex hull and using hill climbing. Or we could build some kind of spatial subdivision structure to limit which vertices need to be looped over. The challenge is to make it fast on large meshes without making it slower on small ones. The simplest solution might be to use the simple loop for small meshes, and something more sophisticated when the number of vertices is above a threshold.

[peastman]

The real problem is _collision_convex_polygon_convex_polygon(). It contains a series of loops like this.

godot/servers/physics_3d/godot_collision_solver_3d_sat.cpp

Lines 2132 to 2144 in ecc86af

	for (int i = 0; i < edge_count_A; i++) {
	Vector3 e1 = p_transform_a.basis.xform(vertices_A[edges_A[i].a]) - p_transform_a.basis.xform(vertices_A[edges_A[i].b]);
	for (int j = 0; j < edge_count_B; j++) {
	Vector3 e2 = p_transform_b.basis.xform(vertices_B[edges_B[j].a]) - p_transform_b.basis.xform(vertices_B[edges_B[j].b]);
	Vector3 axis = e1.cross(e2).normalized();
	if (!separator.test_axis(axis)) {
	return;
	}
	}
	}

This one loops over every pair of edges. There also are loops over all pairs of vertices and all vertex/edge pairs. Inside each loop it calls separator.test_axis(), which itself loops over all vertices in each mesh. So given two meshes that each have N vertices, the cost of this routine is O(N^3). We can definitely do better! I'll try some experiments.

[MagickPanda]

hmmm the convex object I was using is rather simple, I didn't check exact number of vertices,but I think it only has like few hundred at max, since the model I used to generate convex is just a lowpoly plane model with minimal faces.

[Zireael07]

@MagickPanda the model used in this original issue was a lowpoly boxy building, you would think the convex shape would be simple but nope, lots of vertices!

[AThousandShips]

In this case it is actually just 28 vertices for the convex shape, so this affects even low-poly convex shapes