Cloth collision system improvements #81864

New Issue

Germano Cavalcante · 2020-10-19T19:53:46+02:00

2020-10-19 19:53:46 +02:00

Status: Work in progress

Team
Commissioner: ? Core developer or artist, sign off the project, works as client.
Project leader: ? Main developer responsible for the implementation, only in one project.
Project members: - Optional other developers, can be in multiple projects at once.

Description
Big picture:
Currently, blender uses a method adapted from the "Discrete Collision Detection" - Between each step of the frame, it is detected when a triangle invades the collision margin of the other and thus an impulse vector is added to move the triangles away.
However, the blender solution is inefficient as it uses the same solver steps (called in the UI as "quality steps") to test the collision.
The ideal would be to interpolate the triangles of the a previous and current frame according to the "collision steps".

But even interpolating the triangles of the previous frame, this solution is limited because if the triangle moves too fast, the collision is missed.
Those impulses can also cause random explosions in complex simulations.

The idea of the new system is to use a method of "Continuous Continuous Detection" and make the collision more independent of the quality steps.

Use cases:

Faster and more accurate simulations

Design:

Decrease the number of steps needed to resolve collisions (1 step for any collision would be ideal).
Have the option to collide only the edges or vertices of the cloth.

Engineer plan:

Avoid the use of impulses to define the final position. (The exact position and velocity can be defined and set).
Use continuous collision detection (CCD) methods to avoid missed collisions between frames. (The "secant method" under development for the particle system is a good candidate).

Work plan

**{icon check-circle color=green} Milestone 1 **

Research
Code reorganization
Adaptation of the new system
New system.
Time estimate: 1 week if the secant method proves appropriate, 2 weeks or more otherwise.

**Status:** `Work in progress` --- **Team** **Commissioner:** `?` *Core developer or artist, sign off the project, works as client.* **Project leader:** `?` *Main developer responsible for the implementation, only in one project.* **Project members:** `-` *Optional other developers, can be in multiple projects at once.* **Description** **Big picture:** Currently, blender uses a method adapted from the `"Discrete Collision Detection"` - Between each step of the frame, it is detected when a triangle invades the collision margin of the other and thus an impulse vector is added to move the triangles away. However, the blender solution is inefficient as it uses the same solver steps (called in the UI as "quality steps") to test the collision. The ideal would be to interpolate the triangles of the a previous and current frame according to the "collision steps". But even interpolating the triangles of the previous frame, this solution is limited because if the triangle moves too fast, the collision is missed. Those impulses can also cause random explosions in complex simulations. The idea of the new system is to use a method of `"Continuous Continuous Detection"` and make the collision more independent of the quality steps. **Use cases**: * Faster and more accurate simulations **Design:** * Decrease the number of steps needed to resolve collisions (1 step for any collision would be ideal). * Have the option to collide only the edges or vertices of the cloth. **Engineer plan:** * Avoid the use of impulses to define the final position. (The exact position and velocity can be defined and set). * Use continuous collision detection (CCD) methods to avoid missed collisions between frames. (The "secant method" under development for the particle system is a good candidate). **Work plan** **{icon check-circle color=green} Milestone 1 ** - [x] Research - [ ] Code reorganization - [ ] Adaptation of the new system *New system.* Time estimate: `1 week` if the secant method proves appropriate, `2 weeks or more` otherwise.

Germano Cavalcante self-assigned this 2020-10-19 19:53:46 +02:00

Germano Cavalcante commented

2020-10-19 19:53:46 +02:00

Added subscriber: @mano-wii

TheRedWaxPolice commented

2020-10-19 21:34:54 +02:00

Added subscriber: @TheRedWaxPolice

Joseph Eagar commented

2020-10-19 23:14:21 +02:00

Added subscriber: @JosephEagar

Joseph Eagar commented

2020-10-19 23:14:21 +02:00

IIRC, isn't this how the cloth code originally worked? I know researchers disagree on whether it's a good idea or not; the consensus seems to be that it is (or at least, is unavoidable), I think? Impulse collisions are tricky in general. IIRC some papers combine the two approaches along with a third one:

If impulses resolve collisions, yay!
If not, force the collisions to resolve.
If that fails:

Mark impact zones by traversing connected intersecting triangles.
Treat each zone as a rigid body surface, until such time as #2 succeeds in untangling the mess.

