2. Primitivas 2D

7/31/2019 2. Primitivas 2D

1/45

TEMA 2: Primitivas 2D


2/45

ndice

1. Algoritmos de Dibujo de Lneas

1. Algoritmo Bsico Incremental (DDA)

2. Algoritmo de Bresenham

3. Propiedades de las Lneas

2. Algoritmos de Dibujo de Crcunferencias1. Algoritmo del Punto Medio

2. Propiedades de las Lneas Curvas

3. Algoritmos de Relleno

1. Relleno de Polgonos por Scan-line2. Relleno por Inundacin

4. Generacin de Caracteres de Texto

5. Tcnicas de Anti-aliasing

1. Super-sampling2. Area Sampling

3. Anti-aliasing de contornos


3/45

Primitivas 2D En los sistemas raster, las imgenes vienen definidas por la intensidad de sus pixels

controladorde vdeo

controlador

grfico

aplicacin


4/45

Primitivas 2D Los objetos presentes en la imagen se componen de primitivas simples (lneas, puntos)

El sistema grfico dibuja estas primitivas transformndolos en pixels Rasterizacin

0xFF

0xFF

0xFF

0x00

0x85

0x00

0xFF

0xFF

Fila i

Memoria

de vdeo

Los mtodos de conversin deben ser lo ms eficientes posible

La primitiva Punto es la ms sencilla:

se coloca la intensidad deseada en la celda de memoria del frame buffer correspondiente

Cuando el haz de electrones pase por esa lnea horizontal (scan-line), emitir al pasar por esaposicin


5/45

Dibujo de lneas rectas Para dibujar lneas rectas, habr que calcular las posiciones intermedias entre los dos

extremos

Este problema no exista en las pantallas vectoriales o plotters

Sin embargo, las posiciones de los pixels son valores enteros, y los puntos obtenidos de

la ecuacin son reales existe un error (aliasing)

A menor resolucin, mayor es el efecto

Es necesario disponer de mtodos para convertir primitivas en pixels de la forma

ms eficiente posible


6/45

Consideraciones para el dibujo de rectas Hay que calcular las coordenadas de los pixels que estn lo ms cerca posible de una

lnea recta ideal, infinitamente delgada, superpuesta sobre la matriz de pixels.

Las consideraciones que un buen algoritmo debe cumplir son:

la secuencia de pixels debe ser lo ms recta posible

las lneas deben dibujarse con el mismo grosor e intensidad independientemente de su inclinacin

las lneas deben dibujarse lo ms rpido posible

cor r ect o incor r ect o


7/45

y = mx + b

El algoritmo ms sencillo

Calcular

Calcular

Para x=x0 hasta x=x1

y = mx + b

Pintar Pixel (x, round(y))

01

01

xx

yy

x

ym

=

=

00 mxyb =

No es muy eficiente

Cada paso requiere una

multiplicacin flotante, una suma y

un redondeo

P0

y0

y1

x0

P1

x1

La ecuacin de una recta es

m es la pendiente

b es el corte con el eje y


8/45

Algoritmo Bsico Incremental (DDA) Podemos eliminar la multiplicacin de la siguiente manera:

Si m>1 falla pues quedan huecos

Sabemos que yi = mxi + b

Entonces yi+1 = mxi+1 + b = yi+1 = yi + m x

Como x=1, llegamos a la frmula final

Cada pixel se calcula en funcin del anterior

No hace falta calcular b

Solucin: 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 frmula final

yi+1 = yi + m

xi+1 = xi + 1/m


9/45

Algoritmo Bsico Incremental (DDA)

Inconvenientes:

Existen errores de

acumulacin El redondeo es muy

lento

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))


10/45

Algoritmo de Bresenham

Slo usa aritmtica entera

Supongamos el caso 0 < m < 1 hay que decidir qu pixel

dibujamos a continuacin, y slo hay dos candidatos!

El algoritmo debe decidir cul 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 lnea real

xk

xk

+1

yk

yk+1

xk+1

yk

yk+1

xk

d1

d2

y = m (xk + 1) + b

d1 = y yk = m (xk+ 1) + b - yk

