# Blog

During Week 9, my main focus was to make torque work for Polygon vs Polygon. The issue that I had that made the torque not work correctly for the latter case is that my manifold generation was limited. I was only generating one point of contact, which worked fine for circles, but not for polygons. In most cases, we have a collision segment, which we can represent with 2 points.

Here are some code snippets of how I’m handling manifold generation for polygon vs polygon:

Below are the helper methods for clipping and finding the edge to use:

This article helped me a lot with figuring out how to do this.

After adding this, and debugging it, I noticed that there still are some edge cases where the clipping generates only one point of contact when it’s supposed to generate two, but I got over that for two reasons: First, I had an issue with inertia calculation for polygons, which was a more pressing matter, and second, this bug was not that frequent. I’m planning to handle this at a later time.

Coming back to inertia, the method that I was using to calculate the latter was giving me inconsistent values, so I decided to scrap that and follow another method.

What I did is I always took (0, 0) as the centroid, and then translate all of the vertices of the polygons accordingly. Which allowed me to do an easier calculation to get the inertia:

I revisited the torque calculations too by treating some of the edge cases.

Lastly, I updated the testbed, and the most prominent change was that added a random body spawner and a resetter.

Here’s the final product that I got:

You can always check the project on my GitHub.

During Week 8, I started by adding friction to the game engine. Friction is a force that resists the motion of a body, which means it’s opposite to where the body is moving towards. Granted, friction in real life is more complicated than what we represent it as, however, the approximations we do during the calculations, make the latter seem natural enough.

So the way I represented friction is as an impulse along the negative tangent vector of the collision. And when it comes to deciding the tangent, we take the tangent closer to the new relative velocity, which makes sense, since we want the friction to be along the negative of that vector, to resist the motion of the body.

A couple of things to keep in mind when working on friction. First, we need to follow Columb’s Law, which basically clamps the friction impulse to the impulse along the normal. Second, we need to decide on how to calculate the friction factor from both bodies friction factors. I chose to go with a simple average. And last but not least, we need to think about how to represent dynamic friction. I just chose to multiply the static friction factor by a number less than 1 (0.7f to be exact) to get the dynamic friction factor.

Here’s the code that I added to the collision resolution method to account for the friction impulse resolution:

And here is the result of those changes:

After adding friction, I tackled one of my biggest challenges during this project so far: Adding rotational movement, which means adding Torque and Angular velocity.

So I started working on that, however, once I did, I noticed I had a problem in my simulation: the mass of the object affected its free fall speed, which does not make sense. I didn’t notice that before, but when I changed a couple of densities to match real life materials like steel, I discovered that I was resolving gravity incorrectly.

Thus, to fix that, I changed UpdateForces and UpdateVelocities from:

To:

It was a mistake on my part that I didn’t notice because the simulation seemed fine at the time.

After fixing that bug, I did some research on how to add torque. I found this paper that talks about impulse resolution for translating and rotating bodies, which was really informative. The first thing I noticed is that I needed to retrieve the collision contact point. So I added that to the Manifold structure that I added previously, and I populated that in the collision detection phase. I had a problem with Polygon vs Polygon though because the way I implemented SAT, I don’t deduct the collision points from my computations, so that’s the first order for next week update. I noticed also that I needed to implement the perp-dot product, which is the equivalent of the cross product in 3D. That is why I called it Cross product in my implementation:

After that, I updated my impulse resolution computations to account for the angular velocity and to apply torque to the contact point:

Now the results for Circle vs Circle were solid, however, Polygon vs Circle was wacky. Not to mentions polygon vs Polygon since I don’t have correct contact points as of now, which led me to believe that I might have some issues in my polygon inertia computation, so I need to recheck that too next week.

Here is the result for Circle vs Circle:

You can always check the project on my GitHub.

During Week 7, I started by doing more tests on my Broad Phase and the collision resolution, which led me to discover some bugs in my code.

First of all, I had a minor bug in my AABBOverlap method, which was considering the AABB structure differently than it actually is. What I mean by that is, the AABB that I’m using has the top right and the bottom left corners, the AABB that the method was considering has the top left and bottom right corners.

Secondly, I changed the collision detection to work with the next position rather than the current position, which gives a better presentation to the collisions.

After I added a test case where I have multiple objects in the same scene interacting with each other, and the result was not what I was expecting: some bodies didn’t collide and got stuck to each other, others just went inside of other bodies etc.

So I debugged my code and I discovered that the problem was mainly caused by the direction of the normal. The reason why I didn’t notice this problem in the last week is that I had the same orientation from one object to the other, for example, for the polygon vs circle collision, I had the circle at the bottom of the polygon. So what I had to do to fix that bug is to compare the direction of the vector from the center of one object to the other to the normal, if they’re not in the same direction, then I reverse the normal.

That mostly fixed the bug, but not entirely. The issue that I still had was that if I have a large object, the normal is still not correct. The reason behind that is the center is probably far from the collision point, which gives the illusion that the direction between the centers and the normal direction are different, and thus the normal gets reversed. So to fix that issue, I don’t resolve the collision if the impulse causes one object to get closer to the other rather than further, so that avoided me having the smaller object get stuck to the bigger object.

