What’s Up Next?

Non-rectangular forms in SWT are created using Regions, which are areas that you can add and subtract from. Now if you know the shape or path of your non-rectangular form beforehand, it is pretty simple to code.

        Display display = new Display();
	Shell shell = new Shell(display, SWT.NO_TRIM | SWT.ON_TOP);
	//define a region
	Region region = new Region();
	region.add(circle(67, 67, 67));
	region.subtract(circle(20, 67, 50));
	//define the shape of the shell using setRegion
	shell.setRegion(region);

What happens if I want to construct a non-rectangular form based on a bitmap image with transparency (alpha channel)? Something like this:

One quick approach is to do a pixel by pixel comparison and build the region one pixel at a time, however, this has a performance penalty (almost 3 seconds for a 400×250 pixel image). A closer examination points to the multiple calls to add the region as the problem. For an 400×250 image, there would be 100000 calls if done pixel by pixel. What was needed was a way to group contiguous areas together into a larger rectangle to cut down on the number of calls.

The approach I took is to split the image into four quadrants and check if each quadrant is a solid rectangle or not. If a quadrant is not solid (meaning it contains transparent pixels) then that quadrant is further broken down into smaller quadrants until one of the quadrant’s dimension is one pixel and could not be broken down further or the quadrant is totally transparent. Another further optimization is to look for adjacent rectangles that can be further combined into a single rectangle. With this, I was able to cut down the number of calls to add region to 747 for the above image and performance is now down to less than one sec from previous 3 seconds. I guess there are other ways to do this also and further optimizations can be done but this works for me.

The following code returns a region given an image or image data.

package sift.util;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import org.eclipse.swt.graphics.Image;
import org.eclipse.swt.graphics.ImageData;
import org.eclipse.swt.graphics.Rectangle;
import org.eclipse.swt.graphics.Region;

/**
 * ImageDataHelper.java
 *
 * Copyright (c) 2008 August King Li
 *
 * @author  August Li
 * @version  1.0
 */
public class ImageDataHelper {
    public List<Rectangle> rectangleList;

    private boolean isWholeAlpha(ImageData data, Rectangle rect, boolean alpha) {
        if (alpha) {
            for (int y = 0; y < rect.height; y++) {
                for (int x = 0; x < rect.width; x++) {
                    if (! (data.getAlpha(rect.x + x, rect.y + y) == 255)) {
                        return false;
                    }
                }
            }
        }
        else {
            for (int y = 0; y < rect.height; y++) {
                for (int x = 0; x < rect.width; x++) {
                    if (!(data.getPixel(rect.x + x, rect.y + y) != 0)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private void quadCheck(List<Rectangle> rectList, ImageData data, Rectangle rect, boolean alpha) {
        if (rect.width == 1 && rect.height == 1) {
            if (isWholeAlpha(data, rect, alpha)) {
                addList(rectList, rect);
            }
        }
        else if (rect.width == 1 && rect.height > 1) {
            int h1 = (rect.height / 2);
            int h2 = rect.height - h1;
            Rectangle r1 = new Rectangle(rect.x, rect.y, 1, h1);
            checkRectangle(rectList, data, alpha, r1);
            Rectangle r3 = new Rectangle(rect.x, rect.y + h1, 1, h2);
            checkRectangle(rectList, data, alpha, r3);
        }
        else if (rect.width > 1 && rect.height == 1) {
            int w1 = (rect.width / 2);
            int w2 = rect.width - w1;
            Rectangle r2 = new Rectangle(rect.x, rect.y, w1, 1);
            checkRectangle(rectList, data, alpha, r2);
            Rectangle r4 = new Rectangle(rect.x + w1, rect.y, w2, 1);
            checkRectangle(rectList, data, alpha, r4);
        }
        else {
            int w1 = (rect.width / 2);
            int h1 = (rect.height / 2);
            int w2 = rect.width - w1;
            int h2 = rect.height - h1;
            Rectangle r1 = new Rectangle(rect.x, rect.y, w1, h1);
            checkRectangle(rectList, data, alpha, r1);
            Rectangle r2 = new Rectangle(rect.x + w1, rect.y, w2, h1);
            checkRectangle(rectList, data, alpha, r2);
            Rectangle r3 = new Rectangle(rect.x, rect.y + h1, w1, h2);
            checkRectangle(rectList, data, alpha, r3);
            Rectangle r4 = new Rectangle(rect.x + w1, rect.y + h1, w2, h2);
            checkRectangle(rectList, data, alpha, r4);
        }
    }

    private void addList(List<Rectangle> rectList, Rectangle rect) {
        boolean adj = false;
        for (Rectangle r : rectList) {
            if (r.width == rect.width && r.x == rect.x && r.y + r.height == rect.y) {
                //on top
                adj = true;
                r.height = r.height + rect.height;
            }
            else if (r.height == rect.height && r.y == rect.y && r.x + r.width == rect.x) {
                //on side
                adj = true;
                r.width = r.width + rect.width;
            }
        }
        if (!adj) {
            rectList.add(rect);
        }
    }

    private void checkRectangle(List<Rectangle> rectList, ImageData data, boolean alpha, Rectangle rect) {
        if (isWholeAlpha(data, rect, alpha)) {
            addList(rectList, rect);
        }
        else {
            quadCheck(rectList, data, rect, alpha);
        }
    }

    private void generateRectangleList(ImageData imageData) throws IOException {
        rectangleList = new ArrayList<Rectangle>(100);
        boolean alpha = false;
        if (imageData.alphaData != null) {
            alpha = true;
            Rectangle rect = new Rectangle(0, 0, imageData.width, imageData.height);
            quadCheck(rectangleList, imageData, rect, alpha);
        }
        else {
            ImageData mask = imageData.getTransparencyMask();
            Rectangle rect = new Rectangle(0, 0, mask.width, mask.height);
            quadCheck(rectangleList, mask, rect, alpha);
        }
    }

    public Region computeRegionFromImageData(ImageData imageData) throws Exception {
        generateRectangleList(imageData);
        //calls to region.add are slow, so the above code optimizes the no. of rectangles before calling add
        Region r = new Region();
        for (Rectangle rect : rectangleList) {
            r.add(rect);
        }
        return r;
    }

    public Region computeRegionFromImage(Image image) throws Exception {
        return computeRegionFromImageData(image.getImageData());
    }

}