dimforge / parry

2D and 3D collision-detection library for Rust.
https://parry.rs
Apache License 2.0
565 stars 100 forks source link

Fix normal direction for GJK ray casting inside non-solid shapes #183

Closed Jondolf closed 6 months ago

Jondolf commented 6 months ago

Objective

Many shapes like cylinders, cones, capsules, convex polyhedra, and convex polygons use support mapping and a variant of GJK for ray casting.

If the ray origin is inside of the shape and the shape is marked as non-solid (i.e. hollow), the ray casting method shifts the ray origin just outside of the shape and reverses the ray's direction before running GJK a second time. This acts as a way to find the hit point on the boundary as if the ray was to keep travelling inside the shape.

However, the actual final ray cast is still done from the outside of the shape, and the normal ends up pointing outward. This is not the expected result, as the specialized ray casting implementations for shapes like circles, rectangles, triangles, and so on return the normal pointing in the interior of the shape. This makes the ray casting behavior highly inconsistent between shapes, which could lead to critical and hard-to-debug bugs.

The normal should always be pointing in the interior of the shape for non-solid shapes when the ray origin is inside of the shape, even for GJK-based ray casts.

Solution

Simply flip the normal for the non-solid interior hits. I also made the expected behavior clearer in the RayIntersection docs.

Before: (see how the capsule behavior is different)

https://github.com/dimforge/parry/assets/57632562/33c49586-c2ba-44d5-bb27-0361f1d05f2e

After:

https://github.com/dimforge/parry/assets/57632562/3e39948c-a6f6-4f2c-89c8-5f7060cfe207

There is also some visible instability with the GJK-based ray casting due to GJK not converging on a solution, but attempting to fix that is out of scope for this PR.

sebcrozet commented 6 months ago

Good catch, thanks! I rebased the PR on main to fix the CI.