I also didn’t resolve the collision of two objects not moving in opposite directions. And that makes more sense for the user than seeing two objects basically moving in the same direction with the same speed colliding and going in the opposite direction.

Here is a simulation for what I had after:

Phew, now since that is out of the way, let’s talk about the new features. So I added the centroid computation for the polygon shapes, which is used in the collision resolution fixes that I mentioned earlier and is going to be used for Inertia.

And speaking of Inertia, I also calculated that since I’m going to need it when I’m going to add rotational movement support to the engine. So calculating the latter for a concave non-regular polygon wasn’t the easiest thing to figure out. I did the research on how to do it, and the most convenient way I found was described in this article.

The method that I used is basically a combination of Polygon Triangulation using the centroid that we just calculated and Parallel Axis Theorem. The concept is simple, I decompose the polygon into multiple triangles, where each triangle is composed of one of the edges and the center. The inertia of the polygon is the sum of the inertias of the all of the triangles it contains, and the reason behind doing this is that the computation of the inertia of a triangle is easier. This web page gives more info on how to compute a triangle inertia. The inertia I’m computing is the one around the Z axis.

I actually didn’t use exactly the formula mentioned there, but a derivation of it that uses the vertices coordinates, which bodes better for me. I found the formula in one of the comments in the article I mentioned earlier.

The code is not the prettiest but it does the job with the info that I have at my disposal, with the least overhead possible:

Moving on, I added support to static bodies. Static bodies are basically bodies that have infinite mass and zero velocity and are not affected by forces like gravity. The mass and InvMass are represented as zeros in the code so that the formulas would add up.

The static bodies support was actually a preparation step to the next step which is adding gravity to the engine. The reason behind that is having a static body that will prevent the other bodies from falling off the screen, which is handy for the simulation.

Adding gravity is simple, all I had to do is add gravity to the force applied on an object, which will later also contain other forces like friction, and then update the velocity accordingly, and finally update the position:

That did the job, however, I had a problem in the simulation after this; the bodies were sinking into the static body beneath them:

Thanks to this article, I found a solution for this. I’m doing a positional correction for each pair of bodies that just collided:

And that gave me these results:

You can always check the project on my GitHub.

During Week 6, I started by adding a Broad Phase to my collision detection. The Broad Phase is used to basically create pairs of potentially colliding bodies. To do this, I used Axis Aligned Bounding Boxes or AABBs, and the reason behind that is that detecting collision between AABBs is not expensive. Therefore, the Broad Phase helps us avoid doing expensive collision detections between complicated shapes each update, and instead, do those only if two bodies are potentially colliding, which is what we call the Narrow Phase.

Here is my AABB structure:

At this point, I gave my collision module structure some thought. During my research, I saw that many developers have the bodies or colliders they have in the world in the Broad Phase class, and they add them and remove them dynamically, which is something that I already had in my World class, so I ditched that concept and I made the Broad Phase as a Singleton, that for now has one method: GetPotentiallyColldingPairs, to which I pass the list of Bodies that I have in World.

Here is a code snippet showcasing that method:

I make sure that I have duplicate culling during this process.

After that, I started woking on the collision resolution. I added a Manifold structure that holds information about the collision. For now, I’m only considering one point of contact, therefore the structure looks like this:

I’m using this structure for all types of collision resolution, and I’m following the Impulse resolution strategy for that. The idea behind impulse resolution is that we use an impulse, which is an instantaneous change in velocity, to separate objects found colliding.

Here is the code for the collision resolution method:

The challenge after that was building the manifold, which differs depending on the collision type.

For Circle vs Circle collision, it’s as easy as setting the normal as the normalized vector between the centers, and the penetration as the total of radii minus the distance between the circles:

For Circle vs Polygon, it’s nearly the same as Circle vs Circle but with more cases to take care of. If the circle is colliding with one of the vertices, we use the vertex and the center of the circle to build the manifold:

However, when the circle is colliding with an edge, we use the projection point and the circle center to build the manifold:

Polygon vs Polygon was the most challenging one. If you remember from the previous article, I’m using SAT for Polygon vs Polygon collision. To build the manifold, I need to keep track of the smallest overlap and its axis:

Now that all of that is out of the way, here are the results:

You can always check the project on my GitHub.

During Week 5, I focused mainly on finishing up the collisions detection, testing all of its cases and render the results. Creating the testbed was a big part of this week’s work, and the latter helped me debug my collisions detection.

I started by drawing circle and polygon shapes in the testbed. I’m using SFML as my OpenGL library. SFML is a cross-platform C++ multimedia library that provides access to graphics, input, audio, networking and the system. I chose this library because of its ease of use. The purpose of this project is not to learn OpenGL, but to use it to visualize the Physics engine.

To draw different kinds of bodies, I created a WorldRenderer class, which helps render all of the bodies in a world with a fair amount of customization, regardless of their shape.

Here is a code snippet from WorldRenderer:

This method handles rendering a polygon to the screen.

After that, I went back to the collision detection module, and I added the Polygon to Polygon Collision. I used the Separating Axis Theorem (SAT) for this type of collision.

