I am currently working on a game using SFML and Box2D. I am interested in generating collision geometry from the sprite data that I load into SFML. So, for example, an algorithm that would do this would take an image and find the edges (for example where the alpha area starts) and then generating a polygon that fits to those edges.
Can I be pointed to any resources that describe an algorithm to do this?
The topic you’re touching on here is what is known broadly as “Feature Detection” and more specifically as “Edge Detection” (finding the edges in an image) and “Vectorization” (finding the edges in an image and generating an estimation of that image in terms of curve/poly data).
A couple common algorithms for vectorization are Sobel Edge Detection and Canny Edge Detection. Without some background in signal processing, implementing these on your own is going to take some work. Defining bounding data is usually something that is just done by hand, and most sprite based games use bounding boxes or bounding circles to simplify things.
If you’re really interested in polygon based collisions, and if generating the poly data in an external application to be loaded into your project would work I have another option that would work given that you indicated you would like the base the bounding on the edges of the alpha layer/mask. There is an open source application Potrace which performs vectorization of bitmap images. It also has an option which turns off all smoothing so that the generated vectorization is polygonal only (no curves) which is what you’ll want for doing collisions. It’s a command line application, so you could write a small program/script that extracts the alpha layer of the images (or loads the alpha masks - I'm not sure if you’re using masks or loading graphics with alpha layers) and runs them through Potrace. One of the output formats is DXF which is Well Documented and human readable format. It’s quite easy to work with and parse and you should be able to convert it to whatever format you want to store the vector data in.
@ xuincherguixe:
If you mean the process of edge detection itself, then yes, this would introduce a lot of extra computations; signal processing is always computationally expensive. But given the trivial size of polygon data, a development tool (the use of Potrace and some scripts as I described) could be used to generate the poly data to be loaded into the application at run-time along with the graphics.
If you mean extra collision computations due to the high poly count a tool like Potrace would generate, that could also be an issue, Potrace configuration and perhaps some additional form of polygon reduction might be required to get the bounding polygons to a reasonable number. Ultimately unless there is an extremely large number of sprites, or some form of procedural generation going on, just defining the polygons manually and/or just using bounding boxes/circles is probably the more straight forward (if less interesting) method.
