Public Group

# Image Tracing

This topic is 3553 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am wondering how I could do the following: Take an image say black and white and determine which parts of the image are white. Get the vertices to the polygons conforming the white portions of the image. I need several polygons because one problem is that the polygons can't be concave. I am asking this because right now I am using a physics engine that makes bodies for objects based on shapes and the shapes are polygons determined with vertices, the polygons can't be concave. Any help/info on the subject is much appreciated.

##### Share on other sites
You might want to do a search for "vectorization algorithm" or "image vectorization algorithm".

##### Share on other sites
What is it about? I found several pages regarding vectorization algorithms though I can hardly understand what is being said in the articles :S.

'In this paper, a new approach which differentiates from the conventional thinning algorithms in vectorizing a raster line image called maximal inscribing circle (MIC) is used. This region-based vectorization algorithm takes the ensemble of pixels within the line segments collectively as legitimate candidates in deciding the vectorized representation. An iterative procedure is outlined and the criteria for merging short straight line segments into the corresponding curve representation are described. This method cannot only segment the lines and junctions, construct their spatial relationships in a computation efficient manner, but also retain their line width....'

'In this paper we present an algorithm, which vectorize geographical images. The transformation from a raster representation to a vectorial one is a question that has to be frequently treated in the management and processing images. For example the geographical information is readily available on photos, maps, planimetries.'

etc...

##### Share on other sites
Let me guess -- you're trying to make a sprite-based game system with awesomely accurate collision detection for arbitrarily-shaped sprites, but you're wrestling with the fact that the only good polygon-based collision detection algorithms require convex polygons? I was doing this exact thing four years ago, and spent a lot of time and effort trying to do accurate collision detection for arbitrarily-shaped sprites using composited convex polygons. And while it was a good learning experience for me as a developer, it didn't ultimately result in anything useful.

Honestly, most games simply don't need anywhere near that level of detail in collision detection. Every single 2D platforming game I know of uses axis-aligned bounding boxes, or maybe oriented bounding boxes if they have gigantic swords or other rotating, long and narrow objects.

If you have a good convex polygon system, then great! But trying to extend it to trace the outline of an object is going to be way more trouble than it's worth. What I've done for my game is assign a single polygon for an entire class of sprites (e.g. all of the sprites in the run animation have the same bounding polygon). I'd recommend you try the same. If nothing else, it's important in a platforming game (and I grant I don't know if that's what you're working on) to have a consistent bottom to the sprite, so that it doesn't jitter up and down as the character moves around.

##### Share on other sites
Yeah I know, if I didn't really need it I wouldn't even bother. The reason why I need this is because I want to have a destructible terrain and objects. The game is a spaceship game and I want that if a player blows a crater into a giant asteroid he's able to fly into that crater. Being able to eventually blow tunnels into asteroid and terrain.

Edit: This means you know how? Could you help me please ^^?

[Edited by - Antonym on April 29, 2009 12:29:46 PM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634112
• Total Posts
3015567
×