脏矩形 [英] Dirty Rectangles
问题描述
哪里可以找到有关实现一种算法的参考资料，该算法用于计算脏矩形"以最小化帧缓冲区更新?一种显示模型，允许任意编辑并计算更新显示所需的最小位 blit"操作集.
Where may one find references on implementing an algorithm for calculating a "dirty rectangle" for minimizing frame buffer updates? A display model that permits arbitrary edits and computes the minimal set of "bit blit" operations required to update the display.
推荐答案
Vexi 是这个的参考实现.类是 org.vexi.util.DirtyList(Apache 许可)，用作生产系统的一部分，即经过彻底测试，并得到很好的评论.
Vexi is a reference implementation of this. The class is org.vexi.util.DirtyList (Apache License), and is used as part of production systems i.e. thoroughly tested, and is well commented.
需要注意的是，当前的类描述有点不准确，一种通用数据结构，用于保存需要重新绘制的矩形区域列表，并具有智能合并." 实际上确实如此.目前不进行合并.因此，您可以将其视为基本的 DirtyList 实现，因为它仅与dirty() 请求相交以确保没有重叠的脏区域.
A caveat, the currently class description is a bit inaccurate, "A general-purpose data structure for holding a list of rectangular regions that need to be repainted, with intelligent coalescing." Actually it does not currently do the coalescing. Therefore you can consider this a basic DirtyList implementation in that it only intersects dirty() requests to make sure there are no overlapping dirty regions.
这个实现的一个细微差别是，不是使用 Rect 或其他类似的区域对象，而是将区域存储在一个整数数组中，即在一维数组中的 4 个整数块中.这样做是为了运行时效率，尽管回想起来，我不确定这是否有很多优点.(是的，我实现了它.)用 Rect 替换正在使用的数组块应该很简单.
The one nuance to this implementation is that, instead of using Rect or another similar region object, the regions are stored in an array of ints i.e. in blocks of 4 ints in a 1-dimensional array. This is done for run time efficiency although in retrospect I'm not sure whether there's much merit to this. (Yes, I implemented it.) It should be simple enough to substitute Rect for the array blocks in use.
课程的目的是快.使用 Vexi，dirty 可能每帧被调用数千次，因此必须尽可能快地将脏区域与脏请求的交集.不超过4次数字比较来确定两个区域的相对位置.
The purpose of the class is to be fast. With Vexi, dirty may be called thousands of times per frame, so intersections of the dirty regions with the dirty request has to be as quick as possible. No more than 4 number comparisons are used to determine the relative position of two regions.
由于缺少合并，它不是完全最优的.虽然它确实确保脏/已绘制区域之间没有重叠，但您最终可能会得到排列并可以合并到更大区域的区域 - 从而减少绘制调用的次数.
It is not entirely optimal due to the missing coalescing. Whilst it does ensure no overlaps between dirty/painted regions, you might end up with regions that line up and could be merged into a larger region - and therefore reducing the number of paint calls.
代码片段.完整代码 在这里在线.
Code snippet. Full code online here.
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++;
}
...
}
这篇关于脏矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
