Primitivas 2D

TEMA 2: Primitivas 2D

Índice
1. Algoritmos de Dibujo de Líneas
1. 2. 3. Algoritmo Básico Incremental (DDA) Algoritmo de Bresenham Propiedades de las Líneas

2.

Algoritmos de Dibujo de Círcunferencias
1. 2. Algoritmo del Punto Medio Propiedades de las Líneas Curvas

3.

Algoritmos de Relleno
1. 2. Relleno de Polígonos por Scan-line Relleno por Inundación

4. 5.

Generación deCaracteres de Texto Técnicas de Anti-aliasing
1. 2. 3. Super-sampling Area Sampling Anti-aliasing de contornos

Primitivas 2D
• En los sistemas raster, las imágenes vienen definidas por la intensidad de sus pixels

aplicación

controlador gráfico

controlador de vídeo

Primitivas 2D
• • Los objetos presentes en la imagen se componen de primitivas simples (líneas, puntos) El sistemagráfico dibuja estas primitivas transformándolos en pixels Rasterización

Fila i

0xFF 0xFF 0xFF 0x00 0x85 0x00 0xFF 0xFF

Memoria de vídeo

• •

Los métodos de conversión deben ser lo más eficientes posible La primitiva “Punto” es la más sencilla:
– – se coloca la intensidad deseada en la celda de memoria del frame buffer correspondiente Cuando el haz de electrones pase por esa líneahorizontal (scan-line), emitirá al pasar por esa posición

Dibujo de líneas rectas
• • • • Para dibujar líneas rectas, habrá que calcular las posiciones intermedias entre los dos extremos Este problema no existía en las pantallas vectoriales o plotters Sin embargo, las posiciones de los pixels son valores enteros, y los puntos obtenidos de la ecuación son reales existe un error (aliasing) Amenor resolución, mayor es el efecto

•

Es necesario disponer de métodos para convertir primitivas en pixels de la forma más eficiente posible

Consideraciones para el dibujo de rectas
• • Hay que calcular las coordenadas de los pixels que estén lo más cerca posible de una línea recta ideal, infinitamente delgada, superpuesta sobre la matriz de pixels. Las consideraciones que un buenalgoritmo debe cumplir son:
– – – la secuencia de pixels debe ser lo más recta posible las líneas deben dibujarse con el mismo grosor e intensidad independientemente de su inclinación las líneas deben dibujarse lo más rápido posible

correcto

incorrecto

El algoritmo más sencillo
La ecuación de una recta es • • m es la pendiente b es el corte con el eje y
y0

y = mx + b
y1

P1

CalcularCalcular

m=

∆y y1 − y 0 = ∆x x1 − x0

P0
x0 x1

b = y 0 − mx0
• • No es muy eficiente Cada paso requiere una multiplicación flotante, una suma y un redondeo

Para x=x0 hasta x=x1 y = mx + b Pintar Pixel (x, round(y))

Algoritmo Básico Incremental (DDA)
• Podemos eliminar la multiplicación de la siguiente manera: Sabemos que yi = mxi + b Entonces yi+1 = mxi+1 + b = … ⇒ yi+1 = yi+ m ∆x • • • Como ∆x=1, llegamos a la fórmula final yi+1 = yi + m

Cada pixel se calcula en función del anterior No hace falta calcular b Si m>1 falla pues quedan huecos Solución: intercambiamos las variables x e y Sabemos que xi = (1/m) (yi – b) . Entonces: xi+1 = (1/m)yi+1 - b/m = … ⇒ xi+1 = xi + ∆y/m Como ∆y=1, llegamos a la fórmula final xi+1 = xi + 1/m

Algoritmo Básico Incremental (DDA)Funcion Linea_DDA (int x0, y0, x1, y1) dx = x1 – x0 dy = y1 – y0 Si abs(dx) > abs(dy) entonces steps = abs(dx) Si no steps = abs(dy) xinc = dx / steps yinc = dy / steps x = x0 y = y0 Pintar Pixel (round(x), round(y)) Para k=1 hasta k=steps x = x + xinc y = y + yinc Pintar Pixel (round(x), round(y)) • Inconvenientes:
– – Existen errores de acumulación El redondeo es muy lento

Algoritmo deBresenham
• • Sólo usa aritmética entera Supongamos el caso 0 < m < 1 hay que decidir qué pixel dibujamos a continuación, y ¡sólo hay dos candidatos! yk+1 yk xk xk+1 • • • El algoritmo debe decidir cuál de los dos pintar Partamos del pixel (xk, yk), y hay que decidir entre el pixel (xk+1, yk) o (xk+1, yk+1) Para ello calculemos la distancia vertical entre el centro de cada pixel y la línea real y...