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.