It has been a few months since Chipmunk 6.0.3 was released! We’ve had a lot of contracting work to distract us from core Chipmunk development lately. Even so, we’ve been cooking up some new features and now I’m currently working full time putting the final touches on 6.1. So what’s new to get excited about? Here are a lot of words!

One of the features that has been missing from Chipmunk Pro’s autogeometry is some form of concave decomposition. A lot of people use a triangularization algorithm to solve this. Unfortunately, while triangularization is great for creating perfectly decomposed triangle meshes for rendering, and are pretty easy to implement, they doesn’t work very well for generating collision detection shapes. It tends to create more shapes than you want or need and can produce very small or thin shapes. This can clog up the spatial index, giving you poor overall performance, and cause other frustrating artifacts in the simulation quality.

Instead of triangularization, I’ve been working on approximate concave decomposition (ACD) for Chipmunk Pro. This means that you ask Chipmunk to decompose a concave polygon with a distance tolerance, and it will give you back one or more convex polygons that match the shape of the original to within the tolerance. The ACD algorithm tries to match the most important features of the input first to create a high quality decomposition. Also, because it can stop once it satisfies the tolerance, the performance can be really good and used at runtime even. If you want a perfect decomposition, you can still always use a tolerance of 0.0. Although this can take more time and produce more shapes than you might want.

The ACD algorithm shipping with 6.1 isn’t perfect though. I’m still improving it’s splitting plane hueristic to improve how it cuts the polygons (I’m not too happy with the ‘H’ in the image above -_- ), and it doesn’t yet have options to detect or process polygons with holes in them (like the ‘P’). Lastly, if you run ACD on a self intersecting polygon, it might cause it to over-simplify it because it detects the polygon as having a negative tolerance.

Because we are still working on the quality of the algorithm, and its missing the ability to work with holes, we’ve marked it as being beta. Its usable and stable, but its performance and quality might not be as good as some people want yet. I didn’t want to hold up the release longer while I did more research for this, but at the same time didn’t want to leave it in an unusable state.

This has been in the pipeline for a long time! There has been early access to this available through the Chipmunk Pro git repository for some time, but the next release will make it official. This complements the ARM NEON optimized solver and works on any platform that supports pthreads. This is an easy way to take advantage of those extra cores that now ship on everything from desktop to mobile machines. The Chipmunk Pro showcase app on the App Store uses the multi-threaded solver and enables a lot of extra objects to simulate on the iPad 2 and iPhone 4s. Check it out!

Since the beginning of time (or like 2006… whatever), Chipmunk has required that you carefully provide it with convex polygon data with a specific winding. Every good graphics API does this too, so people know to expect this sort of thing right? Nope. I talked with Erin Catto for a while at GDC and he mentioned that the winding and concavity of polygon shapes was one of his biggest support issues and that he recently added a convex hull algorithm so that it would “just work”. I’ve had assertions to ensure concavity and winding, but Erin’s solution was better. 2D game programmers often aren’t graphics experts, and they shouldn’t need to be. I’ve had a nice QuickHull implementation sitting around for some time, so I decided to make it more generic and include it with Chipmunk. Nobody will ever have to bother with concavity or winding ever again. \o/

The main inspiration for the original point query feature in Chipmunk was selecting shapes with the mouse. Using a single point made great sense for this as mice are very precise devices. With touchscreen devices its not perfect. Using a single point to represent a big fat finger doesn’t work very well. Its very frustrating to try to grab a small shape with your finger only to fail repeatedly. I’ve seen some people doing clever sampling tricks to try and get around it, but we can do better! Nearest point queries are the next logical step. Instead of just a yes/no answer to if a point is inside a shape or not, nearest point queries give you the nearest point on the surface of a shape as well as the distance to it (or the depth the point is inside). Now when you tap a big fat finger on the screen, you can trivially find the closest shape within a certain radius. The ChipmunkMultiGrab class in Chipmunk Pro has already been updated to support this.

Almost every language in existence today other than C/C++ has some sort of concept of closures or anonymous functions. One of their uses is to allow you to make some really slick, simple APIs for iterating complex data structures. You just pass a chunk of code to the thing you want to iterate and it will call your code for each object. This is why Chipmunk has so many function based iterators (cpSpaceEachBody(), cpBodyEachShape, cpSpaceSegmentQuery(), etc). Exposing the underlying data structures would be annoying to the user as some of them aren’t simple, and it would mean I can’t change them later if I need to.

Even if you are using Chipmunk from C or C++, most compiler provide some extensions to make your life easier. GCC supports inner functions, and Clang supports blocks. I’ve often encouraged people to use them, as the iterator functions were intended to be used with language features such as these. I started making sample code for a tutorial showing how to use them with Clang blocks, but then decided that I might as well just put that code into the official Chipmunk API instead.

Without the block based iterators, you write code like this:

// Define your callback function somewhere like this:
static void
ScaleIterator(cpBody *body, cpArbiter *arb, cpVect *sum)
{
	(*sum) = cpvadd(*sum, cpArbiterTotalImpulseWithFriction(arb));
}

// ... and then somewhere else use it like this:
cpVect impulseSum = cpvzero;
cpBodyEachArbiter(scaleStaticBody, (cpBodyArbiterIteratorFunc)ScaleIterator, &impulseSum);

With the new block based iterators, its much nicer. You can keep the code all in one place:

__block cpVect impulseSum = cpvzero;
cpBodyEachArbiterBlock(scaleStaticBody, ^(cpArbiter *arb){
	impulseSum = cpvadd(impulseSum, cpArbiterTotalImpulseWithFriction(arb));
});