Vectorization of Raster Regions.

[Calin Leafshade]

I want to convert an AGS region to a series of vertices. Does anyone have any ideas of how to do this?

I have googled it but all the responses seem to be beyond the scope of what i want to do.

A picture:



Basically I want to get the polygons' vertices marked in red, in order, around the shape. I also want to be able to tell which polygon matches which vertices.

Are there any accepted methods for doing this that i dont know about?

[Khris]

You probably found this already, but except for using bezier curves, this is what you have to do: http://potrace.sourceforge.net/potrace.pdf

It always comes down to
1) creating paths at a pixel level
2) turning them into polygons that approximate them

There simply is no other way.

Are you coding a replacement for built-in walking? Or is this for a port?

[Calin Leafshade]

Neither, it is for collision checking.

I don't really understand the maths behind potrace so it might not be worth it.

EDIT: Actually a marching squares algorithm might do it

[Monsieur OUXX]

EDIT: Actually a marching squares algorithm might do it

Hi Calin,; I don't know if it's too late to help you with this, but I thought it might be of some interest to future readers.
Firstly, I'm not sure why you want to use marching squares. Marching squares are usually for the revert process -- in a nutshell : building the final complex shape out of a finite set of prefab basic shapes.

What you're looking for is related to the flood fill algorithms from the ancient days of computing : out of a given grid of pixels, most of them detect the inside and the outside of a shape, then possibly the edges. All you will have to do then is to compute the vertices out of all that.

In your specific case I'd have a special look at the scanline fill algorithm.

All that is quite resources-consuming. I don't think you could do that sort of calculations in real-time during the game. I'd recommend computing it before-hand, when you save your level in your level-editor (if it's what you're planning on doing).

[Calin Leafshade]

In the end, i defined them as polygons in engine:



If nothing else, its more accurate.