Friday, September 25, 2009

2D Physics Engine Tutorial – Part 2

In part 1 I explained what a physics engine does and what kind of physics engines there exists. This post will focus on the collision detection internals of physics engines.

Overview

A physics engine does two things: Collision detection and physics reaction. They work seamless together to create the illusion of things colliding and bouncing back.

Drawing1

Collision Detection

The collision detection part of the engine is responsible for detecting when things overlap and by how much they overlap. Most physics engines have developed a two-tier architecture where you first detect if objects are near each other using a crude representation of the object. Then it performs the collision detection on the objects itself using its real representation. It basically is setup like this:

Broad phase

The broad phase is the one responsible for detecting objects near each other. It was developed to speed up the collision detection phase by reducing the amount of collision checks needed. Imagine a simulation containing 11 balls; the engine would need to do 121 (11^2) expensive (real shape) collision checks. If a broad phase is introduced, this number of checks can be reduced to a smaller amount. Broad phase algorithms usually use AABBs to represent a crude shape of the object. It is a lot cheaper to test AABB vs. AABB than a polygon vs. polygon.

The example from before with 11 balls would in the following images only have to do 121 cheap tests and 25 (5^2) expensive checks.

With and without AABBs:

 WithoutAABB WithAABB

There exists a lot of algorithms to do broad phase tests:

All of them have in common that they divide the screen up into smaller parts using trees (flat or hierarchical), grid or axis-division. Have in mind that no broad phase algorithm is the “best” – it depends on the situation in which they are used.

Narrow phase

When the broad phase has detected that two objects are near each other (their crude representations intersect) the engine should create a pair (sometimes called an arbiter) that contains the two objects. The objects are then tested using the narrow phase algorithm. Unlike the broad phase, the narrow phase tests the real shapes (polygons) against each other. This is an expensive test in most cases since a polygon can be anything from 3 to n points. The narrow phase algorithm needs to find the following information:

  • Does a collision exist
  • Position
  • Normal
  • Distance

The last 3 items are vital for the collision response phase. The information is used to generate a contact; it contains the previous gathered information and can be persisted over several time steps.

ContactPoint

Green: Normal of contact point
Red: Centroid
Black: Shortest distance to collision point

Just like the broad phase collision detection system, there are a lot of narrow phase algorithms:

Improved overview

Now that the collision detection system has been identified, the new overview looks like this:

image

2D Physics Engine Tutorial – Part 1

In this article series the focus will be on identifying the different parts of a physics engine and then how we can implement those parts as simple as possible. There are tons of 2D and 3D engines available on the internet – this is not going to be a contestant to any of those engines, it will purely function as an educational physics engine to better grasp the concepts behind it.

What does a physics engine do

Almost all games need some way of detecting if two objects collide and respond using the proper reaction. It might be Mario standing on top of a platform or Max Payne shooting a bad guy – they both need collision detection and physics.

Wikipedia definition
A physics engine is a computer program that simulates physics models, using variables such as mass, velocity, friction, and wind resistance. It can simulate and predict effects under different conditions that would approximate what happens in real life or in a fantasy world. Its main uses are in scientific simulation and in video games.

Physics engines can be used for so much more than just fun and games:

To us it is naturally that if we toss a ball against a wall, it will hit the wall and bounce back. In the computer world all this has to be simulated.

Types of physics engines

There are two different kinds of physics engines. One of them is used for soft body (deformable) objects and the other is used for rigid body objects (hard/non-deformable)

Soft body physics

Soft body engines are used for deformable physics such as cloth, rubber, jelly or balloons. You can enlarge, rip or puncture a soft body in any way you want. There are both 3D soft body engines and 2D soft body engines. Most of them define their shapes using triangles (or particles) that can change properties (side lengths and angles) and thus deform the body that contains the triangle.

Soft body dynamics are hard to work with because of the deformations applied to a body. If a body needs to try and keep its original shape, all the deformations will have to be kept track off and slowly be resolved to gain its original shape.

Rigid body physics

Rigid body engines are used for non-deformable physics such as spacecrafts, buildings, terrain, player characters and more. They can’t be deformed in any way and only support linear (movement) and angular (rotation)  motion.

Rigid body engines are a lot easier to work with compared to soft body physics. You only have to keep track of movement on the x, y and z-axis and rotation around the centroid of the object.

Play Doh (Soft) and a metal box (Rigid):

