Is pulse scalar or vector

How to Build a Custom 2D Physics Engine Fundamentals and Momentum Resolution

There are many reasons you might want to create a custom physics engine: First, learning and improving your math, physical, and programming skills are good reasons to try a project like this. Second, a customized physics engine can address any kind of technical effect that the creator can create with the skill. In this article, I want to give you a solid introduction to how to create a custom physics engine from scratch.

Physics provides a wonderful means of enabling a player to immerse themselves in a game. It makes sense that mastering a physics engine is a great asset to any programmer. Optimizations and specializations can be made at any time based on a deep understanding of the inner workings of the physics engine.

At the end of this tutorial, the following topics are covered in two dimensions:

  • Easy collision detection
  • Simple manifold
  • Pulse resolution

Here is a quick demo:

Note: Although this tutorial was written in C ++, you should be able to use the same techniques and concepts in almost any game development environment.


requirements

This article covers a fair amount of math and geometry and, to a much lesser extent, the actual coding. A couple of requirements for this article are:

  • A basic understanding of simple vector math
  • The ability to do algebraic math

Collision detection

There are a few articles and tutorials on the internet including Tuts + that cover collision detection. Knowing this, I want to go through the topic very quickly as this section is not the focus of this article.

Axis-aligned bounding boxes

AABB (Axis Aligned Bounding Box) is a box whose four axes are aligned with the coordinate system in which it is located. This means it is a box that cannot rotate, and it is always oriented 90 degrees (usually aligned with the screen). It is commonly referred to as a "bounding box" because AABBs are used to bind other more complex shapes.

An example AABB.

The AABB of a complex shape can be used as a simple test to determine whether more complex shapes in the AABB might overlap. In most games, however, the AABB is used as the basic shape and actually does not bind anything else. The structure of your AABB is important. There are several ways to represent an AABB, but this is my favorite:

struct AABB Vec2 min; Vec2 max; ;

With this form, an AABB can be represented by two points. The minimum point represents the lower limits of the x and y axes, and max represents the higher limits. In other words, they represent the upper left and lower right corners. To see if two AABB shapes intersect, you need to have a basic understanding of the Parting Axis Theorem (SAT).

Here is a short test from Christer Ericson's real-time collision detection, who uses the SAT:

bool AABBvsAABB (AABB a, AABB b) // end up with no intersection if found separated along an axis if (a.max.x < b.min.x="" or="" a.min.x=""> b.max.x) returns false if (a.max.y < b.min.y="" or="" a.min.y=""> b.max.y) return false // No dividing axis found, so there is at least one overlapping axis that returns true.

Circles

A circle is represented by a radius and a point. Your circle structure should look like this:

struct Circle float radius Vec position;

It is very easy to test whether or not two circles intersect: take the radii of the two circles and add them together and see if this sum is greater than the distance between the two circles.

One important tweak to do here is to eliminate the need to use the square root operator:

float distance (Vec2 a, Vec2 b) return sqrt ((ax - bx) ^ 2 + (ay - by) ^ 2) bool CirclevsCircleUnoptimized (circle a, circle b) float r = a.radius + b.radius return r < distance(="" a.position,="" b.position="" )="" bool="" circlevscircleoptimized(="" circle="" a,="" circle="" b="" )="" float="" r="a.radius" +="" b.radius="" r="" *="r" return="" r="">< (a.x="" +="" b.x)^2="" +="" (a.y="" +="" b.y)^2="">

In general, multiplication is a much cheaper operation than the square root of a value.


Pulse resolution

Pulse resolution is a special type of collision resolution strategy. Collision resolution is the process of inheriting two objects that are found to be intersecting so that they do not intersect.

In general, an object within a physics machine has three main degrees of freedom (in two dimensions): movement in the xy plane and rotation. In this article, we are implicitly restricting the rotation and using only AABBs and Circles. The only degree of freedom we really need to consider is movement along the xy plane.

By resolving detected collisions, we limit movement so that objects cannot overlap. The idea of ​​impulse resolution is the use of an impulse (instant change in speed) to separate found objects from each other. To do this, the mass, position and speed of each object need to be considered in some way: we want large objects that collide with smaller objects to move a little during the collision and the small objects to fly away. We also want objects of infinite mass not to move at all.

