| Representación de imágenes en 2D |
|
|
por Rodrigo Cabrera
- Pablo Castro - Rubén Falcón
- David Gonzalez
Rasterización: El término en sí se refiere
a las técnicas usadas para representar imágenes:
transformarlas en mosaicos de píxeles dibujados en diferentes
colores.
Puntos
Rasterizar un punto es muy fácil.
Todo lo que requiere es simplemente actualizar una posición
de memoria con un valor determinado para un color.
Hay que recordar que la primera entrada
en la video RAM se refiere al pixel superior izquierdo de la pantalla,
lo que determina que el sistema de coordenadas va en este caso
con X subiendo hacia la derecha, e Y subiendo hacia abajo :-)
Asumiendo que cada pixel está
representado por un byte, y que las dimensiones de la pantalla
activa son SCREEEN_X_SIZE por SCREEN Y_SIZE , para poner un punto
en (x,y) necesitamos acceder a la posición de memoria y*SCREEN_X_SIZE+x.
Aquí va un poco de código mostrando esto...
unsigned char *ScrBuffer //Buffer de pantalla
void Punto(int X,int Y, unsigned Color)
{
ScrBuffer[Y*SCREEN_X_SIZE+X]=Color;
}
Líneas
La rasterización de una línea
es una parte muy importante de código en cualquier librería
gráfica. También es usada para dibujo de polígonos,
y algunas otras rutinas.
Lo que hay que hacer es asignar un color
específico a todos los puntos en la trayectoria de la línea.
Fácilmente podemos calcular las
coordenadas de todos los puntos pertenecientes a la línea
(xstart,ystart) - (xend,yend).
Repasando un poco de geometría
básica, podemos ver que
dx=xend-xstart
dy=yend-ystart
entonces:
x
dx
x * dy
----- = ----- e y=----------
y
dy
dx
Dado que lo que queremos es asignar todos los puntos en una trayectoria, solamente tendríamos que tomar todos los X en el rango [xstart,xend] y calcular los respectivos valores de Y. Hay, sin embargo, un problema: solamente tenemos, como máximo, (xend-xstart) coordenadas calculadas. Si el rango de Y es mayor que el de X, la trayectoria que calculasemos no sería continua. En este caso, deberíamos calcular las coordenadas al revés, tomando el rango [ystart,yend] y calculando la respectiva X.
Lo que acabamos de explicar es un
algoritmo lógico y fácil de programar, pero no es
usado prácticamente nunca. La razón de esto es la
forma en que se hicieron los cálculos. Se usaron divisiones,
y la división es por lejos la operación más
lenta que realiza cualquier computadora, aún usando coprocesadores
matemáticos
Lo que haremos en cambio, sin usar ninguna
división, será utilizar el algoritmo de Bresenham.
De esta manera podemos encontrar todos los puntos usando algunas
operaciones lógicas y sumas de enteros.
La idea es encontrar el mayor rango entre
[xstart,xend] y [ystart,yend], ir punto por punto y tener una
variable que diga cuándo es tiempo de avanzar en el otro
rango.
Consideremos qué está pasando
en cierto momento durante la rasterización de la línea.
Asumamos que X es el rango mayor(dx>dy) y en esta línea
xstart<xend y ystart<yend:
Aquí, acabamos de dibujar un píxel P en las coordenadas (x,y) y ahora tenemos que decidir hacia dónde vamos, si al píxel L(x+1,y) o al H(x+1,y+1). Los puntos P,H,L en este caso representan centros de píxeles. Dado que la línea tiene que pasar por algún lado en el medio entre H y L, debemos dibujar el píxel cuyo punto está más cerca del punto de intersección I(x+1,real_y). Este píxel puede ser encontrado comparando los segmentos h y l resultados de la intersección. Recordando la dependencia usada en el método de línea anterior, tenemos que:
dy*(x+1)
real_y=-----------
dx
y
dy*(x+1)
h=y+1-real_y => h=y+1- -------------
dx
dy*(x+1)
l=real_y-y => l= ------------- - y
dx
Ahora bien, nosotros estamos interesados en comparar l y h:
dy*(x+1)
l - h = 2* --------------- - 2y-1
dx
Entonces, si l-h>0, significa que
l>h, el punto de intersección L está más
cerca del punto H, entonces H debería ser dibujado, si
l<h el dibujado sería L.
Multipliquemos ambos lados por dx:
dx(l-h)=2dyx+2dy-2dxy-dx
Ahora, como dx está asumido mayor que 0, entondes los signos de (l-h) y dx(l-h) deben ser iguales. Llamemos d a dx(l-h) y encontremos su signo y valor en un lugar Y y el siguiente Y+1:
d = 2dyx - 2dxy +2dy-dx
i
i-1 i-1
d = 2dyx - 2dxy +2dy-dx
i+1
i i
También es posible hallar el valor inicial de d en el primer punto, ya que x==0 e y==0
d =2dy-x
1
Como el signo de d determina hacia cual punto movernos (H o L), vamos a encontrar el valor de d en algún punto i, asumiendo que conocemos su valor en i-1 por cálculos previos:
d - d = 2dyx - 2dxy - 2dyx + 2dxy
i+1 i
i
i i-1
i-1
d - d = 2dy(x - x ) - 2dx(y - y)
i+1 i
i i-1
i i-1
Dependiendo de la decisión tomada en el punto anterior, el valor de d en el próximo punto podría ser:
Si H fue el elegido, porque x - x
=1 e y - y =1
i i-1 i
i-1
d - d = 2dy-2dx
i+1 i
d = d +2dy-2dx
i+1 i
Si, en cambio, el elegido fue L, porque
x - x =1 e y - y =0
i i-1 i
i-1
d - d = 2dy
i+1 i
d = d +2dy
i+1 i
Esto puede parecer un poco complicado,
pero el código para implementarlo ciertamente no lo es.
Lo que tenemos que hacer es encontrar el valor inicial de d y,
dentro del bucle y dependiendo de su signo, añadirle ya
sea (2dy-2dx) o solamente 2dy. Ya que estos valores son constantes,
pueden ser precalculados fuera del bucle.
En la teoría arriba, asumimos
que xstart<xend e ystart<yend. En la vida real, sin embargo,
no podemos garantizar que estas convenciones se cumplan. La manera
de resolver esto es simplemente cambiando los incrementos por
decrementos cuando las suposiciones de arriba no concuerdan con
la realidad.
Debemos también recordar que en
el bucle, cuando el punto elegido es L, el único valor
que se incrementa o decrementa es el asociado al eje con el rango
de línea más grande, mientras que si es elegido
H, tanto X comoY deben ser incrementados o decrementados, ya que
se avanza sobre los dos ejes.
Como puede verse, este algoritmo no involucra ninguna división. Si tiene multiplicación por 2, pero casi todos los compiladores optimizan esto a un SHL. De cualquier forma, si no confiamos en nuestro compilador, podemos hacerlo nosotros mismos...
|
|