Soft versus rigid body

Real-time vs. High-precision

How all this is calculated depends on the type of engine used. There are generally two different types of engines:

Real-Time

Real-time engines are typically used in games and other real time applications. They are used to simulate the game environment, vehicle dynamics, player interactions and more. Real-time engines are usually more focused on performance than accuracy – when a tree falls on a vehicle, we don’t need to know where every single fiber of the tree hits the vehicle with a accuracy of 0.01 mm.

They are identified by the following characterizes:

  • Iterative algorithms
  • Low accuracy
  • High number of concurrent objects
  • Game oriented tools
High-Precision

This kind of engine is mostly used in scientific applications and animated movies. They are used to simulate weather, train collisions, explosions and space shuttle trajectory. They can’t be used for real-time applications because they are too expensive in their computations.

They are identified by the following characterizes:

  • Single pass algorithms
  • High accuracy and precision
  • Low number of concurrent objects
  • Scientific application tools

Sunday, September 20, 2009

Hybrid narrow phase using convexity detection

While writing Convex polygon based collision detection I came up with the idea of using a hybrid narrow phase to maximize usability and performance. It might have been thought of before and if you stumble upon this, I would like to hear your thoughts about it.

It basically consist of taking the pairs found in the broad phase and checking the convexity of the polygons before sending them down to the narrow phase. As I described in the earlier post, SAT only works on convex polygons because it uses the separating axis between two non-colliding convex polygons. This limits the users of the engine to use convex polygons only and thus resort to methods of convex decomposition to get concave polygon support.

If the polygons were checked for their convexity before being send to the narrow phase, the engine could send the pair of potentially colliding polygons to a narrow phase of its choice - depending on the composition of the pair:

  • Convex vs. concave – Send to concave narrow phase
  • Convex vs. convex – Send to convex narrow phase
  • Concave vs. concave – Send to concave narrow phase

The convexity check could even be done at tool-time or engine startup. Whenever the vertices of an object changes it needs to redo the convexity check.

Problems that it would solve:

Small angles

Some triangulation algorithms try to maximize the minimum angle of the triangles (like Delaunay Triangulation). But most will come up with a result that contains narrow triangle and thus it can cause tunneling problems.

Convex seems

Composing a concave polygon from several convex polygons will create a lot of seems (part where the polygons meet) and that can cause trouble for most 2D physics engines. Unrealistic collisions and hiccups can occur in the middle of a collision.

Holes

Because of the precision and accuracy of algorithms (due to iterative nature and float errors) – cases of no-intersection can happen when an intersection is expected. Imagine two narrow triangles where the narrow part are up against each other. A small gap can exist between the triangles and a ray cast in between the two triangles would go right though it. This can of course be solved by extending the edges a little.

Problems that it would create:

Memory issue

The main issue would be memory consumption. Instead of a single narrow phase algorithm you would now have a dual algorithm. Using a narrow phase collider like the Signed Distance Field can consume a lot of memory.

Expensive to change polygons

Again, if you use a narrow phase collider like the SDF you need to recalculate both the convexity check and the cached grid containing the narrow phase data for the physics object. Most games don’t change polygons on the fly, so this should not be a major issue.

Convex polygon based collision detection

A lot of people have asked me: Why use a convex polygon only engine like Box2D? In this post I will provide some info on why convex polygons is the optimal polygon type to use.

What does convex mean?

Convex polygons needs to satisfy the following requirements:

  • All internal angles must be below 180 degrees
  • Every line segment between two vertices can be contained fully inside or at the edge the polygon

Convex-Concave

A non-convex polygon is called a concave polygon and it must have an internal angle measuring greater than 180 degrees. As you might have thought about yourself; concave polygons can be quite handy. Convex-only engines can’t represent a simple player polygon like Pac-Man.

Why use convex-only?

There are really only one big juicy reason: performance

Physics engines are able to take quite a few shortcuts and use cheap algorithms to determine the closest vertex, shortest distance and a lot more. An algorithm like Separating Axis Theorem and the Gilbert – Johnson – Keerthi (GJK) (pdf) algorithm both operate on convex polygons and provide fast, yet robust methods of getting collision information. Fundamentally there are two great features of convex polygons:

  • The existence of a separating plane between two non-colliding convex polygons
  • When two points on two different geometries are at a minimum, they are at a global minimum.

