FarseerPhysics Wiki & Documentation Rss Feed

New Comment on "Screenshots"

theaegd — Tue, 10 Nov 2009 13:11:35 GMT

Tried your engine yestarday, greatest physics engine I have ever come upon for free, thanx!

New Comment on "Screenshots"

Theaegd — Thu, 05 Nov 2009 13:02:04 GMT

Intresting, I will test out your engine tonight, But for these pics, are these made by the engine, or games using the engine?

Updated Wiki: Documentation

genbox — Mon, 26 Oct 2009 17:51:09 GMT

Farseer Physics Engine Manual

Warning

This manual is not up to date. Use http://www.physicspoweredgames.com/FarseerPhysics/Manual2.1.htm instead.

Introduction

The Farseer Physics Engine is an easy to use 2D physics engine designed for Microsoft’s XNA and Silverlight platforms. The Farseer Physics Engine focuses on simplicity, useful features, and enabling the creation of fun, dynamic games.

Overview

Getting right to the nut, the Farseer Physics Engine is designed to control the position and rotation of game entities over time.

In the real world, things move and spin due to applied forces and torques. In Farseer, the same is true. Objects called bodies represent the real world things. As forces and torques are applied, the bodies react according to the laws of 2D physics. The position and rotation of these bodies are then used to update game entities.

In the very simplest outline it works like this:

Create Body object
Add Body object to simulator.
Begin Game Loop
- Apply forces and torques to Body.
- Update the simulator
- Set sprite position and rotation equal to Body position and rotation.
- Draw game sprite
End Game Loop

Bodies, by design, have no geometry in the 2D world and therefore have no concept of collisions.

For collision, Farseer has the Geometry object. Geometry objects are represented as 2D polygons and can be either concave or convex. They are defined by a set of vertices. One or more geometries are attached to a body in order to give the body geometrical awareness. This allows the body to participate in collisions with other bodies(actually other geometries attached to other bodies, but you get the picture.)

<todo: talk about joints, spring, and controllers>

Quick Start Sample

The following is all the code for creating 2 simple bodies with geometry and attaching them with a single revolute joint. This simple sample shows the basics of using Farseer. The rest is really just details. The actual sample can be found in the XNA samples download.

Dynamics

PhysicsSimulator

Overview

The physics simulator manages all physics objects while the simulation is running. It controls the update loop for the simulation.

Public Properties

-GeometryList

The list of geometries that are part of the simulation.
NOTE: This list should be treated as read-only. Items should not be added or removed directly from this list. Use PhysicsSimulator.Add(...) for that.

-BodyList

The list of bodies that are part of the simulation.
NOTE: This list should be treated as read-only. Items should not be added or removed directly from this list. Use PhysicsSimulator.Add(...) for that.

-JointList

The list of joints that are part of the simulation.
NOTE: This list should be treated as read-only. Items should not be added or removed directly from this list. Use PhysicsSimulator.Add(...) for that.

-ControllerList

The list of controllers that are part of the simulation.
NOTE: This list should be treated as read-only. Items should not be added or removed directly from this list. Use PhysicsSimulator.Add(...) for that.

-Vector2 Gravity

The gravity currently applied to objects in the simulation

-int Iterations

The number of internal iterations that will be used to reconscile collision and joint errors. The more iterations used the more stable the collision resolution and joints, however, there is a performance penalty that comes with larger number of iterations.

The default value is 5. If you need more stability for stacking or other situations try 10.

For more info on this property see Erin Catto's paper

-float AllowedPenetration

When two bodies collide some degree of penatration is allowed. This helps decrease oscillations and increases stability, especially of stacked bodies. This value sets the penetration that is allowed.

The default value is .01 and shouldn't need to be changed in normal operation of the engine.

For more info on this property see Erin Catto's paper

-float BiasFactor

This is a more advanced property. It controls how quick the collision error or joint error between bodies is corrected. Lower values make things a bit softer but more stable while higher values make things more rigid but prone to jitter.

This propety should always be between 0 and 1.

The default value is .8. If you need to decrease jitter, try something less than .8. .2 tends to work well.

For more info on this property see Erin Catto's paper

-int MaxContactsToDetect

When two geometries collide, the vertices of their geometries overlap eachother. Some vertices of geometry1 are inside geometry2 and vice-versa. Calculating all the vertecies that overlap takes cpu time. This property sets a maximum on the number of overlapping vertices to find. Essentially it provides a way to short-circuit the collision detection between two bodies in order it increase performance.

