EPA convergence failure on capsules
sebcrozet opened this issue · 2 comments
See the following PR for a code to reproduce the bug: dimforge/rapier#531
The gjk returns intersection, and then epa2 starts.
Adding some logs, it seems it never converges:
Iteration 1: curr_dist = 7.9495697, candidate_max_dist = 11.553711 max_dist = 11.553711, support_point_id = 3
Iteration 2: curr_dist = 8.539658, candidate_max_dist = 9.600317 max_dist = 9.600317, support_point_id = 4
Iteration 3: curr_dist = 9.436261, candidate_max_dist = 9.436432 max_dist = 9.436432, support_point_id = 5
Iteration 4: curr_dist = 9.436262, candidate_max_dist = 9.436306 max_dist = 9.436306, support_point_id = 6
Iteration 5: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 7
Iteration 6: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 8
Iteration 7: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 9
Iteration 8: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 10
Iteration 9: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 11
Iteration 10: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 12
Iteration 11: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 13
Iteration 12: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 14
Iteration 13: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 15
Iteration 14: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 16
Iteration 15: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 17
Iteration 16: curr_dist = 9.436289, candidate_max_dist = 9.43631 max_dist = 9.436306, support_point_id = 18
The problem could be related to the epa value and what it expects the improvement to be. Aside for the check:
if max_dist - curr_dist < _eps_tol {
...
}There coudl be another check to see if any of the values changed, if not the algorithm is probably stuck and we should accept the intersection.
The difference in this case is:
0.00001715999
While eps is:
0.000011920929
The problem occurs either because:
- as points are further away from center or bigger, the result doesn't converge with same accuracy
- as the shapes are bigger, the result also doesn't converge with same accuracy.
Another idea is to use either EPS based on values. Eg. check that the difference between the two is a percentage of total distance.
Another idea would be to increment the EPS based on iteration count, so we don't arrive at a very big iteration index(even if the result would be much more precise, we don't always want that if it takes a lot of iterations)