Una Duda Sobre Dirty Rectangles

[CoLSoN2]

 La idea que tengo de cómo se implementa todo este tinglado es:

1º - Obtener los rects de todos los sprites que han cambiado / se han añadido o quitado (viejo y nuevo).
2º - Procesar todos los rects para cubrir el mismo área con la mínima cantidad de rects.
3º - Blitear todos los sprites clipeándolos contra los rects calculados en el paso 2º.

El problema lo tengo en el paso 2º, ya que me gustaría hacerlo de la forma más óptima posible. ¿Alguien ha implementado algo así? ¿Es tan simple como recorrerlos todos e ir "partiéndolos" mediante uniones e intersecciones? Es que esto me parece que será bastante lento cuando haya bastantes sprites.

IMAGEN

Aquí podeis ver a lo que me refiero en partir dos rects que se solapan de forma óptima. Así nunca se redibujaría una zona dos veces. Aunque no se si, en caso de que un Sprite grande que deba blitearse en 3 o 4 veces (cada uno una parte del mismo) debido a estos rects, bajaría mucho el rendimiento respecto a blitearlo de golpe (siempre hacerlo todo en memoria de sistema y actualizar al final la VRAM).

[Pogacha]

 El dirty rectangles no clipea los sprites, sino que la idea es actualizar solo las zonas del front-buffer donde hallan cambios.

Lo que se solia usar era un span-buffer:

struct Span {
 int x1, x2;
 Span* siguiente;
};

Span * Primer_Span[Alto_De_La_Pantalla];

Luego ordenas los spans de cada linea y realizas las uniones por linea de la pantalla, para enmascarar el bliteado, pero de todas formas no le veo sentido utiliar dirty rectangles si hay muchos sprites.

En el backbuffer no se llama dirty rectangles sino que oclusion-rectangles y solo sirbe si tienes tambien la info de cada sprite

struct Sprite {
 int x, y;
 Texel * Dibujo;
 Span * Mascara [y];
}

Donde creas un juego de spans en el backbuffer pero solo te sirve tambien para ganar velocidad en el solapamiento de los sprites.

Ambas tecnicas mejoran drasticamente si en ves de ordenarlos usas un s-heap-buffer donde usas un heap para sacar ordenados los span de la parva.

Estas tecnicas son complicadas para un juego 2d, se usaban en el quake 1 y motores de tiempo critico, pero han sido descartadas con la aceleracion por hardware.

En conclusion, si usas software y quieres acelerarlo, donde halla pocos cambios en pantalla:

1 - Separas en zonas de interseccion vertical de rectangulos

ZonaVertical
{
 int y0, y1;
 Span *Lista_De_Span; // span que seran comunes entre y0 y y1
};

2 - Unes los span de cada zona

3 - Bliteas del back-buffer al front usando las zonasverticales y sus spans.

Mejor que esto imposible!!.

De todos modos (ojo) solo te dara resultados si hay pocos cambios en pantalla: ejemplo: pacman, pong: arkanoid; nunca algo con fondo animado o demasiados sprites.

Saludos.

[Helius]

 Exactamente, si hay muchos sprites te va a costar más trabajo toda la historia de dirty rectangles que actualizar entera la pantalla. Sólo en el caso de que estés en un ambiente muy restrictivo (como la gba o móviles) alomejor te interesa, pero yo creo que ni con esas...

[CoLSoN2]

 A parte de que es posible que no tenga muchos sprites, lo que quiero es poder evitar en la medida de lo posible blitear esos sprites. Si tengo un fondo estático y alomejor 20 o 30 sprites animados, unos móviles y otros no,  que en total igual ocupan un 50% de la pantalla, pues me ahorro mucho. Siempre teniendo en cuenta que quiero que el target PC sea lo mínimo posible (400-500 MHz sería lo suyísimo), evidentemente en un 2.4ghz podría pasar de todo esto.

P.D.: Pogacha apenas me he enterado de nada XD ¿qué es un span?

[Pogacha]

 La estructura span =

struct Span {
int y;
int x_Comienzo, int x_Fin;
};

El span es un fragmento horizontal de la pantalla.
Saludos.