The default value is 5. It should not need to be changed for most situations.

-int MaxContactsToResolve

Once all collision points between two bodies are found they need to be resolved with impulses. Farseer sorts the list of collisions detected (limited by MaxContactsToDetect) by penetration depth so that it can resolve the deepest collisions first.
This property sets a maximum on the number of collision to resolve.
The default value is 2 and should be enough for most situations. Some stacking situations may require a higher value

Public Methods

-Add(Geometry)

Adds a Geometry to the simulation

-Add(Body)

Adds a Body to the simulation

-Add(Controller)

Adds a Controller to the simulation

-Add(Joint)

Adds a Joint to the simulation

-Clear()

Clears all physics objects from the simulation. More specifically, it clears Bodies, Geometries, Joints, Controllers, and the internal Arbiters.

-Geometry Collide(Vector2 point)

Checks to see if a given point collides with any geometries in the simulation. If it does, the geometry is returned. If it doesen't, null is returned.
This method is very helpful for mouse picking. Just send the mouse click position to this method and if the click collides with a geometry, the geometry will be returned and the geometry has a reference to the underlying Body.

Here is a small example: (point represents the mouse cursor position

Geometry pickedGeometry = physicsSimulator.Collide(point);
if (pickedGeometry != null) {
     LinearSpring mousePickSpring = ControllerFactory.Instance.CreateFixedLinearSpring(physicsSimulator, 
                                                      pickedGeometry.Body, pickedGeometry.Body.GetLocalPosition(point), 
                                                      point, 20, 10);
}

-Geometry Collide(X,Y)

Overload for above method

-PhysicsSimulator()

Constructor that defaults to zero gravity

-PhysicsSimulator(Vector2 gravity)

Constructor with gravity

-Remove(Geometry)

Removes a Geometry from the simulation

-Remove(Body)

Removes a Body from the simulation

-Remove(Controller)

Removes a Controller from the simulation

-Remove(Joint)

Removes a Joint from the simulation

-Update(float dt)

dt is the time in seconds.

This method steps the simulation forward in time. It should be called continuously in an update loop while the game is running.

This method assumes a fixed time step (dt). This means the value of dt should be the same each update call and it should be called with a frequency equal to dt.

For example, if you want to update the simulation at 100 frames per second, you would call update every 10 milleseconds and pass .01 (10ms converted to seconds) as your value for dt.

Example (assumes XNA):
In the Game class:

this.TargetElapsedTime = new TimeSpan(0, 0, 0, 0, 10);  //represents 10ms
this.IsFixedTimeStep = true;

In the Update

protected override void Update(GameTime gameTime) {
physicsSimulator.Update(gameTime.ElapsedGameTime.Milliseconds * .001f); //convert from ms to seconds
}

Body

Overview

Bodies are the core physics objects in Farseer. Forces, torques, and impulses are applied to bodies and the bodies react by moving realistically. Bodies do not contain any form of collision geometry by themselves.

Public Properties

-AngularVelocity

The rate at which a body is rotating

-Enabled

Sets whether or not the body will take part in the simulation. If not enabled, the body will remain in the internal list of bodies but it will not be updated.

-Force

The total amount of force that will be applied to the body in the upcoming loop. The Force is cleared at the end of every update call, so this value should only be called just prior to calling update.

This property is read-only.

-Torque

The total amount of torque that will be applied to the body in the upcoming loop. The Torque is cleared at the end of every update call, so this value should only be called just prior to calling update.

Torque can be thought of as the rotational analog of a force.

This property is read-only.

-TotalRotation

Returns the total rotation of a body. If a body spins around 10 times then TotalRotation wold return 2 * Pi * 10. This property is mostly intended for internal use by the angle joints and springs but it could be useful in some situataions for game related things.

This property is read-only

-XVectorInWorldCoordinates

Returns a unit vector that represents the local X direction of a body converted to world coordinates.

This property is read-only

-YVectorInWorldCoordinates

Returns a unit vector that represents the local Y direction of a body converted to world coordinates.

This property is read-only

Public Methods

BodyFactory

Overview

Public Methods

Arbiter

Overview

Public Methods

Joints

AngleJoint

Overview

Public Methods

FixedAngleJoint

Overview

Public Methods

AngleLimitJoint

Overview

Public Methods

FixedAngleLimitJoint

Overview

Public Methods

RevoluteJoint

Overview

Public Methods

FixedRevoluteJoint

Overview

Public Methods

PinJoint

Overview

Public Methods

SliderJoint

Overview

Public Methods

Joint

Overview

Public Methods

JointFactory

Overview

Public Methods

Controllers

AngleSpring

Overview

Public Methods

FixedAngleSpring

Overview

Public Methods

LinearSpring

Overview

Public Methods

FixedLinearSpring

Overview

Public Methods

Controller

Overview

Public Methods

ControllerFactory

Overview

Public Methods

Collision

Geometry

Overview

Public Methods

GeometryFactory

Overview

Public Methods

Vertices

Overview

Public Methods

AABB

Overview

Public Methods

Grid

Overview

Public Methods

Contact

Overview

Public Methods

Feature

Overview

Public Methods

Example Code Snippets

Here is an old document on how Farseer Collision Detection works: FarseerPhysicsDocumentation.pdf

Updated Wiki: Tutorials

genbox — Tue, 13 Oct 2009 21:07:20 GMT

Here is a list of tutorials and FAQ created by the community:

Tutorials

FAQ

Updated Wiki: EngineUsage

genbox — Sat, 26 Sep 2009 15:49:43 GMT

Games or libraries that uses Farseer Physics

Here is a list of games and libraries that uses or somehow relates to Farseer Physics.

XNA Games

Silverlight Games

Libaries

DEngine - C# XNA 2D Game Engine

Tools

Others

New Comment on "Donations"

fixitchris — Tue, 25 Aug 2009 03:57:48 GMT

Did you get the Xbox yet?

Updated Wiki: Donations

genbox — Sun, 16 Aug 2009 22:33:23 GMT

Donations

This is a list of people who have donated to our project. We would like to thank each and every one of you who donated. It is very much appreciated.

Daniel Gimenez - $50.00 USD
Aranda Morrison - $50.00 USD
Dan Wellman - $15.00 USD
David Fleming - $30.00 USD
Chris Misztur - $5.00 USD + 60GB Xbox360 harddrive
Alex Hogan - $50.00 USD
Jonas Andersson - $20.00 USD
Daniel Armstrong - $100.00 USD
Kevin Small - $20.00 USD
Nicolás Hormazábal - $20.00 USD

Updated Wiki: Donations

genbox — Sat, 15 Aug 2009 14:00:58 GMT

Donations

This is a list of people who have donated to our project. We would like to thank each and every one of you who donated. It is very much appreciated.

Daniel Gimenez - $50.00 USD
Aranda Morrison - $50.00 USD
Dan Wellman - $15.00 USD
David Fleming - $30.00 USD
Chris Misztur - $5.00 USD + 60GB Xbox360 harddrive
Alex Hogan - $50.00 USD
Jonas Andersson - $20.00 USD
Daniel Armstrong - $100.00 USD
Kevin Small - $20.00 USD

Updated Wiki: EngineUsage

genbox — Fri, 14 Aug 2009 18:14:05 GMT

Games or libraries that uses Farseer Physics

Here is a list of games and libraries that uses or somehow relates to Farseer Physics.

XNA Games

Silverlight Games

Libaries

DEngine - C# XNA 2D Game Engine

Tools

Others

Updated Wiki: EngineUsage

genbox — Fri, 14 Aug 2009 18:13:41 GMT

Games or libraries that uses Farseer Physics

Here is a list of games and libraries that uses or somehow relates to Farseer Physics.

XNA Games

Silverlight Games

Libaries

DEngine - C# XNA 2D Game Engine

Tools

Others

Updated Wiki: EngineUsage

genbox — Thu, 13 Aug 2009 00:25:03 GMT

Games or libraries that uses Farseer Physics

Here is a list of games and libraries that uses or somehow relates to Farseer Physics.

XNA Games

Silverlight Games

Libaries

DEngine - C# XNA 2D Game Engine

Tools

Others

Updated Wiki: EngineUsage

genbox — Wed, 12 Aug 2009 14:38:55 GMT

Games or libraries that uses Farseer Physics

Here is a list of games and libraries that uses or somehow relates to Farseer Physics.

XNA Games

Silverlight Games

Libaries

DEngine - C# XNA 2D Game Engine

Tools

Others

Updated Wiki: Tutorials

genbox — Tue, 04 Aug 2009 01:48:00 GMT

Here is a list of tutorials and FAQ created by the community:

Tutorials

FAQ

Updated Wiki: Home

genbox — Sun, 02 Aug 2009 18:23:54 GMT

Manual : API : Screenshots : Videos : The Team : Acknowledgments : Engine Usage : Tutorials & FAQ

Introduction

The Farseer Physics Engine is an easy to use 2D physics engine designed for Microsoft’s XNA and Silverlight platforms. The Farseer Physics Engine focuses on simplicity, useful features, and enabling the creation of fun, dynamic games.

Features

General
- Easy to use!
- Support for XNA (XBOX 360 and Windows)
- Support for Silverlight (1.1 and above)
- Support for managed .Net languages in general (3.0 targeted)
Collision
- Concave and convex polygons supported
- Multiple collision geometries per Body
- Collision categories for complex interaction between physics objects
- Collision callback mechanism
- Multiple narrowphase colliders: SAT and Distance Grid
- Multiple broadphase colliders: SelectiveSweep, SweepAndPrunde and BruteForce.
- Line-Line, Line-AABB, and Line-Geometry collision methods
Dynamics
- Joints
  - Revolute joint (Body to body or fixed to world)
  - Angle joint (Body to body or fixed to world)
  - Slider (Prismatic) joint
  - Pin (Distance) joint
  - Weld joint
- Force controllers
  - Linear spring
  - Angular spring
  - Fluid drag and buoyancy controller with wave generation.
  - Easy to build custom force controllers (Explosions, Steering Behaviors, etc.)
High Level Factories
- Helps you to easily create complex dynamics like chains and rope
- Create several shapes like ellipses, capsules, rectangles and polygons.
Support and Debugging
- Samples framework with samples covering most major engine features. (XNA and Silverlight versions)
- Debug viewer to view all major physics objects (part of samples framework)
- Online user manual with live demonstration of phyiscs engine dynamics

Donations

You choose the amount - Creditcard donations are accepted.
You can donate to the Farseer Physics Engine project by clicking here

See a list of our donations by clicking here.

Updated Wiki: DifferentPhases

genbox — Thu, 30 Jul 2009 04:43:43 GMT

Broad and narrow phase collision detection systems

First a little background before I start explaining the collision systems.

Big O notation
Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Example:

f(x) = x^2 + 2x + 6
will become
f(x) = O(x^2)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.
Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

To give a graphical view of the growth. X is the number of objects and Y is the number of collision checks that needs to be performed.

Now that we know what big O notation is, we can proceed.

Broad Phase collision detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

1. SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

2. Spatial Hash - More info - O(n log(n)) algorithm
If I remember correctly it can be O(1) in best case and O(n^2) in worst case.

We have 4 different broad phase algorithms in Farseer Physics Engine. The two mentioned, a brute force and a Selective Sweep collider.

It is important to remember that the broad phase only detects what objects are close and what objects are far and then create pairs of objects that can be tested against each other. To determine if two objects are close and should be further tested, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that contains the whole object. It is cheaper to test box vs. box instead of a lot of complex polygons.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase collision detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.
We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms, Farseer Physics support the following two (Have in mind that there are many other algorithms):

SAT (Separate Axis Theorem) - More info
Distance Grid - More info

Updated Wiki: DifferentPhases

genbox — Thu, 30 Jul 2009 04:33:18 GMT

Broad and narrow phase collision detection systems

First a little background before I start explaining the collision systems.

Big O notation
Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Example:

f(x) = x^2 + 2x + 6
will become
f(x) = O(x^2)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.
Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

To give a graphical view of the growth. X is the number of objects and Y is the number of collision checks that needs to be performed.

Now that we know what big O notation is, we can proceed.

Broad Phase collision detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

1. SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

2. Spatial Hash - More info - O(n log(n)) algorithm
if I remember correctly. Can be O(1) in best case and O(n^2) in worst case)
We have 4 different broad phase algorithms in Farseer Physics Engine. The two mentioned, a brute force and a Selective Sweep collider.

