Creating polygon cut outs for 2D sprites
Post: #1
I am trying to optimise blended drawing of 2D sprites that have a lot of alpha by mapping them to tight fitting polygon shapes - rather than the standard rectangle.
Because this seems like a common optimisation I would think there exists tools that help you create polygon cut outs based on an image alpha. Sadly my Google searching has not come up with any good results.
Has anyone here come across such a tool - or have suggestions for how to easily create polygon shapes from your image sprites?
Thank you for your help.
Because this seems like a common optimisation I would think there exists tools that help you create polygon cut outs based on an image alpha. Sadly my Google searching has not come up with any good results.
Has anyone here come across such a tool - or have suggestions for how to easily create polygon shapes from your image sprites?
Thank you for your help.
The Monkey Hustle - Now available on the App Store!
Post: #3
Sounds like you're talking about vectorization. The list of software linked at the bottom of that page may be helpful.
Post: #4(Oct 6, 2010 08:38 AM)mariocaprino Wrote: I am trying to optimise blended drawing of 2D sprites that have a lot of alpha by mapping them to tight fitting polygon shapes - rather than the standard rectangle.
Check this out ... http://www.humus.name/index.php?page=Cool
Look for the entry named "Particle trimmer".
Post: #5
Even on the iPhone, it's pretty much guaranteed to be faster to draw a big quad.
The docs say that alpha testing is slow on the iPhone, but it says it in the context of hidden surface removal for 3D stuff. It still seems to speed 2D blending up however. (at least it did back in 2.x on a 1G iPod)
The docs say that alpha testing is slow on the iPhone, but it says it in the context of hidden surface removal for 3D stuff. It still seems to speed 2D blending up however. (at least it did back in 2.x on a 1G iPod)
Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Post: #6(Oct 6, 2010 10:48 AM)Skorche Wrote: Even on the iPhone, it's pretty much guaranteed to be faster to draw a big quad.
The docs say that alpha testing is slow on the iPhone, but it says it in the context of hidden surface removal for 3D stuff. It still seems to speed 2D blending up however. (at least it did back in 2.x on a 1G iPod)
If you are talking about opaque sprites then yeah, it is faster to use regular quads but that's generally not a problem to begin with.
With blending on, using a tight non-rectangular bounding poly can save you a lot of fillrate depending on your sprite's internal alpha shape.
It is simply a matter of balance - if you are fillrate bound , adding a few more vertices per sprite should be irrelevant in terms of vertex processing performance but can save you sometimes 30-40% of fillrate which can be huge.
Post: #7
I guess it seems like you would have to have a large percentage of the area to be transparent. Though I'll give this idea the benefit of the doubt.
Creating a tight fitting polygon would be relatively hard. Creating k-DOPs (k-sided discrete oriented polytopes) is already a non-trivial problem. Creating a tight fitting concave polygon would be much harder.
An easier solution would be a recursive solution. Split the image recursively and only output geometry when you have a full square:
Pseudocode:
If that makes any sense. It should be relatively efficient at keeping the amount of geometry down.
Creating a tight fitting polygon would be relatively hard. Creating k-DOPs (k-sided discrete oriented polytopes) is already a non-trivial problem. Creating a tight fitting concave polygon would be much harder.
An easier solution would be a recursive solution. Split the image recursively and only output geometry when you have a full square:
Pseudocode:
Code:
boolean SplitImage(image, vertex_buffer){
// we are trading vertex cost for fillrate
// probably best to balance it by area
if(image.width*image.height < AREA_THRESHOLD){
return image.is_partly_opaque()
} else {
// each image is split into two other images
subimage1, subimage2 = nil
if(image.width > image.height){
subimage1, subimage2 = image.split_horizontally()
} else {
subimage1, subimage2 = image.split_vertically()
}
subimage1_needs_geometry = SplitImage(subimage1, vertex_buffer)
subimage2_needs_geometry = SplitImage(subimage2, vertex_buffer)
if(subimage1_needs_geometry && subimage2_needs_geometry){
// don't output geometry as it might be joined in a super image somewhere
return true
} else {
if(subimage1_needs_geometry) output_geometry(vertex_buffer, subimage1)
if(subimage2_needs_geometry) output_geometry(vertex_buffer, subimage2)
// geometry has already been output, so return false
return false
}
}
}
if(SplitImage(image, vertex_buffer)) output_geometry(vertex_buffer, image)If that makes any sense. It should be relatively efficient at keeping the amount of geometry down.
Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Post: #8(Oct 6, 2010 10:02 AM)warmi Wrote: Look for the entry named "Particle trimmer".
Thanks, that was just the kind of tool I was looking for!
(Oct 6, 2010 02:05 PM)Skorche Wrote: I guess it seems like you would have to have a large percentage of the area to be transparent. Though I'll give this idea the benefit of the doubt.
I'm currently toying around with multisampling, and it is not difficult to become fillrate limited in this rendering state. I don't know if using polygon cut outs will improve performance - but I am glad I won't have to write a tool to test if it will
The Monkey Hustle - Now available on the App Store!
Post: #9
Oh, I missed that link. Looks like that tool only generates convex hulls. Probably works well for particles, but might not for large cutout shapes. Try it first obviously.
Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Post: #11
Well, marching squares won't get you very far. It will dump out a huge amount of geometry that you will have to simplify. It also only helps if you want to make a tight fitting concave polygon. Simplifying a tight fitting concave polygon is fairly difficult. Once you do that, you also need to triangulate it. To get this far, you've now done a number of the more difficult computational geometry problems. Not saying that it can't be done, but that it probably wouldn't be worth the effort.
You can generate a tight fitting convex hull without using marching squares, and simplifying a convex hull is relatively easy. No need to tesselate anything either. That is what the particle trimmer linked above does near as I can tell.
You can generate a tight fitting convex hull without using marching squares, and simplifying a convex hull is relatively easy. No need to tesselate anything either. That is what the particle trimmer linked above does near as I can tell.
Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
