iDevGames Forums
Creating polygon cut outs for 2D sprites - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: iPhone, iPad & iPod Game Development (/forum-11.html)
+--- Thread: Creating polygon cut outs for 2D sprites (/thread-8178.html)



Creating polygon cut outs for 2D sprites - mariocaprino - Oct 6, 2010 08:38 AM

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.


RE: Creating polygon cut outs for 2D sprites - OneSadCookie - Oct 6, 2010 08:42 AM

I've never heard of anyone doing this Wink


RE: Creating polygon cut outs for 2D sprites - ThemsAllTook - Oct 6, 2010 09:49 AM

Sounds like you're talking about vectorization. The list of software linked at the bottom of that page may be helpful.


RE: Creating polygon cut outs for 2D sprites - warmi - Oct 6, 2010 10:02 AM

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


RE: Creating polygon cut outs for 2D sprites - Skorche - Oct 6, 2010 10:48 AM

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)


RE: Creating polygon cut outs for 2D sprites - warmi - Oct 6, 2010 10:59 AM

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


RE: Creating polygon cut outs for 2D sprites - Skorche - Oct 6, 2010 02:05 PM

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


RE: Creating polygon cut outs for 2D sprites - mariocaprino - Oct 7, 2010 06:09 AM

(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 Smile


RE: Creating polygon cut outs for 2D sprites - Skorche - Oct 7, 2010 06:42 AM

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.


RE: Creating polygon cut outs for 2D sprites - mattz - Oct 7, 2010 05:01 PM

Also: look up marching squares: http://en.wikipedia.org/wiki/Marching_squares


RE: Creating polygon cut outs for 2D sprites - Skorche - Oct 8, 2010 06:24 AM

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.


RE: Creating polygon cut outs for 2D sprites - mattz - Oct 8, 2010 11:47 AM

Yep, I think I misunderstood the OP.