Hello,

I would like to implement continuous point-triangle collision detection as part of a cloth simulation. 

What robust implementations of this are used in practice?

For example it is simple to use a ray-triangle intersection with q (particle start) and q1 (particle end) defining the ray relative to the triangle. Though I find this is not robust as the simulation can force the particles into an implausible state, which once it occurs even by the slightest margin, is unrecoverable. Over-correcting the particles helps somewhat, but introduces oscillations. This could be combined with a closest-point-to-triangle test that runs if the ray-intersection fails, but this seems to me very expensive and is essentially running two collision detection algorithms in one. Is there not a better way to combine them?

I have searched for a long time this but most resources are concerned with improved culling, or improved primitive tests. I've found only one paper that specifically addresses combining CCD & DCD for point-triangle tests (Wang, Y., Meng, Y., Du, P., & Zhao, J. (2014). Fast Collision Detection and Response for Vertex / Face Coupling Notations. Journal of Computational Information Systems, 10(16), 7101–7108. http://doi.org/10.12733/jcis11492), which uses an iterative search with a thickness parameter.

Is there anything beyond what I have described for this?

Sj

EDIT: I am familiar with Bridson, Du, Tang, et al. and the vertex-face penalty force computation, but I don't see how this is fundamentally different from the ray+closest-point test, other than the  cubic formulation allows both the triangle and vertex to change in time. Though Du et al's Dilated Continuous Contact Detection seems like it should do both, so maybe I need to read it again..

I don't have experience specifically with continuous cloth detection, but what is preventing you from using a mixture of CCD and DCD? Typically the solver does not care about what kind of collision detection is used, and can be black boxed from a collision detection point of view.

Depending on your use case there can be many ways to simplify the collision detection. Maybe ray to triangle is not the best option, especially since rays can shoot through vertices or edges in your cloth mesh. Also your point, as represented by a ray, may not make sense either unless it strictly travels along a line over the given timestep.

I got robust cloth to skin collisions by using capsules at skin vertices instead triangles, but the system is quite complicated:

The capsules are aligned along the triangle normal, so the long part is hidden inside the skin. If a cloth particle gets under the skin, it can still be resolved in which direction it should move to get out again.

The capsules are also scaled down along their length so the 'visible' collision surface becomes elliptic instead spherical to get a better shape representing the skin.

I used collision forces only along the direction of the capsules length and ignored their true spherical / elliptic shape (which is pretty wrong but works), but i interpolated multiple collisions to get better approx. of the skin normal.

On top of all that i had a coarse cloth rig, connected rings that slide along the skeleton bones so never go through a leg for example. The real cloth is attached to the rig by simple max distance constraints. The rig also serves as a broadphase replacement (Link on ring tells what small number of capsules every cloth vertex has to check.)

Finally i was able to simulate extreme cases like a long skirt or a very tight skirt robustly and fast. Even when causing immediate changes in character pose or position the cloth never got stuck inside the skin. Only problem remains rare jitter due to incorrect collision resolval mentioned above.

Of course this does not handle cloth self collisions.

Personally i don't believe triangle vs. vertex can ever work, but something like tetrahedron vs. vertex would, which would resolve the jitter i get from the capsules. 

Thanks for your insights both!

Quote

but what is preventing you from using a mixture of CCD and DCD? 

Nothing other than I'd hoped there was something more performant. This is in fact what I have written for now: a Ray Triangle intersection for CCD with Closest-Point-On-Triangle for DCD. 

Quote

The capsules are aligned along the triangle normal, so the long part is hidden inside the skin

Interesting system! It sounds similar to Qian et al's circumsphere. I was thinking of trying something like this.

Quote

Personally i don't believe triangle vs. vertex can ever work

I suspect this as well.

When considering collision detection techniques though I always mentally compare them against the ideal (and most correct) triangle based system. The problem is this is always hypothetical (and I am bad at estimating performance), so I have decided to build a triangle based system for bench-marking.

If it turns out fast enough to use that's a big bonus, as there are some  advantages of triangle meshes over sphere/point based representations, such as better friction emulation.

It didn't occur to me before that what is really needed for a penalty force based response (which I think is the nicest approach because it automatically handles numerical precision error and cloth offset/arbitrary particle size) is a moving-sphere-triangle test, as opposed to a point triangle test, so I've been reading about these.

Since there doesn't seem to be a consensus on the best, I decided to do some performance tests. I picked a few algorithms and put them in a test rig. They were refactored to remove most of the early returns to better emulate behaviour on a GPU. The test rig was configured to generate 100000 rays or so cast into a volumne containing a triangle, then across multiple repeats with multiple particle sizes their execution times were measured.

The algorithms I tested are below, not all of them were 100% working as this is preliminary, but they were working enough I am comfortable using the measurements as a guideline.

1. Moller-Trumbore with a distance offset.

Used as the benchmark. The intersection distance is adjusted so its always a set distance above the surface of the triangle. Not a proper implementation because the ray must still hit the triangle.

2. Flip Code

Implementation I found here: http://www.flipcode.com/archives/Moving_Sphere_VS_Triangle_Collision.shtml

3. Fauerby

Fauerby's intersection test. This didn't work as written, possibly porting mistake.

4. Eberly

Eberly's intersection test (https://www.geometrictools.com/Documentation/IntersectionMovingSphereTriangle.pdf). This didn't work as written as some of the pseudocode functions are missing.

5. Geometric

My own implementation. Uses geometric tests against primitives approximating the Minkowski sum of the radius and triangle, as opposed to finding roots like most of the others (though cylinder intersection still requires it)

