Individual Mesh-Mesh Collision

[jbraumann]

I would like to check a series of - if necessary convex - meshes for collisions. It is not necessary for my use case for them to react to this collision or to provide parameters like the depth, a boolean value is sufficient.
I am struggling to find a reliable approach to realize that. The best case would be a function where I could just reference the two meshes to check, is there something close to that?
Thanks,
Johannes

[danfma]

I guess you are in the same scenario as me... I need to verify if a box will suffer a collision before actually moving it to do some actions... I'm trying with ray traces but it's not so robust...

[RossNordby]

See the CollisionQueryDemo for an example of testing a shape against the simulation. It involves collecting candidates from the broad phase, then using the CollisionBatcher to issue tests.

Two annoyances:

1. The CollisionBatcher does not support boolean queries; it'll give you the full contact manifold regardless. Checking contacts for nonnegative depth would give you boolean information.
2. The CollisionBatcher is a batched API for performance reasons and is overcomplicated for a single boolean query. This is something that's bugged me for a long time and I'd like to address, but it's not done yet.

If the tests are something you'd want to do every single timestep, you could consider adding a body or static into the simulation to collect collision information without generating constraints (by returning false from the INarrowPhase.ConfigureContactManifold function). See the CollisionTrackingDemo for an example of storing out collision information.

There are also sweep tests (as in the SweepDemo). They're typically slower than batched tests in terms of amortized throughput, but the API is not batched so it can be simpler.

[jbraumann]

