Page MenuHome

Fix T78113: Random explosions of cloth with self collision
ClosedPublic

Authored by Germano Cavalcante (mano-wii) on Aug 7 2020, 9:24 PM.

Details

Summary

The problem is caused by a lack of prediction in the isect_line_segment_tri_v3
that incorrectly confirms some intersections of coplanar segments to the triangle.

The idea of this patch is to use another algorithm to detect intersections.

For this purpose, isect_tri_tri_v3 was created, aiming to correct, simplify and
optimize the collision code.

In my tests on a cloth with self collision the simulation went from 1 min and 17 sec
without the patch to 1 min 8 sec with the patch.

Result: With patch | Without patch

Ref T78113

Diff Detail

Repository
rB Blender
Branch
cloth_self_colision (branched from master)
Build Status
Buildable 9426
Build 9426: arc lint + arc unit

Event Timeline

Germano Cavalcante (mano-wii) requested review of this revision.Aug 7 2020, 9:24 PM
Germano Cavalcante (mano-wii) created this revision.
source/blender/blenlib/intern/math_geom.c
2502

Is this really need? Isn't is kinda implicit that if all points on one triangle is on the same side of an other, you only need to make the check once?

If triangle A is all on the positive side of triangle B then triangle B must not have any points that crosses the side barrier as well.

I think a bit more comments explaining the algorithm would be good as I pointed out in my comments.

It took a while for me to realize what it was doing. This could have be much faster if there was some explanation how the algorithm is supposed to work.

Other that that, I don't have anything to complain about really.

source/blender/blenlib/intern/math_geom.c
2466

It is very vague what this does from just looking at the implementation here.

Perhaps add some comments in the code explaining what this is?

I doesn't seem to be some edge length as it can be zero on a positive intersection result.

2555

Should probably be a comment here explaining that we are trying to find the two middle points in the intersection plane.

A--B--C--D

We want to find B-C as it will be the cross section where the triangles intersect.
However there has to be a change in which triangle the point belongs to.

So for example if the first two points belong to triangle A, there is no intersection happening.

Thanks for taking a look, in fact the comments that describe the code can improve.
I will take some time and also check out the other function isect_tri_tri_epsilon_v3 (maybe it will bring a good performance too).

source/blender/blenlib/intern/math_geom.c
2466

I agree that it is still good, I have changed this name several times and I cannot find a good name to describe what this value represents.
Basically it indicates how many edges of triangle A have been intersected.
For example, if a vertex of triangle B crosses the middle of triangle A, this value is zero because only the edges of triangle B intersect.

2502

The description is a little confusing (I will change).
This actually tests the side of the points against the plane of the other triangle.
Each triangle must intersect the plane of the other triangle so that it is possible to have an intersection.
I think a better description would be:
"All vertices of the first triangle are positioned on the same side to the plane defined by the second triangle".

2555

This is a good way to describe that part. (I didn't think that way).
Perhaps that part of the code can be further simplified.

source/blender/blenlib/intern/math_geom.c
2502

Ah, right. I was wrong.
There is some cases where there is a sign change on one triangle, but not the other.

So these checks are correct. I do like your suggested updated description!
It is saying the same thing but in a more verbose way. :)

source/blender/blenlib/intern/math_geom.c
2466

Ah I see.

Perhaps the name could be r_tri_a_edge_isect_count?
Then have a comment further explaining that it is the number of edges that intersect from tri_a.

Germano Cavalcante (mano-wii) marked 3 inline comments as done.

Fixes, deduplicate code and comments

I edited the function and added checks for cases where the vertex of a triangle is coplanar to the other triangle.
I also fixed an error in checking the side of the triangle.
Because of these changes, the time now to bake the tested cloth is 1min and 9sec (different from 1min and 6sec).
I also removed the isect_tri_tri_epsilon_v3 function as it does the same thing, is less efficient (1min and 10 sec), less accurate and the epsilon parameter was being used in an unexpected way (it is used for tolerance of coplanar triangles and not the intersection distance).
I also checked the file attached in T73566 for regressions.

Here the file to test overlap regression (just run the script):

source/blender/blenkernel/intern/collision.c
228

Change _len to _count

Length is not used for how many times something occurs.

source/blender/blenlib/intern/math_geom.c
2453

Am I missing something or is this return value never set if there is any intersection?

The return true above makes this code never execute.

Germano Cavalcante (mano-wii) marked 4 inline comments as done.
  • Rename variables and funcs
  • Fix error with 'r_tri_a_edge_isect_count' not used
  • Fix case in which the triangles are coplanar

Other than my nitpick comments, I think that the code looks good.

Do you want to perform any more tests on this or do you feel that it is ready?

source/blender/blenlib/intern/math_geom.c
2366

Perhaps be a bit more verbose here. So:

/* The triangles intersect because they overlap on the intersection line.
 * Now identify the two points of intersection that are in the middle to get the actual intersection between the triangles.
 * (B--C from A--B--C--D) */
2373

We are rearranging the order, that is true, however the I feel that it should explain that the rearrangement makes it so that the alone vertex is at index 1.

So perhaps something like:

/* Rearrange the triangle so that the vertex that is alone on one side
  * of the plane is located at index 1. */
Germano Cavalcante (mano-wii) marked 2 inline comments as done.
  • Reintroduce accidentally removed fix
  • Improve comments

Do you want to perform any more tests on this or do you feel that it is ready?

Now the time to bake the simulation is 1min and 8sec..
Without the patch it is 1min and 17sec.

This revision is now accepted and ready to land.Aug 10 2020, 2:50 PM