The results (in microseconds, per ray)

                    Algo                                     Avg (us)   StdErr (us)
    _____________________________________    _______    _________

    MollerTriangleCollisionDiagnostics       0.76056    0.0019454
    GeometricTriangleCollisionDiagnostics       2.29    0.0094226
    FlipCodeTriangleCollisionDiagnostics      2.8112     0.010876
    FauerbyTriangleCollisionDiagnostics       1.4425    0.0035103
    EberlyTriangleCollisionDiagnostics        6.3413     0.019937

Interesting to start with. I am glad the Geometric solution is competitive, because conceptually its simple and more hackable than the root finding methods I feel anyway (I can sort of imagine how DCD could be integrated with it already). I think its worth trying to fix Fauerby's, being only half as slow as a basic ray-triangle intersection despite doing considerably more. Eberly's I won't pursue, given that I want a GPGPU implementation eventually and its not a fair comparison after I've gutted all its optimisations!

If you are looking for extreme robustness in a swept test, check out the method outline in this paper:

http://gamma.cs.unc.edu/BSC/BSC.pdf

It covers two variants. There is a fast floating point version which, while not exact, will be correct in the vast majority of cases. I use this variant in my own project and it works great. The paper also covers an exact version which uses extended precision arithmetic, and it should return the exact answer 100% of the time. 

This method says nothing above resolving the collision. You could use a swept test, and then resolve the collision by moving the vertex and triangle such that they lie on the same plane. The issue with this is that on the next iteration / step, it would be impossible to know which side of the triangle the vertex should be on. 

I've used two approaches to deal with this issue.

1) Track collisions from between steps, remembering which side of the triangle the vertex should be on. This way, you can even skip the expensive swept test if a vertex is known to be colliding with a triangle. This is what I would call a corrective approach. You are correcting penetration issues after finding them, potentially over the course of many steps. There are a few issues with this - the biggest being that special handling is required when the vertex reaches the edge of the triangle while still in the "colliding" state. You essentially have to transfer the collision to adjacent triangles to avoid having different saved sides for adjacent triangles.

2) Have a margin on all triangles. This requires two tests - the swept test, as well as a discrete test which simply pushes the vertex away from triangles if closer than the margin. This is what I would call a preventative approach. It prevents any collisions from persisting between iterations / steps. This method is less sensitive to the precision of the swept test than #1. The major issue here is that all collisions must be resolved before advancing to the next step, otherwise you will see missed collisions.

#1 is probably more visually pleasing since you don't have an artificial margin separating things, however I have had more success with #2 since there are less strange cases to deal with.

On 12/26/2017 at 1:06 PM, sebjf said:

Though Du et al's Dilated Continuous Contact Detection seems like it should do both, so maybe I need to read it again..

Do you know of a public version of this paper anywhere? All I can find is various paywalls

16 hours ago, raigan said:

Do you know of a public version of this paper anywhere? All I can find is various paywalls

Hi raigan, here you go: https://www.researchgate.net/publication/266653351_A_FluidCloth_Coupling_Method_for_High_Velocity_Collision_Simulation

On 26/01/2018 at 9:12 PM, coderchris said:

If you are looking for extreme robustness in a swept test, check out the method outline in this paper:

Thank you coderchris, I will take a look! Right now I just use a series of basic swept-primitive-tests with a discrete stage run after to undo forced penetrations. I've never tried a history based version.

15 hours ago, Mike2343 said:

Thought Siggraph 2016/7 had some interesting cloth simulations, pretty sure it wasn't GDC.  But they looked amazing and if I recall (was watching them as background noise so no quoting me on this) they quoted their sources or at least methods used.  Sorry it's so vague, I watched it like 5 months ago after being released from a 3 month hospital stay and I was still fairly drugged up

Thanks Mike2343, I will have a look!

14 hours ago, swiftcoder said:

I'm not sure how practical this currently is, but it appears to be conceptually simpler to perform robust collision detection on a distance field. Mesh deformation is liable to be a bit of a problem, not sure if one can rasterise a model into a volume texture cheaply enough to calculate the distance fields on demand... Might be worth a look

Thanks swiftcoder, I love distance fields, but I am more interested in deformable models right now. I implemented 3d rasterisation into both (vector) distance fields and spatial hashes (w/ triangle collision detection) a while back, and found that BVH re-fitting and traversal on the GPU outperformed both. Spatial hashing performed equivalently to BVHs, but only in the mid-range (30k models and 13k cloth particles), at the extremes BVHs took the prize. (Also distance fields require something like ray-marching for ccd, which is more problematic given what I say last.)

I won't go into detail unless someone asks, but suffice to say the BVH implementation was *a lot* more complex than the 3d rasterisations, needing multiple invocations on the CPU, multiple copies between buffers on the GPU (and I mean just copies), and loops in kernels with memory barriers - and it was still faster.

I've continued with my implementation, putting the basic swept-sphere-primitive tests + dcd stage on the gpu. My 1080 runs ~2.2 million tests in about 0.5 ms, which is ok I guess. Much more interesting though was comparing the perf. with and without the broadphase. A basic AABB for all tris vs. all particles (the broadphase itself only pushing to append buffer) ran at about .25 ms. I know that GPUs nowadays in most cases are memory bound, but I have some sort of mental block and still manage to be surprised by it every time...

The next stage is to implement interpolation/sharing of impulses like Bridson's, so the mesh responds to the collisions as well. Then once that is on the GPU (because it will impact bandwidth quite a bit) I'll run some more complete tests. It'll be interesting once that's done to see what swapping in BSC can do.

thanks for the link sebjf, I just assumed that site was the usual scammy paywall -- cheers