Jump to content

  • Log In with Google      Sign In   
  • Create Account


Composing the concave hull of a textured sprite


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 pondwater   Members   -  Reputation: 191

Like
0Likes
Like

Posted 27 April 2013 - 06:39 PM

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...

 



Sponsor:

#2 irreversible   Crossbones+   -  Reputation: 1243

Like
1Likes
Like

Posted 28 April 2013 - 03:20 AM

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.



#3 grhodes_at_work   Moderators   -  Reputation: 1361

Like
0Likes
Like

Posted 29 April 2013 - 09:47 AM

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


Graham Rhodes Moderator, Math & Physics forum @ gamedev.net




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS