Ropes and cloth with guaranteed no tunnelling?

[josemendez]

I don't really need something like this for my project, but I've been following SIGGRAPH papers that deal with rope and cloth simulation and I think some of them managed to write their simulations such that, a knot for example, will never become untied by pulling on the two ends with any amount of force. Or if you tried to pull a cloth through another, it will never poke through.

Have you looked into any of these solutions? I'm guessing most of them are not realtime.

I'm guessing you're talking about IPC (incremental potential contact: https://ipc-sim.github.io/file/IPC-paper-fullRes.pdf). Unfortunately this approach is not suitable for realtime use (yet).

A method I had used to ensure tunnelling doesn't occur in some of my earlier simulation projects was fairly simple, though the content being simulated was also simple:
[...]
This is to my knowledge the "fastest" way to ensure tunnelling-free collision, though the collision would be "soft" and not prevent interprenetration.

Obi does a conceptually similar thing, called "predictive contacts" or "speculative contacts". This 100% guarantees no tunneling, correct TOI ordering and no missed contacts during a single collision constraint projection:

https://media.contentapi.ea.com/content/...ntacts.pdf
https://www.youtube.com/watch?v=XUsD3xrNJH0
https://ubm-twvideo01.s3.amazonaws.com/o...orGame.pdf

The idea is that each object's -particles and colliders- aabb is expanded using its velocity vector. If the aabbs of two objects overlap, then an infinite plane (defined by the contact point and normal) is generated at the surface of the closest point on one of the objects involved in the collision. During constraint projection, the position/velocities of the objects are adjusted so that they remain on the "correct" side of this plane. If one of the objects is already on the wrong side of the plane, it will adjust its position (move it to the correct side). Otherwise it will adjust its velocity so that it will not pass to the other side during this timestep.

It might be the case that none of the objects actually get to the other side of any plane and no work has to be done, that's why it's called "speculative" or "predictive": it doesn't merely react to collisions, but guesses where they're about to happen and takes action to prevent them.

This has two advantages:

1.- The expensive part (collision detection) which involves calculating signed distances between pairs of objects is only done once per step. The resulting contact list can be reused during multiple iterations and substeps, since it's quite conservative. This makes it practical to use many substeps, increasing simulation accuracy greatly as described here: http://mmacklin.com/smallsteps.pdf

2.- No extra storage required for each contact, as all the information needed for this is already part of a typical contact struct: indices of the pair involved, shortest distance between them and direction (normal).

As a result of this collision scheme, tunneling in Obi can't happen because of thin and/or fast objects, but because of one of two things:

1.- One of the objects has been kinematically moved (no change in velocity, the object suddenly "teleports" to a far away position). No CCD scheme can prevent tunneling in this case, not even IPC unless you use a huge accuracy distance target (d, in the paper) that makes local barrier functions not so local anymore.

2.- Since contacts are generated once per step and reused for all iterations/substeps, other constraints can violate the condition imposed by the contacts since collision planes are only really valid immediately after collision detection (in-between iterations, they're just a good guess). This is what happens when you make a very tight knot: at some point, the distance constraints between particles force them to pass to the other side of what would be the "real" collision plane, since particle positions change quite a lot in between iterations and the original contact planes are no longer a good enough guess. The solution to this would be to perform collision detection every single iteration so that contact planes are constantly updated, but that would make the simulation prohibitively expensive as it forces you to perform collision detection many times per frame.

Another challenge of this approach would be allowing adjacent simplices to "pass on" the knowledge that a collision is occurring to their neighbors, otherwise the particle could pass between two joined simplices.

This is implicitly and automatically handled by the method used to solve the constraint system (in Obi's case, Gauss-Seidel/SOR and averaged Jacobi): the simulation converges towards a state where all constraints are simultaneously met. See: http://obi.virtualmethodstudio.com/tutor...gence.html

Another interesting approach I've seen was to create a Deluaney triangulation of the scene, where vertex points are the corners of collision shapes. If an inversion of any of the triangles occurred from frame 1 to frame 2, it'd check whether the inversion involves a collision.

"Air meshes", right? (https://matthias-research.github.io/page...Slides.pdf) Creating a valid delaunay triangulation of anything is really slow, specially in 3D (tetrahedralization). In this case the mesh has to be constrained to object boundaries, so it's even more expensive. This can also place strict restrictions on the size of the simulation domain, since the larger the domain, the costlier the simulation. The above .pdf slides give numbers for a simple 2D scene: 2 ms spent in simulation, 80 ms spent updating the air mesh.

I've got a fairly optimized variational triangulation for 2D (use case being generating flat meshes from a spline-defined boundary) and it takes around 1 second to triangulate ten thousand points, so this is not exactly realtime.

It's a cool concept, but I've never seen this actually used anywhere.

(On second thought, I think I might like this approach better because it doesn't require remembering projected states or passing collision knowledge between connected simplices.)

But requires generating, storing and updating a tetrahedral mesh, which is far worse!