首页 / 知识

关于图形：脏矩形

2023-04-16 04:39:00

Dirty Rectangles

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

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

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

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

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

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

代码Fragments。完整的代码在这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

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 (wx || hy) {
return;
}
for (int i=ind; inumdirties; 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++;
}

...
}

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

从空白区域开始(也许是一个设置为 0,0,0,0 的矩形 - 您可以将其检测为"不需要更新")

对于添加的每个脏区：

规范化新区域(即确保左小于右，上小于下)
如果脏矩形当前为空，请将其设置为提供的区域
否则，将脏矩形的左上坐标设置为 {dirty,new} 的最小值，将右下坐标设置为 {dirty,new} 的最大值。

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

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

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

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

如果每个多边形有一个边界框(又名"脏矩形")就足够了，那么你就完成了。如果您需要一个整体的复合边界框，则适用相同的算法，但您可以只填充具有最小和最大点的单个框。

现在，如果您在 Java 中执行所有这些操作，您可以使用 getBound2D() 方法直接获取 Area(您可以从任何 Shape 构造)的边界框。

研究 R-tree 和 quadtree 数据结构。

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

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

通过矩形将图像细分为逻辑 12x12。

循环遍历每个像素，如果有差异，那么我告诉子矩形该像素属于哪个像素，其中一个像素和位置存在差异。

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

一旦找到所有差异，我会遍历所有有差异的子矩形，如果它们彼此相邻，则从它们中形成更大的矩形，并使用最左边、最上面、最右边和这些子矩形的最底部差异，以制作我使用的实际差异矩形。

这对我来说似乎工作得很好。如果您还没有实现自己的解决方案，请告诉我，如果您愿意，我会通过电子邮件将我的代码发送给您。同样到目前为止，我是 StackOverflow 的新用户，所以如果您欣赏我的回答，请投票。 :)

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

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#!/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.webp")).convert()
render_group = pygame.sprite.RenderUpdates()
dirty_rect_sprite = DirtyRectSprite(open("some_image.webp"))
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，我会这样做：

制作一个更新()的 Sprite 类，
move() 等方法设置一个"脏"
旗帜。
为每个sprite保留一个矩形
如果您的 API 支持更新矩形列表，请在sprite脏的矩形列表上使用它。在 SDL 中，这是 SDL_UpdateRects。
如果您的 API 不支持更新 rects 列表(我从来没有机会使用除 SDL 之外的任何东西，所以我不知道)，请测试是否可以更快地调用 blit 函数多次或一次大矩形我怀疑任何 API 使用一个大矩形会更快，但同样，除了 SDL，我没有使用任何其他东西。

图形计算用于显示

首页 / 知识

关于图形：脏矩形

Dirty Rectangles

最新内容

相关内容

热门文章

推荐文章

标签云

猜你喜欢