脏的矩形 [英] Dirty Rectangles

问题描述

在哪里可以找到有关实现用于计算脏矩形以最小化帧缓冲区更新的算法的参考？一个显示模型，允许任意编辑并计算更新显示所需的最小比特位操作集。 是这个的参考实现。该类是 org.vexi.util.DirtyList （Apache许可证），并被用作生产系统的一部分，即经过全面测试，并且评论很好。

一个告诫，当前类描述有点不准确，一个通用数据结构，用于保存需要重绘的矩形区域列表，并具有智能合并。实际上它目前没有合并。因此，您可以将其视为基本的DirtyList实现，因为它只与dirty（）请求相交，以确保不存在重叠的脏区域。

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

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

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

代码片段。完整代码 online here 。

  public class DirtyList {
 
 / **脏区域（每个区域都是int [4]）。 * / 
 private int [] dirties = new int [10 * 4]; //动态增长
 
 / **脏区域的数量* / 
 private int numdirties = 0; 
 
 ... 
 
 / ** 
 *用于对整个脏东西列表运行新的dirty（）请求的别名
 *（x，y ）表示顶点坐标和（w，h）底部坐标
 * / 
 public final void dirty（int x，int y，int w，int h）{dirty（x，y，w， h，0）; } 
 
 / ** 
 *向脏列表中添加一个新的矩形;如果
 *区域完全落入现有矩形或
 *矩形集合中（即，不扩大脏区域），则返回false 
 * / 
 private void dirty（int x ，int y，int w，int h，int ind）{
 int _n; 
 if（w  return; 
} 
 for（int i = ind; i  _n = 4 * i; 
 //如果（dirties [_n] <0）{
 continue; 
 //无效垃圾标记为x = -1 
; 
} 
 
 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 existing of existing地区
继续; 
} 
 
 if（x <_x）{
 //新区域开始在现有区域的左边
 
 if（y <_y ）{
 //新区域至少与现有区域的左上角重叠
 
 if（w> _w）{
 //新区域重叠现有区域的整个宽度地区
 
 if（h> _h）{
 //新地区包含现有地区
 dirties [_n] = -1; 
继续; 
} // else {
 //新区域包含现有区域的顶部
 dirties [_n + 1] = h; 
继续; 
 
} else {
 //新区域与现有区域左侧重叠
 
 if（h> _h）{
 // new region包含现有区域的左侧
 dirties [_n] = w; 
继续; 
} // else {
 //新区域与现有区域的左上角重叠
 dirty（x，y，w，_y，i + 1）; 
 dirty（x，_y，_x，h，i + 1）; 
 return; 
 
 $ b $}其他{
 //新区域在现有区域的垂直范围内开始
 
 if（w> _w）{
 //新区域与现有区域水平重叠
 
 if（h> _h）{
 //新区域包含现有区域的底部
 dirties [_n + 3] = Ÿ; 
继续; 
} // else {
 // new region overlapped to the left and right of existing region 
 dirty（x，y，_x，h，i + 1）; 
 dirty（_w，y，w，h，i + 1）; 
 return; 
 
} else {
 //新区域在现有区域的水平范围内结束
 
 if（h> _h）{
 // new region与现有区域的左下角重叠
 dirty（x，y，_x，h，i + 1）; 
 dirty（_x，_h，w，h，i + 1）; 
 return; 
} // else {
 //现有区域包含新区域的右部分
 w = _x; 
继续; 
 
 
} else {
 //新区域在现有区域的水平范围内开始
 
 if（y <_y）{
 //新区域在现有区域上方开始
 
 if（w> _w）{
 //新区域至少与现有区域的右上方重叠
 
 if（h> _h）{
 // new region contains the right of existing region 
 dirties [_n + 2] = x; 
继续; 
} // else {
 //新区域与现有区域的右上方重叠
 dirty（x，y，w，_y，i + 1）; 
 dirty（_w，_y，w，h，i + 1）; 
 return; 
 
} else {
 //新区域横向包含在现有区域中
 
 if（h> _h）{
 // new region overlapps到现有区域的上方和下方
 dirty（x，y，w，_y，i + 1）; 
 dirty（x，_h，w，h，i + 1）; 
 return; 
} // else {
 //现有区域包含新区域的底部
 h = _y; 
继续; 
} 
} else {
 //新区域在现有区域内开始
 
 if（w> _w）{
 // new region overlapps at （h> _h）{
 //新区域与现有区域的右下角重叠
 dirty（x，_h，w） ，h，i + 1）; 
 dirty（_w，y，w，_h，i + 1）; 
 return; 
} // else {
 //现有区域包含新区域的左侧部分
 x = _w; 
继续; 
} else {
 //新区域被水平地包含在现有区域中
 
 if（h> _h）{
 //现有区域包含新的顶部部分地区
y = _h; 
继续; 
} // else {
 //新区域包含在现有区域
 return; 
} 
} 
} 
} 
 
 //区域有效;存储它以呈现
 _n = numdirties * 4; 
 size（_n）; 
 dirties [_n] = x; 
 dirties [_n + 1] = y; 
 dirties [_n + 2] = w; 
 dirties [_n + 3] = h; 
 numdirties ++; 
} 
 
 ... 
} 
  

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

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.

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.

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屋！