It is important to remember that the broad phase only detects what objects are close and what objects are far and then create pairs of objects that can be tested against each other. To determine if two objects are close and should be further tested, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that contains the whole object. It is cheaper to test box vs. box instead of a lot of complex polygons.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase collision detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.
We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms, Farseer Physics support the following two (Have in mind that there are many other algorithms):

SAT (Separate Axis Theorem) - More info
Distance Grid - More info

Updated Wiki: DifferentPhases

genbox — Thu, 30 Jul 2009 04:23:01 GMT

Broad and narrow phase collision detection systems

First a little background before I start explaining the collision systems.

Big O notation
Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Example:

f(x) = 5x^8 + 5x + 6
will become
f(x) = O(5x^8)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.
Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

Now that we know what big O notation is, we can proceed.

Broad Phase collision detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

1. SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

2. Spatial Hash - More info - O(n log(n)) algorithm
if I remember correctly. Can be O(1) in best case and O(n^2) in worst case)
We have 4 different broad phase algorithms in Farseer Physics Engine. The two mentioned, a brute force and a Selective Sweep collider.

It is important to remember that the broad phase only detects what objects are close and what objects are far and then create pairs of objects that can be tested against each other. To determine if two objects are close and should be further tested, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that contains the whole object. It is cheaper to test box vs. box instead of a lot of complex polygons.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase collision detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.
We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms, Farseer Physics support the following two (Have in mind that there are many other algorithms):