A simple example of pulse resolution.

To achieve such effects and to follow the natural intuition of the behavior of objects, we use rigid bodies and some math. A rigid body is just a shape that is defined by the user (i.e., you, the developer) and is implicitly defined as non-deformable. Both AABBs and circles in this article are non-malleable and will always be either AABB or Circle. No squeezing or stretching allowed.

Working with rigid bodies can greatly simplify many calculations and derivations. For this reason, rigid bodies are commonly used in game simulations, which is why we will use them in this article.

Our objects collided - now what?

Assuming we found two shapes that intersect, how can you actually separate the two? Let's say our collision detection gave us two important pieces of information:

  • Collision normal
  • Penetration depth

In order to apply an impulse to both objects and move them apart, we need to know which direction they are being pushed and by how much. The collision normal is the direction in which the pulse is applied. The depth of penetration determines (along with a few other things) how big an impulse will be. This means that the only value to solve for is the size of our momentum.

Now let's go on a long hike to see how we can solve this momentum magnitude. We'll start with our two objects that intersect:

Equation 1

\ [V ^ AB = V ^ B - V ^ A \] Note that to create a vector from position A to position B, you need to do the following:. \ (V ^ AB \) is the relative speed from A to B. This equation should be expressed in the form of the collision normality \ (n \) - that is, we want to know the relative speed from A to B along the direction of the collision normal:

Equation 2

\ [V ^ AB \ cdot n = (V ^ B - V ^ A) \ cdot n \]

We are now making use of the dot product. The dot product is simple; it is the sum of the component-related products:

Equation 3

\ [V_1 = \ begin matrix x_1 \ y_1 \ end of matrix, V_2 = \ begin matrix x_2 \ y_2 \ end of matrix \ V_1 \ cdot V_2 = x_1 * x_2 + y_2 * y_2 \]

The next step is the introduction of the so-called Restitution coefficient. Restitution is a term that means elasticity or swing. Every object in your physics engine is represented as a decimal value. However, only a decimal value is used in the pulse calculation.

To decide which restitution to use (denoted by \ (e \) for epsilon), you should always use the lowest restitution involved in the collision for intuitive results:

// Given two objects A and B e = min (A.restitution, B.restitution)

Once \ (e \) is captured, we can put it in our equation to solve the momentum magnitude.

Newton's law of restitution states the following:

Equation 4

\ [V '= e * V \]

This just means that the speed after a collision is equal to the speed before it multiplied by a constant. This constant represents a "jump factor". In view of this, it becomes relatively easy to integrate the restitution into our current derivation:

Equation 5

\ [V ^ AB \ cdot n = -e * (V ^ B - V ^ A) \ cdot n \]

Notice how we introduced a negative sign here. In Newton's law of restitution, \ (V '\), the resulting vector after the jump, actually goes in the opposite direction of V. So how do we represent opposite directions in our derivation? Introduce a negative sign.

So far, so good. Now we have to be able to express these velocities under the influence of an impulse. Here is a simple equation for modifying a vector by a momentum scalar \ (j \) along a given direction \ (n \):

Equation 6

