algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de...
TRANSCRIPT
![Page 1: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/1.jpg)
Algoritmos para dibujo de líneas
Realizado por:
● Natalya Blanco
● Rubén Arévalo
Universidad Simón BolívarComputación gráfica I
Sep – Dic 2011
![Page 2: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/2.jpg)
Contenido
•Líneas
•Algoritmo DDA
•Algoritmo Breseham
•Algoritmo Xiaolin Wu o Antialiasing
![Page 3: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/3.jpg)
Líneas
• La Recta es una sucesión infinita o continua de puntos alineados en una sola dirección.
•
• Es una de las primitivas básicas en Computación Gráfica
• Viene dada por la ecuación Y=mX+b , donde m es la pendiente de la recta y b es el corte con el eje Y.
A
B
Figura 1
![Page 4: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/4.jpg)
Líneas
• Para dibujar la recta hay que hallar todos los puntos medios entre el inicial y el final.
• El problema es que la ubicación de cada pixel se representa con un entero y las posiciones halladas mediante la ecuación son valores reales.
• Por lo tanto, se necesitan formas eficientes de dibujar la recta lo más parecida posible a la realidad, a pesar de las limitaciones que las pantallas de píxeles nos pongan.
![Page 5: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/5.jpg)
Transformar primitivas en pixeles
Las coordenadas de los píxeles deben estar lo más cerca posible de una
línea recta real
Un algoritmo debe cumplir con:
• La secuencia de píxeles debe ser lo más recta que se pueda.
• Las líneas deben tener el mismo grosor e intensidad sin importar el grado de inclinación
• Las líneas deben dibujarse lo más rápido posible
![Page 6: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/6.jpg)
Transformar línea a pixel
Figura 2 – Tomada de www2.dis.ulpgc.es/~ii-fgc/Tema%202%20-%20Primitivas%202D.pdf
![Page 7: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/7.jpg)
Algoritmo Ineficiente
Algoritmo:
Se calcula m (pendiente)Calculo de b (pto de corte en el eje Y) Para x=x0 hasta x=xn
y = mx + bDibujar pixel (x,redondear(y))
Se necesita una multiplicación flotante, una suma y un redondeo por cada paso
![Page 8: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/8.jpg)
Analizador diferencial digital
Algoritmo DDA
Busca determinar los valores enteros correspondientes más próximos a la trayectoria de la línea para la otra coordenada.Para una pendiente positiva, |m| ≤ 1, se realiza el muestreo de x en intervalos y se calcula el valor sucesivo de y con la siguiente ecuación:
Yk+1 = Yk +m
El subíndice k crece con razón 1 hasta alcanzar el valor final, y m toma valores entre 0 y 1 reales, los valores de y calculados deben ser redondeados. Si la pendiente es negativa, se utiliza un caso análogo con la siguiente ecuación:
Xk+1 = Xk + 1/m
![Page 9: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/9.jpg)
Algoritmo DDA
Pseudo Código
Función DDA_Line (int X0, y0, x1, y1)Dx = x1 - x0Dy = y1 – y0Si |Dx| > |Dy| entonces pasos = |Dx|
Si no pasos = |Dy|xinc = Dx / pasosyinc = Dy / pasosx = x0y = y0Dibujar Pixel (redondear(x), redondear(y))Para k=1 hasta k = pasos
x = x + xincy = y + yincDibujar Pixel (redondear(x), redondear(y))
![Page 10: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/10.jpg)
Problemas DDA
• Presenta errores de acumulación
• Redondeo lento
Mejora Separar los incrementos m y 1/m en
parte entera y fraccionaria, para reducir a operaciones de enteros
![Page 11: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/11.jpg)
Código DDA - JAVAvoid Line(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1){
float x, y, xs, ys;int dx, dy, steps;dx = x1 – x0;dy = y1 – y0;x = x0;y = y0;if (abs(dx) > abs(dy))
steps = abs(dx);else
steps = abs(dy);if (steps == 0) {
XdrawPoint(display,win,gc,round(x),round(y));fprintf(stderr,”this line is a point”);Return;
}xs = dx/steps;ys = dy/steps;for (i = 0; i <= steps; i++){
XdrawPoint(display,win,gc,round(x),round(y));x = x + xs;y = y + ys;
}}
Tomado de: Alfredo Weitzenfeld – Gráfica la Línea. Recuperado de http://www.docstoc.com/docs/273281/Graficos-Lineas-Circulos?term=linea-algoritmo-completo-bresenham#
![Page 12: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/12.jpg)
Algoritmo Breseham
Calcula cuál de dos píxeles es el más cercano a la trayectoria de una línea.
El pixel (Xk, Yk) se divide en (Xk+1, Yk) y (Xk+1, Yk+1) y hay que decidir cuál pintar, cualculando la distancia vertical entre el centro de cada pixel y la línea real.
Figura 3 – Tomada de www2.dis.ulpgc.es/~ii-fgc/Tema%202%20-%20Primitivas%202D.pdf
![Page 13: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/13.jpg)
Algoritmo Bresenham
Pseudo Código
Función Bresenham (int X0, y0, x1, y1)// para el caso 0 < m < 1, siendo x0 < x1
Dibujar Pixel (x0, y0)Calculamos: A=2∆yB=2∆y-2∆x
Obtener el valor para p0 = 2∆y-∆x
Para cada Xk sobre la líneasi pk < 0
Dibujar Pixel (xk+1, yk)pk+1 = pk + A
si pk > 0Dibujar Pixel (xk+1, yk+1)pk+1 = pk + B
• Si m > 1: intercambiamos x e y
• Si m < 0: el cambio es similar
![Page 14: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/14.jpg)
Código Bresenham
public void Bresenham(Graphics g,int x0, int y0, in t x1, int y1) int x, y, dx, dy, p, incE, incNE, sx, sy; dx = (x1 - x0); dy = (y1 - y0);/* Se determina el punto para comenzar, y para terminar */ if (dy < 0) {
dy = -dy; Sy = -1;
} else sy = 1;
if (dx < 0) { dx = -dx; Sx = -1;
} else sx = 1;
x = x0; y = y0;
g.drawLine( x0, y0, x0, y0);
![Page 15: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/15.jpg)
Código Bresenham – Cont./* se itera hasta el final de la línea */ if(dx>dy){
p = 2*dy - dx; incE = 2*dy; incNE = 2*(dy-dx); while (x != x1){
x = x + sx; if (p < 0){
p = p + incE; } else { y = y + sy; p = p + incNE;
} g.drawLine( x0, y0, x0, y0); } }else{ p = 2*dx - dy; incE = 2*dx; incNE = 2*(dx-dy); while (y != y1){ y = y + sy; if (p < 0){ p = p + incE; } else { x = x + sx; p = p + incNE; } g.drawLine( x0, y0, x0, y0); }}}
![Page 16: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/16.jpg)
Anti-Aliasing
Aliasing es la apariencia de ”escaleras” o ”escalones” que se forman debido a la discretización de lo píxeles.
Propuesta Hardware:- Mayor resolución- Píxeles más pequeños
Figura 4 – tomada de www.cimat.mx/~cesteves/cursos/cg/pdf/Antialiasing.pdf
![Page 17: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/17.jpg)
Algoritmo Xiaolin Wu
Mejora del algoritmo de Bresenham, para dibujar rectas en dispositivos de gráficos rasterizados de manera que se reduzca el aliasing.
Esta basado en dibujar parejas de píxeles a lo largo del trazado de la línea con diferentes intensidades, en función de la a la recta real.
![Page 18: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/18.jpg)
función plot(x, y, c) es Dibujar el pixel en (x, y) con brillo c (donde 0 ≤ c ≤ 1)
función ipart(x) es Retornar parte entera de x
función redondear(x) es Retornar ipart(x + 0.5)
función fpart(x) es Retorna parte fraccional de x
función rfpart(x) es Retorna 1 - fpart(x)
Pseudo código Xiaolin Wu
![Page 19: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/19.jpg)
Pseudo código (Cont.)
función dibujarLinea(x1,y1,x2,y2) es dx = x2 - x1 dy = y2 - y1 Si abs (dx) < abs (dy) entonces intercambiar x1, y1 intercambiar x2, y2 intercambiar dx, dy Si x2 < x1 intercambiar x1, x2 intercambiar y1, y2 gradiente = dy / dx
xend = redondear (x1) yend = y1 + gradiente * (xend - x1) xgap = rfpart(x1 + 0.5) xpxl1 = xend ypxl1 = ipart(yend) dibujar (xpxl1, ypxl1, rfpart(yend) * xgap) dibujar (xpxl1, ypxl1 + 1, fpart(yend) * xgap) intery = yend + gradiente
![Page 20: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/20.jpg)
Pseudo código – (Cont.)
xend = redondear (x2) yend = y2 + gradiente * (xend - x2) xgap = fpart(x2 + 0.5) xpxl2 = xend ypxl2 = ipart (yend) dibujar (xpxl2, ypxl2, rfpart (yend) * xgap) dibujar (xpxl2, ypxl2 + 1, fpart (yend) * xgap) // ciclo principal for x from xpxl1 + 1 to xpxl2 - 1 do dibujar (x, ipart (intery), rfpart (intery)) dibujar (x, ipart (intery) + 1, fpart (intery)) intery = intery + gradientefin
![Page 21: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/21.jpg)
![Page 22: Algoritmos para dibujo de líneas - ldc.usb.vevtheok/cursos/ci4321/sd11/trabajo1/... · continua de puntos alineados en una sola dirección. ... Un algoritmo debe cumplir con:](https://reader031.vdocumento.com/reader031/viewer/2022022619/5bad644509d3f217678cfea6/html5/thumbnails/22.jpg)
Referencias
• Tema 2 - Primitivas 2D. Recuperado Noviembre 8, 2011 de www2.dis.ulpgc.es/~ii-fgc/Tema%202%20-%20Primitivas%202D.pdf
• Algoritmo DDA Analizador Diferencial Digital. Recuperado Noviembre 8, 2011 de http://maiki69.tripod.com/DDA.htm
• Rosetta Code - Xiaolin Wu's Line Algorithm . Recuperado Noviembre 8, 2011 de http://rosettacode.org/wiki/Xiaolin_Wu%27s_line_algorithm
• Medellín Anaya, Héctor E. Algoritmo basado en la ecuación de la recta. Recuperado Noviembre 8, 2011 de http://galia.fc.uaslp.mx/~medellin/Applets/LineasRectas/Recta.htm
• Algoritmo DDA . Recuperado Noviembre 8, 2011 de http://sites.google.com/site/proyectosroboticos/algoritmo-dda
• Gómez, Francisco (Febrero 16, 2011) - Una breve introducción a Antialiasing. Recuperado Noviembre 8, 2011 de www.cimat.mx/~cesteves/cursos/cg/pdf/Antialiasing.pdf