Faster algorithm for mesh collision detection

[peastman]

This is a first draft of a fix for #48587, very slow performance for collision detection between large meshes. The problem comes from the algorithm used in _collision_convex_polygon_convex_polygon(), which scales as O(n^3) in the size of the meshes. I replaced it with a different algorithm, Minkowski Portal Refinement. The code is based on an implementation I wrote some years ago for another open source project, Simbody.

I tested it on the scene from #62689, which involves a few bouncing objects represented by high resolution meshes. With the current algorithm, the program hangs and needs to be force quit. It goes into a loop that technically isn't infinite, but might as well be. The new algorithm handles it effortlessly with no perceptible drop in frame rate.

A few notes about the code.

• At the moment I'm ignoring the margin arguments, because I wasn't completely certain how to interpret them. Should I treat it as convolving each object with a sphere whose radius equals the margin?
• This routine isn't specific to meshes. It can be used for any convex shapes. I suspect it will also be faster than the current routines for mesh-primitive collisions, though I haven't tested yet. If so, those routines can be removed. For collisions of simple primitives, the analytical solutions will of course be faster.
• When I wrote the original version of the code, Simbody was distributed under the MIT license. It later moved to the Apache license. To avoid licensing issues for Godot, I used the original MIT version. There haven't been any meaningful changes to this routine in any case.
• There likely is room for further speedup by changes to get_support() and project_range(). For a large mesh, there are faster ways to do it than looping over every vertex. That's an independent change that can wait until later.

Bugsquad edit: See also https://github.com/godotengine/godot/pull/56393.

[akien-mga]

When I wrote the original version of the code, Simbody was distributed under the MIT license. It later moved to the Apache license. To avoid licensing issues for Godot, I used the original MIT version. There haven't been any meaningful changes to this routine in any case.

For the record, you could use either version. Since you are the original author, you have two options to contribute this code:

• Original license which should be included in the code, and so either Apache or MIT is fine, we already have third-party dependencies using either.
• Relicense the code you're contributing (for which you're copyright holder) under Godot's own license, so no additional license header is needed.

It's up to you which form you prefer, both are ok.

[peastman]

The copyright technically belongs to "Stanford University and the Authors". So although I'm the sole author, it seems best not to try to relicense it.

[peastman]

I have a question about the existing collision detection code. I'm looking into making this function more generic so it can be used for more types of convex objects, not just meshes. A complication is the fact that SeparatorAxisTest is templatized on the classes of the two objects that are colliding. However, I can't see any reason for it to be. As far as I can tell, the only thing it ever does with the objects is call virtual functions defined by the parent GodotShape3D class: get_supports() and project_range(). Would it be reasonable to remove those two template arguments and have it declare the objects as GodotShape3D*? Or are they there for a reason I've missed?

[peastman]

I tried making the change described above and everything seems to compile and work fine. That allows the MPR routine to work with any kind of shapes, not just meshes. I also increased the iteration threshold to eliminate the jittering described in #57313. I then tried profiling a series of tests to see how its performance compares to the existing SAT routines for mesh-primitive collisions.

In each test, a single object falls onto a single other object and either stops or rolls off. The falling object is a mesh with either 10, 22, or 102 vertices. The object it falls onto is a primitive, either a sphere, capsule, or box. I record the mean time in microseconds taken by calls to the relevant _collision_X_Y() function. Here are the results.

Primitive Shape	Mesh Vertices	SAT (us)	MPR (us)
sphere	10	26.9	8.5
capsule	10	28.9	9.6
box	10	38.4	13.2
sphere	22	39.9	8.9
capsule	22	39.6	11.1
box	22	86.0	14.2
sphere	102	250.6	22.0
capsule	102	562.4	20.7
box	102	432.2	40.0

For small meshes MPR is about 3x faster than the existing routine. For larger meshes it increases to more than 10x faster. The difference should be even larger for still larger meshes. So I'm going to replace those routines as well.

[reduz]

This is very interesting. I was thinking about optimizing this by converting to GJKEpa for cases where there are too many points. I am familiar with MPR but have not used it much, how does it stack up against it? In my experience these methods work very well for convex polyhedra because they give you exact results (unlike stuff with curved surfaces). The margin is basically just an extra margin added to the collision, so its no longer polyhedra, but this is only really used for move_and_slide, not the physics engine.

The other optimization I wanted to make is using octahedral encoding for the support map, for cases where where the amount of points is quite large, this should massively improve the support function.

[reduz]

@peastman Regarding your question, its done this way original mostly so the project_range function can be inlined, but seeing the code it seems this is not the case any more in 3D for some reason.

[peastman]

I'm not sure how GJK and MPR compare for speed. When people compare them, the main differences they cite are that GJK is much more complicated to implement, and that it's less numerically robust. I'd guess they're roughly competitive in speed, but that isn't based on direct experience.

Should I ignore the margin, or treat it as convolving the mesh with a sphere? I'm still a bit confused about its exact meaning. Here is how the margin setting is described in the UI:

The collision margin for the shape. Used in Bullet Physics only.

