Graficación 2D

La computación gráfica 2D corresponde al conjunto de técnicas que tienen como objeto la generación de una imagen digital a partir de modelos geométricos bidimensionales. Estas técnicas son principalmente empleadas en interfaces gráficas de usuario y en aplicaciones desarrolladas a partir de tecnologías de impresión y dibujo, como tipografía, cartografía y dibujo técnico, entre otras. El origen de las mismas se remonta a la década de los 50's en la que aparecieron dispositivos con soporte para gráficos vectoriales.

Los gráficos vectoriales y de rasterización conforman las principales categorías de la computación gráfica 2D. Aquellos emplean primitivas geométricas basadas en ecuaciones matemáticas (e.g., puntos, líneas, curvas y polígonos) para representar las imágenes; mientras que en éstos, la imagen se representa mediante una matriz rectangular de píxeles que puede ser desplegable en un dispositivo de salida cualquiera.
Interfaces gráficas
Una interfaz gráfica permite al usuario interactuar gráficamente (de modo visual) con distintos dispositivos electrónicos, como PCs, PDAs, etc. Las interfaces gráficas, en contraste con las textuales, ofrecen elementos gráficos (i.e., indicadores visuales) que sirven para representar las acciones de la aplicación disponibles al usuario. Dichas acciones son usualmente ejecutadas mediante la manipulación directa de los elementos gráficos presentes en la interfaz. Por razones históricas, el dominio de las interfaces gráficas se encuentra restringido al espacio bidimensional.

Debido al advenimiento del software libre, en la última década se ha dado una gran proliferación y desarrollo de paquetes de interfaces gráficas. Entre los más destacados se tienen los siguientes: Qt, Wxwidgets, GTK+, Motif, XForms, FLTK.

2.1 trazo de líneas rectas

Una línea es una sucesión continua de puntos (trazado), como por ejemplo un trazo o un guion. Las líneas suelen utilizarse en la composición artística, se denomina en cambio «raya» a trazos rectos sueltos, que no forman una figura o forma en particular.

En geometría euclidiana, la recta o la línea recta, se extiende en una misma dirección, existe en una sola dimensión y contiene infinitos puntos; está compuesta de infinitos segmentos (el fragmento de línea más corto que une dos puntos). También se describe como la sucesión continua e indefinida de puntos en una sola dimensión, es decir, no posee principio ni fin.

Un algoritmo de discretización de líneas calcula las coordenadas de los pixeles que están sobre o cerca de una línea ideal infinitamente delgada sobrepuesta a una trama bidimensional. 

En principio nos gustaría que la secuencia de píxeles estuviera lo más cerca posible de la línea ideal y que además fuera lo más recta posible. Consideremos por el momento líneas de 1 píxel de grosor que tengan exactamente un pixel de dos niveles en cada columna (en cada fila para líneas de pendiente mayor o igual que ±1).

Para visualizar la geometría supondremos que mostraremos un pixel como un punto circular centrado en la posición (x, y) de la trama.

Algoritmo incremental básico

La estrategia más sencilla para discretizar líneas es calcular la pendiente m como Δy/Δx e incrementar xen 1 a partir del punto más a la izquierda. Así se calculará :

yi= m * xi+ B; ∀xi

Así se obtendrá pares de puntos (xi, round(yi)) donde round(yi) = floor(0,5 + yi). En la práctica esta estrategia podría ilustrarse de la siguiente forma: 

Esta estrategia, aunque es sencilla no es muy eficiente ya que requiere realizar una multiplicación y una suma en punto flotante y además invocar a la función floor por cada iteración (punto dibujado). Observemos que

yi+1= m * xi+1+ B = m * (xi+ Δx) + B = yi + m * Δx

y como Δx es 1, entonces

yi+1= yi + m.

Resumiendo, si xi+1= xi+ 1, entonces yi+1= yi+ m.

Si |m| > 1, un incremento en crea un incremento en y mayor que 1. Por lo tanto, se debe invertir los papeles de x e y, es decir, aumentar x en Δx= Δy/m = 1/m y asignarle un incremento unitario a y.

Otros casos especiales corresponden a la discretización de líneas con pendiente ∞y 0, los cuales deben tratarse en forma particular, notar que el primer caso se da cuando Δxes 0 y el segundo cuando Δy es 0.

