Грязные прямоугольники
Где можно найти ссылки на реализацию алгоритма вычисления "грязного прямоугольника" для минимизации обновлений кадрового буфера? Модель дисплея, которая разрешает произвольное редактирование и вычисляет минимальный набор "битовых" операций, необходимых для обновления дисплея.
6 ответов
Чтобы построить наименьший прямоугольник, содержащий все области, которые нужно перекрасить:
- Начните с пустой области (возможно, прямоугольник установлен на 0,0,0,0 - то, что вы можете определить как "обновление не требуется")
Для каждой грязной области добавлено:
- Нормализуйте новую область (т.е. убедитесь, что слева меньше правого, сверху меньше нижнего)
- Если грязный прямоугольник в настоящее время пуст, установите его в предоставленную область
- В противном случае установите левую и верхнюю координаты грязного прямоугольника на наименьшую из {грязных, новых}, а правую и нижнюю координаты на наибольшую из {грязных, новых}.
Windows, по крайней мере, поддерживает область обновления об изменениях, о которых она была проинформирована, и о любой перекраске, которую необходимо выполнить из-за того, что окно скрыто и открыто. Регион - это объект, который состоит из множества, возможно, прерывистых прямоугольников, многоугольников и эллипсов. Вы говорите Windows о части экрана, которую нужно перекрасить, вызывая InvalidateRect - для более сложных областей есть также функция InvalidateRgn. Если вы решили выполнить рисование до того, как будет получено следующее сообщение WM_PAINT, и вы хотите исключить его из грязной области, есть функции ValidateRect и ValidateRgn.
Когда вы начинаете рисовать с BeginPaint, вы предоставляете PAINTSTRUCT, который Windows заполняет информацией о том, что нужно рисовать. Один из членов - это самый маленький прямоугольник, содержащий недопустимую область. Вы можете получить сам регион, используя GetUpdateRgn (вы должны вызывать это до BeginPaint, потому что BeginPaint помечает все окно как допустимое), если вы хотите минимизировать рисование, когда есть несколько маленьких недопустимых областей.
Я предположил бы, что, поскольку минимизация рисования была важна на Mac и на X, когда эти среды были изначально написаны, существуют эквивалентные механизмы для поддержки области обновления.
Vexi является эталонной реализацией этого. Класс org.vexi.util.DirtyList (Apache License) и используется как часть производственных систем, то есть тщательно протестирован, и хорошо прокомментирован.
Предостережение: описание класса в настоящее время немного неточно: "Структура данных общего назначения для хранения списка прямоугольных областей, которые необходимо перекрасить, с интеллектуальным объединением". На самом деле это в настоящее время не делает объединение. Поэтому вы можете считать это базовой реализацией DirtyList в том смысле, что она только пересекает запросы dirty(), чтобы убедиться в отсутствии перекрывающихся грязных областей.
Один нюанс этой реализации состоит в том, что вместо использования Rect или другого подобного объекта области, области сохраняются в массиве целых чисел, то есть в блоках по 4 дюйма в одномерном массиве. Это сделано для эффективности времени выполнения, хотя в ретроспективе я не уверен, есть ли в этом много достоинств. (Да, я реализовал это.) Должно быть достаточно просто заменить Rect для используемых блоков массива.
Цель занятия - быть быстрым. С Vexi, грязный может вызываться тысячи раз за кадр, поэтому пересечение грязных областей с грязным запросом должно быть как можно быстрее. Для определения относительного положения двух регионов используется не более четырех числовых сравнений.
Это не совсем оптимально из-за отсутствия объединения. Хотя это гарантирует отсутствие перекрытий между грязными / окрашенными областями, вы можете получить области, которые выстраиваются в линию и могут быть объединены в более крупную область - и, следовательно, уменьшить количество вызовов рисования.
Фрагмент кода. Полный код онлайн здесь.
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++;
}
...
}
Похоже, вам нужен ограничивающий прямоугольник для каждой фигуры, которую вы отображаете на экране. Помните, что ограничивающий прямоугольник многоугольника можно определить как "нижний левый угол" (минимальная точка) и "верхний правый угол" (максимальный пункт). То есть, x-компонент минимальной точки определяется как минимум всех x-компонентов каждой точки в многоугольнике. Используйте ту же методологию для y-компонента (в случае 2D) и максимальной точки ограничительной рамки.
Если для полигона достаточно иметь ограничивающий прямоугольник (он же "грязный прямоугольник"), все готово. Если вам нужен общий составной ограничивающий прямоугольник, применяется тот же алгоритм, за исключением того, что вы можете просто заполнить один прямоугольник минимальными и максимальными точками.
Теперь, если вы делаете все это на Java, вы можете получить свой ограничивающий прямоугольник для Area (который вы можете построить из любого Shape) непосредственно с помощью getBound2D() метод.
Я только недавно написал класс Delphi для вычисления разностных прямоугольников двух изображений, и был весьма удивлен тем, насколько быстро он работал - достаточно быстро, чтобы работать в течение короткого таймера и после сообщений мыши / клавиатуры для записи активности экрана.
Шаг за шагом, как это работает:
Подразделяя изображение на логические 12x12 прямоугольниками.
Перебирая каждый пиксель и, если есть разница, я говорю суб прямоугольнику, к какому пикселю принадлежит, что есть разница в одном из его пикселей и где.
Каждый под-прямоугольник запоминает координаты его самой левой, самой верхней, самой правой и самой нижней разницы.
Как только все различия найдены, я перебираю все суб-прямоугольники, которые имеют различия, и формирую из них большие прямоугольники, если они находятся рядом друг с другом, и использую самые левые, самые верхние, самые правые и нижние большинство различий этих суб-прямоугольников, чтобы сделать фактические различия прямоугольников, которые я использую.
Это, кажется, работает очень хорошо для меня. Если вы еще не внедрили собственное решение, дайте мне знать, и я отправлю вам код, если хотите. Кроме того, на данный момент я новый пользователь Stackru, поэтому, если вы оцените мой ответ, пожалуйста, проголосуйте за него.:)
Какой язык вы используете? В Python Pygame может сделать это для вас. Используйте группу RenderUpdates и некоторые объекты 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, вот что я бы сделал:
- Сделайте класс Sprite, который update(), move() и т. Д. Метод устанавливает "грязный" флаг.
- Сохраняйте прямоугольник для каждого спрайта
- Если ваш API поддерживает обновление списка ссылок, используйте его в списке ссылок, чьи спрайты грязные. В SDL это SDL_UpdateRects.
- Если ваш API не поддерживает обновление списка ссылок (у меня никогда не было возможности использовать что-либо кроме SDL, поэтому я не знаю), проверьте, быстрее ли вызывать функцию blit несколько раз или один раз с большой прямоугольник Я сомневаюсь, что любой API будет быстрее, если использовать один большой прямоугольник, но опять же, я не использовал ничего, кроме SDL.