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

Look into R-tree and quadtree data structures.