\ [V '= V + j * n \]

Hopefully the above equation makes sense as it is very important to understand. We have a unit vector \ (n \) that represents a direction. We have a scalar \ (j \) that indicates how long our \ (n \) vector will be. Then we add our scaled \ (n \) vector to \ (V \) to get \ (V '\). This is just adding one vector to another, and we can use this little equation to apply one momentum of one vector to another.

There's a little more work to be done here. Formally, an impulse is defined as a change in impulse. Momentum is. Knowing this, we can represent an impulse as formally defined:

Equation 7

\ [Momentum = mass * velocity \ velocity = \ frac momentum mass \ hence V '= V + \ frac j * n mass \]

The three dots in a small triangle (\ (\ therefore \)) can be read as "therefore". It is used to show that the thing can be used ahead of time to infer that what comes next is true.

So far, good progress has been made! However, we need to be able to express momentum using \ (j \) in two different objects. In the event of a collision with objects A and B, A is pushed in the opposite direction from B:

Equation 8

\ [V '^ A = V ^ A + \ frac j * n mass ^ A \ V' ^ B = V ^ B - \ frac j * n mass ^ B \]

These two equations will shift A away from B along the unit direction vector \ (n \) by momentum scalar (amount of \ (n \)) \ (j \).

Now all you have to do is merge equations 8 and 5 together. Our resulting equation looks something like this:

Equation 9

\ [(V ^ A - V ^ V + \ frac j * n mass ^ A + \ frac j * n mass ^ B) * n = -e * (V ^ B - V ^ A) \ cdot n \ \ therefore \ (V ^ A - V ^ V + \ frac j * n mass ^ A + \ frac j * n mass ^ B) * n + e * (V ^ B - V ^ A) \ cdot n = 0 \ ]

If you remember, the original goal was to isolate our scale. This is because we know in which direction the collision should be resolved (assumed by the collision detection) and have only solved the magnitude of that direction. The size, which is unknown in our case, is \ (j \); We have to isolate \ (j \) and then solve.

Equation 10

\ [(V ^ B - V ^ A) \ cdot n + j * (\ frac j * n mass ^ A + \ frac j * n mass ^ B) * n + e * (V ^ B - V ^ A) \ cdot n = 0 \ \ therefore \ (1 + e) ​​((V ^ B - V ^ A) \ cdot n) + j * (\ frac j * n mass ^ A + \ frac j * n Mass ^ B) * n = 0 \ \ hence \ j = \ frac - (1 + e) ​​((V ^ B - V ^ A) \ cdot n) \ frac 1 mass ^ A + \ frac 1 Mass ^ B \]

Angry! That was pretty much math! It's all over for now. It is important to know that in the final version of equation 10 we have \ (j \) on the left (our strength) and everything on the right is all known. This means that we can write some lines of code to resolve our momentum scalar \ (j \). And boy is the code a lot more readable than math notation!

void ResolveCollision (Object A, Object B) // Calculate relative speed Vec2 rv = B.velocity - A.velocity // Calculate relative speed in relation to the normal direction float velAlongNormal = DotProduct (rv, normal) // Do not resolve when separate the speeds when (velAlongNormal> 0) returns; // Calculate the restitution float e = min (A. Restitution, B. Restitution) // Calculate the impulse scalar float j = - (1 + e) ​​* velAlongNormal j / = 1 / A.mass + 1 / B.mass // Apply impulse Vec2 impulse = j * normal A. speed - = 1 / A. mass * impulse B. speed + = 1 / B. mass * impulse

There are a few important points to keep in mind in the code example above. The first thing is the check on line 10,. This review is very important. This ensures that you only resolve a collision when the objects start moving towards each other.

Two objects collide, but the speed separates them on the next picture. Do not resolve this type of collision.

When objects move away from each other, we don't want to do anything. This prevents objects that should not be considered a collision from being separated from each other. This is important in order to create a simulation that follows human intuition of what should happen during object interaction.

Second, note that the inverse mass is calculated multiple times for no reason. Simply save your inverse mass in each object and calculate it once in advance:

A.inv_mass = 1 / A.mass Many physics engines actually do not store raw mass. Physics engines often store inverse mass and inverse mass alone. It just so happens that most of the math that involves mass is in the form of.

The last thing to note is that we are intelligently distributing our momentum scalar \ (j \) over the two objects. We want small objects to bounce off large objects with a large proportion of \ (j \) and that the speed of the large objects is changed by a very small proportion of \ (j \) ..

To do this, you can do the following:

float mass_sum = A.mass + B.mass float ratio = A.mass / mass_sum A.speed - = ratio * pulse ratio = B.mass / mass_sum B.speed + = ratio * pulse

It is important to know that the code above corresponds to the example function from before. As mentioned earlier, inverse masses are very useful in a physics machine.

Sinking objects

If we go ahead and use the code we have so far, objects will run into each other and jump off. That's great, although what if one of the objects has infinite mass? Well, we need a good way to represent infinitely many masses in our simulation.

I suggest using zero as infinite mass - although we are trying to calculate the inverse mass of an object with zero, we have a division by zero. To work around this problem, do the following when calculating inverse mass:

if (A.mass == 0) A.inv_mass = 0, otherwise A.inv_mass = 1 / A.mass

A value of zero results in correct calculations during pulse resolution. That's still fine. The problem of sinking objects arises when something sinks into another object due to gravity. Perhaps something with little restitution hits a wall of infinite mass and begins to sink.

This decrease is due to floating point errors. With every floating point calculation, a small floating point error is introduced due to hardware. (For more information, see Google [Floating Point Error IEEE754].) Over time, this error accumulates in position errors, causing objects to sink into one another.

In order to correct this error, it must be taken into account. To correct this positional error, I'll show you a method called linear projection. The linear projection reduces the penetration of two objects by a small percentage. This is done after the pulse is applied. The position correction is very simple: move each object along the collision normality \ (n \) by a percentage of the penetration depth:

void PositionalCorrection (Object A, Object B) const float percent = 0.2 // normally 20% to 80% Vec2 correction = PenetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n A.position - = A .inv_mass * correction B.Position + = B.inv_mass * correction

Notice that we're scaling this by the total mass of the system. This leads to a position correction that is proportional to our mass. Small objects are pushed away faster than heavier objects.

There's a little problem with this implementation: if we always fix our positional error, the objects will jump back and forth while lying on top of each other. To prevent this from happening, some leeway must be given. We only perform a position correction if the penetration is above any threshold called "slop":

void PositionalCorrection (Object A, Object B) const float percent = 0.2 // normally 20% to 80% const float slop = 0.01 // normally 0.01 to 0.1 Vec2 correction = max (penetration - k_slop, 0.0f) / (A. inv_mass + B.inv_mass)) * percent * n A.position - = A.inv_mass * correction B.position + = B.inv_mass * correction

This means that objects can always penetrate something without the position correction occurring.


Simple generation of distributors

The final topic to be covered in this article is simple manifold. A diverse In mathematical terms, something is like "a collection of points that represents an area in space". However, when I refer to the term "manifold" I am referring to a small object that contains information about a collision between two objects.

Here is a typical manifold build:

struct manifold object * A; Object * B; Float penetration; Vec2 normal; ;

When detecting collisions, both the penetration and the collision normal should be calculated. To find this information, we need to expand on the original collision detection algorithms earlier in this article.

Circle against circle

Let's start with the simplest collision algorithm: circle against circle. This test is mostly trivial. Can you imagine in which direction the collision should be resolved? It is the vector from circle A to circle B. This can be obtained by subtracting the position of B from A.

The penetration depth refers to the radii of the circles and the distance from each other. The overlap of the circles can be calculated by subtracting the summed radii by the distance from each object.

Here is a complete example algorithm for generating the manifold of a collision between circle and circle:

bool CirclevsCircle (Manifold * m) // Set a few pointers to each object Object * A = m-> A; Object * B = m → B; // Vector from A to B Vec2 n = B-> pos - A-> pos float r = A-> radius + B-> radius r * = r if (n.LengthSquared ()> r) returns false // Circles collided, now compute the manifold float d = n.Length () // do the actual sqrt // if the distance between the circles is not zero if (d! = 0) // distance is difference between Radius and distance m-> penetration = r - d // use our d because we have already executed sqrt within Length () // points from A to B and a unit vector c-> normal = t / d is true / / Circles are in the same position else // pick random (but consistent) values ​​c-> penetration = A-> radius c-> normal = Vec (1, 0) return true

The most notable things here are: we don't do square roots until we need to (objects are found to be colliding), and we check that the circles aren't exactly in the same position. If they were in the same position, our distance would be zero and we need to avoid dividing by zero when calculating.

AABB versus AABB

The AABB-to-AABB test is a little more complex than Circle vs Circle. The collision normal is not the vector from A to B, but a face normal. An AABB is a box with four faces. Every face has a normal face. This norm represents a unit vector that is perpendicular to the face.

Investigate the general equation of a line in 2D:

\ [ax + by + c = 0 \ normal = \ begin bmatrix a \ b \ end bmatrix \]

In the above equation, and are the normal vector for a line and the vector is assumed to be normalized (vector length is zero). Our collision normality (direction to resolve the collision) will be towards one of the face normals.

Do you know what a line represents in the general equation? is the distance from the origin. This is very useful for testing if a point is on one side or the other of a line, as you will see in the next article.

Now all you have to do is figure out which face one of the objects collides with the other object and we have our normalcy. However, sometimes multiple faces of two AABBs can intersect, e.g. B. when two corners intersect. That means we have to find that Axis of least penetration.

Two axes of penetration; The horizontal x-axis is the axis of least penetration and this collision should be resolved along the x-axis.

Here is a complete algorithm for AABB-AABB elbow generation and collision detection:

bool AABBvsAABB (Manifold * m) // Set a few pointers to each object Object * A = m-> A Object * B = m-> B // Vector from A to B Vec2 n = B-> pos - A-> pos AABB abox = A-> aabb AABB bbox = B-> aabb // Calculate half dimensions along the x-axis for each object float a_extent = (abox.max.x - abox.min.x) / 2 float b_extent = ( bbox .max.x - bbox.min.x) / 2 // Calculate overlap on x-axis float x_overlap = a_extent + b_extent - abs (nx) // SAT test on x-axis if (x_overlap> 0) / / Calculate half dimensions along the x-axis for each object float a_extent = (abox.max.y - abox.min.y) / 2 float b_extent = (bbox.max.y - bbox.min.y) / 2 // Calculate the overlap on the float of the y-axis y_overlap = a_extent + b_extent - abs (ny) // SAT test on the y-axis if (y_overlap> 0) // determine which axis is the axis of smallest penetration is if (x_overlap> y_overlap) // show in direction B that n is points from A to B if (nx < 0)="" m-="">normal = Vec2 (-1, 0) else m-> normal = Vec2 (0, 0) m-> penetration = x_overlap return true else // Show in direction B that n points from A to B if (n.y < 0)="" m-="">normal = Vec2 (0, -1) otherwise m-> normal = Vec2 (0, 1) m-> penetration = y_overlap return true

Circle against AABB

The last test I'll cover is the Circle vs. AABB test. The idea here is to compute the closest point on the AABB to the circle; From there, the test is converted into something similar to the Circle-vs-Circle test. When the closest point is calculated and a collision is detected, normality is the direction closest to the center of the circle. The penetration depth is the difference between the distance to the closest point and the radius of the circle.


AABB circle section diagram.

There is a tricky special case. If the center of the circle is inside the AABB, the center of the circle needs to be shortened to the nearest edge of the AABB and normality rotated.

bool AABBvsCircle (Manifold * m) // Set a few pointers to each object Object * A = m-> A Object * B = m-> B // Vector from A to B Vec2 n = B-> pos - A-> pos // Next point on A to the center of B Vec2 closest = n // Calculate half extensions along each axis float x_extent = (A-> aabb.max.x - A-> aabb.min.x) / 2 float y_extent = (A-> aabb.max.y - A-> aabb.min.y) / 2 // point in brackets at the edges of the AABB next. X = brackets (-x_extent, x_extent, next.x) the next. y = Clamp (-y_extent, y_extent, close.y) bool inside = false // The circle is in the AABB. So we need to clip the center of the circle // to the nearest edge if (n == closest) inside = true // Find the closest axis if (abs (nx)> abs (ny)) // Closest Clamp extension if (densest.x> 0) next.x = x_extent otherwise next // Clamp on narrowest extension if (closest.y> 0) next.y = y_extent next closest // Ea rly outside of the Radius is shorter than the distance to the closest point and // circle not inside the AABB if (d> r * r &&! Inside) returns false // avoid sqrt until we need d = sqrt (d) // collision normal must be turned outwards if the circle // was within the AABB, if (inside) m-> normal = -n m-> penetration = r - d else m-> normal = n m-> penetration = r - d return true

Conclusion

Hopefully you've learned something about physics simulation by now. This tutorial is enough to set up a simple custom physics engine that has been built from scratch. In the next part we will cover all of the necessary extensions that all physics engines will need, including:

  • Sort and sort out contact pairs
  • Broadphase
  • Layering
  • integration
  • Time trial
  • Halfspace intersection
  • Modular structure (materials, mass and forces)

Hope you enjoyed this article and I look forward to answering questions in the comments.