godot: Physics 3D SAT solver produces incorrect collision normals between large sphere and capsule
Godot version
4.0 beta 10
System information
Windows 10, NVidia 2070, Vulkan Mobile
Issue description
A human-sized (0.4 x 1.8 x 0.4) CapsuleShape3D on top of a large (50 x 50 x 50) SphereShape3D produces unstable normals when performing a move_and_collide down.
In discussions on the physics channel of the Godot Contributors Chat, the SAT solver isn’t a good choice when the exact collision information can be solved analytically.
The problem with the SAT solver is that it ends up producing two collision points A and B on the two colliding shapes, and then the vector between them is used to build the normal. The problem is that A and B end up being extremely close (1e-4 distance), so normalizing the vector results in a large amplification of any numeric errors.
The current API for the _collision_<shape1>_<shape2>() functions can only report their findings via the _CollectorCallback API, and that only allows for providing the A and B points. Instead the collision functions should also have a means of providing exact analytic collision information if available.
Steps to reproduce
Construct a scene consisting of a large 50m sphere with a capsule shape resting on top of it. Then perform a move_and_collide down and print the collision normal vector.
Minimal reproduction project
This demo walks a capsule around the top of a large sphere drawing the normal vector. The vector flickers between the correct normal and weird unstable normals:
About this issue
- Original URL
- State: closed
- Created 2 years ago
- Reactions: 3
- Comments: 18 (17 by maintainers)
@peastman @Malcolmnixon Awesome work troubleshooting this guys! This has been a major major hard-stoppage point for me and several others I know attempting open-world projects in Godot, was definitely a bit of a demotivator, but seeing your efforts here gives me some optimism we may see some results soon!
It seems that SAT is good for collision “detection” but sucks for contact “determination”. Using SAT requires numeric expressions which involve the size of the objects and the margin between them; and IEEE 32-bit floats don’t have the significant digits for it.
I can’t currently conceive of a solution to SAT contact determination., The best you can do is calculate the most accurate axis possible, but you’re still relying on the get_supports() to produce points on each object that are close enough to make sense, and that just doesn’t seem to be a dependable operation.
All I can think of doing at this point is replacing the SAT collision detection/determination code with analytic solutions in as many places as possible.
I’ve been debugging the cylinder-cylinder case. It seems to just be numerical precision. I compared two successive steps, one on which it successfully finds the collision and one on which it doesn’t. Between the two steps, the moving cylinder’s z coordinate changes by a tiny amount, from 1.096738 to 1.109235. That leads to a tiny change in the axis direction, from (0, 0.999941, 0.01086) to (0, 0.999983, 0.005893).
That axis gets passed to the large cylinder’s
get_supports()function. It returns an edge that will get passed to_generate_contacts_edge_circle(). The tiny change in axis leads to a large change in the edge’s z coordinate, from 1.085994 to 0.589262. That edge is outside the moving cylinder and no contacts get generated.In order to debug the physics problems further, I created a test project that rolls different CharacterBody3D shapes over different StaticBody shapes. I’ve attached a zip - PhysicsCollisionTest.zip, but the project can also be accessed at https://github.com/Malcolmnixon/PhysicsCollisionTest.
Roughly 43% (18 out of 42) collision tests show failures.
The exact results are as follows:
1 - Unstable normals 2 - No collisions 3 - Periodic collision misses 4 - Invalid collision positions
Agreed. Up to you whether you want to include the optional normal in the current PR, or get it merged first then do it in a separate PR. I can add it if you want or leave it to you, whatever you prefer.
Sphere-box is also an easy one to do analytically. And I think that box-capsule can be done by checking against each of the twelve edges of the box (each one is a capsule-capsule test), plus testing the ends of the capsule against the full box (each is a sphere-box test).