Monday, March 22, 2010

Image Transparency (aka an absurd application of convex hull)

Android makes it very easy to load an image as a bitmap:

int resID = context.getResources().getIdentifier(...);
Bitmap bitmap = BitmapFactory.decodeResource(context.getResources(), resID);

But once you have that Bitmap, if it has significant transparency, kiss your performance goodbye. Getting decent performance back is going to be anything but easy. For our Penguins game we wanted to have all images of the penguins (one per frame of animation) to be identically sized so that they could be easily positioned. This means that each image (frame of animation) has a large amount of fully transparent pixels. Drawing all of these fully transparent pixels absolutely destroyed our frame rate in the emulator. Essentially, the emulator has dreadful alpha blending performance.

So, the question was - how could we keep our images with lots of fully transparent pixels and have good performance? The obvious answer was to have Android draw as few of the fully transparent pixels as possible. The Canvas class which is used for drawing has the following method:

Canvas#clipPath(Path path);

So it was now necessary to build the best possible Path around each penguin image. I wanted a programmatic solution, particularly because at the time of writing the code I was not working with the final artwork. So the first step was to figure out an efficient way to access all of a bitmap's pixels. Bitmap has a convenient method to access an individual pixel, but calling that methods tens of thousands of times for each image results in dreadful performance. (Even though this computation is only done while the game is loading, not each frame.)

Turns out there's a very easy way to get the pixels as a linear array:

int width = bitmap.getWidth();
int height = bitmap.getHeight();
int[] pixels = new int[width*height];
bitmap.getPixels(pixels, 0, width, 0, 0, width, height);

Now that we have the pixels we want find the boundary pixels. (Note: If our images had fully transparent pixels inside of non-transparent pixels this approach would not have worked as well.) So the next step was to find all of the boundary pixels:

ArrayList points = new ArrayList();
for(int x = 0; x < width; x++)
{
  int firstY = -1, lastY = -1;
  for(int y = 0; y < height; y++)
  {
    boolean transparent = (pixels[y*width+x] == Color.TRANSPARENT);
    if(!transparent)
    {
      if(firstY == -1)
      {
        firstY = y;
      }
      lastY = y;
    }
  }

  if(firstY != -1)
  {
    points.add(new Point(x, firstY));
    points.add(new Point(x, lastY));
  }
}

A Path could then be built from these pixels. (If we were to actually do this, it would be easier to build the Path using two ArrayLists, one for top half, the other for the bottom Path.) I gave this a try, and the performance was marginally better. The Path fit perfectly and therefore had an enormous amount of line segments in it. I had just traded one performance slow down for another. I wanted a way to have a Path that was guaranteed to include all of the penguin, would not have many fully transparent pixels, but also a lot less line segments. I had an absurd idea - why not implement the convex hull algorithm over the boundary points? So I did, and it worked. Performance increased dramatically. I was now drawing a few fully transparent pixels, but the Path object had far fewer line segments.


Below is a diagnostic mode where the clipping Path is being draw. The bottom penguin is in mid-left thwack.



4 comments:

  1. Thank you for the article! I need to do the exact same thing. Do you mind sharing the code with the convex hull algorithm? If you don't want to post it would you please email it to me? This would be a big help.
    Thank you very much.
    -Chris
    ch393366@gmail.com

    ReplyDelete
  2. thanks for this article.can you guide me how can i bound these points on canvas. means i want to draw these points on canvas and when user touch within the bounded area of these points object will moves according to that.

    ReplyDelete
  3. This is one of the superior and advance post.Your blog information is very clear and easy to understand.
    Android app developers

    ReplyDelete
  4. I lately came beyond your web-site and accept been account affluence of posts of yours. I aloof anticipation I'd add a quick animadversion and let you apperceive that you've got a actively nice weblog.

    Android developers

    ReplyDelete