Optimum set of dirty rectangles

Question

I'm looking for an algorithm here, independent of specific programming language.

The problem:

We have a 2-dimensional display area (think simple buffer of pixels). Periodically, some of the pixels are changed. We need to find a set of rectangles that encapsulate all changed pixels.

It would be trivial, but undesirable, to compute a single, potentially large, rectangle that encapsulates all changed pixels. We would rather have multiple, smaller, tight-fitting rectangles down to a specified minimum size (that is a variable which can be changed).

For example, suppose that within the entire display area, a few pixels in the upper left corner changed and a few pixels in the lower right corner changed. We do NOT want to compute a single dirty rectangle of the entire area - we instead want two dirty rectangles: a small one in the upper left and a small one in the lower right.

Performance is critical, hence this question.

This problem crops up all of the time, definitely in video codecs and remote desktop compression areas, I presume. In my case, it is a recurring problem during graphical image manipulations that involve multiple users simultaneously drawing in a shared area.

Does anyone know of published algorithms for this or know of a solution you have used in the past?

Thanks!

Answer 1

Screen video/remote desktop codecs generally divide the screen into tiles and then transmit bitmaps for the changed tiles only. The tile images are typically then ZLIB-compressed.

There are various ways to improve on this, e.g.

• Give each tile its own bounding rectangle, covering the changed pixels in that tile (to avoid re-transmitting the whole tile if only a few pixels have changed.)
• Prime the compressor with the previous contents of the tile (this greatly improves compression efficiency if you are recording a window being dragged or sprites moving in a 2D game.)

For example Adobe Flash uses a combination of all three techniques in its "Screen Video 2" codec.

If you don't want to use compression, a combination of tiles & bounding boxes is a good compromise. E.g. if you have just two changed pixels at opposite corners only those two pixels will be updated, but if you have a region with scattered changes (e.g. typing in a text editor) the changes are combined into a few large rectangles which is probably more efficient than breaking it into hundreds of small rectangles.)

Answer 2

My idea, with two decision options:

I wrote it in some kind of pseudocode ..

Basically for the first option you decide on a percentage that your area's must comply to meet minimum dirty pixels count.

And for the second option, you decide if the difference in this factor or dirty pixels per area changes too much if you expand to include this pixel.

    struct DirtyPixelArea
{
    Vec2 topLeft;
    Vec2 size;
    list<Vec2> dirtyPixels;

    void AddPixelToArea();

    int Area();
    int DirtyPixelsArea(); // sums all dirty pixels in area
};

list<DirtyPixelArea>  dirtyPixelsAreaList

void add_dirty_pixel(Vec2 dirtyPixel)
{
    closest_area = find_closest_area_to_pixel(dirtyPixel).copy();

    //option 1 - begin

    closest_area.add_dirty_pixel(dirtyPixel);

    if (closest_area.DirtyPixelsArea() > (closest_area.Area() * 0.25))   // you can experiment on choosing your own dirty pixel factor
    {
        update_area_in_list(closest_area);
    }
    else
    {
        new_area = new DirtyPixelArea();
        new_area.AddPixelToArea(dirtyPixel);
        add_area_in_list(new_area);
    }

    //option 1 - end

    // option 2 - begin
    original_area = find_closest_area_to_pixel(dirtyPixel);
    closest_area.add_dirty_pixel(dirtyPixel)

    original_area_factor = original_area.DirtyPixelsArea() / original_area.Area();
    closest_area_factor = closest_area.DirtyPixelArea() / closest_area.Area();

    if ( closest_area_factor / original_area_factor > 0.5)
    {
        update_area_in_list(closest_area);
    }
    else
    {
        new_area = new DirtyPixelArea();
        new_area.AddPixelToArea(dirtyPixel);
        add_area_in_list(new_area);
    }

    // option 2 - end

}

Answer 3

Look into R-tree and quadtree data structures.