Sign in to follow this  
pondwater

Composing the concave hull of a textured sprite

Recommended Posts

pondwater    191

I'm writing a 2D rendering engine, and currently I have shadow casting on convex shapes generated from the sprite textures. I would like to expand it to concave shapes, so now i need the concave hull of my sprite. Generating the edge vertices isn't difficult, it is assembling them into a coherent ordering that is giving me trouble.

 

CAtZyCa.png

 

 

I know there are more than one concave hulls for a generic set of points, but im hoping it is possible to exploit the spatial locality of the points produced from the texture to ensure the correct hull.

 

At first I was hoping to simply pick a random point, and then choose the closest point and just follow the trail. However, this fails quite easily. I'm wondering if anyone has any knowledge about this or any ideas on how to accomplish this...

 

Share this post


Link to post
Share on other sites
irreversible    2860

For a point cloud, check this out.

 

Overall, holes are a real tough cookie to support unless you set up some rules: eg a hole can never intersect an edge. Otherwise you'll always have ambiguity, which cannot really be resolved. Also, if you increase your vertex count to one per pixel, you'll effectively be running marching squares on the shape, which should give you expected results if the shape doesn't fold back on itself and none of the hole edges/vertices are closer to the shape's edges than two pixels.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385

There's a fancy technqiue called Active Contours, or snakes, that could be used. I'll let you google it. Non-trivial to implement. You would prime the algorithm by computing the convex hull around the sprite.

 

You could use a flood fill algorithm to find the outer boundary pixels ignorning the holes, Set your seed point to be the upper-left pixel. Run the flood fill to produce a mask, which will not show the holes. Then construct your concave outer boundary from the mask.

 

Graham

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this