Creating polygon cut outs for 2D sprites

Member
Posts: 23
Joined: 2010.08
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.

The Monkey Hustle - Now available on the App Store!
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
I've never heard of anyone doing this Wink
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #3
Sounds like you're talking about vectorization. The list of software linked at the bottom of that page may be helpful.
Quote this message in a reply
Member
Posts: 166
Joined: 2009.04
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".
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
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)

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 166
Joined: 2009.04
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.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
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:
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.
Quote this message in a reply
Member
Posts: 23
Joined: 2010.08
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 Smile

The Monkey Hustle - Now available on the App Store!
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
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.
Quote this message in a reply
Member
Posts: 45
Joined: 2006.07
Post: #10
Also: look up marching squares: http://en.wikipedia.org/wiki/Marching_squares
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 45
Joined: 2006.07
Post: #12
Yep, I think I misunderstood the OP.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Tessellation / Polygon triangulation on iPhone mortenmo 0 2,980 Sep 10, 2008 11:20 AM
Last Post: mortenmo