¿Dónde se pueden encontrar referencias sobre la implementación de un algoritmo para calcular un "rectángulo sucio" para minimizar las actualizaciones del búfer de cuadros? Un modelo de visualización que permite ediciones arbitrarias y calcula el conjunto mínimo de operaciones "bit blit" necesarias para actualizar la pantalla.Rectángulos sucios
para construir el rectángulo más pequeño que contiene todas las áreas que necesitan ser repintados:
Para cada zona sucia añadido:
de Windows, por lo menos, mantiene una región actualización de los cambios que ha sido informada de la misma y cualquier repintado que hay que hacer debido a la ventana que se oculta y revelada. Una región es un objeto que se compone de muchos rectángulos, polígonos y elipses posiblemente discontinuos. Le dice a Windows sobre una parte de la pantalla que necesita ser repintada llamando a InvalidateRect; también hay una función InvalidateRgn para áreas más complicadas. Si elige pintar antes de que llegue el siguiente mensaje WM_PAINT y desea excluirlo del área sucia, existen funciones ValidateRect y ValidateRgn.
Cuando comienza a pintar con BeginPaint, proporciona un PAINTSTRUCT que Windows completa con información sobre lo que debe ser pintado. Uno de los miembros es el rectángulo más pequeño que contiene la región no válida. Puede obtener la región usando GetUpdateRgn (debe llamar esto antes de BeginPaint, porque BeginPaint marca toda la ventana como válida) si desea minimizar el dibujo cuando hay varias áreas pequeñas no válidas.
Supongo que, como minimizar el dibujo era importante en Mac y en X cuando esos entornos se escribieron originalmente, existen mecanismos equivalentes para mantener una región de actualización.
"cuando esos entornos fueron escritos originalmente" - Creo que siempre ha sido, y siempre será importante, ya que el administrador de ventanas es un código de nivel semi-bajo de uso muy común que desea ejecutar lo más rápido posible . – bgw
¿Qué idioma estás usando? En Python, Pygame puede hacer esto por ti. Usa el grupo RenderUpdates y algunos objetos Sprite con atributos de imagen y rect.
Por ejemplo:
#!/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))
Si usted no está usando Python + Pygame, esto es lo que yo haría:
Parece que lo que necesita es un cuadro delimitador para cada forma que está renderizando en la pantalla. Recuerde que un cuadro delimitador de un polígono se puede definir como "inferior izquierdo" (el punto mínimo) y "superior derecho" (el punto máximo). Es decir, el componente x del punto mínimo se define como el mínimo de todos los componentes x de cada punto en un polígono. Use la misma metodología para el componente y (en el caso de 2D) y el punto máximo del cuadro delimitador.
Si es suficiente tener un cuadro delimitador (también conocido como "rectángulo sucio") por polígono, ya está. Si necesita un cuadro delimitador global compuesto, se aplica el mismo algoritmo, excepto que puede completar un cuadro individual con puntos mínimos y máximos.
Ahora, si usted está haciendo todo esto en Java, puede obtener su cuadro delimitador para una Area (que se puede construir a partir de cualquier Shape) directamente usando el getBound2D() method.
Acabo de escribir una clase Delphi para calcular los rectángulos de diferencia de dos imágenes y me sorprendió lo rápido que corría, lo suficientemente rápido para ejecutarse en un temporizador corto y después de los mensajes del mouse/teclado para registrar la actividad de la pantalla.
El paso a paso esencial de la forma en que funciona es por:
sub-dividir la imagen en 12x12 lógica por rectángulos.
Pasando por cada píxel y si hay una diferencia, le digo al sub-rectángulo al que pertenece el píxel que hay una diferencia en uno de sus píxeles y dónde.
Cada sub-rectángulo recuerda las coordenadas de su propia diferencia más a la izquierda, a la más alta, a la derecha y a la inferior.
Una vez que se han encontrado todas las diferencias, recorro todos los rectángulos que tienen diferencias y formulo rectángulos más grandes si están uno al lado del otro y uso el más a la izquierda, el más alto, a la derecha -la mayoría y la mayoría de las diferencias de esos sub-rectángulos para hacer rectángulos de diferencia real que uso.
Esto parece funcionar bastante bien para mí. Si aún no ha implementado su propia solución, hágamelo saber y le enviaré mi código si lo desea. También a partir de ahora, soy un nuevo usuario de StackOverflow, así que si aprecia mi respuesta, por favor vote por ella. :)
Vexi es una implementación de referencia de esto. La clase es org.vexi.util.DirtyList (Licencia de Apache) y se usa como parte de los sistemas de producción, es decir, se ha probado minuciosamente y está bien comentada.
Una advertencia, la descripción actual de la clase es un poco inexacta, "Una estructura de datos de propósito general para contener una lista de regiones rectangulares que necesitan ser repintadas, con coalescencia inteligente." En realidad, actualmente no se fusiona.Por lo tanto, puede considerar esto como una implementación básica de DirtyList, ya que solo intercepta las solicitudes dirty() para asegurarse de que no haya regiones sucias superpuestas.
El único matiz de esta implementación es que, en lugar de utilizar Rect u otro objeto de región similar, las regiones se almacenan en una matriz de entradas, es decir, en bloques de 4 ints en una matriz de 1 dimensión. Esto se hace para la eficiencia del tiempo de ejecución, aunque en retrospectiva no estoy seguro de si esto tiene mucho mérito. (Sí, lo implementé). Debería ser lo suficientemente simple para sustituir Rect por los bloques de matriz en uso.
El objetivo de la clase es rápido. Con Vexi, el sucio puede llamarse miles de veces por cuadro, por lo que las intersecciones de las regiones sucias con la solicitud sucia deben ser lo más rápidas posible. No se usan más de 4 comparaciones numéricas para determinar la posición relativa de dos regiones.
No es del todo óptimo debido a la falta de fusión. Si bien no asegura superposiciones entre regiones sucias/pintadas, puede terminar con regiones que se alinean y podrían fusionarse en una región más grande, y por lo tanto, reduciendo el número de llamadas de pintura.
Fragmento de código. Código completo 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++;
}
...
}
Una aclaración del idioma, la plataforma y el caso de uso permitiría responder a esta pregunta de una manera más útil. – Will
La etiqueta del cuadro delimitador puede ayudar. –