脏矩形

Question

在哪里可以找到有关实现计算“脏矩形”以最小化帧缓冲区更新的算法的参考资料？ 一种显示模型，允许任意编辑并计算更新显示所需的最小“位块传输”操作集。

Answer 1

Vexi 是此的参考实现。 该类是 org.vexi.util.DirtyList（Apache 许可证），并用作生产系统的一部分，即经过彻底测试，并得到很好的评论。

需要注意的是，当前的类描述有点不准确，“一种通用数据结构，用于保存需要重新绘制的矩形区域列表，并具有智能合并功能。”实际上，目前还没有这样做合并。 因此，您可以认为这是一个基本的 DirtyList 实现，因为它仅与 dirty() 请求相交，以确保没有重叠的脏区域。

此实现的一个细微差别是，区域不是使用 Rect 或其他类似的区域对象，而是存储在一个整数数组中，即一维数组中的 4 个整数块中。 这样做是为了提高运行时效率，尽管回想起来我不确定这样做是否有很多优点。 （是的，我实现了它。）用 Rect 替换正在使用的数组块应该足够简单。

该类的目的是快。 使用 Vexi，脏可能每帧被调用数千次，因此脏区域与脏请求的交集必须尽可能快。 使用不超过 4 个数字比较来确定两个区域的相对位置。

由于缺少合并，它并不完全是最佳的。 虽然它确实确保脏/绘制区域之间没有重叠，但您最终可能会得到排列并可以合并到更大区域的区域 - 从而减少绘制调用的数量。

代码片段。 完整代码 在线访问。

public class DirtyList {

    /** The dirty regions (each one is an int[4]). */
    private int[] dirties = new int[10 * 4]; // gets grown dynamically

    /** The number of dirty regions */
    private int numdirties = 0;

    ...

    /** 
     *  Pseudonym for running a new dirty() request against the entire dirties list
     *  (x,y) represents the topleft coordinate and (w,h) the bottomright coordinate 
     */
    public final void dirty(int x, int y, int w, int h) { dirty(x, y, w, h, 0); }

