Add arc/semicircle collider

[alice-i-cecile]

This is a useful primitive, that can be checked much more quickly (and accurately) than the equivalent polyline or convex hull.

It's also a vital component of slime volleyball!

[alice-i-cecile]

Data-wise, we want something like:

struct Semicircle {
   radius: f32,
   starting_angle: Radians,
   ending_angle: Radians,
}

[Jondolf]

I don't think Parry supports this currently, and I'm pretty arcs would have to be done using a polyline approach anyway.

As a utility, I might be able to add "Bezier colliders" though, which would form a polyline collider from a Bezier curve of a given quality. This could be used for arcs, 2D hills, hollow circles, and other such things. I'm not sure if it makes more sense as a built-in thing or a 3rd party crate though, since I haven't seen other engines have any built-in support for arc or Bezier colliders, and it's a utility more than a primitive shape.

[alice-i-cecile]

Makes sense that you're limited by what Parry supports; for my use case I'll be perfectly fine with polylines.

Hmm, I think that an example might be a better fit for the general "construct a polyline collider from a bezier curve or arc": the code should be simple and it's a nice demonstration of how to practically use the polyline colliders.

[Xesau]

One thing that might be interesting, is to add "subtraction" colliders (compare with "addition" Compound colliders). So it would collide if inside a Cylinder, but not inside a box positioned such that if you subtract the box from the cylinder, you get a semicircle / cylinder cut in half. Though this is probably something that should be directed to Parry.

[Jondolf]

One thing that might be interesting, is to add "subtraction" colliders (compare with "addition" Compound colliders).

Something like Godot's CSGs/boolean operations? We could already support not reporting contacts when a "subtraction" collider is present in a contact, but it wouldn't be able to affect the actual contact data.

I don't think computing contacts for dynamic CSGs is even technically possible (see this) unless we first convert the colliders to trimeshes and e.g. transform points to not intersect the "subtraction" colliders. Even then, the CSG would have to be static, or we would have to rebuild the collider whenever a subtraction collider moves.

If we were to add CSGs, I would say it would be better to implement it for visual Bevy meshes first. Parts of the implementation could then be maybe used for colliders as well.

[Xesau]

CSG-like colliders indeed. I'm not sure why it would not be possible. Forgetting optimization for now, take object A and B. Wouldn't it be to iterate over all subshapes of A and/or B, calculate their contacts/intersections, and then walk the CSG tree to filter out contacts that are outside the CSG shape?

[Xesau]

Here's an example of what I mean. I have not tested this code at all, and I've not implemented CSG to CSG collisions yet, only CSG to simple shapes.

struct Shape {
    shape: SharedShape,
    position: Vector,
    rotation: Quat,
}

enum Collider {
    Union(*mut Collider, *mut Collider),
    Difference(*mut Collider, *mut Collider),
    Intersection(*mut Collider, *mut Collider),
    Shape(Shape)
}

/// Collider1 and Collider2 are possibly Constructive Solid Geometry (CSG) shapes.
/// We need to determine if they are intersecting, so we need to walk the CSG tree
/// and check whether they have collisions in the correct sub-shapes.
/// If they do, we need to return the contacts for those sub-shapes.
/// This is NOT optimized. We are probably doing a lot of unnecessary work here.
fn csg_contacts(collider1: Collider, collider2: Collider) -> Vec<ContactData> {

    // First get a flat list of all the sub-shapes of collider1 and collider2.
    let shapes1 = all_sub_shapes(collider1);
    let shapes2 = all_sub_shapes(collider2);

    // And calculate contact data between ALL the sub-shapes.
    let contact_datas: Vec<ContactData> = Vec::with_capacity(shapes1.len() * shapes2.len());
    for collider1 in shapes1 {
        for collider2 in shapes2 {
            let isometry1 = utils::make_isometry(collider1.position, collider1.rotation);
            let isometry2 = utils::make_isometry(collider2.position, collider2.rotation);
            let isometry12 = isometry1.inv_mul(&isometry2);
            let convex = collider1.is_convex() && collider2.is_convex();

            let contact_data = parry::query::DefaultQueryDispatcher
                .contact(
                    &isometry12,
                    collider1.shape,
                    collider2.shape,
                    prediction_distance,
                )
                .unwrap()
                .map(|contact| ContactData {
                    point1: contact.point1.into(),
                    point2: contact.point2.into(),
                    normal: contact.normal1.into(),
                    penetration: -contact.dist,
                    convex,
                });
            contact_datas.push(contact_data);
        }
    }
    
    // If collider1 is not a CSG shape, we need to check if collider2 is a CSG shape.
    if let Shape(shape1) = collider1 {
        // If collider2 is not a CSG shape, we don't need to perform a CSG check, and we
        // can just return the contacts for the two shapes. There should only be one contact
        // in the contacts vec.
        if let Shape(shape2) = collider2 {
            return contacts[0];
        }

        // If collider2 is a CSG, we must perform a simple CSG check
        // contacts is thus an array of contacts between every sub-shape of collider2 and shape1
        else {
            complex_csg_check(collider2, shape1, contact_datas);
        }
    }
    
    // If collider1 is a a CSG shape, we need to check if collider2 is a CSG shape.
    else {
        // If collider2 is not a CSG shape, we must perform a simple CSG check
        // contacts is thus an array of contacts between every sub-shape of collider1 and shape2
        if let Shape(shape2) = collider2 {
            simple_csg_check(collider1, shape2, contact_datas);
        }

        // If collider2 is also a CSG, we must perform a complex CSG check
        // contacts is an array of contacts between every sub-shape of collider1 and collider2
        else {
            complex_csg_check(collider1, collider2, contact_datas);
        }
    }
}

