graphics - pro - Rectángulos sucios

titles pack premiere pro templates

Question

¿Dónde se pueden encontrar referencias sobre la implementación de un algoritmo para calcular un "rectángulo sucio" para minimizar las actualizaciones del frame buffer? Un modelo de visualización que permite ediciones arbitrarias y calcula el conjunto mínimo de operaciones "bit blit" necesarias para actualizar la pantalla.

Answer 1

Para construir el rectángulo más pequeño que contiene todas las áreas que necesitan ser repintadas:

• Comience con un área en blanco (quizás un rectángulo establecido en 0,0,0,0 - algo que puede detectar como "no se requiere actualización")

Para cada área sucia agregada:

• Normalice la nueva área (es decir, asegúrese de que la izquierda esté por debajo de la derecha, arriba por debajo de la inferior)
• Si el rectángulo sucio está actualmente vacío, configúralo en el área suministrada
• De lo contrario, establezca las coordenadas izquierda y superior del rectángulo sucio en la más pequeña de {dirty, new}, y las coordenadas derecha e inferior a la más grande de {dirty, new}.

Windows, al menos, mantiene una región de actualización de los cambios que se le han informado, y cualquier repintado que deba realizarse debido a que la ventana se oscurece y se revela. 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 empiezas a pintar con BeginPaint, le proporcionas a 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.

Answer 2

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 no está usando Python + Pygame, esto es lo que haría:

• Haz una clase Sprite que sea update (), move () etc. El método establece un indicador "sucio".
• Mantenga un rect por cada sprite
• Si su API admite actualizar una lista de rects, utilícela en la lista de rectas cuyos sprites están sucios. En SDL, esto es SDL_UpdateRects.
• Si su API no es compatible con la actualización de una lista de rects (nunca he tenido la oportunidad de usar nada además de SDL, así que no lo sé), pruebe para ver si es más rápido llamar a la función blit varias veces o una vez con un gran rect. Dudo que cualquier API sea más rápida usando un rect grande, pero de nuevo, no he usado nada además de SDL.

Answer 3

Parece que lo que necesitas es un cuadro delimitador para cada forma que estás 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, listo. Si necesita un cuadro de límite global compuesto, se aplica el mismo algoritmo, excepto que puede completar un cuadro único con puntos mínimos y máximos.

Ahora, si está haciendo todo esto en Java, puede obtener su cuadro delimitador para un Area (que puede construir desde cualquier Shape ) directamente utilizando el método getBound2D() .

Answer 4

Recientemente escribí 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.

La esencia paso a paso de cómo funciona es por:

1. Subdividiendo la imagen en 12x12 lógico por rectángulos.

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

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

4. 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, el más a la derecha y el inferior la mayoría de las diferencias de esos sub-rectángulos para hacer la diferencia real de rectángulos 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 , así que si aprecia mi respuesta, por favor vote por ella. :)

Answer 5

Mire en las estructuras de datos de árbol en R y árbol cuádruple .

Answer 6

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, completamente probada y bien comentada.

Una advertencia, la descripción actual de la clase es un poco inexacta, "Una estructura de datos de propósito general para mantener una lista de regiones rectangulares que necesitan ser repintadas, con una fusión 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 usar Rect u otro objeto de región similar, las regiones se almacenan en una matriz de ints, 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 ser 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 en línea aquí .

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++;
}
...
}