IIRC, isn't this how the cloth code originally worked? I know researchers disagree on whether it's a good idea or not; the consensus seems to be that it is (or at least, is unavoidable), I think? Impulse collisions are tricky in general. IIRC some papers combine the two approaches along with a third one: 1. If impulses resolve collisions, yay! 2. If not, force the collisions to resolve. 3. If that fails: - Mark impact zones by traversing connected intersecting triangles. - Treat each zone as a rigid body surface, until such time as #2 succeeds in untangling the mess. ```

Joseph Eagar commented

2020-10-19 23:19:20 +02:00

Btw, is the cloth code not doing continuous collision detection?

Joseph Eagar commented

2020-10-19 23:56:00 +02:00

Okay, I have written a small set of slides introducing continuous collision detection.

https://docs.google.com/presentation/d/1XW4_czKu6wB7JRnxTReaHI2q3GLI6jr7BaIyZ93z3JY/edit?usp=sharing

Here are a more comphrensive set of slides:

http://www.cs.unc.edu/~lin/COMP259-S05/LEC/14.ppt

It's really not that hard.

Okay, I have written a small set of slides introducing continuous collision detection. https://docs.google.com/presentation/d/1XW4_czKu6wB7JRnxTReaHI2q3GLI6jr7BaIyZ93z3JY/edit?usp=sharing Here are a more comphrensive set of slides: http://www.cs.unc.edu/~lin/COMP259-S05/LEC/14.ppt It's really not *that* hard.

Germano Cavalcante commented

2020-10-20 01:07:41 +02:00

Thanks for the papers @JosephEagar!

As far as I could see in the code, the cloth collision system does not work with "continuous collision detection".
I tried to implement something like that. But I haven't found any papers on Triangle x Triangle collisions (which is currently used in the code).
I only find information about this type of collision detection with Point x Triangle or Edge x Edge.
I was informed of a detection solution that tests the distances procedurally between each frame until it finds the exact collision interval.
If I'm not mistaken this solution is currently used for particles, but something similar can be implemented for cloths.

But before delving further into this, I developed a simple but not so accurate algorithm that simply considers what direction each pair of triangles should take at the end of the collision.
Initial testing shows a promising result (1 sample):

Thanks for the papers @JosephEagar! As far as I could see in the code, the cloth collision system does not work with "continuous collision detection". I tried to implement something like that. But I haven't found any papers on `Triangle x Triangle` collisions (which is currently used in the code). I only find information about this type of collision detection with `Point x Triangle` or `Edge x Edge`. I was informed of a detection solution that tests the distances procedurally between each frame until it finds the exact collision interval. If I'm not mistaken this solution is currently used for particles, but something similar can be implemented for cloths. But before delving further into this, I developed a simple but not so accurate algorithm that simply considers what direction each pair of triangles should take at the end of the collision. Initial testing shows a promising result (1 sample): ![cloth.gif](https://archive.blender.org/developer/F9018629/cloth.gif)

Joseph Eagar commented

2020-10-20 01:27:26 +02:00

You don't really need triangle/triangle testing per se. IIRC you only need triangle/point and edge/edge, you can build triangle/triangle out of those.

Germano Cavalcante commented

2020-10-20 01:50:29 +02:00

Well noted. I don't know why I didn't think about it. It is worth the implementation.
But since I already developed a simple collision detection algorithm between "morphing" triangles, this new algorithm could stay for a milestone 2 (I don't intend to spend much time on that).
It is also good to consider the efficiency of this new algorithm since it will test all combinations Vert_a x Tri_b, Vert_b x Tri_a, Edge_a x Edge_b.

Well noted. I don't know why I didn't think about it. It is worth the implementation. But since I already developed a simple collision detection algorithm between "morphing" triangles, this new algorithm could stay for a milestone 2 (I don't intend to spend much time on that). It is also good to consider the efficiency of this new algorithm since it will test all combinations Vert_a x Tri_b, Vert_b x Tri_a, Edge_a x Edge_b.

Dalai Felinto commented

2020-10-20 10:52:13 +02:00

Added subscriber: @dfelinto

Dalai Felinto commented

2020-10-20 10:52:13 +02:00

Hi Germano, without any real production-like file showing the limitations of the current system, there is no way to show that this project is really needed. It also works as a way to validate the project success.