Box2D v2.3.1 Released

Google Code no longer allows for downloads, therefore you will have to use SVN to get v2.3.1:

svn checkout http://box2d.googlecode.com/svn/tags/v2.3.1

You can view the changes here: https://code.google.com/p/box2d/source/list

The main change was the conversion of the Testbed to use GLFW and imgui instead of freeglut and GLUI. GLUI was not supported and I was having trouble with freeglut in newer versions of Visual Studio. If you work in Visual Studio 2013 or Xcode 5, you can open the project file and get started. On other platforms you will have to do more work to set things up. The big difference in running the Testbed is that the working path needs to be setup correctly so that the font may be loaded. In Visual Studio you can set the working path under the project settings. In Xcode you can setup a custom working directory in the Testbed scheme. The Testbed will crash if it fails to load the font file.

GDC 2014 Physics Tutorial

We had another successful tutorial this year at the Game Developer Conference in San Francisco. Thanks to everyone that attended!

Since Google Projects no longer hosts files, I am hosting new GDC files on this site. Get them here.

Next year I’d like to open up the Physics Tutorial a bit. If you’d like to present, please contact me on Twitter @erin_catto.

Computing a Basis

Given a normalized 3D vector, here’s an efficient method for computing a full basis. The computed basis is axis aligned if the input vector is axis aligned.

In SSE land you can eliminate the branch using a select operation.

Troublesome Triangle

I ran into a problem computing a polygon normal using Newell’s method as described in Christer Ericson’s excellent book Real-Time Collision Detection. In this case the polygon happens to a be a triangle that is close to the origin. So I would guess that Newell’s method would yield a great result. However, this is not true. I only get 2 digits of accuracy in single precision.

Here is the triangle:
p1 = (0.331916571f, 0.382771939f, -0.465963870f)
p2 = (0.378853887f, -0.246981591f, -0.440359056f)
p3 = (0.331879079f, 0.382861078f, -0.465974003f)

I knew I was getting a bad normal because some of my convex hull code was failing. So I decided to analyze the problem. First of all, this triangle has edge lengths of around 0.6320, 0.6321, and 1e-4. So this is a sliver and it is well known that slivers can be numerically challenging.

I computed a baseline normal using doubles. Doubles yielded the following normal vector (truncated to 6 digits):
normal_doubles = (0.206384 -0.0243884 -0.978167).
I got the same result computing the normal in many different ways. So I am confident that this is accurate.

Then I computed the normal many several different ways using single precision:
- 1 way using Newell’s method as stated in Christer’s book
- 3 ways using edge cross products
- 3 ways using Newell’s method on the triangle shifted to each vertex (suggested by Christer)
- 1 way using Newell’s method on the triangle shifted to the centroid

Here is the code:

And here are the results:
0.205007 -0.0244907 -0.978454
0.206384 -0.0243884 -0.978167
0.206417 -0.0243837 -0.97816
0.206384 -0.0243884 -0.978167
0.206377 -0.0243887 -0.978168
0.206453 -0.024386 -0.978153
0.206315 -0.0243899 -0.978182
0.206375 -0.0243882 -0.978169

Exact:
0.206384 -0.0243884 -0.978167

As you can see, Newell’s method is only giving 2 digits of accuracy. Every other method is giving close to 4 digits of accuracy or more. The best result is from n1 and n2. Both of these are cross products that include the shortest edge. This agrees with Gino van den Bergen’s comments on Twitter.

Shifting the triangle origin to one of the vertices or the centroid all improve Newell’s method substantially. I’m a little disappointed that Newell’s method is still not as good as _any_ of the cross products. The price of generality?

Bottom line:
1. Shift a vertex to the origin before applying Newell’s method.
2. Cross products can produce triangle normals that are superior to the results of Newell’s method.
3. Switching to doubles can solve numerical problems, but it is better to first understand the underlying issue.

New Testbed GUI

I’m making progress on a revised testbed framework using GLFW, GLEW, and imgui.

This is replacing the old framework that uses freeglut and GLUI. GLUI is no longer supported and freeglut has been having some problems with newer versions of Visual Studio. Maybe freeglut 3.0 will be better. GLFW is well maintained and very small. Hopefully it works well on OSX.

Anyhow, I’m excited by the results, so I decided to post a screenshot. I’m hoping to commit this in the next few days. I need to repair text rendering and get the XCode project fixed up.

NewTestbed

Box2D 2.3.0 Released

It has been a long time, but version 2.3.0 has finally been released. You can get it here: .

Here are the changes:

  • Polygon creation now computes the convex hull. Vertices no longer need to be ordered.
  • The convex hull code will merge vertices closer than dm_linearSlop. This may lead to failure on very small polygons.
  • Added b2MotorJoint.
  • Bug fixes.

Next year, Google Code will not allow new downloads: . So I am now using SVN tags for releases. If you want to switch over to using tags now, then you can use this:

svn checkout http://box2d.googlecode.com/svn/tags/v2.3.0

I plan to switch to this method for the next release of Box2D. Hopefully Google will make it easier to download a tagged version.

GDC 2013

This year’s physics tutorial was a lot of fun and all the speakers did a great job. We had some new speakers this year and all the presentations contained new material. You can get all the presentations here: Downloads. Look for files with a summary prefix of “GDC 2013″.

You can get Glenn Fiedler’s presentation here: click

__m128

The best way to use SSE is to use the __m128 intrinsic directly. Unfortunately Visual Studio displays the values backwards (w,z,y,x). Bleh. Here is a change to autoexp.dat to correct the order.

First comment out this line:

And add this line:

Shape Coordinates

Keep in mind that a shape does not know about bodies and stand apart from the dynamics system. Shapes are stored in a compact form that is optimized for size and performance. As such, shapes are not easily moved around. You have to manually set the shape vertex positions to move a shape. However, when a shape is attached to a body using a fixture, the shapes move rigidly with the host body. In summary:

  • When a shape is not attached to a body, you can view it’s vertices as being expressed in world-space.
  • When a shape is attached to a body, you can view it’s vertices as being expressed in local coordinates.