Generating Concave Hull
Before the working on collision algorithms, I needed my program to generate 2D object geometries. I came up with a simple method which could calculate the concave hull of a 2D image. The program crates lots of line equations that merge at the center of the image, then it starts checking the transparency values of each point on each line far away from the image, and once it detects a non transparent pixel, the program adds that coordinate to a vertex array. While coding this algorithm, I made the program visually draw each scan-line and hull vertex in order to make sure it worked correctly, and the pictures below is a screenshot from depicting the debug lines and vertices. The image actually has a rectangular size larger than the blue weird object at the center, and all pixels outside of the blue image are transparent.
Implementing Graham’s Scan to generate Convex Hull
After succeeding scanning the vertices that form the concave hull of the 2D object, I needed to extract the convex hull from this concave hull so that I could directly use the SAT algorithm to check the presence of any collision. I used the Graham’s Scan algorithm to generate the convex hull displayed below.
SAT collision detection algorithm worked really well, in fact if was inefficient since it compares all edges of two shapes which is lots of comparisons in total. Also I wanted to make the object to stop at the right position when it collided to make a realistic collision effect. I had heard about a faster algorithm called GJK which is actually harder to implement compared to SAT. To implement the GJK, I used this great tutorial, and luckily I knew this person from the HandmadeHero tutorial series who inspired me before to make my own 2D rendering engine in C from scratch. So I implemented the GJK algorithm, found some bugs, fixed them and it worked.
While I was reading about the GJK algorithm, I also had read that it was used with EPA to calculate the collision response vector. So I learned EPA and implemented and it worked.
My Own Algorithm
GJK and EPA works for for 3D objects, in fact my object was 2D and I thought I could optimize the algorithm to run efficiently for 2D objects. While modifying the GJA and EPA algorithms, I found an alternative way to check the presence of collision and calculate the penetration vector in a single algorithm. I implemented the algorithm, and it worked fine. I optimized this algorithm even further to make it work at constant time when objects collide at the same points at each frame by storing the final collision edges for the next frame. Check the video below.
When I first developed the collision algorithm, I described it informally on 2 sheets of paper, so that I wouldn’t completely forget it.
Then I decided to describe the algorithm a little more formally using Latex. You can download it below. I actually wanted to make some tests and share the results in the paper, in fact I did not go that far. Although this paper give a solid explanation of the algorithm, there are some typos and redundant explanations.
While reading about the Minkowski Sum concept, all the texts were explaining a super simple concept in the hardest way. So I made a Minkowski-Sum calculator to assist learning this concept using Java-script which was fun to make.