Physics Engine Introduction

Although I don't know if it will be a separate engine in Llamathrust I will explain in this article the basics of physics engines or I should say realtime physics simulation.

This is a diagram of how a physics engine work:

Integrate Velocities

In this part the linear and angular velocities of the objects are translated into position and rotation by integration. There are several numerical integration techniques used for solving the equation of motion. The integrator has to be simplectic so, basically, it handle springs better but if you want to read more about it here is a link to an answer that explain it really well. I found that semi-implicit Euler mehtod is fast enough and simplectic.

Collision Detection

A very intuitive thing to do at first is to compare every pair of objects in the scene to see if they collide, this is okey if there are less than 100 objects wich is a small and very rare amount in a last gen game.

Even though there are less than 100 objects is still a lot if we perform an overlapping test in complex meshes, which all meshes are this days, so a simple solution is to link a simple mesh to the complex mesh and if the two simple meshes overlap then we test the complex meshes dividing the process into 2 phases. All simple meshes should be the same shape.

First Phase also know as Broadphase:

The most common shapes used for the first phase are: Ordered from fastest to slowest

sphere, axis aligned bounding box (AABB), oriented bounding box.

Sphere

Axis Aligned Bounding Box

Oriented Bounding Box

The sphere is really simple to test an overlap:

|center1 - center2| < radius1 + radius2

The aabb is also simple but need a few lines.

for every axis:

min1 < min2 && min2 < max1 || max2 > min1 && min1 > min2

The obb need a algorithm called Separating Axis Theorem or SAT which I wont cover in this post.

They have their advantages and disadvantages:

• Sphere: Super fast but very inaccurate since most of its voulme may be empty.

• AABB: Fast and fit most of the shapes.

• OBB: Slowest of the three but the best fitting for any shape.

I choosed AABB for Llamathrust implementation.

We still have another problem. What do we do if there are more than a 100 objects? We resort to data structures!

We have two common data-structures for this:

1. Sort and Prune

2. AABB-tree

The first wasn't convenient for my game since will have too much dynamics objects so I choosed AABB-Tree.

The AABB-Tree is a binary tree sorted by volume or areas of the AABB. This will have it's own post later on.

Second Phase also known as Narrowphase:

Since the simple meshes are really inaccurate we need to test with a more accurate shape or the mesh it self that give us 2 options or a 3rd in between:

• Approximated shapes (OBB, cone, cylinder, sphere, plane, etc)

• Complex mesh (the rendererd mesh)

I choose somewhere in between, approximated shapes for every object but the terrain that will have the complex shape.

There are general algorithms for convex shapes, since working with concave shapes is really slow there is no much information about concave algorithm instead they propose solutions to work them as convex shapes like compound shapes, and the most common algorithm are:

• SAT

• Gilbert–Johnson–Keerthi (GJK)

And once again we dont choose SAT but GJK because is more eficient for arbitrary polyhedra though, eventually, I will use specialized algorithm for pairs not involving complex mesh so SAT will be used at one point.

Constraint Solver

This "physics engine" is constraint based that mean that objects interact between them by constraint. In this kind of physics engines the collision response is also a constraint.

By this time I am learning about this topic, if someone is at this stage this link seems awesome.

That's all for this post, folks. Bye!