Cloth collision detection-What is the currnt stateof the art

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
mobeen
Posts: 122
Joined: Thu May 05, 2011 11:47 am

Cloth collision detection-What is the currnt stateof the art

Post by mobeen »

Hi all,
I am trying to find the current state of the art in cloth collision detection either GPU or CPU. I have seen this(http://www-evasion.imag.fr/Publications ... HRFCFMS04/) Eurographics report and this thesis(http://www.mpi-inf.mpg.de/~bargmann/doc ... tion_S.pdf) but they seem quite old.

Does anyone have any new pointers? possibly using GPU/openCL/CUDA whatever?
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Cloth collision detection-What is the currnt stateof the

Post by bone »

I was just at the OpenCL site the other day, and I think they have an example program for cloth simulation, but I didn't note if it involved collision.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Cloth collision detection-What is the currnt stateof the

Post by Erwin Coumans »

What collision shapes do you want the cloth to collide against?

For gaming purposes, I can imagine the following combinations would be useful:

A) cloth against cloth (and self collision)
B) cloth against convex shape
C) cloth against concave triangle meshes

We have some discrete GPU collision detection for convex shapes, that can also be used for cloth against convex. It let you query a point against a convex shape, and it returns the penetration depth/normal/location. Would that be of any use for you?
Thanks,
Erwin
kloplop321
Posts: 55
Joined: Sun Jan 01, 2012 7:37 pm

Re: Cloth collision detection-What is the currnt stateof the

Post by kloplop321 »

The issue is still up that cloth does not self collide.
Shouldn't that be updated on google code if it is the case?
mobeen
Posts: 122
Joined: Thu May 05, 2011 11:47 am

Re: Cloth collision detection-What is the currnt stateof the

Post by mobeen »

HI Erwin,
Thanks for the reply. Well I wanted to see what has been done in collision detection for cloth
this includes collision with concave and convex meshes as well as self collision and collision between two clothes. I wanted to see what is the state of the art in this.
Dani3L
Posts: 28
Joined: Tue Jun 30, 2009 6:56 am
Location: Switzerland
Contact:

Re: Cloth collision detection-What is the currnt stateof the

Post by Dani3L »

There is also the method : Optimized Spatial Hashing for Collision Detection of Deformable Objects that is used in Position Based Dynamics for cloth simulation.
User avatar
freemancw
Posts: 5
Joined: Sun Jan 22, 2012 6:09 pm
Location: Chapel Hill, NC, USA
Contact:

Re: Cloth collision detection-What is the currnt stateof the

Post by freemancw »

User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Cloth collision detection-What is the currnt stateof the

Post by Erwin Coumans »

A promising approach is Efficient Geometrically Exact Continuous Collision Detection by T. Brochu, E. Edwards, and R. Bridson, Proc. SIGGRAPH 2012.

It is open-source code and I made a fork that compiles on Windows, Linux and Mac OSX here:
https://github.com/erwincoumans/experim ... /exact-ccd
User avatar
jarno
Posts: 57
Joined: Tue Mar 16, 2010 1:42 am

Re: Cloth collision detection-What is the currnt stateof the

Post by jarno »

I've been rewriting a lot of the Bullet softbody collision code redoing the vertex-face collision detection, adding edge-edge detection, supporting self-collision with the same, and sprinkling it with multithreading.

Like the Brochu et al. paper I do the constant velocity approximation. I initially tried the approach of solving the cubic, but that proved to be too unstable and too slow. Instead I approximated it to a quadratic.

For example, the vertex-face case is equivalent to determining when the plane of the face moves through the origin (by considering everything relative to the vertex). As all the vertices are moving linearly, this is normally a cubic problem as the normal direction (non-normalised) of the plane changes cubically over time. But for small timesteps the cubic term of the normal direction turns out to be very small compared to the other terms (one reason why solving the cubic tends to be unstable). So I drop it and solve the resulting quadratic.
I should note that I use fairly small timesteps compared with typical Bullet use, such as 1/180th of a second.

The results look quite similar to the ones presented in the paper, with cloth stacking up on itself without self-intersecting.

I do find that I still need to have a collision margin to avoid vertices from switching sides when sliding over a surface, but it is very small (I default to a few millimetres). I haven't figured out a good and cheap way of keeping track of which side of the (often not closed) surface each vertex should remain while sliding.

---JvdL---
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Cloth collision detection-What is the currnt stateof the

Post by bone »

Do you mind sharing how you handle the edge-edge case? My version is atrocious, but basically works.
User avatar
jarno
Posts: 57
Joined: Tue Mar 16, 2010 1:42 am

Re: Cloth collision detection-What is the currnt stateof the

Post by jarno »

Edge versus edge can actually be transformed to be similar to vertex versus face.
In short, vertex versus face with linearly moving vertices is done by:
  1. Convert to vertex versus plane by determining the plane equation for the face
  2. Convert to origin versus plane by considering the problem relative to the vertex
  3. Solve the resulting cubic equation, or use the quadratic approximation, to get the potential collision time values
  4. Check each potential collision time for actual collision by evaluating the vertex positions at those times and doing a vertex inside/outside face check
The edge versus edge case can be converted to a vertex versus plane problem by collapsing one edge to a point, and extruding the other edge in the same direction to form a quadrilateral.
Compute the plane equation for that quadrilateral, and now you have a vertex versus plane problem just like with vertex-face.
Solve as before (steps 2 and 3) to get the potential collision times, and check each time with a full edge versus edge intersection test. And yes, this last step does have an annoying number of cases to check with some care needed for numeric stability.

Some care also has to be taken when computing the plane equation due to degeneracies, for example if the two edges are parallel at the start or end of the time interval.

I then put the resulting edge-edge collision data in an array similar to what SContact is for vertex-face, and process it in btSoftBody::PSolve_SContacts().

---JvdL---
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Re: Cloth collision detection-What is the currnt stateof the

Post by bone »

jarno wrote:The edge versus edge case can be converted to a vertex versus plane problem by collapsing one edge to a point, and extruding the other edge in the same direction to form a quadrilateral.
A-ha! That's the trick I was missing. Thanks for the idea!
dlx
Posts: 7
Joined: Fri Aug 03, 2012 8:39 pm

Re: Cloth collision detection-What is the currnt stateof the

Post by dlx »

Hi jarno,

Do you have any intention to contribute your implementation back to bullet physics?

Regards.....

jarno wrote:I've been rewriting a lot of the Bullet softbody collision code redoing the vertex-face collision detection, adding edge-edge detection, supporting self-collision with the same, and sprinkling it with multithreading.

Like the Brochu et al. paper I do the constant velocity approximation. I initially tried the approach of solving the cubic, but that proved to be too unstable and too slow. Instead I approximated it to a quadratic.

For example, the vertex-face case is equivalent to determining when the plane of the face moves through the origin (by considering everything relative to the vertex). As all the vertices are moving linearly, this is normally a cubic problem as the normal direction (non-normalised) of the plane changes cubically over time. But for small timesteps the cubic term of the normal direction turns out to be very small compared to the other terms (one reason why solving the cubic tends to be unstable). So I drop it and solve the resulting quadratic.
I should note that I use fairly small timesteps compared with typical Bullet use, such as 1/180th of a second.

The results look quite similar to the ones presented in the paper, with cloth stacking up on itself without self-intersecting.

I do find that I still need to have a collision margin to avoid vertices from switching sides when sliding over a surface, but it is very small (I default to a few millimetres). I haven't figured out a good and cheap way of keeping track of which side of the (often not closed) surface each vertex should remain while sliding.

---JvdL---
Post Reply