Polyline-Polyline intersection fails since 0.22

[s-nie]

The following code started failing with the 0.22 release. It seems that polyline intersections are not detected reliably anymore.

use parry2d_f64::{
    math::{Isometry, Point},
    query::contact,
    shape::Polyline,
};

fn main() {
    // Large closed rectangle
    let vertices = [
        [-5.0, 20.0],
        [-45.0, 20.0],
        [-45.0, -20.0],
        [-5.0, -20.0],
        [-5.0, 20.0],
    ];
    let line1 = Polyline::new(vertices.into_iter().map(Point::from).collect(), None);

    // Small closed rectangle
    let line2 = Polyline::new(
        [
            [-1.0, -1.0],
            [4.0, -1.0],
            [4.0, 1.0],
            [-1.0, 1.0],
            [-1.0, -1.0],
        ]
        .into_iter()
        .map(Point::from)
        .collect(),
        None,
    );

    let result = contact(
        &Isometry::default(),
        &line1,
        // On the large rectangle
        &Isometry::new([-25.0, -20.0].into(), -1.57),
        &line2,
        0.0,
    );

    // Fails since 0.22.0
    assert!(result.is_ok_and(|c| c.is_some()));
}

[wlinna]

I tested this with parry2d (f32), and it happens there too.
I found this bug report, because my application has regressed severely since upgrading parry to 0.22 or higher. Though I haven't pinpointed it to Polyline-Polyline intersection yet, I do use them a quite a lot.

I will try to simplify this test case further and add a visualization this week.

[wlinna]

The test can be simplified by removing the rotation from the line2's Isometry. I also made the large rectangle smaller to make the screenshots smaller. Here are the screenshots of the simplified test:

Rectangles before transformation:

Rectangles with the transform applied

I made an interesting discovery. If I pretransform the vertices of line2 with line2_transform, the test passes. However, if I don't pretransform and instead give line2_transform to contact function, the test fails.

I debugged the code and it turns out that in contact_with_shape of CompositeShapeRef the intersect_aabb does not produce any results and the body of the for loop never executes.

  let ls_aabb2 = shape2.compute_aabb(pose12).loosened(prediction);
  let mut result = None::<(u32, Contact)>;

  for part_id in self.0.bvh().intersect_aabb(&ls_aabb2) {
...

Here is the simplified test code

 #[test]
    fn test_parry_segment_intersection2() {
        use rapier2d::parry::{
            math::{Isometry, Point},
            query::contact,
            shape::Polyline,
        };

         // Large closed rectangle
        let vertices = [
            [0.0, 0.0],
            [-10.0, 0.0],
            [-10.0, -10.0],
            [0.0, -10.0],
            [0.0, 0.0],
        ];
        let line1 = Polyline::new(vertices.into_iter().map(Point::from).collect(), None);

        let line2_transform = Isometry::new([-5.0, -10.0].into(), 0.0);

        // Small closed rectangle
        let line2 = Polyline::new(
            [
                [-1.0, -1.0],
                [4.0, -1.0],
                [4.0, 1.0],
                [-1.0, 1.0],
                [-1.0, -1.0],
            ]
            .into_iter()
            .map(Point::from)
            // PRETRANSFORM VERTICES
            // .map(|p| line2_transform.transform_point(&p))
            .collect(),
            None,
        );

        let result = contact(
            &Isometry::default(),
            &line1,
            // On the large rectangle
            // IF VERTICES HAVE BEEN PRETRANSFORMED
            // &Isometry::default(),
            &line2_transform,
            &line2,
            0.0,
        );

        // Fails since 0.22.0
        assert!(result.is_ok_and(|c| c.is_some()));
    }

[s-nie]

Thanks for the investigation! Do you think it could be the same issue that is fixed in #388?

[wlinna]

It seems relevant, and the discovered root cause would explain why including a transform breaks contact. I might be able to run this test on that PR tomorrow. Hopefully even my own program.

Thanks for pointing out!

[dog-molecule]

That would be great! I was only able to test the fix in Godot, but yes, I believe you're having the same issue, so it should fix it

[wlinna]

Yeah, the PR fixed this issue. I was going to suggest adding the unit test in the PR, but it was merged already. Thanks for fixing!

(Unfortunately for me and my application, my program still exhibits the same regressions since 0.22, and I need to figure out what causes them)