Hello, I am a highschool student and have been working on a 2D game with a friend. I have done most of the programming from scratch using only 3 STB libraries. Recently I went to rewrite the physics engine for the game as it had a few bugs and didn't scale well—I had initially written it from following Handmade Hero. Initially I was planning for the new system to use discrete collision detection with GJK and EPA. After implenting the two, I found that GJK worked fine, however I encountered a problem with EPA.
The problem was that EPA doesn't take into account the change in position of the colliding objects and only returns the closest edge. I quickly found out that this does not work if you have multiple tiles constituting a platform or floor for the player to run on. EPA would end up returning the side edge of the tile, whereas the correct edge would be the top one, this unfotunately resulted in the player falling through the floor. I read about a few solutions to this, however I thought that it should be possible to modify EPA to take into account the dP of the object.
Rather simply this leads to a modified EPA where the polygon is not expanded based on the closest edge, but instead based on whichever edge is intersecting with the dP of the object. Like EPA the algorithm would iterate on the simplex returned by GJK, meaning that the polygon must contain the origin so if the dP is treated as a ray it must intersect with an edge. A few cases were possible:
1: The dP doesn't intersect with the edge at all, this edge isn't considered
2: The dP is colinear with the edge, this edge is kept unless the dP intersects another edge
3: The dP intersects with the edge, this edge is kept and the loop searching for the edge is broken
3.5. If the dP were a ray it would intersect with the edge, this edge is kept unless the dP is colinear with another edge or intersects another
The rest of the algorithm basically does the same thing as EPA. It uses the intersecting edge to expand the polygon in the direction given by the normal of the edge. If it is able to expand the polygon then the algorithm would loop again, otherwise you then have the intersecting edge. Using this edge you can calculate the intersection point. The time of impact could be calculated by either 1-IntersectionPoint.X/dP.X or 1-IntersectionPoint.Y/dP.Y. The time of impact would be clamped to be within the range of 0 to 1. The normal would then be the inverse of the normal used to expand the polygon. If the intersection point is further along the direction of dP than dP itself (case 3.5—and the time of impact would <0), then the object was colliding before the start of the frame. This allows the algorithm to do a bit of penetration correction.
The GJK support functions would be modified to return the object swept along its dP, in order to prevent tunnelling. In addition to account for multiple moving objects you would use the difference of the dPs of the two objects, then reduce it to one moving object with the new dP and one static one.
I have implented this algorithm and support functions for squares, wedges, and circles. Thankfully I haven't encountered any major flaws in the way this algorithm works. One flaw I have observed is that the moving object can clip the corner of a wedge, which isn't too desirable but can be solved by adding a step height. It seems similar to Casey's idea of searching for a valid position instead of searching for a valid time. I however think that it likely has been documented somewhere else in a paper or something, however I am not entirely sure how to find it if it actually has or not. So far I have been unable to think of any obvious major drawbacks of using this algorithm as it currently works just fine for what I have done so far. I am also unsure how well this would scale into 3 dimensions, as it will be more complicated to calculate the intersecting triangle face of the polytope. Hopefully the explanation I have given isn't too bad.