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