Algoritmo para gráficos de líneas PDF

Preview

Summary

Download Algoritmo para gráficos de líneas PDF

Description

ALGORITMO PARA GRAFICACIÓN DE LÍNEAS • Un sistema gráfico dibuja primitivas transformándolas en píxeles de una determinada intensidad, que se iluminan cuando durante el barrido de pantalla el haz de electrones realice el escaneado de la línea horizontal que lo contiene, proceso conocido como rasterización. • La primitiva punto es la más simple, comprende una sola celda que se ilumina. • Los algoritmos para desplegar líneas rectas se basan en la ecuación: Y = m.x + b

(1)

• Las posiciones de los píxeles son valores enteros, que tienen una superficie, en tanto que los valores dados por la ecuación son puntos reales. • En las posiciones intermedias existe un cierto error, y será necesario aplicar un método eficiente que convierta las primitivas en píxeles • Para visualizar una recta se deben determinar las coordenadas de los píxeles más cercanos a ella

ALGORITMO DEL PUNTO MEDIO PARA DISCRETIZACIÓN DE LÍNEAS (Bresenham) • Tiene por objeto calcular las coordenadas de los pixeles que se encuentran más próximos a la línea ideal, que serán los que se iluminen. • Las líneas con pendiente en el intervalo [-1,1], inclusive, deben tener iluminados uno o más de un pixel en cada columna y uno por fila, y fuera de ese intervalo han de tener uno o más pixeles en cada fila y uno por columna. • Se considera la pantalla como una malla, por lo que a un pixel le corresponden coordenadas enteras. • Se parte del círculo ennegrecido, y habrá que escoger entre los dos siguientes (círculos huecos).

ALGORITMO DEL PUNTO MEDIO (Bresenham) (II) •

Sea Q, punto de intersección entre línea y la línea de la malla para xp +1

• •

Se calcula la diferencia entre E y NE respecto a Q, eligiendo el pixel con menor distancia a Q Si el punto medio M está encima de la línea, E está más cerca, y viceversa.

•

Método para calcular a qué lado la línea queda M (algoritmo Bresenham)

•

Conviene en este caso la ecuación implícita de la recta : (ax + by + c = 0)

•

Si dx = x1 – x0, ; dy = y1 – y0 , la pendiente m = dy / dx ,

• •

Luego y = (dy / dx)*x + B. Y multiplicando por dx , se tiene En consecuencia: F(x,y) = dy *x - dx*y + B * dx ,

•

a= dy ;

•

Para 0< m < 1, es sencillo comprobar:

•

Si F(x,y) = 0, el punto está en la línea

•

Si F(x,y) > 0, M está debajo de la línea; (EQ-EM)= (+)

•

Si F(x,y) < 0, M está encima de la línea, y (EQ-EM)= (-)

b= - dx ;

c= B * dx

ALGORITMO DEL PUNTO MEDIO (Bresenham) (III) • Calcular F(x,y) en el punto medio (xp +1, yp + ½), y evaluar el signo • Por definición, d = a (xp +1) + b( yp + ½) + c • Si d > 0, se elige el píxel NE, y si es menor de cero el píxel E • Si d = 0, puede elegirse cualquiera, y se elige E por convenio • La siguiente elección dependerá de lo elegido anteriormente (N o NE): • Si se elige E, se incrementa solo en dirección x, por lo que • dnuevo = F(xp + 2, yp + ½) = a (xp +2) + b( yp + ½) + c • danterior = a (xp +1) + b( yp + ½) + c ; operando y restando ambos se tiene: dnuevo = danterior + a • Incremento a usar tras elegir E: ΔE = a = dy •

Si se elige NE, se tiene:

•

dnuevo = F(xp + 2, yp + 3/2) = a (xp +2) + b( yp + 3/2) + c;

•

Restando ambos : dnuevo = danterior + a + b

•

Incremento de “d” cuando se elige NE (ΔNE) = a + b = dy - dx

ALGORITMO DEL PUNTO MEDIO (Bresenham) (IV) Conclusión: •

En cada paso, escoger entre 2 píxeles, dependiendo del signo de la variable en el paso anterior

•

Después, actualizar la variable de decisión, sumando ΔE ó ΔNE al valor anterior, obteniendo dnuevo

•

Primer píxel (x0 , y0), se calcula “d” de forma directa, con el primer punto medio situado en (x0 + 1, y0 + ½):

•

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

•

Como (x0 , y0 ) es un punto en línea, F (x0 , y0 ) = 0, dinicio = a + b/2 = dy - dx /2

y:

•

Si multiplicamos por 2 , eliminamos la fracción sin afectar al símbolo de decisión : dinicio = 2a + b ; dinicio = 2dy - dx

•

Para E, dnuevo = danterior + 2a = danterior + 2dy ;

•

Para NE, dnuevo = danterior +2 (a + b) = danterior + 2dy - 2dx

Recta del 2º octante

Recta del 2º octante

ALGORITMO DEL PUNTO MEDIO (Bresenham) (EJERCICIO)...