2D Physics Engine

Description

Fizz is a 2D, real-time physics engine.

It is implemented with as much generality as possible. All collision detection and resolution algorithms are dimension agnostic, meaning it could be expanded into a 3D engine without any major functionality changes.

Additionally, the interface to describe colliders is very general; the main requirement is a function to find support points. Therefore, even though only convex polygons and circles are supported currently, other shapes such as ellipses could be added easily.

I deeply enjoyed learning both the physics and algorithms needed for computers to simulate realistic motion through this project. It was very satisfying to try to capture the dynamics of everyday interactions using only math, and even more so to be able to tweak the rules of those interactions in my simulation.

Source code is available here.

Features

Technologies

• Built for / using my custom game engine, Nutella

Features

• Broad phase collision detection using quadtrees
• Narrow phase collision detection using the Gilbert-Johnson-Keerthi algorithm and the Expanding Polytope algorithm
• Impulse based collision resolution

What I’m most proud of: The Algorithms

This project really tested my technical skills - both on the math side and the computer science side. It is a surprisingly difficult problem to teach a computer to check when two shapes are overlapping, and even more difficult to extract information about how they are overlapping. But these problems are fundamental to simulating believable physics, and so I had to learn and implement some rather complicated algorithms.

Reading Papers: I chose to do this mainly from the original papers where the algorithms were published. Though these papers were likely not the fastest way to create a working product, I saw several advantages to doing things this way. Seeing technical arguments for the correctness of the algorithms gave me a much deeper understanding of why and how they work. I can use this information in the future to design my own algorithms to solve similar problems. Additionally, I wanted to practice my technical reading skills, and learn how to better understand dense, technical writing. I wouldn’t have been able to do any of this by simply googling someone else’s implementation.

Linear Algebra: While implementing these algorithms, I learned about several mathematical concepts that were new to me, such as simplices, linear and affine combinations, and Minkowski differences. I ended up implementing classes or methods for many of these concepts in code, helping me to further understand them. I also was exposed to a neat way to derive the impulse forces required to separate two colliding objects, and implemented that as well.

Getting the algorithms to work correctly felt especially rewarding, since I had accomplished something more independently than I usually do most of my projects. Sites like StackOverflow are wonderful to find quick solutions and small nuggets of wisdom, but I wanted to prove to myself that I was not dependent on them to be a successful programmer. This project was my opportunity to do just that, and to make something that I think is really cool in the process.

What was most challenging: Measuring Performance

Physics calculations can get quite computationally expensive, especially if they are not implemented well. As part of building this project, I researched several different algorithms, and often implemented multiple of them. However, I found it difficult to tell which one, if any of them, was more performant.

Many of my simulations were very small on the scale of a professional physics engine, having just a handful of objects. For these very small simulations, even unreasonably inefficient algorithms often did not produce a visible slowdown. In particular, it was difficult to tell if my broad phase collision detection algorithms actually gave any benefit, since they are designed to mitigate the cost of having many objects in a scene.

Large Test Scenes: My first approach was to create code that procedurally creates many objects in a scene. This on its own was not particularly challenging, but did not provide a satisfying solution. Even with many more objects, trying to visually gauge the performance felt very imprecise and error prone.

Developed Profiling System: The ultimate solution I settled on was to integrate profiling code into my engine itself. I created a custom object with an overridden destructor that writes the time passed since its creation to a json file. Using this object, I can profile scopes easily by using stack allocations and automatic destruction when the scope exists. This gave me much more precise information about how much time I was spending in each method, and usually gave a clear indication of which algorithm performed better.