SAT (Separate Axis Theorem) - More info
Distance Grid - More info

Updated Wiki: DifferentPhases

genbox — Thu, 30 Jul 2009 04:20:12 GMT

Broad and narrow phase collision detection systems

First a little background before I start explaining the collision systems.

Big O notation
Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Example:

f(x) = 5x^8 5x 6
will become
f(x) = O(5x^8)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.
Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

Now that we know what big O notation is, we can proceed.

Broad Phase collision detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

1. SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

2. Spatial Hash - More info - O(n log(n)) algorithm
if I remember correctly. Can be O(1) in best case and O(n^2) in worst case)
We have 4 different broad phase algorithms in Farseer Physics Engine. The two mentioned, a brute force and a Selective Sweep collider.

It is important to remember that the broad phase only detects what objects are close and what objects are far and then create pairs of objects that can be tested against each other. To determine if two objects are close and should be further tested, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that contains the whole object. It is cheaper to test box vs. box instead of a lot of complex polygons.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase collision detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.
We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms, Farseer Physics support the following two (Have in mind that there are many other algorithms):

SAT (Separate Axis Theorem) - More info
Distance Grid - More info

Updated Wiki: DifferentPhases

genbox — Thu, 30 Jul 2009 03:49:26 GMT

Broad and narrow phase collision detection systems