Thanks a lot! The SweepTests sound promising, I guess I would only have to create a Simulation and BufferPool, load a mesh via e.g. var mesh1 = DemoMeshHelper.LoadModel(content, BufferPool, "Content\\newt.obj", new Vector3(30)); and then run something like StandardTestSweep(mesh1, mesh2, ref position, worldA, worldB, renderer); and get the intersection from what in the demo is var intersected = task.Sweep(...?
Or am I missing something? And does it do a broad phase automatically, or would that have to be added? I guess comparing only the bounding boxes of the two meshes...

[RossNordby]

In the context of queries against the simulation, the broad phase can efficiently provide candidates for testing by using its acceleration structure. The built-in simulation queries use it. If you already know the specific pairs you'd like to test, there's no need for the broad phase.

Notably, Mesh-Mesh is the one pair type that is unsupported for sweeps. They're expensive, complicated, and basically shouldn't exist, so I made the simplification to exclude them for now. You can still do Mesh versus other types, but note that it'll still be much slower than using a simpler representation and/or using the CollisionBatcher to execute many vectorized tests together.

(The CollisionBatcher does support testing Mesh-Mesh, though it's strongly recommended against.

Here's an example of using the sweep in a more isolated context, using the same Filter as the demo:

var testShapeA = DemoMeshHelper.LoadModel(content, BufferPool, @"Content\newt.obj", new Vector3(1, 1, 1));
var testShapeB = new Box(1, 1, 1);
var poseA = new RigidPose(new Vector3(0, 0, 0));
var poseB = new RigidPose(new Vector3(1f, 0, 0));

Simulation.Statics.Add(new StaticDescription(poseA, Simulation.Shapes.Add(testShapeA)));
Simulation.Statics.Add(new StaticDescription(poseB, Simulation.Shapes.Add(testShapeB)));

unsafe bool Intersects<TShapeA, TShapeB>(TShapeA a, RigidPose poseA, TShapeB b, RigidPose poseB)
    where TShapeA : struct, IShape
    where TShapeB : struct, IShape
{
    var filter = new Filter();

    var task = Simulation.NarrowPhase.SweepTaskRegistry.GetTask(TShapeA.TypeId, TShapeB.TypeId);
    if (task == null)
        return false;
    return task.Sweep(
        Unsafe.AsPointer(ref a), TShapeA.TypeId, poseA.Orientation, default,
        Unsafe.AsPointer(ref b), TShapeB.TypeId, poseB.Position - poseA.Position, poseB.Orientation, default,
        0f, 1e-2f, 1e-5f, 25, ref filter, Simulation.Shapes, Simulation.NarrowPhase.SweepTaskRegistry, BufferPool,
        out _, out _, out _, out _);
}

var intersects = Intersects(testShapeA, poseA, testShapeB, poseB);
Console.WriteLine($"intersects: {intersects}");

Note that you don't have to have a simulation to use this function; you could just create your own with DefaultTypes.CreateDefaultSweepTaskRegistry().

[danfma]

It looks like you read my mind! That works very perfectly for me!
The API is a bit overwhelmed but the result is the expected! I will try using the BroadPhase to minimize the number of tests too.

Maybe we just need some small BepuPhysics.EasyWay library to handle some of those hard things! hahaha :D

If you accept, I will try to compile some utilities and send you an MR!

[RossNordby]

I often have some difficult-to-predict requirements that make that sort of broad contribution difficult to preapprove, but one thing that is definitely useful is just giving me a list of the helpers you ended up using in your project. No need for the actual implementations, either; the primary value is in knowing your specific use cases. Can't guarantee I'll fill them all in "officially," but it helps prioritize and I would appreciate it.

[jbraumann]

I really appreciate the input (and, of course, the software itself)! So if I can get by with a ConvexHull then I could use the unsafe bool Intersects() from above?

For mesh against mesh, I could use most of the code from the Render method in the CollisionQueryDemo and change the Query object to consist of a Mesh and a RigidPose, correct?

I already played around with the code and it seemed that the Query objects would only detect collisions with other elements in the scene, but not between themselves. Does that mean I would have to add one mesh to Simulation.Statics and use the other as a Query object to check for collisions?

Thanks!

[RossNordby]

So if I can get by with a ConvexHull then I could use the unsafe bool Intersects() from above?

Yup.

I already played around with the code and it seemed that the Query objects would only detect collisions with other elements in the scene, but not between themselves. Does that mean I would have to add one mesh to Simulation.Statics and use the other as a Query object to check for collisions?

If you know the exact pair you want to test, you can skip the broad phase entirely and just use the CollisionBatcher directly.

For example:

    /// <summary>
    /// Adds a shape pair to the collision batcher for testing. Does not flush the batcher.
    /// </summary>
    /// <typeparam name="TShapeA">Type of the first shape to test.</typeparam>
    /// <typeparam name="TShapeB">Type of the second shape to test.</typeparam>
    /// <typeparam name="TCallbacks">Type of the callbacks to use for the collision tests.</typeparam>
    /// <param name="a">First shape to test.</param>
    /// <param name="poseA">Pose of the first shape to test.</param>
    /// <param name="b">Second shape to test.</param>
    /// <param name="poseB">Pose of the second shape to test.</param>
    /// <param name="speculativeMargin">Speculative margin to use for the collision test.</param>
    /// <param name="pairId">Pair id to associate with this test. The pair id will be reported in the callback when the batcher finishes the pair.</param>
    /// <param name="batcher">Batcher to add the pair to.</param>
    public unsafe void AddPairToBatcher<TShapeA, TShapeB, TCallbacks>(TShapeA a, RigidPose poseA, TShapeB b, RigidPose poseB, float speculativeMargin, int pairId, ref CollisionBatcher<TCallbacks> batcher)
        where TShapeA : unmanaged, IShape
        where TShapeB : unmanaged, IShape
        where TCallbacks : struct, ICollisionCallbacks
    {
        batcher.Add(TShapeA.TypeId, TShapeB.TypeId, sizeof(TShapeA), sizeof(TShapeB), &a, &b, poseB.Position - poseA.Position, poseA.Orientation, poseB.Orientation, speculativeMargin, pairId);
    }

This does not directly run the pair test. The test will only be run when enough pairs have been added to the batcher to warrant a batch execution. You can also force all pairs to be tested immediately by calling Flush. All results are reported to the TCallbacks used by the CollisionBatcher.

If you wanted to use it in a nonbatched way for a boolean test, you could do something like:

    /// <summary>
    /// Simple callbacks for a single unbatched boolean test.
    /// </summary>
    struct BooleanCallbacks : ICollisionCallbacks
    {
        /// <summary>
        /// The intersection state of the tested pair. Since there's only one test, there's no need for fancier state.
        /// </summary>
        public bool Intersected;

        public bool AllowCollisionTesting(int pairId, int childA, int childB) => true;

        public void OnChildPairCompleted(int pairId, int childA, int childB, ref ConvexContactManifold manifold) { }

        public void OnPairCompleted<TManifold>(int pairId, ref TManifold manifold) where TManifold : unmanaged, IContactManifold<TManifold>
        {
            for (int i = 0; i < manifold.Count; ++i)
            {
                if (manifold.GetDepth(i) >= 0)
                {
                    Intersected = true;
                    return;
                }
            }
        }
    }

    /// <summary>
    /// Tests whether to shapes touch.
    /// </summary>
    /// <remarks>This is a simple unbatched test. It will be much slower than running many tests in vectorized bundles, but shows how it could work conceptually.</remarks>
    /// <typeparam name="TShapeA">Type of the first shape to test.</typeparam>
    /// <typeparam name="TShapeB">Type of the second shape to test.</typeparam>
    /// <typeparam name="TCallbacks">Type of the callbacks to use for the collision tests.</typeparam>
    /// <param name="a">First shape to test.</param>
    /// <param name="poseA">Pose of the first shape to test.</param>
    /// <param name="b">Second shape to test.</param>
    /// <param name="poseB">Pose of the second shape to test.</param>
    /// <param name="shapes">Shapes collection to look up child shapes. Needed for compounds.</param>
    /// <param name="collisionTaskRegistry">Collision task registry defining collision tasks for type pairs.</param>
    /// <returns>True if the pair touches, false otherwise.</returns>
    public unsafe bool PairTouches<TShapeA, TShapeB>(TShapeA a, RigidPose poseA, TShapeB b, RigidPose poseB, Shapes shapes, CollisionTaskRegistry collisionTaskRegistry)
       where TShapeA : unmanaged, IShape
       where TShapeB : unmanaged, IShape
    {
        var collisionBatcher = new CollisionBatcher<BooleanCallbacks>(BufferPool, shapes, collisionTaskRegistry, 0, new BooleanCallbacks());
        collisionBatcher.Add(TShapeA.TypeId, TShapeB.TypeId, sizeof(TShapeA), sizeof(TShapeB), &a, &b, poseB.Position - poseA.Position, poseA.Orientation, poseB.Orientation, 0, 0);
        collisionBatcher.Flush();
        return collisionBatcher.Callbacks.Intersected;
    }

I should also mention that Mesh triangles are one-sided, so it's very easy for Mesh-Mesh results to seem nonsensical. It's possible for two meshes to obviously intersect while no contacts are generated because all intersections would have normals on the triangle backfaces. This, combined with triangles being infinitely thin and meshes having no internal volume, are a big part of the reason I steer people away from allowing Mesh vs Mesh tests to be a thing. (Simple convex approximations are preferred, and compounds created from convex decomposition are best where single convexes aren't workable.)

[danfma]

@jbraumann I did the following. I'm still evolving the code but maybe it can help you.

public struct CollisionQuery(Simulation simulation)
{
    private const float SweepMinimumProgression = 1e-1f;
    private const float SweepConvergenceThreshold = 1e-5f;
    private const int SweepMaximumIterationCount = 1;

    public float BroadPhaseSearchRadius { get; init; } = 1;
    public CollidableMobility TargetMobility { get; init; } = CollidableMobility.Dynamic;

    public IEnumerable<BodyReference> GetCollisionsAtDirection(
        BodyReference body,
        Vector3 translation
    )
    {
        var enumerator = new BroadPhaseOverlapEnumerator(simulation)
        {
            References = new QuickList<CollidableReference>()
        };

        GetBodiesWithinRadius(body.Pose.Position, ref enumerator);

        var shape = simulation.Shapes.GetShape<Box>(body.Collidable.Shape.Index);

        foreach (var reference in enumerator.References)
        {
            if (reference.Mobility != TargetMobility || reference.BodyHandle == body.Handle)
                continue;

            var otherBody = simulation.Bodies.GetBodyReference(reference.BodyHandle);
            var otherShapeType = otherBody.Collidable.Shape;
            var otherShape = simulation.Shapes.GetShape<Box>(otherShapeType.Index);

            if (WillOverlap(body, ref shape, otherBody, ref otherShape, translation))
            {
                yield return otherBody;
            }
        }

        enumerator.Dispose();
    }

    private void GetBodiesWithinRadius(
        in Vector3 offset,
        scoped ref BroadPhaseOverlapEnumerator enumerator
    )
    {
        var area = new Sphere(BroadPhaseSearchRadius);

        area.ComputeBounds(Quaternion.Identity, out var min, out var max);
        min += offset;
        max += offset;

        simulation.BroadPhase.GetOverlaps(min, max, ref enumerator);
    }

    private bool WillOverlap(
        in BodyReference body1,
        ref Box shape1,
        in BodyReference body2,
        ref Box shape2,
        in Vector3 translation
    )
    {
        unsafe
        {
            var task = simulation.NarrowPhase.SweepTaskRegistry.GetTask(Box.TypeId, Box.TypeId);
            var filter = Filters.TrueForAll;

            if (task is null)
                return false;

            var expectedPosition = body1.Pose.Position + translation;
            var target = body2.Pose.Position - expectedPosition;

            var overlaps = task.Sweep(
                shapeDataA: Unsafe.AsPointer(ref shape1),
                shapeTypeA: Box.TypeId,
                orientationA: body1.Pose.Orientation,
                velocityA: default,
                shapeDataB: Unsafe.AsPointer(ref shape2),
                shapeTypeB: Box.TypeId,
                offsetB: target,
                orientationB: body2.Pose.Orientation,
                velocityB: default,
                maximumT: 0,
                minimumProgression: SweepMinimumProgression,
                convergenceThreshold: SweepConvergenceThreshold,
                maximumIterationCount: SweepMaximumIterationCount,
                filter: ref filter,
                shapes: simulation.Shapes,
                sweepTasks: simulation.NarrowPhase.SweepTaskRegistry,
                pool: simulation.BufferPool,
                t0: out _,
                t1: out _,
                hitLocation: out _,
                hitNormal: out _
            );

            return overlaps;
        }
    }
}

I will check your last message and evaluate that against what I did, @RossNordby ! Thank you!

[danfma]

I just realized IEnumerable will be on the heap... so maybe I can use the same idea of your enumerator to keep them on the stack instead.

[jbraumann]

@danfma Thanks a lot for the code, I'll try it out later today! The application isn't super performance-centric as it only needs to check once, rather than for every frame.