d2 = (yk + 1 y) = yk + 1 - m (xk+ 1) - b


11/45


La diferencia entre ambas constantes nos ayudar a decidir qu pixel pintar

d1 d2 = 2m (xk + 1) 2yk + 2b 1

Multiplicando por x eliminamos el parmetro m, que no es entero

pk = x (d1 d2) = 2 y xk 2 x yk + C, donde C = 2 y + x (2b 1)

Como x > 0, el signo de pk coincide con el de la diferencia (d1 d2), y por tanto:

Si pk > 0 d1 > d2 hay que pintar el pixel (xk+1, yk+1)

Si pk < 0 d1 < d2 hay que pintar el pixel (xk+1, yk)

xk+1

yk

yk+1

xk

d1

d2

La gran ventaja es que puede calcularse pk+1 a partir del

anterior pk, utilizando solamente aritmtica entera!

pk+1 = = pk + 2 y 2 x (yk+1 yk)

0 1 dependiendo del signo de pk


12/45


Si m > 1, intercambiamos

las variables x e y

Si m < 0, el cambio essimilar

Funcion Bresenham (int x0, y0, x1, y1)

// slo para el caso 0 < m < 1, siendo x0 < x1

Pintar Pixel (x0, y0)

Calcular las constantes A=2 y, B=2 y-2 x

Obtener el valor para p0= 2 y- x

Para cada xksobre la lnea

si pk < 0

Pintar Pixel (xk+1, y

k)

pk+1 = pk + A

si pk> 0


k+1)

pk+1

= pk+ B


13/45

Ejemplo

P0 = (20, 10)

P1 = (30, 18)

2y = 16

2y - 2x = -4

x = 10

y = 8

p0 = 6


14/45

Direccionando el Frame Buffer

Para acceder al pixel (0,0)

Para acceder al pixel (x,y)

Para acceder al pixel (x+1,y)

Para acceder al pixel (x+1,y+1)

Fila 0

FrameBuffer

Fila 1(0,0)

xm axymax

I(0,0) = FB[0]

I(x,y) = FB[0] + y (xmax + 1) + x

I(x+1,y) = I(x,y) + 1

I(x+1, y+1) = I(x,y) + xmax + 1

(0,0)

(1,0)(2,0)

(xmax-1,0)

(0,1)

(0,2)

Si el punto (0,0) fuera la esquina superior izquierda, y la y

creciera hacia abajo, habra que usar I(x, ymax-y) en lugar

de I(x,y)


15/45

Problemas con la intensidad

El grosor de la lnea depende de lapendiente

Sin embargo, ambas usan el mismo

nmero de pixels

Si I es la intensidad de cada pixel, la

intensidad por unidad de longitud de Aes I, pero la de B es I/V2 el ojo lo

nota

Solucin:

A

B

Que la intensidad de los pixels dependa de la pendiente


16/45

Tipos de lnea

Existen varios tipos: continua, discontinua,con puntos

Los procedimientos para dibujar estas lneas

van mostrando secciones contiguas de pixels,

y luego se van saltando otros

Cmo se puede implementar esto?

Las secciones de pixels se especifican mediante una

mscara

Ejemplo: 1111000 se pintan 4 pixels y se saltan 3

Al fijar el nmero de pixels, las longitudes son diferentes

segn la direccin

Solucin:

ajustar el nmero de pixels dependiendo de la pendiente

Otra forma para dibujar lneas discontinuas sera tratar

cada tramo como una lnea individual


17/45

Grosor de lnea

Cmo podemos pintar lneas de grosor mayor que 1?

Solucin: si la pendiente es menor que 1, para cada posicin de x pintamos una seccin

vertical de pixels, tantos como ancho de lnea queramos, por igual a cada lado

Si la pendiente es mayor que 1, se usan secciones horizontales

Hay que tener en cuenta que el ancho de las

lneas horizontales y verticales ser V2 veces

ms grueso que las diagonales


18/45

Problemas en las terminaciones

Existe un problema en los bordes finales de laslneas: son siempre horizontales o verticales!

Tres soluciones diferentes:

Otra forma para dibujar lneas gruesas es pintar el rectngulo relleno