Collision margins allow collision detection to be more efficient by adding an extra shell around shapes. Collision algorithms are more expensive when objects overlap by more than their margin, so a higher value for margins is better for performance, at the cost of accuracy around edges as it makes them less sharp.

That seems to imply this just relates to an optimization in Bullet, but I'm not quite sure if that's true.

The other optimization I wanted to make is using octahedral encoding for the support map

That sounds like a very good plan.

[akien-mga]

Should I ignore the margin, or treat it as convolving the mesh with a sphere? I'm still a bit confused about its exact meaning. Here is how the margin setting is described in the UI:

The collision margin for the shape. Used in Bullet Physics only.

The margin is indeed something that was only used by the Bullet implementation, now removed. It should likely be removed from the API, unless we need to keep it to enable easier re-implementation of Bullet and other similar libraries as GDExtension. I mentioned this when removing Bullet in #58946 - you can see how it was used in the removed code.

So while I'm not familiar with this code, I think you can safely ignore it now.

[reduz]

When people compare them, the main differences they cite are that GJK is much more complicated to implement, and that it's less numerically robust. I'd guess they're roughly competitive in speed, but that isn't based on direct experience.

I really have not done any of this in probably around 15 years, so my understanding of this from back then is as follows (give or take).

• These algorithms are approximations for finding the origin of a Minkowski difference, which can be interpreted as the two closest points towards which a pair of convex shapes can be separated (minimum separation axis)
• As such they are not exact, but they work very well with convex polyhedra.
• Because they are not exact, physics engines that rely on this instead of SAT use a two step narrow phase. The first adds a small margin and use GJK to test. As in most cases when collision is almost at rest the penetration depth is very small, GJK with a margin is enough and its very fast and precise. When the penetration depth exceeds the GJK margin, then the algorithm switches to EPA or MPR.
• So, both EPA and MPR are deep penetration solving algorithms. They are not as exact, but as you don't need a lot of precision for this its ok that they are inexact, as afterwards GJK will fix things.

In my experience from back in the time, EPA was very very good. It was not perfect and its slower, but it did a great job and it could be used on its own for polyhedra because it gave exact results. MPR I found to be not as good, but then again still good for deep penetration if used alongside GJK and faster.

This is why using MPR for this seems like its probably not going to produce precise collision results. But then again, it has been a looooooong time since I did any of this and my memory may not be great.

Should I ignore the margin, or treat it as convolving the mesh with a sphere? I'm still a bit confused about its exact meaning.

Convolving the mesh with a sphere is correct.

[peastman]

Here is how I understand them (also based on reading I did a long time ago, so my memory of GJK especially is quite rusty). There are two different problems we're trying to solve.

1. Determine whether the two objects are in contact.
2. If they are, determine the direction along which they most deeply interpenetrate.

GJK and MPR both solve the first one exactly. They give a robust answer about whether the objects are colliding. GJK doesn't even attempt to solve the second problem. That's why it's followed by another algorithm like EPA when it detects a contact. MPR gives an approximate answer to the second problem. It determines that the contact direction is inside the portal formed by three directions. Each iteration makes the portal smaller, so you can get an arbitrarily accurate answer by doing more iterations.

The margin is indeed something that was only used by the Bullet implementation, now removed.

Convolving the mesh with a sphere is correct.

I'll let the two of you hash this out. :)

[rburing]

I'll let the two of you hash this out. :)

They're both correct, talking about different margins: there is the margin property of Shape3D which was only used by Bullet and is currently unused in master, and there is a margin which is passed around as a parameter to some functions in the physics server, which has the effect of convolving the relevant shape(s) with a sphere of that radius.

[peastman]

Got it, thanks. How can I test it? In what situations will a non-zero margin be passed?

[peastman]

I implemented the margin option. I believe this PR is now feature complete.

[reduz]

This is an amazing work! I am still a bit in doubt about which algorithm to use to optimize this. Next month we will have our working becnhmark server and after Beta a lot of focus will be put on creating proper benchmarks and doing optimization for them.

I will probably come back to this by them so we can compare a few different approaches and eventually decide. In either case feel free to pass by the #physics channel in chat.godotengine.org for more specific physics discussion!

[aaronfranke]

@peastman There is interest from core contributors in this PR (ex: see positive comments from @reduz above), but it needs to be rebased and squashed. See PR workflow for details.

The relationship between this PR and #67481 also needs to be clarified. Does #67481 supersede this? Regardless, it would likely be helpful to rebase this so that it may be used as a reference.

[peastman]

I'm not sure what the status of #67481 is. It copied the MPR collision routine from this PR, so possibly it was meant to supersede it. But it hasn't had any activity in a while, so I don't know if it's still active or if it's been abandoned.

The core of this PR is _collision_generic(). It's mostly self contained and should need little or no updating. There've been a lot of changes to the surrounding code that invokes it which will create lots of conflicts if we try to merge the current master branch into this one. It might be easier to create a new PR, copying over that routine and making other changes as appropriate. That might be exactly what #67481 is meant to be. I'm just not sure.