ALGORITMO DE PUNTO MEDIO (Bresenhan)

El algoritmo anterior utiliza aritmética de punto flotante, lo que hace lo hace tener cierta desventaja. Bresenhan desarrollo un algoritmo que sólo emplea aritmética entera, es decir, que calcula (x,y) a partir de (x,y).

Para ilustrarlo supondremos que la pendiente de la línea está entre 0 y 1 (las líneas de otras pendientes se pueden obtener por reflexión). Al punto extremo inferior le denominaremos (x,

y) y al superior derecho (x,y).

Consideremos la situación ilustrada en la siguiente figura, en la cual, según la formulación de Bresenhan, se calcula la diferencia entre las distancias E y NE a Q y se usa el signo de la diferencia para seleccionar la mejor aproximación dela línea al píxel cuya distancia desde Q sea la menor. 

En la formulación del algoritmo de punto medio se observa a que lado de la línea se encuentra el punto medio M, es fácil ver que si M está por encima de la línea, el pixel E es el más cercano y si el punto medio M está por debajo de la línea el punto NE será el elegido. Así escomo en el ejemplo el punto elegido será el NE

¿Cómo se calcula qué lado debe quedar el píxel?  Supongamos que representa la línea por

F(x, y) = a*x + b*y + c.

y consideremos nuevamente

Δx = x1- x0

Δy = y1- y0

con esto la ecuación de la línea queda

y = Δy/Δx*x + B

ambas ecuaciones interceptan su pendiente, por lo tanto, podemos escribir

F(x, y) = Δy*x - Δx*y + B*Δx

donde a = Δy; b = -Δx; y, c = B*Δx.

Como nuestro criterio se basa en el valor de la funcion en el punto (Xp+1, Yp +1/2), por definicion:

d= a*(Xp+1)+b*(Yp+1/2)+c
que corresponde a la ecuacion original evaluada en el siguiente punto medio. Si d>0 se elige el pixel NE; si d<o se elige E y si d=o se puede elegir cualquiera, aunque en eeste ultimo caso se debe quesar establecido cual se elegira.

Los valores de M y d para el siguiente punto depende de la eleccion de NE o E.
Si se eleige E,M se incremente una unidad en la direccion x, poir lo tanto:

dnuevo = F(xp+2, yp+1/2) =a*(xp+2) + b*(yp+½) + c

pero:

dviejo=a*(Xp+1)+b*(Yp+½=+c

Al restar dviejo a dnuevo se obtiene la diferencia incremental



dnuevo=dviejo+a

El incremento que se usa después de elegir E se denomina ΔE y su valor es ΔE = a = Δy.

En otras palabras, con solo sumar ΔE a la variable de decision actual podemos obtenre, en forma incremental, el valir de la variable de decision en el siguiente paso, y sin tener qaue calcular F(M)

Si se elige NE, M se incrementa en una unidad, tanto en la direccion x como en la direccion y, y luego
dnuevo=F(Xp+2,Yp+3/2)=a*(Xp+2)+b*(Yp+3/2)+c

Aplicando el procedimiento de resta para obtener la diferencia incremental:
dnuevo = dviejo + a + b 
El incremento que sumamos a d después de elegir NE se llama ΔNE y corresponde a ΔNE = a + b = Δy - Δx.

Resumiendo el algoritmo del pinto medio, en cada paso el metodo escoge entre dos pixeles basándose en el signo de una variable de decisión. Esta variable de decisión se actualiza sumándole ΔE o ΔNE

Como el primer pixel esta en  (X0,Y0= se puede calcular directamenre eligiendo E o NE. El primer punto medio esta en :

 (x0+1, y0+½)
y
F(x0+1,y0+½)= a*(x0+1) + b*(y0+½)+c
= a*x0 + b*y0 + c + a + b/2
=F(x0,y0)+a+b/2

sin embrago,(x0,y0 es un punto de la linea, luego F(x0,y0=0, entonces

dinicial = a + b/2 = Δy - Δx/2. 
Para eliminar la división por 2 se redefine F multiplicandola por 2, lo cual no afecta al signo de la variable de decisión.