最佳的一组脏兮兮的矩形 [英] Optimum set of dirty rectangles

问题描述

问题：

我们有一个二维显示区域
（想象一下像素的简单缓冲区）。
定期地，一些像素被改变
。我们需要找到一组
矩形，它们封装了所有
更改的像素。

这将是微不足道的，但不可取的是
来计算一个单一的，可能是
的大矩形，它封装了所有
变化的像素。我们宁愿将
多个较小的紧密配置的
矩形降至指定的最小
大小（即可以变为
的变量）。例如，假设在
整个显示区域内，
中的几个像素左上角改变了，
几右下角的像素
已更改。我们不想计算整个
区域的
单个脏矩形 - 我们想要两个肮脏的
矩形：上边的
中的一个小矩形和一个小的矩形

性能非常关键，因此存在这个问题。

我猜想，这个问题总是会出现，绝对是在视频编解码器和远程桌面压缩领域。就我而言，在图形图像操作过程中，涉及多个用户同时在共享区域中绘图的问题是一个反复出现的问题。

有人知道已发布的算法或已知的您在过去使用过的解决方案？

谢谢！

解决方案

屏幕视频/远程桌面编解码器通常会将屏幕分成多个图块，然后仅为已更改的图块传输位图。平铺图像通常是ZLIB压缩的。

有多种方法可以改进，例如

• 为每个图块分配一个自己的边界矩形，以覆盖该图块中已更改的像素（以避免只有几个像素发生更改时重新传输整个图块）。
  
• 用压缩器的前一个内容填充压缩器（如果您正在录制被拖动的窗口或在2D游戏中移动的精灵，这将极大地提高压缩效率。）

例如Adobe Flash在其Screen Video 2编解码器中使用了所有三种技术的组合。

如果您不想使用压缩，瓷砖和瓷砖的组合。包围盒是一个很好的折衷。例如。如果在对角处只有两个变化的像素，那么只会更新这两个像素，但是如果您有一个分散变化的区域（例如，在文本编辑器中键入），则这些更改会合并为几个较大的矩形，这可能比把它分成数百个小矩形。）

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!

解决方案

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.)

这篇关于最佳的一组脏兮兮的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！