Big O notation

First a little background before I start explaining the collision systems. Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Example:

f(x) = 5x^8 5x6
will become
f(x) = O(5x^8)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). Having a O(n log(n)) is obviously better as it grows slower. Now that we know what big O notation is, we can proceed.

Broad Phase collision detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions, but only if you have a few objects It becomes quite expensive (CPU wise) when you add more and more objects to the simulator because you will have to check each and every object against the next. As I wrote before, that is O(n^2). If you have 100 objects in your screen, we would have to do 10000 collision test. Not good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests performed. We obviously don't need to test objects far away from the player against the player. Those tests can be eliminated by having an algorithm that tests the distance using the X and Y axis of the screen.. There are many algorithms that can eliminate tests, a few of them are:

1. SAP (Sweep and Prune) - O(n log(n))

2. Spatial Hash- O(n log(n))
if I remember correctly. Can be O(1) in best case and O(n^2) in worst case)
We have 4 different broad phase algorithms in Farseer Physics Engine. The two mentioned, a brute force and a Selective Sweep collider.

It is important to remember that the broad phase only detects what objects are close and what objects are far and then create pairs of objects that can be tested against each other. To determine if two objects are close and should be further tested, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that contains the whole object. It is cheaper to test box vs. box instead of a lot of complex polygons.

Narrow Phase collision detection

Once the broad phase collider has done its job, we are left with a couple of object pairs that needs further testing. A physics engine needs to know exactly how deep polygons have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygons and finds out where those two polygons intersect.

Updated Wiki: Donations

genbox — Wed, 29 Jul 2009 10:16:28 GMT

Donations

This is a list of people who have donated to our project. We would like to thank each and every one of you who donated. It is very much appreciated.

Daniel Gimenez - $50.00 USD
Aranda Morrison - $50.00 USD
Dan Wellman - $15.00 USD
David Fleming - $30.00 USD
Chris Misztur - $5.00 USD + 60GB Xbox360 harddrive
Alex Hogan - $50.00 USD
Jonas Andersson - $20.00 USD
Daniel Armstrong - $100.00 USD