Tambin aparecen problemas al conectar lneas aparecen huecos en las uniones!

Tres soluciones diferentes:

Butt cap Round cap Projected cap

Miter join Round join Bend join


19/45

La ecuacin de un crculo de radio R centrado en (x0, y0) es

(x-xc)2 + (y-yc)

2 = R2

Algoritmo de fuerza bruta:

No es nada eficiente

Cada paso requiere una raz cuadrada

El espaciado entre pixels no es uniforme

Dibujo de circunferencias

(xc,yc)

R

2

0

2

0 )( xxRyy =

Para x=xc-R hasta x=xc+R

Calcular

Pintar Pixel (x, round(y))


20/45

Otra forma

Cmo solucionar lo de los agujeritos?

Pasando a coordenadas polares

x = xc + R cos t

y = yc + R sin t

(xc,yc)

Rt=0

t=/2

t=

t=3/2

El valor del incremento del ngulo t debe ser lo

suficientemente pequeo para evitar los huecos

Podemos reducir clculo aplicando simetras:

12

3 4

Incluso el primer octante es

simtrico al segundo a

travs de la diagonal1

2

Conclusin: dibujando slo el segundo

octante, desde x=0 hasta x=y podemospintar todo el crculo

Problema: se necesitan races

cuadradas y funciones trigonomtricas

demasiado costoso


21/45

Algoritmo del Punto Medio

Hay que determinar el pixel ms cercano a lacircunferencia

Consideremos el centro del crculo en (0,0)

Comenzaremos en el punto (0,R) e iremos desde

x=0 hasta x=y, donde la pendiente va de 0 a -1

Slo pintaremos el primer octante

Sea la funcin:

f(x,y) = x2 + y2 R2

Este test lo ejecutaremos en los puntos medios

entre los pixels que hay que decidir

< 0 (x,y) est dentro

= 0 (x,y) est sobre la circunferencia

> 0 (x,y) est fuera


22/45


Supongamos ya dibujado el pixel (xk, yk)

pk = f (xk + 1, yk ) = (xk + 1)2 + (yk )

2 R2

pk+1 = f (xk+1 + 1, yk+1 ) = (xk+1 + 1)2 + (yk+1 )

2 R2

pk+1 = pk + 2xk+1 + 1 + (y2

k+1y2

k) (yk+1yk)

0 1 dependiendo del signo de pk

Por lo tanto: Si pk < 0 pk+1 = pk + 2xk+1 + 1 hay que pintar el pixel (xk+1, yk)

Si pk > 0 pk+1 = pk + 2xk+1 - 2yk+1 + 1 hay que pintar el pixel (xk+1, yk-1)

Empezamos en el punto (0, R). Cunto vale p0?

p0 = f (1, R-1/2) = = 5/4 R no es entero!

Sin embargo, da igual. Podemos redondearlo, porque todos los incrementos son enteros,

y slo queremos utilizar el signo de pk, y no su valor


23/45


Funcion PuntoMedio (int xc, yc, float R)

Pintar Pixel (0, R)

Calcular p0= 5/4 R // si R es entero, p

0= 1-r

Para cada xk

si pk< 0

Pintar Pixel (xk+1, yk)

pk+1 = pk + 2xk + 3

si pk> 0


k-1)

pk+1 = pk + 2xk 2yk + 5

Determinar por simetra los puntos de los otros 7 octantes

Pintar Pixel (x+xc, y+yc)


24/45

Ejemplo

R = 10 p0 = 9

(x0, y0) = (0, 10)


25/45

Tipos de lneas

Para dibujar lneas discontinuas usaremos mscaras como en las rectas

Al copiar al resto de octantes hay que tener en cuenta la secuencia del interespaciado

Las longitudes varan con la pendiente


26/45

Grosor de lnea

Existen 3 mtodos:

1. Pintando secciones horizontales o verticales segn sea la pendiente mayor o menor que 1

2. Rellenar el espacio entre dos curvas paralelas, separadas por una distancia igual al ancho

que queremos

3. Usar una brocha e irla moviendo a lo largo de la curva1 1 1

1 1 1

1 1 1


27/45

Relleno de primitivas

