2 Muestreo

Muestreo

Trazado de Líneas
Rellenado de polígonos
Antialiasing

© 2002 J.C.Dürsteler - UPF- IUA

Introducción
• Representar figuras => iluminar píxeles
apropiadamente
• Ciertas primitivas son más fáciles de muestrear
que otras
• En una escena pueden haber miles de primitivas
a dibujar => el rendimiento es esencial
• Algunos paquetes gráficos sólo soportan ciertas
primitivas => hay que reducirlotodo a ellas
• Sistemas acelerados por Hardware.

 2002 J.C.Dürsteler

Introducción
• Problema:
– Los dispositivos raster son discretos y los objetos
continuos
– El dispositivo de salida es limitado

• ¿Cómo convertir figuras continuas en su
representación discreta?
• Muestreo o rasterización, filtrado y recortado =>
– Perdida de información
– Transformación de información.

 2002J.C.Dürsteler

Arquitectura
• Memoria de presentación (Frame
buffer) alineada en ‘y’
• Es más costoso multiplicar que
sumar
• Muchos procesadores trabajan
más rápido con aritmética entera
que en coma flotante
• Hay que evitar dibujar dos veces
la misma primitiva o el mismo
píxel. Coherencia.

 2002 J.C.Dürsteler

001010010101001
010010100010100

Muestreo de puntos
• Memoria de representación nxm puntos
• Ladirección d de un píxel de
coordenadas enteras (x, y) es

d = x + m·y
• Un punto matemático no tiene área Un
píxel si
• Los puntos son reales; los píxeles
enteros
• Representar píxeles requiere realizar al
menos una traslación un escalado y un
redondeo...

 2002 J.C.Dürsteler

0123456……….m
1 0010100 ……...01
2 0100101 ...……00
. ………………….
n 0110111 ...……00

Muestreo de líneas
• Objetivo: encontrarlos píxeles
más próximos a la trayectoria de
la recta
• Ptos. de partida (x0, y0) y (x1, y1)

x x1  x0
y  y1  y0

y  y0 y

x  x0 x

y1  y0
y  y0 ( x  x0 ) 
x1  x0
 2002 J.C.Dürsteler

Analizador Diferencial
Digital
DDA
• Otra forma de verlo: resolver la ecuación
diferencial que define la recta

dy
cte
dx

=>

y1  y0 y
 cte
x1  x0 x

• La solución de la aproximación pordiferencias
finitas es

yi 1  yi  y;
y1  y0
yi 1  yi 
x
x1  x0
 2002 J.C.Dürsteler

DDA
• Bajo estas premisas podemos realizar un
algoritmo:
• Normalizamos  x y  y de forma que el mayor de
ambos sea la unidad
• Aplicamos iterativamente hasta llegar al final de
la recta las ecuaciones

yi 1  yi  y
xi 1  xi  x
 2002 J.C.Dürsteler

DDA
•

void DDA (int x1, int y1, int x2, inty2, int
•
color) {

x= x1+sgn(x1)*0.5; /* Redondeo el */

•

float dist, x, y;

•

y= y1+sgn(x1)*0.5 ; /* punto inicial*/

•

float dx, dy;

•

for (i=0; i<=dist; i++){

•

int i=0;

•

if (fabs(x2-x1) >= fabs(y2-y1) )

•
•
•

dist=fabs (x2-x1) ;
else
dist=fabs (y2-y1) ;

•

dx=(x2-x1) /dist;

•

dy=(y2-y1) /dist;

•

punto (floor(x), floor(y), color);

•

x=x+ dx;

•

y=y+ dy;

•
•

}
}
Atención(x1, y1) no igual a (x2, y2)
Truncado de enteros como floor
Sgn función signo

 2002 J.C.Dürsteler

DDA
• Problemas
– División => Números reales
– Redondeo => Números reales

• Operaciones costosas computacionalmente y en
coma flotante
• Interesa obtener un algoritmo rápido y eficiente
– Números enteros exclusivamente
– Sólo sumas, restas y asignaciones

 2002 J.C.Dürsteler

Algoritmo deBresenham
• También llamado del punto medio
• A partir de un punto inicial comparamos si la
recta pasa por encima o por debajo del punto
medio en el paso i+1
• Entonces decidimos a que píxel pasamos
• Condicionantes
– x0=0, y0=0
– Suponemos que la pendiente está entre 0 y 1
– Los demás casos se resuelven por reflexión
respecto al eje apropiado

y  y
y  y0 ( x  x0 )  1 0
x1  x0

 2002J.C.Dürsteler

y  y
y x  1 0
x1  x0

Algoritmo de
Bresenham
• Recordemos

y1  y0
y  y0 ( x  x0 ) 
x1  x0
• En las condiciones anteriores
• x0=0, y0=0

y1  y0
y x 
x1  x0
 2002 J.C.Dürsteler

Algoritmo de
Bresenham
• Algoritmo incremental a
partir de un pixel anterior
• Estrategia: Comparar QS y QD
para ver cual es el pixel mas
cercano

y ( x  1) ( x  1)

y
x

( x  1) y
x
( x  1)...