Algoritmos de Dibujo de Líneas

M.I.A Daniel Alejandro García López

Algoritmo de dibujo de líneas Un segmento de línea recta dentro

de una escena esta definido por las coordenadas de los dos extremos del segmento.

Digitalizar la línea para obtener un conjunto de posiciones enteras discretas

Así una posición de línea calculada como (10.48, 20,51) se convierte en la posición del píxel (10,21)

Ecuaciones de las líneas

Para determinar las posiciones de los píxeles a lo largo del un trayecto de línea recta se utilizan las propiedades geométricas de la línea.

La ecuación punto-pendiente cartesiana

Y=m.x+b (m])pendiente (b) intersección en y

M=(y-y0)/(x-x0) B=y0-m.x0

Para cualquier intervalo horizontal ãx correspondiente a un ãy especificado mediante la formula: ãx=ãy/m

Algoritmo de Análisis diferencial digital Basado en calcular ãy o ãx: las líneas se

muestrean a intervalos unitarios según una de las coordenadas y los correspondientes valores enteros más próximos al trayecto lineal se calculan para la otra coordenada.

Si m<=1 podemos muestrear a intervalos unitarios según el eje de las x(ãx=1) y calculamos los valores sucesivos de y como: yk+1=yk+m

El subíndice k adopta valores enteros comenzando en 0 para el primer punto e incrementándose en una unidad cada vez hasta alcanzar el extremo de la línea

Si m>1.5 invertimos los papeles x e y, es decir muestreamos a intervalos unitarios de y y calculamos los valores de x consecutivos mediante xk+1=xk+(1/m)

en este caso, cada valor de x calculado se redondea a la posición del píxel más cercana en la línea de exploración actual.

Si las líneas deben procesarse desde el extremo situado más a la izquierda hasta el extremo situado más a la derecha utilizamos

Yk+1=yk-m xk+1=xk-(1/m)

Desventajas

Requiere aritmética de punto flotante, la que es mas lenta y costosa.

Es inapropiado para implementar por hardware

El redondeo es una operación real adicional

Las líneas largas pueden verse afectada por errores de redondeo en m.

Algoritmo de Análisis diferencial digital Camina a lo largo del eje x desde x0

hasta x1 Para cada valor xi se calcula Yi y lo

redondea al píxel mas próximo El calculo de Yi+1=Yi +m lo que

equivale a incrementar a X en 1 Sustituyendo las coordenadas en los

extremos Yi=m*xi +B Yi+1=m*(xi +1) +B

Algoritmo de Análisis diferencial digital Simplificando Yi+1 =yi + m

Extensión por simetría

Dy<0 A

Dx<0 B

Abs(Dy)/Abs(Dx)>1 C

Algoritmo de Bresenham

Preciso y eficiente Utiliza sólo cálculos enteros para

determinar los incrementos El algoritmo comprueba un signo de

un parámetro entero cuyo valor es proporcional a la diferencia entre las separaciones verticales de las dos posiciones del píxel con respecto a la trayectoria lineal

Algoritmo de Bresenham 1. Introducir los dos extremos de la línea y

almacenar el extremo izquierdo 2. Configurar el color para la posición del búfer

de la imagen, es decir dibujar el primer punto 3. calcular las constantes ⌂x,⌂y,2⌂y y 2⌂y-2⌂x,

y obtener el valor inicial del parámetro de decisión que será p0=2⌂y-⌂x

4. Para cada xk a lo largo de la línea, comenzando en k=0, realizar la siguiente comprobación. Si pk<0, el siguiente punto que hay que dibujar será (xk +1,yk) y

Pk+1=pk +2⌂y En caso contrario, el siguiente punto

que habrá que dibujar es (xk +1,yk +1) y pk+1=pk +2⌂y -2⌂x

5. Realizar el paso 4, ⌂x -1 veces

Ejemplo

Digitalizar la línea definida por los vértices (20,10) y (30,18)

Pendiente =8/10 ⌂x=10, ⌂y=8 2⌂y=16, 2⌂y-2⌂x=-4

k pk (xk+1, yk+1)

0 6 (21,11)1 2 (22,12)2 -2 (23,12)3 14 (24,13)4 10 (25,14)5 6 (26,15)6 2 (27,16)

Int dx=fabs(xEnd-x0), dy=fabs(yEnd-Y0);

Int p=2*dy –dx Int twoDy=2*dy,

twoDyMinusDx=2*(dy-dx); Int x,y; If(x0>xEnd){

X=xEnd Y=yEnd; xEnd=x0;

}

Else{ X=x0; Y=y0; } setPixel(x,y); While(x<xEnd){▪ X++;▪ If(p<0)▪ P+=twoDy;▪ Else{

Y++; P+=twoDyMinusDx

▪ }▪ setPixel(x,y);

}