Contact query giving incorrect result for Frustums

[Davidster]

Hello!

First of all: thank you for the incredible library 😄

I am experiencing some unexpected behaviour and was wondering if someone could help me troubleshoot it. I want to test if two frustums are intersecting but it seems to be producing inconsistent results as can be seen in the video below, where I am showing the left frustum in green if I get Some(Contact) back from rapier3d::parry::query::contact::contact:

frustum_intersection_jitter_2.mp4

Here is how I am implementing the test:

impl FrustumDescriptor {
    pub fn frustum_intersection_test(
        &self,
        other: &FrustumDescriptor,
    ) -> Option<rapier3d::parry::query::contact::Contact> {
        rapier3d::parry::query::contact::contact(
            &rapier3d::na::Isometry::identity(),
            &self.to_convex_polyhedron(),
            &rapier3d::na::Isometry::identity(),
            &other.to_convex_polyhedron(),
            0.0,
        )
        .unwrap()
    }

    pub fn to_convex_polyhedron(&self) -> ConvexPolyhedron {
        let points: Vec<_> = self
            .to_basic_mesh()
            .vertices
            .iter()
            .map(|vertex| Point::from(vertex.position))
            .collect();
        ColliderBuilder::convex_hull(&points)
            .expect("Failed to construct convex hull for frustum")
            .build()
            .shape()
            .as_convex_polyhedron()
            .unwrap()
            .clone()
    }
}

I'm using the same to_basic_mesh() function to display the frustum in my debug setup as in the video, so I'm quite sure the vertices are OK. For full details on the implementation you can check out this commit

---

Update: added unit test

I've added a unit test in my fork of parry, it can be seen here. Below is a screenshot with a visualisation of the two frustums which I copied from my engine directly into the test:

The test fails despite confirming that one point of the left frustum lies inside the right frustum:

test geometry::epa3::cuboid_cuboid_EPA ... ok
test geometry::trimesh_intersection::trimesh_plane_multi_intersection ... ok
test geometry::trimesh_trimesh_toi::trimesh_trimesh_toi ... ok
test geometry::cuboid_ray_cast::shape_ray_cast_points_to_surface ... ok
test geometry::convex_hull::test_complex_convex_hull ... ok
test geometry::convex_polyhedra_contact::convex_polyhedra_contact ... FAILED

failures:

---- geometry::convex_polyhedra_contact::convex_polyhedra_contact stdout ----
thread 'geometry::convex_polyhedra_contact::convex_polyhedra_contact' panicked at 'assertion failed: contact.is_some()', crates/parry3d/tests/geometry/convex_polyhedra_contact.rs:57:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    geometry::convex_polyhedra_contact::convex_polyhedra_contact

test result: FAILED. 19 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.37s

[Davidster]

Update: added unit test

[Davidster]

From what I can tell this is an issue with the epa algorithm as gjk is returning a GJKResult::Intersection, which causes a fallback onto epa for trying to find the contact points and then it fails to do so in the unit test I added. I guess it's also possible that the simplex reused from gjk is bad. epa is hitting the max iteration check of niter > 10000 at which point I saw in the debugger that there were plenty of vertices and deleted faces:

I currently don't need the contact points, all I need is to know that there is an intersection so the intersection test is good enough for me at the moment:

pub fn frustum_intersection_test(&self, other: &Frustum) -> bool {
    rapier3d::parry::query::intersection_test(
        &rapier3d::na::Isometry::identity(),
        &self.to_convex_polyhedron(),
        &rapier3d::na::Isometry::identity(),
        &other.to_convex_polyhedron(),
    )
    .unwrap()
}

[Davidster]

After further investigation (and producing a failing case with intersection_test), I eventually tried with f64 and it fixes the intersection_test failing case as well as the contact test I mentioned above. That said, I still get many jitters with the contact query even in f64, the behavior is still similar to the original video I posted.

For now I will switch to rapier_f64/parry_f64 and just use the intersection_test which seems very stable in f64 mode.

[Davidster]

Here is my second failing unit test for intersection_test:

https://github.com/Davidster/parry/blob/4edb6863635adf39f2b937da31ac4a82a12428b8/crates/parry3d/tests/geometry/convex_polyhedra_intersection.rs

[Ughuuu]

Ok, was looking into this a bit more and read a little bit about EPA algorithm. It appears the EPA algorithm can go indefinitely as long as a better result is found (which is not the case here, at least for me it is not).
The distances it finds for me are:

11.5537109
9.600317
9.43643188
9.43630599

9.43630981

As you can see, the last one is an increase in distance, so it did not find a better one. Not sure if EPA algorithm ensures that we find a better distance every iteration or not, in which case the algorithm could just stop iterating if it finds a worse distance.

Either way, 10000 iterations seem like a very large number. Maybe either a smaller number, eg 20, 50, or something based on the total polygon vertices(eg vertices * 5 or so). Or have it configurable.

Also, if it does stop in that while there after a number of iterations, it should still return the contact, as it did find "something". Right now it returns None, which causes this issue.