    /** 
     *  Add a new rectangle to the dirty list; returns false if the
     *  region fell completely within an existing rectangle or set of
     *  rectangles (i.e. did not expand the dirty area)
     */
    private void dirty(int x, int y, int w, int h, int ind) {
        int _n;
        if (w<x || h<y) {
            return;
        }
        for (int i=ind; i<numdirties; i++) {
            _n = 4*i;
            // invalid dirties are marked with x=-1
            if (dirties[_n]<0) {
                continue;
            }

            int _x = dirties[_n];
            int _y = dirties[_n+1];
            int _w = dirties[_n+2];
            int _h = dirties[_n+3];

            if (x >= _w || y >= _h || w <= _x || h <= _y) {
                // new region is outside of existing region
                continue;
            }

            if (x < _x) {
                // new region starts to the left of existing region

                if (y < _y) {
                    // new region overlaps at least the top-left corner of existing region

                    if (w > _w) {
                        // new region overlaps entire width of existing region

                        if (h > _h) {
                            // new region contains existing region
                            dirties[_n] = -1;
                            continue;
                        }// else {
                        // new region contains top of existing region
                        dirties[_n+1] = h;
                        continue;

                    } else {
                        // new region overlaps to the left of existing region

                        if (h > _h) {
                            // new region contains left of existing region
                            dirties[_n] = w;
                            continue;
                        }// else {
                        // new region overlaps top-left corner of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(x, _y, _x, h, i+1);
                        return;

                    }
                } else {
                    // new region starts within the vertical range of existing region

                    if (w > _w) {
                        // new region horizontally overlaps existing region

                        if (h > _h) {
                            // new region contains bottom of existing region
                            dirties[_n+3] = y;
                            continue;
                        }// else {
                        // new region overlaps to the left and right of existing region
                        dirty(x, y, _x, h, i+1);
                        dirty(_w, y, w, h, i+1);
                        return;

                    } else {
                        // new region ends within horizontal range of existing region

                        if (h > _h) {
                            // new region overlaps bottom-left corner of existing region
                            dirty(x, y, _x, h, i+1);
                            dirty(_x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains right part of new region
                        w = _x;
                        continue;
                    }
                }
            } else {
                // new region starts within the horizontal range of existing region

                if (y < _y) {
                    // new region starts above existing region

                    if (w > _w) {
                        // new region overlaps at least top-right of existing region

                        if (h > _h) {
                            // new region contains the right of existing region
                            dirties[_n+2] = x;
                            continue;
                        }// else {
                        // new region overlaps top-right of existing region
                        dirty(x, y, w, _y, i+1);
                        dirty(_w, _y, w, h, i+1);
                        return;

                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // new region overlaps to the above and below of existing region
                            dirty(x, y, w, _y, i+1);
                            dirty(x, _h, w, h, i+1);
                            return;
                        }// else {
                        // existing region contains bottom part of new region
                        h = _y;
                        continue;
                    }
                } else {
                    // new region starts within existing region

                    if (w > _w) {
                        // new region overlaps at least to the right of existing region

                        if (h > _h) {
                            // new region overlaps bottom-right corner of existing region
                            dirty(x, _h, w, h, i+1);
                            dirty(_w, y, w, _h, i+1);
                            return;
                        }// else {
                        // existing region contains left part of new region
                        x = _w;
                        continue;
                    } else {
                        // new region is horizontally contained within existing region

                        if (h > _h) {
                            // existing region contains top part of new region
                            y = _h;
                            continue;
                        }// else {
                        // new region is contained within existing region
                        return;
                    }
                }
            }
        }

        // region is valid; store it for rendering
        _n = numdirties*4;
        size(_n);
        dirties[_n] = x;
        dirties[_n+1] = y;
        dirties[_n+2] = w;
        dirties[_n+3] = h;
        numdirties++;
    }

    ...
}

Answer 2

要构建包含所有需要重新绘制的区域的最小矩形：

• 从空白区域开始（可能是设置为 0,0,0,0 的矩形 - 您可以检测为“不需要更新”）

对于每个脏区域添加：

• 规范化新区域（即确保左小于右，上小于下）
• 如果脏矩形当前为空，则将其设置为提供的区域
• 否则，将脏矩形的左和上坐标设置为{dirty,new} 中最小的一个，右侧和底部坐标为 {dirty,new} 中最大的一个。

Windows 至少维护一个更新区域，其中包含已通知的更改以及由于窗口被遮挡和显示而需要完成的任何重新绘制。 区域是由许多可能不连续的矩形、多边形和椭圆组成的对象。 您可以通过调用 InvalidateRect 告诉 Windows 屏幕的一部分需要重新绘制 - 对于更复杂的区域，还有一个 InvalidateRgn 函数。 如果您选择在下一个 WM_PAINT 消息到达之前进行一些绘制，并且希望将其从脏区域中排除，可以使用 ValidateRect 和 ValidateRgn 函数。

当您开始使用 BeginPaint 进行绘画时，您需要提供一个 PAINTSTRUCT，Windows 会用该 PAINTSTRUCT 填充有关需要绘画的内容的信息。 其中成员之一是包含无效区域的最小矩形。 如果您想在存在多个小的无效区域时最小化绘制，您可以使用 GetUpdateRgn 获取区域本身（您必须在 BeginPaint 之前调用它，因为 BeginPaint 将整个窗口标记为有效）。

我认为，由于在最初编写这些环境时最小化绘图在 Mac 和 X 上非常重要，因此存在用于维护更新区域的等效机制。

Answer 3

听起来您需要的是要渲染到屏幕上的每个形状的边界框。 请记住，多边形的边界框可以定义为“左下角”（最小点）和“右上角”（最大点）。 即，最小点的 x 分量定义为多边形中每个点的所有 x 分量中的最小值。 对 y 分量（在 2D 的情况下）和边界框的最大点使用相同的方法。

如果每个多边形有一个边界框（也称为“脏矩形”）就足够了，那么就完成了。 如果您需要整体复合边界框，则适用相同的算法，只不过您可以只用最小点和最大点填充单个框。

现在，如果您在 Java 中完成所有这些操作，则可以直接使用 getBound2D()方法。

Answer 4

您使用什么语言？ 在 Python 中，Pygame 可以为你做到这一点。 使用 RenderUpdates Group 和一些具有图像和矩形属性的 Sprite 对象。

例如：

#!/usr/bin/env python
import pygame

class DirtyRectSprite(pygame.sprite.Sprite):
    """Sprite with image and rect attributes."""
    def __init__(self, some_image, *groups):
        pygame.sprite.Sprite.__init__(self, *groups)
        self.image = pygame.image.load(some_image).convert()
        self.rect = self.image.get_rect()
    def update(self):
        pass #do something here

def main():
    screen = pygame.display.set_mode((640, 480))
    background = pygame.image.load(open("some_bg_image.png")).convert()
    render_group = pygame.sprite.RenderUpdates()
    dirty_rect_sprite = DirtyRectSprite(open("some_image.png"))
    render_group.add(dirty_rect_sprite)

    while True:
        dirty_rect_sprite.update()
        render_group.clear(screen, background)
        pygame.display.update(render_group.draw(screen))

如果你不使用Python+Pygame，我会这样做：

• 创建一个名为 update() 的 Sprite 类，
  move() 等方法设置“脏”
  旗帜。
• 为每个精灵保留一个矩形
• 如果您的 API 支持更新矩形列表，请在精灵为脏的矩形列表上使用它。 在 SDL 中，这是 SDL_UpdateRects。
• 如果您的API不支持更新矩形列表（我从来没有机会使用除SDL之外的任何东西，所以我不知道），请测试一下多次调用blit函数还是使用一次调用blit函数是否更快大矩形。 我怀疑任何 API 使用一个大矩形都会更快，但同样，除了 SDL 之外我没有使用任何东西。

Answer 5

我最近刚刚编写了一个 Delphi 类来计算两个图像的差异矩形，并且对它的运行速度感到非常惊讶 - 速度足够快，可以在很短的计时器内以及在记录屏幕活动的鼠标/键盘消息之后运行。

其工作原理的逐步要点是：

1. 将图像按矩形细分为逻辑 12x12。

2. 循环遍历每个像素，如果存在差异，那么我告诉子矩形该像素属于哪个像素，其中一个像素存在差异，以及差异在哪里。

3. 每个子矩形都会记住它自己的最左、最上、最右和最下差异的坐标。

4. 找到所有差异后，我会遍历所有有差异的子矩形，如果它们彼此相邻，则将它们形成更大的矩形，并使用最左边、最顶部、最右边以及这些子矩形最底部的差异，以形成我使用的实际差异矩形。

这似乎对我来说效果很好。 如果您尚未实施自己的解决方案，请告诉我，如果您愿意，我会通过电子邮件将我的代码发送给您。 另外，到目前为止，我是 StackOverflow 的新用户，所以如果您喜欢我的回答，请投票。 :)

Answer 6

查看 R-tree 和 四叉树 数据结构。