Marching Squares for Objective Chipmunk

June 5th, 2010| Posted by slembcke
Categories: Development | Tags: , ,

So part of the plan for Objective-Chipmunk is to add useful utility features that don’t make sense to add at the level of Chipmunk’s C API. To that end, I’ve been cleaning up my old marching squares code so that it can be used with Objective-Chipmunk. Basically marching squares is an algorithm that turns an image into vector outlines. As Chipmunk can only work with vector data, this will help you bridge Chipmunk more closely with your art pipeline!

Marching squares.

The shapes are traced out of an antialiased image mask pixel by pixel. This generates a list of 2464 tiny blue line segments, one for each pixel where there is an edge. Next I join all the segments together into polylines and loops and simplify them down to 45 red line segments. Finally, I turn these into convex hulls composed of the 33 green line segments. It’s fast too. The entire process takes 39 milleseconds on my laptop. I’d expect about a quarter of a second on the iPhone 3G.

Possible uses include creating levels for your iPhone games directly from an image or generating sprite collision outlines when you load the sprite! It’s also fast enough that you could use it for deformable terrain or other unique effects.

I also made a second variation of the algorithm designed to work with hard edged shapes such as a low resolution tile map. The line segments it outputs will outline every surface, optimizing away seams in the floors and walls instead of creating a short segment for each tile. Even with a large tile map, say 128×128, regenerating the segments when a tile changes would take only a few milliseconds.

I’m also planning on making a command line tool that will read an image and output the line segment information. It could even spit out a header file with a data structure holding all the segments so it could just become a part of your build process. Drop a new level image onto XCode and automatically have it automatically create the collision info for you!

The backend code is all pretty much working, now I just need to wrap it up with a nice API.

Comments are closed.