time_of_impact_support_map_support_map returns None when it shouldn't with very specific inputs

[bolshoytoster]

I'm trying to get the TOI between a moving square (Cuboid) and a stationary line (Segment), so I'm using time_of_impact_support_map_support_map. This works perfectly fine most of the time, but I realised that I keep getting some Nones, when there definetely should be a collision.

These Nones always appear for certain inputs (the square's initial position/velocity). For example, if the square starts at (15.689465, 54.00709) with velocity (0.0081385, -0.999966), it returns None, but if you add or subtract .000001 from any of those values, it returns Some.

I have created an MRE:

fn main() {
	let vel = Vector2::new(0.0081385, -0.999966);
	let segment = Segment::new(Point2::new(1., 1.), Point2::new(124., 1.));
	let cuboid = Cuboid::new(Vector2::repeat(2.));

	// These two work properly
	assert!(
		time_of_impact_support_map_support_map(
			&Isometry2::translation(15.689464, 54.00709),
			&vel,
			&segment,
			&cuboid,
			f32::INFINITY,
			true,
		)
		.is_some()
	);

	assert!(
		time_of_impact_support_map_support_map(
			&Isometry2::translation(15.689466, 54.00709),
			&vel,
			&segment,
			&cuboid,
			f32::INFINITY,
			true,
		)
		.is_some()
	);

	// This one fails
	assert!(
		time_of_impact_support_map_support_map(
			&Isometry2::translation(15.689465, 54.00709),
			&vel,
			&segment,
			&cuboid,
			f32::INFINITY,
			true,
		)
		.is_some()
	);
}

This obviously also happens with time_of_impact, and also with a Polyline instead of a single Segment.

I narrowed down the point that the wrong one diverges from the correct ones to two lines in minkowski_ray_cast in src/query/gjk/gjk.rs:

parry/src/query/gjk/gjk.rs

Lines 350 to 351 in e57762f

	let _ = simplex.add_point(support_point.translate(&-curr_ray.origin.coords));
	proj = simplex.project_origin_and_reduce();

In the correct versions, at the end of the two lines, simplex.dimension() == 1, however, in the wrong version, it is 2, causing the function to return None early.

I, however, have no idea how simplexes work; so I couldn't go any further. Hopefully someone else can figure this out.

This issue also exists in ncollide.

[dubrowgn]

Sounds like this could be the same root cause as #107.

[Jondolf]

minkowski_ray_cast is used for both support-mapped time of impact queries and ray casts, so this also affects local_ray_intersection_with_support_map_with_params, which is used for ray casting for at least cylinders, cones, capsules, convex polyhedra, and convex polygons. This can be seen in #183 as the ray hit "flickering" for the capsule as the algorithm returns None in cases where it clearly shouldn't.

It seems like the issue here is essentially that GJK (or in this case the ray cast onto the Minkowski difference) uses a tolerance value that is too strict for checking whether the origin is contained within the CSO for the simplex of the maximum dimension. In other words, for one of the termination criteria, the algorithm is too strict for what it considers to be a valid result, which causes misses even in cases where there should be a clear hit.

The specific line in question is this min_bound check:

parry/src/query/gjk/gjk.rs

Lines 353 to 359 in e19f9f0

	if simplex.dimension() == DIM {
	if min_bound >= _eps_tol {
	return None;
	} else {
	return Some((ltoi / ray_length, ldir)); // Point inside of the cso.
	}
	}

Making the tolerance larger by multiplying it by 10 seems to fully fix the issue for me in my demo. I am unsure whether this is a "correct" solution however, and the scale of the shapes in the scene could potentially affect results.