2D Physics System

This slideshow requires JavaScript.

Overview

The 2D Physics Engine is a physics system integrating the collision detection and resolution pipeline with 2D primitives. I decided to implement this system to improve physics and math infrastructure of my engine back then and learn about more physics concepts.

Info

  • Role: Programmer
  • Engine: Personal engine
  • Language/Tool: C++, OpenGL, GLSL
  • Dev Time: 2 months

Features

  • 2D primitives including disc, capsule and AABB2 and OBB2
  • Collision detection pipeline on these primitives
  • Collision resolution pipeline on these primitives
  • Linear and angular dynamics
  • Broadphase processing using Bounding Volumes, Sweep and Prune and Quadtree
  • Restitution and friction
  • Debug draws (texts, wireframe primitives, etc)
  • Continuous collision detection (or CCD) with the Minkowski difference

Pipeline

  • The physics scene is in charge of the physics core loop
  • The loop updates dynamics of each object, generates contacts and uses them to resolve collisions with objects’ positions and velocities

Collision Detection

Manifold

  • Contact data are stored in Manifold
  • To generate contacts we need to test intersections among objects
  • A general test is the one between on OBB2 with the Separating Axis Theorem, which can be extended into tests on general convex shapes

SAT

  • The theory says that if we can find an axis, along which the intervals of the two shapes projected onto this axis do not intersect, we can conclude that the two shapes do not intersect
  • There is one problem: we do not know the exact location of the contact point, an important contact info for resolution. The solution is a variation of the SAT, which uses the concept of Supporting Point.
  • The Supporting Point of a face is defined to have the most negative extension along that face’s normal. If the face only has a point with positive extension, we say that it does not have a SP at all.
  • The modified SAT now becomes: iterate faces of the shape, if any face does not have a SP against vertices of the other shape, then they do not collide. But if such point exists, the SP itself gives us location info we missed.

Here is a snippet of finding an SP along certain normal direction of an OBB2:

 

Collision Resolution

For collisions, some physics engines simulate them with an impulse model.

Linear Impulse

  • The linear impulse in normal direction considers the relative velocity along that direction, the restitution factor e, and the product over sum of inverse mass to compute final result
  • The tangent version applies in direction of tangent instead, and uses friction, not restitution

Angular Impulse

  • Angular impulse is a little different, since we cannot assume the force is applied on the center of mass
  • From the center to the contact point P, there is a displacement vector, R, which is important in this model
  • This time we need the cross product of normal and R to form a torque, and divide that with moment of inertia I.

  • Same logic for tangent version, except that friction replaces restitution.

Here is the resolution core for OBB2 vs OBB2:

linear impulse – box vs box
angular impulse – box vs box

With collision generation and resolution implemented, I already have an artifact that shows decent dynamics:

Note how the boxes turn to grey to show lower restitution and to purple for higher friction. Both decrease momentum in the scene.

 

Broadphase

Collision detection is very expensive. We need some way to improve performance – the Broadphase. 

Broadphase is where we filter collision pairs that are unnecessary to even bother with because we know for sure that they cannot collide. There are a lot of techniques for this; I implemented a Bounding Volume filter, the Sweep and Prune algorithm and the Quadtree.

The BV filter is naive: if the BVs do not overlap, then it is impossible for their objects to overlap. I’ve tested using disc and AABB as BV.

The SAP and Quadtree are described below:

Sweep and Prune

  • SAP uses a similar concept: if we project the shape onto an axis to form an interval, we know the shapes do not overlap if their intervals do not overlap
  • A good candidate of the axis is the world x-axis as left
  • You can combine with more axes if you want (like x and y axis at the same time), as long as you make sure that it does not do too much work and beats the purpose of optimization

Quadtree

  • With Quadtree, I splitted the screen into four identical rectangular sections recursively, so that shapes not in the same section of the level never collide
  • Note on the left that sometimes when the static platform lies with itself in the bottom right section, it is not highlighted, and not part of the collision pipeline

Here is a snippet of quadtree insertion, which dynamically updates the tree as new objects add in:

 

CCD

Continuous collision detection aims for solving the tunneling effect, where if an object moves too fast, it may “fly through” the obstacles.

Minkowski Difference

  • The Minkowski Difference is the math building block behind CCD
  • It says that if the set of vertices of object A is A, and same for B as B, the Minkowski difference is AB, ignoring duplicates
  • It is meaningful that if A and B overlaps, A-B must include the origin, since you can find such a point that is in both sets. Check the demo on right.

Time of Impact

  • There are two methods we can use: relative velocity and raycasts
  • We use relative velocity to fix the frame of an object, making the life easier. We use raycast since we can use its parameter t to find the exact TOI.
  • With these, we raycast from the origin in the reverse direction of the relative velocity, and see when that ray hits the Minkowski shape. That timestamp is the TOI. See the demo.

The logic for the AABB case is:

 

Post Mortem

What went well

  • Improved the 2D Math and Physics infrastructure of my Engine a lot
  • Developed an interest on 3D Physics, which later became my thesis topic
  • Spent some time on polishing the debug draw system which helped a lot in many projects

What went wrong

  • Had to go off track and fix some hidden bugs in my renderer before I implemented physics features
  • Did not have enough time to get into 2D convex shape collision
  • Spent quite some time on validating math before actually implementing Physics based on them

Action Plan

  • Have a plan for setting up test cases to validate infrastructures, graphics or math
  • Continue to research on general shapes and implement their collisions