Splashdust.net

This post is obsolete, go here instead: http://www.splashdust.net/2009/10/box2d-mouse-drawing-now-with-ear-clipping/

In my physics game making endeavors I eventually came across the problem of getting arbitrary polygons in to physics simulation engines such as Box2D.

The problem is that such engines cannot handle concave polygons. And also a polygon cannot have more than a certain number of vertices (for performance reasons I would assume). So in order to feed your polygon to the engine you need to convert it to a format that the engine will be happy with. If it is a concave polygon with lots of vertices it will have to be split up into a set of less complicated convex polygons.

Since I basicly suck at math I had no clue how to do these kinds of calculations, so I turned to google to see if someone else might have already solved the issues. And indeed someone had.

Regarding the problem of concave polys and vertex limits I found a great AS3 class for polygon triangulation over here: http://actionsnippet.com/?p=1462
That class takes a polygon and spits out a bunch of triangles, which when put together assumes the same hull shape as the original polygon. This solved a lot of my problems. However, triangulation does not work when there are overlapping segments in the polygon, which might easily be the case when one jots a bunch of lines on the screen in no particular order. So I needed something to make order from that kind of mess. What I found was the Graham scan algorithm, neatly converted to AS3 at http://blog.efnx.com/as3-creating-a-convex-polygon-from-unordered-points/

Then, of course, I had to convert these classes to haxe, but that was mostly a matter of find-and-replace.

So now I have the following set up:

* Draw a bunch of line segments while the mouse button is down.

* When mousebutton comes up, feed the segments to a function; makeBody()

* If they consist of less than 8 vertices and make up a convex polygon and are in a clockwise order (checked using algorithms found here), then we reverse the vertices to make them CCW and then feed them straight to Box2D. Otherwise we’ll treat it the same way as 8 < vertices polygons.

* If it is more than 8 vertices, than we need to triangulate before Box2D gets them. And if it turns out that they cannot be triangulated, then we’ll feed them to the Graham scan to straighten them out, and then back to the triangulator to try again. If it manages to triangulate this time, then Box2D will get the result. If not, something went terribly wrong, and the whole thing will probably fall into an endless loop of Graham scanning and triangulating.

And that’s that! The result is below for you to play around with.

And here’s the source code.

Instructions:

* Draw bodies using your mouse.

* Hold shift while drawing to make static bodies (ground).

* Hold down “T” to see the shapes that make up each body.

Thanks to Zevan Rosser (www.actionsnippet.com), Schell (blog.efnx.com) and Paul Bourke (debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm) for posting awesome code!

Tags: box2d, flash, Graham scan, haxe, triangulation

This entry was posted on Tuesday, October 20th, 2009 at 9:33 pm and is filed under Box2D, Game dev, Web development. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.