1 Graficación IA7200-T Algoritmos Clásicos

2 Una Línea Ideal Solo podemos lograr una aproximaciónIluminar pixeles tan cerca a la línea ideal como sea posible Pixel e {0,1} Graficación

3 Linea Ideal Recta y continua Se debe interpolar Debe ser eficienteSolo es posible a 0 y 45o Se debe interpolar Debe ser eficiente Se requiere dibujar muchas!!! Graficación

4 Linea Simple Basada en la ecuación: y = mx + b Solución:incrementa x, resuelve para y Se require aritmética de Punto Flotante Graficación

5 Funciona? Sí, para líneas con m<=1.Si m>1, la línea se hace muy discontinua. Se requiere mas de 1 pixel por columna Solución? - simetría. Graficación

6 Modificar algoritmo por octanteo incrementar en x si dy Graficación

7 Algoritmo DDA Inicio - Fin - DDA = Digital Differential AnalyserDifferencias finitas Tratar la linea como una ecuación paramétrica en t : Inicio - Fin - Important algorithm. Graficación

8 Algoritmo DDA Empezar en t = 0 En cada paso, incrementar t en dtElegir un valor para dt Asegurar que se nos pasan pixeles: Implica y dt = maximum(dx, dy) Graficación

9 Algoritmo DDA line(int x1, int y1, int x2, int y2) { float x,y;int dx = x2-x1, dy = y2-y1; int n = max(abs(dx),abs(dy)); float dt = n, dxdt = dx/dt, dydt = dy/dt; x = x1; y = y1; while( n-- ) { point(round(x),round(y)); x += dxdt; y += dydt; } n – rango de t. Graficación

10 Algoritmo DDA Aun se necesitan muchas operaciones de PF.2 ‘round’s y 2 adds por pixel. Hay una manera más simple? Podemos usar solo aritmética entera? Mas fácil de implementar en hardware Graficación

11 Observación en Líneas while( n-- ) { draw(x,y); move right;if( below line ) move up; } Graficación

12 Arriba o Debajo de la Línea?Test para pixel Escribir la línea en forma implícita: F<0 para puntos arriba de la línea, F>0 para puntos debajo. Graficación

13 Testing for the side of a line.Need to find coefficients a,b,c. Recall explicit, slope-intercept form : So: Graficación

14 Variable de Decisión Se llama variable de decisión Evaluar F ent M NEVery important. M E Pixel anterior (xp,yp) Posible pixel actual Posibles pixeles siguientes Graficación

15 Variable de Decisión Si se elige E: Recuerden:Evaluatar d para el siguiente pixel. Depende si se elige E o NE: Si se elige E: Recuerden: NE M E Entonces: Pixel Previos (xp,yp) Posible Pixel Siguiente Posible Pixel Actual Graficación

16 Variable de Decisión Si se elige NE: So : M NE E Pixel Previos (xp,yp)Posible Pixel Siguiente Posible Pixel Actual Graficación

17 Resumen del Algoritmo de Punto MedioElegir entre 2 pixelse en cada iteración, dependiendo del signo de la var. de decisión Atualizar la variable de decisión dependiendo de que pixel es elegido Comenzar en (x1,y1) Calcular en valor inicial de d Graficación

18 Valor Inicial de d Inicioo: (x1,y1)Pero (x1,y1) es un punto en la línea, F(x1,y1) =0 Multiplicar por 2 para remover la fracción  no afecta el signo Graficación

19 Algoritmo de Bresenhamvoid MidpointLine(int x1,y1,x2,y2) { int dx=x2-x1; int dy=y2-y1; int d=2*dy-dx; int increE=2*dy; int incrNE=2*(dy-dx); x=x1; y=y1; WritePixel(x,y); while (x < x2) { if (d<= 0) { d+=incrE; x++ } else { d+=incrNE; x++; y++; } WritePixel(x,y); Graficación

20 Bresenham no fue el final!Algoritmo doble de Xiaolin Wu: El programa de dibujado es un autómata (máquina de estados finitos). i.e. Checar los siguientes dos pixeles de la línea. Solo existen un número finito (pequeño) de posibilidades. El algoritmo doble explota simetría dibujando simultáneamente de ambos extremos hacia el centro. Graficación

21 Algoritmo Doble Las posiciones posibles de los dos pixeles siguientes dependen de la pendiente – pixel actual en azul: 0<=m<=½ ½<=m<=1 1<=m<=2 m>2 Graficación

22 Círculos Podemos usar Bresenham para círculos Usar simetría 8-tuple EPixel Previos Posible Pixel Actual Posible Pixel Siguiente Graficación

23 Círculos La forma Implícita de un círculo es:Las Funciones son ecuaciones lineales en términos de (xp,yp) Llamado punto de evaluación Graficación