Video Game Design 5 | Physics Engine, Collision Detection and Solution, and Further Concepts of…

Series: Video Game Design

Video Game Design 5 | Physics Engine, Collision Detection and Solution, and Further Concepts of Physics Engine

  1. Physics Engine

(1) The Definition of Physics Engine

A physics engine provides a service of the physics simulation calculation for a virtual environment. Basically, there are generally two flavors,

  • High-precision offline engines: mainly for scientific researches
  • Real-time engines: mainly for video games or physical predictions for robots

There are many different games that are implemented with a physics engine. For example,

  • Bridge Builder
  • Trials

(2) List of Real-Time Physics Engine

  • Havok: one of the most famous commercial game engine
  • Newton
  • Open Dynamics Engine (ODE): open source
  • Nvidia PhysX: Unity with this integration

(3) Components in the Physics Engine

So here are some of the components that we can find in a physics engine. We have,

  • Bodies: usually rigid bodies like boxes, spheres, capsules, triangle meshes, etc.
  • Connector: ways for attaching bodies
  • Forces: notation how we are reacting on the bodies
  • Constraint: the constraint is similar to connectors
  • Collision detection: we can only provide collision detection without any dynamics

(4) The Definition of Body

In terms of the concept of bodies, we have mentioned that most of them are rigid bodies. Here are some common types of a body,

  • Dynamic Body: this we can move the body around (moveable)
  • Static Body: this means we can not move this body (unmoveable) (maybe) because of the infinite mass
  • Enabling/Disabling Body: in general, it is important to enable objects that are useful
  • Sleep/Awake Body: a body may move a bit at the beginning and quickly settle down (i.e. sleep). But you can also do something else (e.g. kick the ball) to move the body around (i.e. awake).
  • Body with Layers/Groups: this is like a separate physics universes that are sort of superimposed one on top of another.

Bodies also have some other properties that as you would expect like,

  • Position
  • Orientation
  • Velocity
  • Angular Velocity
  • Other Properties: mass, dynamic/static friction, restitution (bounciness), softness, anisotropic friction (skateboard), mesh shapes with per triangle materials (terrain)

(5) The Definition of Collision

Collision basically means one shape is intersecting with another one.

(6) The Definition Collision Hulls

Collision hulls are used to reduce the complexity of collision calculation. They are in general made from the primitives (e.g. boxes for vehicles, capsules for skeletons) mentioned before.

(7) Ways to Create Collision Hulls

Hulls are often required to be convex if non-static for performance because it reduces the calculation, and here are some ways about how to create them,

  • Minimum Hulls: Usually, we have a minimum hull to concave the source. For example, we can use an ordinary box for containing an object, but if we want something tighter, we can rotate the box to find the smallest convex one with the object inside.
  • Compound Colliders: Of course, you can also make hulls by hand. In Unity, we commonly use compound colliders with fixed joints and connections to produce the concave effect.
  • Hierarchical Collision Hull: Access aligned bounding box around different parts of a complicated shape so we have a large simple bounding collision hull to test for the intersection, and then work down to more specific geometry.

(8) The Definition of Skin Width

The skin width is a dilation or expansion of the geometry so whatever geometry you have for your collider, imaging filling it with air and expand it to a larger form by some amount as if there is a skin on top of the true geometry. In physics, this is called a contact offset or a rest offset.

2. Collision Detection and Solution

(1) Discrete Collision Detection

Discrete collision updates the collider position once per fixed frame and detects the collision between the overlapping colliders. Imagine a case when we have a ball with a constant velocity, and in each fixed frame time, we can perform a collision detection of it to the wall. For example, as it is shown in the figure below, the detection will show no collision from t0 to t4, but it will detect a collision at t5.

(2) Discrete Collision Detection Problem: Tunneling

So what if we have a skinny wall. Let’s assume this ball has the same property, the same velocity, the same scale, and etc, and we also perform the same collision detection in each frame. However, what we have now is that the ball can pass through the wall between t4 and t5, because the wall is too thin to be detected or in the other perspective, the ball is too fast for the wall.

There are several ways to deal with this problem.

  • Slow the ball: the easiest solution is that we can simply slow down the ball so that at some frame, we can detect this collision
  • Ban skinny walls: also, we can use big thick walls instead of skinny walls so that won’t be a problem for us

