GJK Algorithm
Project Work in Computer Graphics and Interaction - masters's course - Graded A
Platform
Windows PC
Tools used
Unity, Visual Studio, OpenGL, GLUT.
Duration
6 weeks
Team Size
1
The course
The project was done for a master's course called Computer Graphics and Interaction. As our professor said "A big part of Computer Graphics and Interaction is math-programming". I chose to focus on the interaction side of it, which to a big degree is about simulating physics and motion. The course consisted of both some interesting lab assignments and a larger project I present below.
The Project - Graded A
Since I had previously been responsible for programming collision handling in game development projects during the bachelor I was curious about learning more in detail how collision algorithms work. In my research I learned that an algorithm called GJK is a fundamental piece and I decided to try and implement this in Unity as a plugin. Since many online descriptions of the algorithm omitted the computation of closest points between objects and usually exemplified in 2D, I decided to fill a void by implementing these aspects in my project.
As seen in the GIF at the top, the implementation detects insersection of convex polyhedra, making them red, and draws white lines between the closest points of the non-intersecting objects.
The final report, written as a scientific article submission, can be read here:
(If the iframe for the pdf above isn't working you can download the pdf here: [Report.pdf].)
The code for the GJK algorithm, including computation of closest points, is available here: [github.com/frilel/CLCollision].
The Unity project example, which the GIF at the top shows, is available here: [github.com/frilel/GJK_tester].
I also kept a blog that sort of documented my work process which can be read here: [Blog].
Lab Assignments - Graded PASS
The course also had some interesting and challenging labs. The lab track I chose mainly had me explore programming with OpenGL in C++. Some of the notable things I learned was to write basic vector math and quaternion classes. Using these classes I would make OpenGL draw a simple tank 3D model, assembled with separate pieces. The view frustum could be moved with keyboard input to look around the tank. Learned how to apply transformations to OpenGL matrices. This had me learn about how transforms and transform hierarcy for animating parts work in detail. I programmed a basic Bounding Volume Hierarcy for making penetration/collision tests with, exemplified in the GIF above.
More can be read in my lab reports here: [Google Drive Folder].