rustgd / collision-rs

A collision extension to cgmath
Apache License 2.0
124 stars 24 forks source link

Weird Rectangle-ConvexPolygon collision result #115

Open hayashi-stl opened 4 years ago

hayashi-stl commented 4 years ago

If we define a rectangle and a complex polygon along with their transforms as such:

macro_rules! vec_points {
    ($($points:tt),*) => {
        vec![$(Point2::new $points),*]
    };
}

let r = Rectangle::new(0.75, 1.0);
let p = ConvexPolygon::new(vec_points![(0.5, 0.5), (-0.5, 0.5), (-0.5, -0.5)]);

let r_t = Matrix3::new(1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.858333333333344, 0.0, 1.0);
let p_t = Matrix3::new(1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0);

and then do an intersection test as such:

let gjk = GJK2::new();
let inter = gjk.intersection(&CollisionStrategy::FullResolution, &r, &r_t, &p, &p_t);
println!("Intersection: {:?}", inter);

the resulting contact is:

Intersection: Some(Contact { strategy: FullResolution, normal: Vector2 [1.0, 0.0], penetration_depth: 1.733333333333344, contact_point: Point2 [0.4904761904761967, 0.5], time_of_impact: 0.0 })

From my previous tests, this should have the normal and contact point on the rectangle, but the normal is pointing right though it is on the left of the rectangle. In addition, the penetration depth is a whopping 1.73, which shouldn't be possible because neither shape is that long.

hayashi-stl commented 4 years ago

It seems like the origin is contained by the simplex with just the first 2 support points. That's an edge case

hayashi-stl commented 4 years ago

And the culprit is a call to triple_product in SimplexProcessor::reduce_to_closest_feature that returns a vector that is approximately vec2(-8.88e-16, 0.0). The x value is about 4 times f64::EPSILON, which makes the ulps_eq! call comparing it to the zero vector to return false. Maybe we should figure out how bad it can get and relax the comparison?