Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Ropes and cloth with guaranteed no tunnelling?
#1
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.

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:

  • A particle was in an 2D environment. In the environment were horizontal line segments that the particles would collide with.
  • For simplicity, assume the particle and line segments have 0 radius.
  • The space around a line segment was divided into 6 parts: above to the right, above, above to the left, below to the right, below, and below to the left. (I'll abbreviate these as AR, A, AL, BR, B, and BL.)
  • If the particle passed through from one region to another suggesting a collision occurred, like A to B, it'd add a force that pushes the particle into region A (a point on the line segment).
  • If, at the end of frame 1, after summing all forces acting on the particle still resulted in the particle being in region B, it'd remember that the particle is "supposed" to be in region A and continue pushing the particle into it on the next frame.
  • If the particle passed through from, for example, AR to BR, the line segment would now remember that the particle switched from "supposed to be above" to "supposed to be below" and no longer try to push the particle above it.
Another way to describe it:

Code:
for each line segment L
    for each particle P
        P.Zone[L] is the current zone around L that P resides despite collision
        L.Zone[P] is the zone that L remembers P residing in last frame
        
        if a comparison of the two zones, P.Zone[L] and L.Zone[P] suggest a collision occurred
            newZone is the zone closest to P.Zone[L] that doesn't suggest a collision:
                For example, if P.Zone[L] is BL and L.Zone[P] is A, newZone would be AL.
                
            Apply a force to P that pushes it into zone newZone.
            L.Zone[P] <= newZone
        
        else
            L.Zone[P] <= P.Zone[L]



This approach could be made more accurrate by checking if the path of the particle intersected the line, rather than just comparing the 6-mode states for an invalid zone passing. Also, instead of just remembering the "last valid zone", it could remember the "last valid state", that is where the particle WOULD be if its collision force was the only force acting on it; the state resulting from projecting the particle.
Also, this approach does permit the particle to "poke through" the line segment, but it will always try to push the particle above it unless the particle makes a "legal" collision-free path around it. If there were a heavy object trying to pull the particle through the line segment, it wouldn't pass through freely; it'd likely reach equilibrium somewhere under the line but prevent it from falling.

This approach could be generalized to all simplices, but would require temporary memory that is freed when the collision is resolved. E.g. a list of collisions that is populated when a collision is detected, which are then removed from the list when the collision resolves.
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 to my knowledge the "fastest" way to ensure tunnelling-free collision, though the collision would be "soft" and not prevent interprenetration.

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. (E.g. a triangle's top vertex passing through its bottom edge, which is marked as a collision boundary.) If it did, it'd apply forces to correct the inversion by pushing the vertices opposite to a collision edge through to the correct side. Otherwise, it'd re-mesh the region around the inversion. (I think it continuously improves mesh quality by performing greedy edge flips, excluding edges that involve a collision boundary, or if it'd cause a false negative.) This also prevents falling through, since the inverted triangle will not get remeshed if it is collision-related, and the only way to fix the inversion is to push the particle back through the collision boundary.
I'm guessing this could be generalized to "thick" collisions by biasing edges of the triangle towards an inversion. It could also be sped up by selectively including elements in the mesh based on AABB overlap and using the beginning-of-frame state to construct the mesh of newly added elements.
(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.)
Reply
#2
(03-06-2021, 12:06 AM)Hatchling Wrote: 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).

Quote: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.

Quote: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

Quote: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.

Quote:(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! Gran sonrisa
Reply