Large convex hulls produce incorrect contact manifolds

[Jondolf]

Hi! I'm having an issue in my physics engine bevy_xpbd where convex hulls with large faces can return invalid contact manifolds, which produces very buggy and explosive behavior. This also impacts rapier and bevy_rapier, so it is most likely an issue in parry.

bevy_xpbd:

2023-09-22.18-05-08.mp4

bevy_rapier:

2023-09-23.11-41-06.mp4

In these examples, the ground is a 20,000 x 20,000 convex hull, but even 500 x 500 has issues. However, smaller convex hulls like 30 x 30 don't really have any problems. Using f64 precision also helps. Other collider types like trimeshes also don't have issues even at much bigger scales.

When a faulty collision occurs, the contact normal is often flipped and the contact points are almost inverted (contact that should be at the bottom of the cube is at the top). This causes very large penetration depths and explosions.

I tried to track down where the issue is, and based on logs it looks like it often happens when this line returns GJKResult::ClosestPoints. Changing exact_dist to false helps a bit, but it causes other issues, and I think it only helps because it makes gjk return early (I think). I also logged normals, and the incorrect normals seem to be computed in gjk::closest_points, but I don't know the reason for those incorrect normals. Maybe the support map for the convex hull is wrong?

I can try to set up a repro specifically for parry if I can, but it's easiest to reproduce in e.g. bevy_rapier by just spawning some cubes onto a large flat convex hull and moving them around.

[Jondolf]

Here's code for reproducing the issue in bevy_rapier3d:

use bevy::prelude::*;
use bevy_rapier3d::prelude::*;

fn main() {
    App::new()
        .add_plugins((DefaultPlugins, RapierPhysicsPlugin::<()>::default()))
        .insert_resource(ClearColor(Color::DARK_GRAY))
        .insert_resource(Msaa::Sample4)
        .add_systems(Startup, setup)
        .add_systems(Update, movement)
        .run();
}

#[derive(Component)]
struct Cube;

fn setup(
    mut commands: Commands,
    mut materials: ResMut<Assets<StandardMaterial>>,
    mut meshes: ResMut<Assets<Mesh>>,
) {
    // Ground
    commands.spawn((
        PbrBundle {
            mesh: meshes.add(Mesh::from(shape::Box::new(2000.0, 0.1, 2000.0))),
            material: materials.add(Color::rgba(0.7, 0.7, 0.8, 0.3).into()),
            ..default()
        },
        RigidBody::Fixed,
        Collider::from_bevy_mesh(
            &Mesh::from(shape::Plane {
                // The larger this is, the worse the issues are
                size: 2000.0,
                subdivisions: 0,
            }),
            // Convex decomposition is similarly buggy for large colliders
            // since it produces a convex hull as well.
            // Manually creating the convex hull also doesn't help.
            &ComputedColliderShape::ConvexHull,
        )
        .unwrap(),
    ));

    let cube_size = 2.0;

    // Spawn cube stacks
    for x in -2..2 {
        for y in -2..2 {
            for z in -2..2 {
                let pos = Vec3::new(
                    x as f32 * (cube_size + 0.05),
                    y as f32 * (cube_size + 0.05),
                    z as f32 * (cube_size + 0.05),
                );
                commands.spawn((
                    PbrBundle {
                        mesh: meshes.add(Mesh::from(shape::Cube { size: cube_size })),
                        material: materials.add(Color::rgb(0.2, 0.7, 0.9).into()),
                        transform: Transform::from_translation(pos + Vec3::Y * 8.0),
                        ..default()
                    },
                    RigidBody::Dynamic,
                    Velocity::default(),
                    Collider::cuboid(cube_size * 0.5, cube_size * 0.5, cube_size * 0.5),
                    Cube,
                ));
            }
        }
    }

    // Directional light
    commands.spawn(DirectionalLightBundle {
        directional_light: DirectionalLight {
            illuminance: 20_000.0,
            shadows_enabled: true,
            ..default()
        },
        transform: Transform::default().looking_at(Vec3::new(-1.0, -2.5, -1.5), Vec3::Y),
        ..default()
    });

    // Camera
    commands.spawn(Camera3dBundle {
        transform: Transform::from_translation(Vec3::new(0.0, 12.0, 40.0))
            .looking_at(Vec3::Y * 5.0, Vec3::Y),
        ..default()
    });
}

fn movement(keyboard_input: Res<Input<KeyCode>>, mut query: Query<&mut Velocity, With<Cube>>) {
    for mut lin_vel in &mut query {
        if keyboard_input.pressed(KeyCode::W) || keyboard_input.pressed(KeyCode::Up) {
            lin_vel.linvel.z -= 0.15;
        }
        if keyboard_input.pressed(KeyCode::A) || keyboard_input.pressed(KeyCode::Left) {
            lin_vel.linvel.x -= 0.15;
        }
        if keyboard_input.pressed(KeyCode::S) || keyboard_input.pressed(KeyCode::Down) {
            lin_vel.linvel.z += 0.15;
        }
        if keyboard_input.pressed(KeyCode::D) || keyboard_input.pressed(KeyCode::Right) {
            lin_vel.linvel.x += 0.15;
        }
    }
}

It produces this: (with debug-render)

bevy-rapier-convex-hull-issues.mp4

[aevyrie]

In these examples, the ground is a 20,000 x 20,000 convex hull, but even 500 x 500 has issues.

IIRC most game worlds without floating origin systems need to be smaller than ~2km a side to prevent jittering during rendering at the extents. If the units are meters here, I don't think this is a problem that can be solved without chunking colliders into more reasonable sizes. or using something custom for e.g. an infinite plane.