Global Intersection Analysis: a great idea for collision detection

For the past few days I've been dedicated to solve the self-collision problem in cloth simulation, and here's some insights I've found for self-collision detection:

1. collisions are generated because of positions of vertices are changed. So ideally, assuming the cloth starts without any self-collision, a naive collision detection need to be performed as long as   all vertices are moved.

2. there're two types of collision: continuous collision and static collision.
    continuous collisions are detected by testing the trajectory against a surface. That is a ray-triangle intersection test for common case. The ray starts from the position of a vertex in last frame, and ends on the current position.
    static collisions are detected by testing whether a vertex is under a certain surface, which is testing signed distance of a vertex and a triangle in general case.

3. problem for cloth simulation: cloth is just one single sheet of mesh, which means there's no negative distance for vertex against triangle. So static collision detection would fail because in case like a vertex is below triangle, you cannot distinguish if it is penetrating from above or coming from below without penetration.

4. problem for PBD: as I mentioned before, ideally a naive collision detection(contains either one type of the collision detection) has to be performed once vertices are moved. If PBD is being used, the problem would arise because the positions of vertices are moved in the resolving constraints pass without performing collision detection per iteration.
    So as always is the case, some vertices are move into a certain surface by resolving constraints, while no collision are detected. In the following frame, this kind of collision will not be detected because continuous collision will not treat this one as a collision, while static collision fails because of cloth is too thin to have a negative value.

5. Possible solution: a. GIA(global intersection analysis). b. potential collision constraints.

a. GIA is proposed in this paper. Yet as mentioned in the paper, this method has limitations when it comes to a boundary-penetrating case. I had an idea for perfecting this method, by running flood-fill on both edge and surface.

b. potential collision constraints is the idea I come up with after these days. When doing intersection test, we set a proper threshold for particle-triangle intersection. And add potential collision constraints for resolving pass. They have not collide yet, but since the distance is smaller than the threshold, it's possible for them to collide in the resolving pass. So if they collide in the resolving path, collision will be corrected. Make sure all self-collisions are resolved before entering next frame, so that even the collision detection only support continuous collision, there won't be any problem.

These are two of my ideas, and I'll start a independent project on this. Since for the first idea I'm not sure how to implement it. There're too many topological things related. And for the second idea, I don't have any idea how to set a proper threshold.

Good luck to me!

Cloth Simulation using PBD

Recently I've been working on a cloth simulation project as a new homework assignment for CIS 563.

It turns out that cloth simulation is harder and thus more interesting than I imagined.

I'm following Matthias Muller's Position Based Dynamics paper for implementation. I've also done a solid simulation using another of his paper with similar idea. These ideas are really innovative. They do not make that much physical sense, but they follow physical laws, and most importantly, they are a lot faster than physically based method like mass-spring-damper system.

Here's a demo for the cloth simulation. Right now it does has stretch / bend / pinned point / collision constraints, but no self intersection has been taken into consideration.

In fact, the self-intersection is the most interesting part to me. Because the cloth is just a thin layer of unclosed mesh, it's impossible to define a collision with it: position would make sense on both side of the cloth.

I'm looking into this problem right now, following these papers:
http://www.cs.ubc.ca/~rbridson/docs/cloth2002.pdf
http://www.cs.ubc.ca/~rbridson/docs/cloth2003.pdf
http://graphics.pixar.com/library/UntanglingCloth/paper.pdf

Hopefully I can find some insights from these paper and improve this project in the following days.