(3) Tunneling Solution 1: Single Raycast

When the ball is moving, we can just perform a simple raycast from the previous position to the current.

However, this solution is not perfect. When we hit the wall on the edge or we have a crack or seam in the wall, this single raycast may not be enough to detect the collision because it is actually missing. This will probably result in gameplay breaking.

(4) Tunneling Solution 2: Multiple Raycasts

To fix this problem, another way is to add more raycasts and at the same time, of course, the cost of these raycasts is much more expensive.

Except for the cost, another problem is that we may not be able to detect collision on very tiny things (e.g. bullets). We are actually reaching the point that we could consolidate all of our multiple raycasts into something else.

(4) Tunneling Solution 3: Silhouette Raycasts

Even if we rotate the raycasts to create silhouettes, we can still miss some tiny objects. As a result, we will finally have some problem of missing something tiny at a really high cost.

(5) Tunneling Solution 4: Speculative

One solution in PhysX is called speculative or speculative collision detection. What it does is that PhysX normally has this skin width, which is usually a very some and constant offset but if you enable speculative collision to section what happens is that there is a dynamic skin width.

When the ball is fast, the skin can expand to its compensation. When the ball slows down, the skin can shrink back to its default. However, it does have some problems because the skin might not actually grow fast enough to what it is about to collide with, and we can still end up with tunneling.

(6) Collision with Rotation

Now, imagine we have a rotating axe and we would like to see if it can collide with the wall. You may find out that this fast rotation makes all the previous techniques tricky, even though we can still do the discrete collision detection. In general, there can be two compromises for this,

  • Restrict the maximum velocity: In Unity and PhysX, what we commonly do is restrict the maximum value of the angular velocity by Rigidbody.maxAngularVelocity so that the rotation problem will not be that complicated.
  • Use a blur hull: As far as we concern, the axe can exactly pass through the wall without any collision. However, this can be complicated for calculation and it is actually not that important for gameplay. So in fact, you may not need anything seems like an axe, and probably, a disc can be probably fine.
  • Take a smaller step: often, the best solution is to take a smaller step in terms of our simulation by increasing our frame rate. Knowing the size of the objects, a speed threshold can be identified where tunneling might occur. When that speed is exceeded, start sub-stepping but otherwise use discrete collision detection.

(7) Collision Dynamics

So how can we resolve our collisions? Ultimately, we want something that is realistic, so we have certain expectations we are looking for if two objects collide. This means that we want to see something (e.g. bounce back, push away, drop, etc.) with one of them.

So we actually need some methods to do this.

(8) Collision Dynamics Methods 1: Penalty Force Method

There are some mechanisms to deal with this and one of the earliest ones is called the penalty force method. This is actually the one used in the game Trespasser.

The basic concept of the penalty force method is that we sort of recognizing that an object, when it applies with something else, is touching the object, and we need a correct for this touch to make sure that they have already gotten to the point that they are crossing the boundary from one to another. The result of the application of a force vector is to be added to the point of deepest penetration on successive simulation steps, so that we can, as a result, push the shape away.

(9) Improvements on Penalty Force

So now let’s consider some improvements on the penalty force method. What we are going to do are,

  • Relax the contact criteria via skin width: the skin is like an expansion of the shape
  • Consider all collision contacts (not just the deepest): we will see this in a few minutes
  • Find a solution that addresses all constraints introduced by the collision contacts

(10) All Contact Points

If we have two surfaces that are touching in their flesh. There’s not points of contact, instead, there’s a whole area of contacts. So when we say all the contacts, we are actually going to simplify that based on perimeter vertices. Usually, spheres, cylinders, and capsule ends are unique cases as compared to triangles. Since this is along the parameter of the contact area, our corrective forces are applying. So the collision dynamics is still going to work effectively.

(11) Skin Width for Contacts

Another way is that we can define the contacts based on the skin penetration instead of the actual geometry touches. The cool thing about using this approach is that we can begin correcting, which means we can spread our corrective forces over multiple frames.

We can also make it proportional to the degree of penetration like it can be scaled according to how much penetration there is. If two object skins are barely touching, we can have a very small corrective force. So soft collision correction as skin penetrations can become stronger and stronger as further penetration. This is greater for friction modeling and reducing jitter by using a smoother sort of approach. Friction modeling benefits from fact that skin penetration can persist across simulation steps and, therefore, contact point persist.

