dimforge / parry

2D and 3D collision-detection library for Rust.
https://parry.rs
Apache License 2.0
591 stars 104 forks source link

Improve convergence of epa algorithm in case it's stuck #245

Closed Ughuuu closed 3 months ago

Ughuuu commented 4 months ago

Improves converges by checking if it's stuck. In such a case return a result, as a better solution will not be found, and most likely they are intersecting but not within the EPS.

Also decrease max iterations from 10000 to 100. It usually converges in 4-5 iterations, no need to ever do as many. Also we never really want a precision that big, we are ok with a lower precision most times.

Possibly fixes:

Ughuuu commented 4 months ago

With this fix it actually returns a contact (didn't know how to draw the intersection better):

image

Also it does so in 5 iterations and returns a collision, instead of doing 10000 iterations and returning None.

Vrixyz commented 4 months ago

Thanks! I'd like to add a test for this scenario, would a setup like https://github.com/dimforge/rapier/pull/531 be the correct candidate ?

Ughuuu commented 4 months ago

Sure, thats what I used locally. I didn't put the effort to migrate that sample to the parry repo, but probably that would be next step.

Vrixyz commented 3 months ago

:tada: yay! I'd like to add a changelog line before merging though