Dada un rea cerrada, hay que ser capaz de rellenar los pixels interiores con un colordeterminado


28/45

Relleno de primitivas

Existe 2 categoras de mtodos

1. Relleno por scan - line: fila a fila va

trazando lneas de color entre aristas

2. Relleno por inundacin: a partir de un

punto central, se va expandiendorecursivamente hasta alcanzar el borde

del objeto


29/45

Relleno por Scan-Line

Para cada scan-line que cruce el polgono sebusca la interseccinentre la lnea de barrido y

las aristas del polgono

Dichas intersecciones se ordenan y se rellenan a

pares El problema es existen problemas cuando se

intersecta un vrtice

x0 x1 x2 x3

En la scan-line yapareceran 5 aristas

intersectadas!

Cmo lo solucionamos?


30/45

Relleno por Scan-Line

Solucin: contarlo slo una vez

Pero entonces habra problemas en la

scan-line y

Solucin: contarlo slo una vez

Pero entonces habra problemas en la

scan-line y

Cmo distinguir entre ambos casos?

La diferencia de la lnea yes que las

aristas estn al mismo lado de la scan-

line

Cmo detectarlo?

Mirando si los tres vrtices en cuestin

son montonamente crecientes o

decrecientes


31/45

Aceleracin del Scan-Line

En lugar de calcular para cada scan-line las intersecciones contodos las aristas delpolgono, podemos ir aprovechando el clculo en cada scan-line anterior

La pendiente de la arista es

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

Como y = 1 entre cada scan-line:

xk+1 = xk + 1/m

Para acelerar an ms podemos pasar a aritmtica entera:

xk+1 = xk + x / y

Podemos ir incrementando el contador en x unidades en cada scan-line

Cuando el contador supere y, restamos y y hacemos x++


32/45

Algoritmo optimizado para el relleno scan-line

Primero hay que crear una tabla de bordes (TB), para todas las aristas del polgono(exceptuando las horizontales)

Cada arista viene representada por cuatro valores

Coordenada y del punto ms alto

Coordenada x del punto ms bajo

Inversa de la pendiente

Puntero a otra arista en la misma scan-line

Se crea un vector vaco, con tantas posiciones como filas tenga la pantalla, y se coloca

cada arista en la posicin de la scan-line del punto ms bajo

yt xd 1/m


33/45

Algoritmo optimizado para el relleno scan-line

Comenzamos desde abajo, y vamos creandouna lista de bordes activos (LBA), que

contendrn en cada iteracin las aristas

cruzadas por dicha scan-line

Funcion Scanline()

Inicializar LBA vaca y crear TB

Repetir hasta que LBA y TB vacas

Mover de TB a LBA lados con ymin

= y

Ordenar LBA segn x

Rellenar usando pares de x de LBA

Eliminar lados de LBA con y = ymax

Incrementar y a la siguiente scan-line

Actualizar las x en LBA


34/45

Relleno por inundacin

Empieza en un punto interior y pinta hasta encontrar la frontera del objeto

Partimos de un punto inicial (x,y), un color de relleno y un color de frontera

El algoritmo va testeando los pixels vecinos a los ya pintados, viendo si son frontera o no

No slo sirven para polgonos, sino para cualquier rea curva sobre una imagen se usanen los programas de dibujo


35/45

Algoritmo de relleno por inundacin

Hay dos formas de considerar los vecinos : 4 u 8

Dependiendo de qu esquema elijamos, el relleno

ser diferente

Funcion Inundacin(x, y, col1, col2)

color = LeerPixel (x,y)

Si (color!=col1 && color!=col2) entonces

PintaPixel (x,y,col1)

Inundacin (x+1, y, col1, col2);

Inundacin (x-1, y, col1, col2);

Inundacin (x, y+1, col1, col2);

Inundacin (x, y-1, col1, col2);

El algoritmo se presta a un

esquema recursivo muy

simple


36/45

Algoritmo optimizado de relleno por inundacin

El algoritmo anterior necesita mucha memoria, y siel rea a rellenar es muy grande se desborda la pila

Cmo podemos ahorrar memoria para poder

rellenar reas de cualquier tamao?

