resolv icon indicating copy to clipboard operation
resolv copied to clipboard

fix: Fix mtv calculation for both polygon-polygon as well as polygon-circle intersections.

Open d3rped opened this issue 1 year ago • 3 comments

This fixes the potential incorrect direction of the MTV.

While testing I noticed that polygon-circle intersections have a similar issue once the circles center is inside the polygon. A naive approach would be to do the same check and set the the magnitude to 2*r - smallest.Magnitude and invert it.

if cp.Center().Sub(other.position).Dot(smallest.Unit()) < 0 {
    smallest = smallest.Unit().Scale(-other.radius * 2 + smallest.Magnitude())
}

But that only works if the intersecting points are on the same edge.

d3rped avatar Sep 01 '24 13:09 d3rped

I noticed that polygon-polygon collisions have a similar issues to the one circles have. Center point outside of lager polygon: centerOut Center point inside of larger polygon: centerIn

I want to properly solve all the issues before this can be merged.

d3rped avatar Sep 02 '24 13:09 d3rped

I've fixed the polygon-polygon mtv calculation. Your implementation of the overlap function was faulty. Checking for the min/max of both may be quicker but it does not handle intersections in which the min and max of one projection are contained by the other projection. In the example I gave in my last comment the mtv becomes the width of the smaller polygon.

Regarding the polygon-circle mtv calculation. The approach to only check against the polygons vertices and the center of the intersecting points is clever but can lead to wrong results. I propose two different solutions:

  1. Only add the intersection center point to the checked vertices if it is not contained by the polygon. This means that there are some cases in which the mtv is not actually the minimum, but only in cases in which the current solution would give incorrect results anyways.

  2. Solve it the traditional way, that is: Project the circle against all polygon edges and find the minimum overlap. Keep the check against the polygons vertices (without the intersection center point)

d3rped avatar Sep 03 '24 09:09 d3rped

For now I've implemented solution 2 as it does not have any corner cases. Hope I didn't make any mistakes.

This should be ready for review now.

d3rped avatar Sep 03 '24 11:09 d3rped

Finally, haha! Excellent - thank you very much for the contribution! Really appreciate it!

SolarLune avatar Oct 29 '24 18:10 SolarLune