Где можно найти ссылки на реализацию алгоритма вычисления «грязного прямоугольника» для минимизации обновлений буфера кадров? Модель дисплея, которая разрешает произвольные изменения и вычисляет минимальный набор операций «бит-бит», необходимых для обновления дисплея.Dirty Rectangles
Чтобы построить самый маленький прямоугольник, содержащий все области, которые должны быть перекрашены:
Для каждой грязной области добавил:
для Windows, по крайней мере, поддерживает область обновления изменений, что он был информирован и любой перекраски, что должно быть сделано из-за окна будучи затемняется и раскрывается. A регион - это объект, состоящий из множества, возможно, прерывистых прямоугольников, многоугольников и эллипсов. Вы сообщаете Windows о части экрана, которую необходимо перекрасить, вызывая InvalidateRect - для более сложных областей есть функция InvalidateRgn. Если вы решите сделать некоторую живопись до появления следующего сообщения WM_PAINT, и вы хотите исключить это из грязной области, существуют функции ValidateRect и ValidateRgn.
Когда вы начинаете рисовать с помощью BeginPaint, вы поставляете PAINTSTRUCT, что Windows заполняет информацией о том, что нужно раскрасить. Один из элементов - это самый маленький прямоугольник, который содержит недопустимую область. Вы можете получить этот регион с помощью GetUpdateRgn (вы должны вызывать это перед BeginPaint, потому что BeginPaint отмечает все окно как действительное), если вы хотите минимизировать рисование, когда имеется несколько небольших недопустимых областей.
Я бы предположил, что, поскольку минимизация чертежа важна на Mac и X, когда эти среды были первоначально написаны, существуют эквивалентные механизмы для поддержания области обновления.
Какой язык вы используете? В 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, вот что я хотел бы сделать:
Похоже, что вам нужна ограничивающая рамка для каждой фигуры, которую вы визуализируете на экране. Помните, что ограничивающий прямоугольник многоугольника может быть определен как «нижний левый» (минимальная точка) и «верхний правый» (максимальная точка). То есть, х-компонент точки минимума определяется как минимум всех х-компонент каждой точки в многоугольнике. Используйте ту же методологию для y-компонента (в случае 2D) и максимальной точки ограничивающего прямоугольника.
Если вам достаточно иметь ограничительную рамку (она же «грязный прямоугольник») на каждый полигон, все готово. Если вам нужен общий составной ограничивающий прямоугольник, применяется тот же алгоритм, за исключением того, что вы можете просто заполнить один ящик минимальными и максимальными точками.
Теперь, если вы делаете все это в Java, вы можете получить ограничительную рамку для в Area (который можно построить из любого Shape) непосредственно с помощью getBound2D() method.
Я недавно написал класс Delphi для вычисления разностных прямоугольников двух изображений и был очень удивлен тем, как быстро он работал - достаточно быстро, чтобы работать в коротком таймере и после сообщений мыши/клавиатуры для записи активности экрана.
Шаг за шагом сутью, как это работает на:
подразделяя изображение в логическую 12x12 прямоугольников.
Проникновение через каждый пиксель, и если есть разница, то я говорю о суб-прямоугольнике, к которому принадлежит пиксель, что есть разница в одном из его пикселей и где.
Каждый суб-прямоугольник запоминает координаты своей самой левой, самой верхней, самой правой и самой нижней разницы.
После того, как все различия были найдены, я просматриваю все суб-прямоугольники, которые имеют отличия, и формируют из них большие прямоугольники, если они находятся рядом друг с другом и используют самый левый, самый верхний, правый самые и самые нижние различия этих суб-прямоугольников, чтобы использовать фактические разностные прямоугольники, которые я использую.
Это, похоже, работает для меня хорошо. Если вы еще не внедрили свое собственное решение, сообщите мне, и я пришлю вам ваш код, если хотите. Также на данный момент я новый пользователь StackOverflow, поэтому, если вы оцениваете мой ответ, пожалуйста, проголосуйте. :)
Vexi является эталонной реализацией этого. Класс org.vexi.util.DirtyList (Apache License) и используется как часть производственных систем, то есть тщательно протестированных и хорошо комментируется.
Предостережение, в настоящее время описание класса несколько неточно, «Структура данных общего назначения для хранения списка прямоугольных областей, которые необходимо перекрасить, с интеллектуальным объединением». На самом деле в настоящий момент это не происходит.Поэтому вы можете рассматривать эту базовую реализацию DirtyList в том, что она пересекает только грязные() запросы, чтобы убедиться, что нет перекрывающихся грязных областей.
Единственный нюанс этой реализации состоит в том, что вместо использования объекта Rect или другого аналогичного региона регионы сохраняются в массиве из целых чисел, то есть в блоках из 4-х целых чисел в 1-мерном массиве. Это делается для эффективности времени выполнения, хотя в ретроспективе я не уверен, есть ли для этого большая заслуга. (Да, я его реализовал.) Это должно быть достаточно простым, чтобы заменить Rect на используемые блоки массива.
Целью класса является fast. С Vexi, грязные могут называться тысячи раз за кадр, поэтому пересечения грязных регионов с грязным запросом должны быть как можно быстрее. Для определения относительного положения двух регионов используется не более 4 сопоставлений.
Это не совсем оптимально из-за отсутствия коалесценции. Несмотря на то, что он не обеспечивает совпадений между регионами с грязным/окрашенным цветом, вы можете оказаться в регионах, которые выстраиваются в линию и могут быть объединены в более крупный регион, и, следовательно, уменьшают количество вызовов краски.
Фрагмент кода. Полный код 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++;
}
...
}
Прояснение языка, платформы и прецедента позволило бы ответить на этот вопрос более полезным способом. – Will 2008-11-18 14:24:08
Тег ограничивающей рамки может помочь. – 2008-11-28 15:18:17