# Creating primitive geometry from 2d bitmap

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

## Recommended Posts

Hello, I am working on a physics addition for a software program and I would like to be able to generate collision primitives for 2d "sprites" that are just images. I am looking for ways to go about this. My thoughts are to use some sort of best fit algorithm but I am a bit lost as to what exactly would be involved in doing this. If anyone can shed some light on this topic I would be very appreciative. I am not looking for complete answers, just help finding the right direction to begin my research. Thank you.

##### Share on other sites
Here in GameDev's own library of Articles, there's a section on Collision Detection, including an article on Pixel-Perfect collision detection.

I'd suggest starting with the last link and going backwards, but surely something in one of those links should put you on the right track. [smile]

-jouley

[Edit: Another one for 2D image collision.]

##### Share on other sites
I think the OP is looking for a way to produce a polygonal(?) approximation of the sprite's geometry to use as a collision model (against other polygonal shapes) instead of raster scanning.

I've never done this myself, but one way might be to use an algorithm similar to marching cubes ("marching squares") to create an outline based on the sprite. Basically, you place a regular grid of points on the graphic and mark each grid intersection as "empty" or "solid" based on what color is underneath. Then look at the four corners of each grid square; if the square has both empty and solid vertices then the outline goes through the square, specifically through sides that connect an empty and a solid vertex. It wouldn't be pixel-perfect but you could easily tune its accuracy vs. complexity/performance by changing the grid resolution.

##### Share on other sites
Quote:
 Original post by Fingers_I think the OP is looking for a way to produce a polygonal(?) approximation of the sprite's geometry to use as a collision model (against other polygonal shapes) instead of raster scanning.

Whoopsies! In that case, how complex are the images - 32 pixels square, 1024 by 512, simple shapes or complex? What degree of "perfection" do you need - "Pixel" perfect, or just a general collision? Are the shapes represented convex? Generated at runtime, or all part of the application at load time?

There are ways to optimize a completely accurate polygonal representation, but how applicable they will be depends on what exactly you need them to do.

-jouley

##### Share on other sites
Hey, the primitive geometries need to be genenerated at loadtime. I would like to be able to fit a circle if I have a circle and a rectangle if I have a rectangle in my image, and in any other case simple line primitives would be fine.

I am using a collision lib called flatland and it has circle, box, and line collision primitives, so I would like to be able to break my sprites down into them.

The images vary in size but probally bigger then 32x32 and less then 640x480.

Thanks for the help, if you can point me in the right direction I would appreciate it!

##### Share on other sites
Fingers_ suggestion is a good one - the marching squares approach will let you create boundaries for any arbitrary rasterized image.

It could be possible to speed things up if you flag the images that are roughly circular as circles, or roughly rectangular as rectangles, then just skip the generation and assign a circle or rectangle. You'd lose some precision, but whether or not that matters is a pretty subjective call.

-jouley

• ### What is your GameDev Story?

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

• 11
• 15
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
634151
• Total Posts
3015826
×