La solucin consiste en no explorar todos los

vecinos de cada pixel, sino slo a lo largo de un

scan-line

Rellenamos el span donde se encuentra el punto

inicial

Adems, guardamos las posiciones iniciales de todos

los spans de las lneas horizontales contiguas al

scan-line


37/45

Generacin de caracteres de texto

Las letras y nmeros pueden dibujarse en muchos estilos y tamaos

Typeface: cada dseo diferente para una familia entera de

caracteres (Courier, Helvetica, Arial)

Existen dos formas de representacin:

Bitmap Fonts (usando una malla rectangular de pixels)

ms simples de definir y dibujar

requieren mucho espacio de almacenamiento, porque cada variacin entamaa o formato requiere un nuevo bitmap

Outline Fonts (usando una lista de segmentos rectos y curvos)

ahorran ms memoria

los diferentes tamaos y formatos se crean fcilmente a partir de laforma original

lleva ms tiempo procesarlas

pueden pintarse huecas o rellenas

Pueden pintarse en cualquier orientacin

T i i li i


38/45

Tcnicas anti-aliasing

Las primitivas construidas con los algoritmos rastertienen una apariencia de escalera, debido a la

discretizacin en pixels

Soluciones hardware:

mayor resolucin de las pantallas

existe un lmite paraque el Frame Buffer mantenga su refresco a 30 Hz

pixels ms pequeos: existe un lmite en la precisin delhaz de electrones

I di it li d


39/45

Imagen digitalizada

S li


40/45

Bresenham en subpixels

Super-sampling

Consiste en incrementar virtualmente la malla de pixels, engaando a Bresenham

Una vez calculada la recta para los subpixels, determinamos el color del pixel real

Cada pixel representa entonces un rea finita de la pantalla, y no un punto infinitesimal

Para dibujar una recta, contamos el nmero de subpixels que estn sobre la lnea

La intensidad del pixel final ser proporcional al contador anterior

Para mscaras 3x3 tendremos 3 posibles intensidades

Bresenham en pixels

100% 33%

66%

33%

66%

Apariencia final

S per sampling


41/45

Super-sampling

Otra versin de super-sampling diferente consiste en considerar que las lneas tienenun grosor de 1 pixel son en realidad un rectngulo

Lo que hacemos entonces es contar los subpixels que caen dentro del rectngulo

Para mscaras 3x3 tendramos 9 intensidades diferentes

Se requiere ms clculo que la versin anterior, pero el resultado es ms exacto

NOTA: Si el fondo de la imagen tiene color,debemos promediar entre ambos colores para

determinar el valor del pixel

Area sampling


42/45

Area-sampling

La intensidad del pixel viene dada por el rea de interseccin entre cada pixel y elobjeto que se va a dibujar

Para estimar el rea sera muy costoso evaluar la integral

Lo que hacemos es testear una malla de puntos interiores al pixel y calcular cuntos

caen dentro del rectngulo mtodo de integracin de Montecarlo

Si el fondo tambin tiene color, promediamos entre ambos como antes

90% de pixels dentro 90% de intensidad

Ejemplo de anti aliasing de lneas


43/45

Ejemplo de anti-aliasing de lneas

sin anti-aliasing con anti-aliasing

Anti aliasing de contornos


44/45

Anti-aliasing de contornos

Cuando el aliasing se produce en un contorno que separa dos zonas de color diferente(aristas de un polgono relleno) aliasing de contornos

La solucin consiste en incorporar las tcnicas anteriores a los algoritmos de scan-line

Area-sampling: Segn el rea de polgono que caiga dentro de cada pixel de la frontera,

determinamos el color final

Super-sampling: Aadimos ms scan-lines en la imagen virtual que le pasamos al algoritmo

de relleno decidimos el color de los pixels frontera en funcin de dnde acabe cada

scan-line

rea-sampling Super-sampling

Ejemplo de anti aliasing de contornos


45/45

Ejemplo de anti-aliasing de contornos

A1

A2

21

21 )()(

AA

amarilloAverdeAcolor

+

+=

color

2. Primitivas 2D

Documents

Transcript of 2. Primitivas 2D