(12) Case Study: Edgry and Rolonda

Now, let’s see a case of two shapes. The shape on the left called Edgry is flying through the air towards Rolonda. At the beginning, we have tested nothing because there’s no penetration.

But as the simulation advances, our tests for intersection are going to be get an intersection of the skin only. At that point, we are going to generate the metadata or the book keeping to keep track of the contract point. And we may choose a small proportional corrective force proportional to the degree of the interpenetration of the skin. At this time, the skin interpenetration is quite small and therefore, there has to be a small correction.

But if it does continue, now we are going to ramp up the corrective force and this will be, again, based on the skin interpenetration. So now, we are going to get a larger corrective force, and ideally we may be able to push that part into a stable contact.

If this collision continues, we are going to get to the point where’s an actual contact of the actual geometry. This will result in a lot of forces. So when this happens, you will have to ramp all the way up to the maximum of the skin base correction for forces. This will push them apart if there’s any restitution allowed by the simulation.

But sometimes, things don’t work out the way you want. This will usually happen when you have lots of objects involved and they are all pushing each other. And somehow, you end up with the inner geometry in addtion to the skin. At that point, the actual geometry are intersecting and you have a last ditch extreme corrective force to apply, which can be set in PhysX or Unity.

Because you don’t want to real geometry collisions, you are expected to get a result that the Edgry will go flying through the air and go off like extreme heights.

(13) A Common Bug: Sea of Thieves

In this case, we will see a common bug for geometry collision. We are going to use an example in the game Sea of Thieves. This bug happens when a boat sinks, and then for whatever reason, it flies.

So what actually happens here is when the ship first scuttled, it goes physics control under kinematic control because there is an animation just plays that it is moving down below the water or sea level. So it goes down for a while and then they turn off the kinematic control and go under the simulation control. Under water, there are some rigid bodies like the sand and seaweed, so there maybe a terrain collider or some static mesh collider. So now the physics simulation decide that there is a huge amount of interpenetration occurring right now and we have to apply a maximum corrective force.

(14) Linear-Complementary Problem (LCP)

So when we have a contact, the most commonly solution we are going to apply is based on the linear-complementary problem (LCP) with Jacobian constraints. The goal of this solution is to help you find the degrees of freedom relative to the contacts and to answer how can the object move under this contact.

Jacobian is actually a mathematical concept like a pre-derived path of least resistance to enforce a constraint (e.g. a direction vector in constraint space). It actually allows you to determine what those degrees of freedoms are and then it would be like adjustments to position in an orientation.

3. Further Concepts of Physics Engine

(1) The Defintion of Forces

Forces are the ways to make the objects around. The most common force in the physics engine is the gravity, but this is not always the case because you may want some layers of the simulation that are not affected by the gravity.

(2) The Defintion of Impulse

The impulse is a kind of instantaneous force and it results in a change of the velocity. It stops after there’s no over a single frame. This will be great for jumping. In Unity, there are different variations of impulse

(3) The Defintion of Connectors

Connectors is what we use to attach our shapes and it means to restrict motions between actors relative to the degree of freedom. These are implemented with multibody dynamics with Jacobian constraints. There are some other aspects connectors dealing with,

  • connect collision
  • flexibility
  • degree of freedom
  • etc.

There are also several types of connectors,

  • spring
  • force
  • damping
  • joint motor
  • breakable joints

There are also different types of constraints to the connectors,

  • hard constraint: the rules should never be violated
  • soft constraint: the rules are designed to be violated
  • joint constraint: there are some degrees of freedom with linear or angular amounts

(4) The Definition of Deactivation

Because it is important to minimize calculations in a real-time simulation, we have to limit the actors that are active in simulation at a time. So sometimes, we have to sleep the linear and angular velocity of the rigid bodies.

(5) Common Steps of Applying a Physics Engine

  • set gravity vector
  • make some kind of ground surface that doesn’t fall
  • apply forces to bodies
  • adjust joint parameters as necessary
  • call collision detection
  • step the simulation based on time
  • keep the graphics objects and physics object in synchronizations
  • deactivate some objects