SAT states that: “If two convex objects are not penetrating, there exists an axis for which the projection of the objects will not overlap.

Pretty simple concept, here’s a diagram that illustrates how SAT works:

You can see there that all of the projections collide, if we had at least one projection that does not collide, that means that the polygons do not collide.

Here is my implementation in C++ for SAT:

For now, I’m banking on the fact that the polygons are convex since my SAT implementation assumes that the polygons are convex, and it’s not treating the case where the polygons are concave. There is a way to add support for concave polygons, but it’s a stretch goal for now.

I would recommend this article as a good read to understand how SAT works. I actually got the diagram explaining SAT from that article.

To test the different collisions, I added first an update method to the World which will go through the bodies and call their Update method, which updates the transform of the body proportionally to the elapsed time since the last frame. And in consequence, I added a game loop that calls the world Update after a certain fixed time, that depends on a fixed frame rate. The reason behind having the framerate fixed is to have a consistent output and also to avoid updating the world too frequently.

I created different bodies from different JSON files to simulate the different kinds of collisions. Here is the result for that:

You can always check the project on my GitHub.

During Week 4, I started to work on collisions detection while still adding elements that I needed to the engine core along the way.

I started by adding a singleton JSON parser that initializes and creates bodies from JSON files. I’m using RapidJson as my library for parsing. The parser can parse bodies with different shapes, be it a circle shape, or a polygon shape which I’ll be talking about more later in the article.

Here are some examples of parsable JSON files:

This slideshow requires JavaScript.

And to make sure the parser works perfectly, I added some unit tests.

After that, I made the abstract class Shape as an RTTI by adding an RTTI class that does safe runtime type casting and type checking, and by inheriting that class from Shape. I added the PolygonShape class which represents a polygon shape. Same with CircleShape, it inherits from Shape, and thus implements its methods. I postponed calculating the inertia and the mass center, though, for time sake.

And finally, I created a Collision class that handles the different types of collisions: Circle vs Circle, Circle vs Polygon and Polygon vs Polygon.

Circle vs Circle collision check is really straight forward: all I had to do is compare the distance squared and the sum of the radiuses squared:

I”m using squared values here for performance purposes.

Circle vs Polygon, on the other hand, was a little bit tricky. To check if a Circle collides with a Polygon, we’re going to use some math concepts like projection, dot product etc. and also the Voronoi diagram.

The following diagram shows a convex polygon and its Voronoi regions. To create the Voronoi regions, we draw lines perpendicularly from the end of each edge:

The algorithm I’m using goes like this:

• Look for the closest vertex to the circle, while doing so, if the current vertex is colliding, which means the distance squared is less than the radius squared then we’re done, if not we continue.
• Check if the circle is within the region of either edge of the two side edges of the vertex. If so, check if the distance from the edge to the circle center is less than the radius.
• If we have no collision, we check if the circle is inside the polygon since we know that the circle will be to the left of at least one of the two edges of the nearest vertex if it is inside the polygon.

No unit tests are done on this yet.

You can always check the project on my GitHub.

During Week 3, I continued to work on the Engine core. I added a World class, which contains all of the created bodies. It also contains the gravity and it will be the centerpiece for the physics engine simulation.

I also added factories to create bodies through the world and fixtures through bodies. These factories take in configuration structs to make the creation easier and also allow us to reuse those configurations.

Here’s an updated version of the structure now:

After that, I tested the world and the bodies creation sequence with a unit test to make sure I don’t have any memory leaks or issues.

Here’s the test I did:

You can always check the project on my GitHub.

During Week 2, I started to work on the Engine core. The first thing I did is that I decided to use GLM as my math library and I tried the different functionalities it provides for vector2 math. I tested things such as the dot product, arithmetic operations, vector normalization, reflect etc.

I’m planning to add my own math library that will use GLM, however, which will introduce some specific functions and optimizations related to my project, such as length squared.

After that, I started working on the rigidbody. I drew a lot of inspiration from Box2D when structuring my rigidbody, since the latter has a modular structure that I admired.

Here’s a class diagram illustrating the structure:

You can always check the project on my GitHub.

During my third semester at FIEA, I chose to do a 2D physics engine in C++ as my programming personal project. The project is called Physia2D.

The goal is to have a physics engine with bodies that have three degrees of freedom: Movement along the XY plane and rotation. Also, a testbed for the engine using OpenGL is part of the plan.

During Week 1, I worked on the presentation for the proposal of this project and started reading about how to write a 2D Physics engine. I found the Box2D manual to be very useful, as well as several blogs that explained how a physics engine operates.

I made a rough schedule for the project that looks like this:

• Week 1: Set up the project and do more research on the subject.
• Week 2-3: Engine Core: Math tools and the basic architecture of the engine (Rigidbodies and their components …).
• Week 4-5: Collision detection (Broading phase and Narrow phase) and resolution.
• Week 6-7: Prepare the testbed for the simulation.
• Week 8: Add Gravity and Friction.
• Week 9: Optimizations.
• Week 10: Finishing touches and buffer time.

After the presentation, I started by setting up the project and proceeded to read more about the subject.

You can check the project on my GitHub.