Showing posts from September, 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.OverviewA physics engine does two things: Collision detection and physics reaction. They work seamless together to create the illusion of things colliding and bouncing back.Collision DetectionThe 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 phaseThe 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 containi…

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 doAlmost 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 …

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 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 degreesEvery line segment between two vertices can be contained fully inside or at the edge the polygonA 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: performancePhysics 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 o…

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 unboxingBoxing 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: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: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 fin…

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.