That might sound like gibberish for the layman. I’m not going to explain what those two characteristics involve, but suffice to say that you can cut down on the complexity of the algorithms used.

Problems with using convex-only engines

In a performance point of view there are really no problems with using convex-only algorithms. The problems that arise are mainly usability (ease of use and convenience for the users). If the user supply the engine with a concave polygon, all kinds of weird collisions will happen. A check is needed to make sure the supplied polygon is of convex nature. But that topic is reserved for another blog post.

The main approach for supporting concave polygons in a convex-only engines is described below.

Convex decomposition

This method involves the use of either triangulation algorithms or algorithms that finds a number of convex polygons from a convex polygon. The idea behind convex decomposition is to simply split a concave polygon into smaller convex polygons. This way a convex-only engine can support concave polygons. A lot of algorithms exist to do this. To name a few: Earclip, Delaunay triangulation and Seidel’s triangulation algorithm.

Here is an example of a triangulated concave polygon using a Constrained Delaunay Triangulation algorithm.

cdt-dude

Thursday, September 3, 2009

Performance tips and tricks – part 4

In part 3 I explained some common manual compiler optimization tricks. This time we go back to the code itself to find places where optimizations does a difference.

Boxing and unboxing

Boxing is the process of encapsulating a value type into a reference type. Unboxing is the reverse process. They both take some time and might happen several times in your application without your knowledge. Here is some example code on boxing/unboxing:

Box-unbox 

Since int is a primitive and thus a value type, it gets boxed and stored on the heap (where reference types live, compared to stack where value types live). This makes our lifes easy, but it also comes at a performance penalty.

You can easily identify boxing and unboxing operations by their IL code names:

ILCode

Boxing is called box and unboxing is called unbox in IL code. You can use Reflector to have a look at the IL code generated by your application.

Boxing is very expensive performance wise. Try to avoid encapsulating value types into reference types. Try to find other ways of doing the same, you can use generics as an example.

Exception handling

Exceptions are great for reporting problems. Many logging systems catch exceptions thrown and log them to a file. The problem is that exceptions are expensive to use and catch. In high performance applications they should not be used in performance critical parts of the code. All data should be sanitized, checked and exceptions should be thrown before the data enters the performance critical part of the code.

A few things you should think about when using exceptions:

  • Do not throw exceptions inside loops
  • Do not throw exceptions inside performance critical code
  • Do throw exceptions in helpers, managers and data layers and other run-once and use-multiple times code.

The last item can be a bit of a gray area since you can use helpers, managers and data layers inside performance critical code. I trust you to figure that part out yourself.

String operations

Strings can be your best friend or worst nightmare. They are easy to use and easy to manipulate. What could be wrong with using strings?

They are immutable. Memory allocations and thus garbage collections can become a problem. C# does a really great job of optimizing strings in such a way that minimum memory allocations take place. But even then there are still quite an overhead of using strings. Because they are immutable, all string operations create a new string instead of manipulating the old one. The new string take up some space (2 bytes for each character) and the whole memory copying operation also take some time. Lets take a look at some string concatenations:

Normal string

StringForLoop

Using this code you will get the string “0123456789”. Problem with this code is that you allocate 11 strings. Yes, that is right, 11 strings:

  • initial allocation = 1
  • appending = 10
  • final result = 1

The allocation, the representation and writing the string to the console in C# takes up nearly 4 kb. The string operation itself takes up a couple of 100 bytes.

StringBuilder object

A better solution compared to normal strings is to this is to use the StringBuilder object. it contains a mutable (changeable) array.

StringBuilder

The StringBuilder object allocates a lot less, but it still has an overhead. It is an object, it contains a resizable array, it has some a lot of functionality. Allocating a StringBuilder object often can actually be slower than normal strings.

Char arrays

Char arrays can be even faster. They are mutable and they contain no overhead.

CharArray

It can be up to 10 times faster than a StringBuilder object (depending on how it is used) but it also has some disadvantages:

  • You have to know the maximum size of the string (char array is fixed size)
  • Can only be used in simple manipulation scenarios.

Tuesday, September 1, 2009

New Farseer Physics Engine based game – FreeGoo

For those of you who don’t know about World Of Goo, the best advice you get today is to buy it and try it out. It is one of my favorite games, complete with a great story, nice graphics and dynamic gameplay. FreeGoo is a Farseer Physics Engine based clone of World Of Goo. Try it out.