// Simple CSG check. Filter out contacts between csg_collider subshapse 
fn simple_csg_check(csg_collider: Collider, shape: Shape, contact_datas: Vec<ContactData>) {
    simple_csg_check_recursive(csg_collider, 0, shape, contact_datas)
}

/// Returns vec of contact data, and next contact_index
fn simple_csg_check_recursive(csg_collider: Collider, contact_index: usize, shape: Shape, contact_datas: &Vec<ContactData>) -> (Vec<ContactData>, usize) {
    match csg_collider {
        // Collisions should be in collider1, collider2 or both
        Collider::Union(collider1, collider2) => {
            let (contacts1, next_contact_index1) = simple_csg_check_recursive(*collider1, contact_index, shape, contact_datas);
            let (contacts2, next_contact_index2) = simple_csg_check_recursive(*collider2, next_contact_index1, shape, contact_datas);

            // Merge vecs
            let mut matching_contacts = contacts1;
            matching_contacts.extend(contacts2);

            (matching_contacts, next_contact_index2);
        }
        // Collisions should be in collider1 and not in collider2
        Collider::Difference(collider1, collider2) => {
            let (contacts1, next_contact_index1) = simple_csg_check_recursive(*collider1, contact_index, shape, contact_datas);
            let (contacts2, next_contact_index2) = simple_csg_check_recursive(*collider2, next_contact_index1, shape, contact_datas);

            // Filter out contact_datas that are in collider1 but not in collider2
            let matching_contacts = contacts1.iter().filter(|contact1| {
                !contacts2.iter().any(|contact2| {
                    contact1.point1 == contact2.point1 &&
                    contact1.point2 == contact2.point2 &&
                    contact1.normal == contact2.normal &&
                    contact1.penetration == contact2.penetration
                })
            }).collect();

            (matching_contacts, next_contact_index2);
        }
        // Collisions should be in both collider1 and collider2
        Collider::Intersection(collider1, collider2) => {
            let (contacts1, next_contact_index1) = simple_csg_check_recursive(*collider1, contact_index, shape, contact_datas);
            let (contacts2, next_contact_index2) = simple_csg_check_recursive(*collider2, next_contact_index1, shape, contact_datas);

            // Filter out contact_datas that are not in both contacts1 and contacts2
            let matching_contacts = contacts1.iter().filter(|contact1| {
                contacts2.iter().any(|contact2| {
                    contact1.point1 == contact2.point1 &&
                    contact1.point2 == contact2.point2 &&
                    contact1.normal == contact2.normal &&
                    contact1.penetration == contact2.penetration
                })
            }).collect();

            (matching_contacts, next_contact_index2);
        },
        // Collisions should be in shape.
        Collider::Shape(shape) => {
            // Once we're at the end of the CSG tree, we can just return any contact between
            // this shape and the other shape.
            return (contact_datas[contact_index], contact_index + 1);
        }
    }
}

fn complex_csg_check(csg_collider1: Collider, csg_collider2: Collider, contact_datas: Vec<ContactData>) {
    todo!("implement")
}

fn all_sub_shapes(collider: Collider) -> Vec<Shape> {
    let vec = vec![];
    add_sub_shapes(&mut vec, collider);
    vec
}

fn add_sub_shapes(vec: &mut Vec<Shape>, collider: Collider) {
    match collider {
        Collider::Union(collider1, collider2) => {
            add_sub_shapes(vec, *collider1);
            add_sub_shapes(vec, *collider2);
        }
        Collider::Difference(collider1, collider2) => {
            add_sub_shapes(vec, *collider1);
            add_sub_shapes(vec, *collider2);
        }
        Collider::Intersection(collider1, collider2) => {
            add_sub_shapes(vec, *collider1);
            add_sub_shapes(vec, *collider2);
        }
        Collider::Shape(shape) => vec.push(shape),
    }
}

[alice-i-cecile]

It looks like Parry has a Cone collider that we should be able to adapt for this?