Lucia Barron Graficacion: 2.1 Trazo de líneas rectas y 2.2 Representación y trazo de polígonos

DDA

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el calculo ya sea de Dy o Dx por medio de las ecuaciones:

(4) Dy = m Dx

(5) Dx = Dy / m

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.

Tomemos una línea con pendiente positiva, si la pendiente | m | £ 1, se hace el muestreo en x en intervalos unitarios (Dx = 1 y Dy = m dado que m = Dy / Dx) y se calcula cada valor sucesivo de y como:

(6) yk+1 = yk+ m

El subíndice toma valores enteros a partir de 1 y aumenta a razón de 1 hasta alcanzar el valor final.

Ya que m puede ser cualquier numero real entre 0 y 1, los valores calculados de y deben redondearse al entero mas cercano. Para líneas con una pendiente | m | > 1, se revierten las funciones de x y y, o sea, se realiza un muestreo de y en intervalos unitarios (Dy = 1 y Dx = 1/m dado que m = Dy / Dx) y se calcula cada valor sucesivo de x como:

(7) xk+1 = xk+ 1/m

Las ecuaciones (6) y (7) se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al derecho.

Si este procesamiento se revierte, entonces Dx o Dy serian -1, y yk+1 = yk - m o xk+1 = xk - 1/m

Algoritmo de Bresenham para trazar líneas

Un algoritmo preciso y efectivo para la generación de líneas de rastreo, desarrollado por Bresenham (1965), convierte mediante rastreo las líneas utilizando solo cálculos incrementales con enteros que se pueden adaptar para desplegar también curvas.

El algoritmo busca cual de dos pixeles es el que esta mas cerca según la trayectoria de la línea.

Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1.

Las posiciones de pixel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.

Si se inicia desde el extremo izquierdo (x0,y0) de una línea determinada, se pasa a cada columna sucesiva y se traza el pixel cuyo valor de y se aproxima mas a la trayectoria de la línea de rastreo.

Si suponemos que se debe desplegar el pixel en (xk,yk), a continuación se necesita decidir que pixel se debe desplegar en la columna xk+1.

Las alternativas son los pixeles (xk+1,yk), y (xk+1,yk+1).

Al realizar el muestreo en la posición xk+1 designamos la separación de pixeles verticales de la trayectoria de la línea matemática como d1 y d2.

La coordenada de y en la línea matemática en la posición de la columna de pixel xk+1 se calcula como:

(10) y = m (xk + 1) + b

Entonces

d1 = y - yk = m (xk + 1) + b – yk y d2 = (yk + 1) - y = yk + 1 - m (xk + 1) - b

La diferencia entre estas dos separaciones es

(11) d1 - d2 = 2 m (xk + 1) - 2 yk + 2 b - 1

Un parámetro de decisión pk para el paso k en el algoritmo de línea se puede obtener al reordenar la ecuación anterior, de modo que implique solo cálculos de enteros.

Esto se logra sustituyendo m = Dy / Dx donde Dx y Dy son las separaciones horizontal y vertical de las posiciones de los extremos de la línea y al definir:

(12) pk = Dx (d1 - d2) = Dx (2 Dy / Dx (xk + 1) - 2 yk + 2 b - 1)

= 2 Dy xk - 2 Dx yk + 2 Dy + 2 b Dx - Dx

= 2 Dy xk - 2 Dx yk + c

El signo de pk es el mismo que el de d1 - d2 puesto que Dx > 0 en el ejemplo.

El parámetro c es un constante, donde c = 2 Dy + 2 b Dx - Dx, que es independiente del pixel.

Si el pixel yk esta mas cerca de la trayectoria de la línea que el pixel yk + 1 (es decir d1 < d2), entonces el parámetro de decisión pk es negativo.

En ese caso, trazamos el pixel inferior; de otro mode, trazamos el pixel superior.

Los cambios de coordenadas a lo largo de la línea ocurren en pasos unitarios ya sea en la dirección de x o en la de y.

Por tanto, es posible obtener los valores de parámetros de decisión sucesivos al utilizar cálculos incrementales en enteros. En el paso k + 1, el parámetro de decisión se evalúa con base en la ecuación anterior como:

pk+1 = 2 Dy xk+1 - 2 Dx yk+1 + c

Al sustraer la ecuación (12) de la anterior obtenemos

pk+1 - pk = 2 Dy (xk+1 - xk) - 2 Dx( yk+1 - yk)

Pero xk+1 = xk + 1, de manera que

(13) pk+1 = pk + 2 Dy - 2 Dx( yk+1 - yk)

donde el termino yk+1 - yk es 0 o 1, dependiendo del signo del parámetro p. Este calculo recurso de los parámetros de decisión se realiza en cada posición entera de x, empezando en el extremo izquierdo de las coordenadas de la línea. El primer parámetro p0 se evalúa a partir de la ecuación (12) en la posición del pixel inicial (x0,y0), sustituyendo

con b = y0 - m x0 y m = Dy / Dx.

p0 = Dx (2 Dy / Dx(x0 + 1) - 2 y0 + 2 (y0 - (Dy / Dx) x0) - 1)

= 2 Dy x0 + 2 Dy - 2 Dx y0 + 2 Dx y0 - 2 Dy x0 - Dx

donde se obtiene la siguiente ecuación:

(14) p0 = 2 Dy - Dx

En resumen, los pasos son:

1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

2. Se carga (x0,y0) en el bufer de estructura, o sea, se traza el primer punto.

3. Se calculan las constantes Dy, Dx, 2Dy, 2Dy-2Dx, y se obtiene el valor inicial para el parámetro de decisión como p0 = 2 Dy - Dx.

4. En cada xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: si pk < 0, el siguiente punto que se debe trazar es (xk+1,yk) y pk +1 = pk + 2 Dy. De otro modo, el siguiente punto en trazarse es (xk+1,yk+1)

y pk +1 = pk + 2 Dy - 2Dx.

5. Se repite el paso 4 otras Dx veces.