Introducción a la

Computación Gráfica (1316)

Algoritmos básicos de gráficos de
barrido para dibujar primitivas
bidimensionales
Capítulo 3 del libro:
Introducción a la Graficación por Computador

Foley – Van Dam – Feiner – Hughes - Phillips

 Esquema General (I)
Ducto de salida

Primitivas de salida
Atributos de salida

Biblioteca Gráfica
Programa de la

Modelo Control de Ventanas

Aplicación

Gráfico CopyPixel
de datos
Control de dispositivo
de entrada
Medidas de disposit.
de entrada

Ducto de entrada
 Esquema General (II)

Memoria
Biblioteca Gráfica

discretización
Primitivas

Módulos de
Atributos
Memoria
Gráfica Display
 Esquema General (III)

Primitivas
Biblioteca Gráfica

Atributos

Controlador

Memoria
Gráfica
Display
Copiado de píxeles a
la memoria gráfica

Copiado de píxeles de
la memoria gráfica

Hardware de pantalla o
hardware gráfico
 Discretización de líneas

Se considerarán solamente líneas de pendiente 0 <= m <= 1

y líneas de un píxel de grosor.
 Discretización de líneas

Algoritmo incremental básico

yi=mxi + B i
y luego pintar el píxel (xi,round(yi))

¿Problemas?
(xi,yi)
¿Es eficiente?

(xi,Round(yi))
 Discretización de líneas

Algoritmo incremental básico

yi=mxi + B i
yi+1=mxi+1 + B =m(xi +x)+ B= yi + mx

Si x=1  yi+1= yi + m (xi+1,Round(yi +m))

(xi,yi)
(xi+1,yi +m)

(xi,Round(yi))
 Discretización de líneas

Algoritmo de línea de punto medio

Aritmética ENTERA

<0

=0
NE
Q >0
M

P=(xp,yp) E
Opciones Opciones
Píxel para Píxel para Píxel
anterior actual siguiente
 Discretización de líneas

Algoritmo de línea de punto medio

La representación explícita de la recta:

y=(dy/dx)·x + B

Se transforma en otra implícita:

F(x,y)= a·x + b·y + c = dy·x – dx·y + B·dx = 0

Donde:
a=dy ; b=-dx ; c= B·dx
 Discretización de líneas

Algoritmo de línea de punto medio

Propiedades de F(x,y)
NE
Q
M
F(x,y)=0 en la línea
F(x,y)>0 en los puntos debajo de la línea E
P=(xp,yp)
F(x,y)<0 en los puntos sobre la línea Opciones Opciones
Píxel
anterior para Píxel para Píxel
actual siguiente

 Aplicamos F al punto M ; d = F(M)=F(xp+1,yp+½)

Si d > 0  se elige el píxel NE

Si d <= 0  se elige el píxel E
 Discretización de líneas

Algoritmo de línea de punto medio

d = a(xp + 1) + b(yp + ½) + c
NE

M
Llamemos dviejo a este d Q

P=(xp,yp) E

Píxel Opciones Opciones

anterior para Píxel para Píxel
actual siguiente

Si se eligió el píxel E, ¿cuál es el valor dnuevo?

dnuevo = a(xp + 2) + b(yp + ½) + c = (a(xp + 1) + b(yp + ½) + c) + a

dnuevo = dviejo+ a = dviejo+ dy = dviejo + E Entero

 Discretización de líneas

Algoritmo de línea de punto medio

dviejo = a(xp + 1) + b(yp + ½) + c NE

Q
M

P=(xp,yp) E

Píxel Opciones Opciones

anterior para Píxel para Píxel
actual siguiente
Si se eligió el píxel NE, ¿cuál es el valor dnuevo?

(
dnuevo = a(xp + 2) + b(yp + 3/2) + c = a(xp + 1) + b(yp+1/2) + c + a+b )
Entero
dnuevo = dviejo + (a+b) = dviejo + (dy-dx) =dviejo +NE
 Discretización de líneas
Repaso: Algoritmo de línea de punto medio
Quiero dibujar el segmento entre (x0,y0) y (xfin,yfin) que tienen
coordenadas enteras => la recta tiene coeficientes enteros.
El primer punto medio está en
F(x0+1,y0+½)=F(x0,y0)+a+b/2= a+b/2

Dibujo (x0,y0)
Defino dnuevo= a + b/2
p=0
Mientras no llegué a xfin
Según el signo de dnuevo
elijo y dibujo (xp+1,yp+1)  M    dnuevo
p=p+1
Fin
 Discretización de líneas

Repaso: Algoritmo de línea de punto medio

El problema es que dinicio= a + b/2, por lo que hay una fracción
inicial que perjudica todos los cálculos posteriores.

¿Solución?: Multiplicar la función F por 2

F(x,y)=(ax + by + c) → 2*F(x,y)=2ax + 2by + 2c
2*F y F mantienen los signos y se anulan en los mismos puntos.

Conclusiones:
Para cada paso, dnuevo se calcula a partir de una suma entera.
El algoritmo se puede generalizar para líneas con pendientes
que no estén entre 0 y 1.
Discretización de
circunferencias
 Discretización de circunferencias
Ecuación del círculo centrado en el origen:
X2 + y2 = R2

Función explícita:
y=±sqrt(R2-x2)

y al discretizar queda:
y=round(±sqrt(R2-x2))

¿Problemas? ¿Es eficiente?

 Discretización de Circunferencias

Problemas en la forma tradicional de

discretización de circunferencias
Precisa utilizar raíz cuadrada y redondeo
Uso de punto flotante
Dibujo de la circunferencia con huecos
 Discretización de Circunferencias

Simetría de 8 lados
 Discretización de Circunferencias

Algoritmo de círculo de punto medio

P=(xp,yp) E

M ME

>0
SE
MSE =0
<0

Píxel Opciones Opciones

anterior para Píxel para Píxel
actual siguiente
 Discretización de Circunferencias

Algoritmo de círculo de punto medio

Se considera solo 45° de un círculo, de x=0 a x=y=R/sqrt(2) .
dviejo = F(xp+1,yp-½)= (xp+1)2 + (yp-½)2 – R2

Si dviejo < 0 se escoge E y luego el punto medio es ME

dnuevo = F(xp+2,yp-½)= (xp+2)2 + (yp-½)2 – R2
dnuevo = dviejo + (2xp + 3)  E = (2xp + 3) Entero

Si dviejo >= 0 se escoge SE y luego el punto medio es MSE

dnuevo = F(xp+2,yp-3/2)= (xp+2)2 + (yp- 3/2)2 – R2 Entero
dnuevo = dviejo + (2xp–2yp+5)  SE = (2xp–2yp+5 )
 Discretización de Circunferencias

Algoritmo de círculo de punto medio

E y SE varían en cada paso (en el caso lineal son ctes.).
Las operaciones para el cálculo de los dnuevo son enteras.
Falta ver cómo comienza el algoritmo.

Si se parte del punto (0,R), con R entero

el siguiente punto medio es (1,R-½), o sea:
F(1,R-½)=1+(R2-R+¼)-R2= 5/4 –R= dviejo
¿Problema?

Solución: cambio de variable h=d - ¼  hviejo = 1-R

Esto funciona porque h comienza y continúa con valores
enteros
 Discretización de Circunferencias

Algoritmo de círculo de punto medio

En lugar de preguntar por d<0 se pregunta por

h<-1/4

Como h se inicia con enteros y luego sigue con

enteros, entonces resulta igual preguntar por
h<0

Si un entero es menor que -1/4, también es

menor que 0.
 Discretización de Circunferencias

Algoritmo de círculo de punto medio

Rellenado de polígonos

Línea de rastreo
 Rellenado de polígonos

Se utiliza el algoritmo del punto Solamente se dibujan los

medio puntos interiores del polígono.
 Rellenado de polígonos

1. Hallar las intersecciones de la línea de rastreo con todas

las aristas del polígono

2. Ordenar las intersecciones aumentando la coordenada x

3. Colocar todos los píxeles entre pares de intersecciones

que se encuentren dentro del polígono, utilizando la
regla de paridad impar:

La paridad es inicialmente par y cada intersección

cambia la paridad; solo se dibuja cuando la paridad
es impar.
 Rellenado de polígonos

Preguntas a responder para realizar el paso 3

Colocar todos los píxeles entre pares de intersecciones que se

encuentren dentro del polígono, utilizando la regla de paridad impar

3.1 Dada una intersección con un valor Xarbitrario y fraccionario, ¿cómo

determinamos cuál de los dos píxeles a cada lado de la intersección
es el interior?
3.2 ¿Cómo tratamos el caso especial de las intersecciones en
coordenadas enteras de los píxeles?
3.3 ¿Cómo tratamos el caso especial del paso 3.2 para vértices
compartidos?
3.4 ¿Cómo tratamos el caso especial del paso 3.2 si los vértices definen
una arista horizontal?
 Rellenado de polígonos

Preguntas a responder para realizar el paso 3

3.1 Dada una intersección con un valor x arbitrario y fraccionario,

¿cómo determinamos cuál de los dos píxeles a cada lado de la
intersección es el interior?

Solución:
Si nos movemos hacia la derecha a una intersección fraccionaria, y
estamos dentro del polígono, redondeamos hacia abajo en la
coordenada x de la intersección (definiendo el píxel interior). Si
estamos fuera, redondeamos hacia arriba la coordenada x
(definiendo también un píxel interior).
 Rellenado de polígonos

Preguntas a responder para realizar el paso 3

3.2 ¿Cómo tratamos el caso especial de las intersecciones en

coordenadas enteras de los píxeles?
Solución:
Si el píxel del extremo izquierdo de un tramo tiene coordenada x
entera, lo definimos como interior. Si el píxel de extremo derecho
tiene coordenada x entera, lo definimos como exterior.
 Rellenado de polígonos

Preguntas a responder para realizar el paso 3

3.3 ¿Cómo tratamos el caso especial del paso 3.2 para vértices
compartidos?
Solución:
En el cálculo de paridad, contamos solo los vértices ymin de las
aristas y no los vértices ymax.
 Rellenado de polígonos

Preguntas a responder para realizar el paso 3

3.4 ¿Cómo tratamos el caso especial del paso 3.2 si los vértices
definen una arista horizontal
Solución:
No se cuentan los vértices de las aristas horizontales.
No son ni ymin ni ymax.
 Rellenado de polígonos

Astillas

Cuando hay polígonos con aristas

tan cercanas que crean una astilla.

Pueden haber líneas de rastreo sin

pintar.

Se puede solucionar si en lugar de

2 valores posibles para el píxel, se
permiten valores de intensidad
que varíen como función de la
distancia entre el centro del píxel y
la primitiva.
 Algoritmo de recorte de líneas de
Cohen-Sutherland

F D

D´ D´
B B
H C
C
E
H´ J A H´
A G´
G´
J´
G
I´
I
 Algoritmo de recorte de líneas de Cohen-Sutherland

Asignación de códigos de región

1001 1000 1010

0001 0000 0010

0101 0100 0110

 Algoritmo de recorte de líneas de
Cohen-Sutherland
F D
1001 1000 1010 E & F = 0001 & 1001 = 0001
D´
B C & D = 0000 & 1000 = 0000
E H
0001 0000 C 0010
A & B = 0000 & 0000 = 0000
A H´ J
G´ G & H = 0100 & 0010 = 0000
G J´
0101 I & J = 0100 & 0010 = 0000
0100 I´ 0110
I

Se asigna un número a cada extremo de un segmento

y se le aplica la operación lógica AND (bit a bit).
Si da  0000  se rechaza la línea trivialmente
 Algoritmo de recorte de líneas de
Cohen-Sutherland
D
1001 1000 1010 Si no se puede rechazar
D´ trivialmente la línea, se la divide
H en 2 segmentos / uno o ambos
0001 0000 C 0010
se puedan descartar.
H´
G´
G
0101 0110
0100

Se divide considerando las aristas que crucen la línea. Eso

se conoce a través de los códigos de los puntos extremos.
El orden de las aristas es arriba, abajo, derecha, izquierda.
 Algoritmo de recorte de líneas de
Cohen-Sutherland
D
C 1000 1010
1001 I Si no se puede rechazar
B
H trivialmente la línea, se la divide
A
en 2 segmentos / uno o ambos
0000 0010
0001 G se puedan descartar.
F
E AD  DB y BA
0101 0110 Ignoramos DB y a B le
0100
asignamos 0000

IE  IH y HE. Ignoramos IH. H  0010

HE  HF y FE. Ignoramos FE. F 0000
HF  HG y GF. Ignoramos HG. G 0000
Recorte de Polígonos
 Recorte de Polígonos

Algoritmo de Sutherland-Hodgman
 Recorte de Polígonos

Algoritmo de Sutherland-Hodgman

• El polígono se compone de una serie de vértices v1, v2, ..., vn

• Las aristas se forman de vi a vi+1 y de vn a v1
• El algoritmo recorta el polígono con respecto a una sola
arista de la ventana por vez.
• El algoritmo recorre el polígono arista por arista. En cada
paso se añaden cero, uno o dos vértices a la lista de salida.
i: primera
• Hay 4 casos posibles a analizar: salida

Interior Exterior Interior Exterior Interior Exterior Interior Exterior

s p s

p: segunda
s s salida
p: salida p
i: salida
(no hay salidas)
 Recorte de Polígonos

Algoritmo de Sutherland-Hodgman
1. La arista está completamente dentro de las fronteras de recorte
 se agrega el vértice p a la lista de salida.
2. Se agrega el punto de intersección i con la frontera se agrega a
la lista de salida.
3. Ambos vértices se hallan fuera de las fronteras, por lo que no
hay salida.
4. El punto de intersección i y el vértice p se añaden a la lista de
salida.
i: primera
salida
Interior Exterior Interior Exterior Interior Exterior Interior Exterior
s p s

p: segunda
s s salida
p: salida p
i: salida
(no hay salidas)
Recorte de Polígonos
 Eliminación de Artefactos de Discretización
(Antialiasing)

• Las aristas a veces sufren el efecto de “serramiento” o

“escalonamiento”. Esto es un efecto del fenómeno de
aliasing.
 ANTIALIASING

Solución 1: Aumento de la resolución

 ANTIALIASING

Solución 2: Muestreo de área no ponderada

5
Píxel
4

1 Línea de (1,1) a (9,4)

0
0 1 2 3 4 5 6 7 8 9 10
La línea se considera como un rectángulo de color que cubre una
porción de la malla.
Los píxeles se los consideran como un embaldosado de azulejos.
Por columna no hay en general un solo píxel pintado.
 ANTIALIASING

Solución 2: Muestreo de área no ponderada

5

0
0 1 2 3 4 5 6 7 8 9 10

Según el porcentaje del píxel cubierto por la línea, es el

porcentaje del color negro.
 ANTIALIASING

Solución 2: Muestreo de área no ponderada

Función de ponderación
de caja W Píxel

Región de superposición Línea deseada

Subvolumen Ws

El cubo tiene volumen = 1

Según el volumen Ws, es la tonalidad de gris del píxel.
 ANTIALIASING

Solución 2: Muestreo de área no ponderada

Áreas iguales, a distinta distancia del centro del píxel, se

consideran de igual forma en área no ponderada, y de
distinta forma en área ponderada
 ANTIALIASING

Solución 3: Muestreo de área ponderada

No ponderada versus ponderada

Área no ponderada: La intensidad del píxel se

define exclusivamente por el área muestreada.

Área ponderada: La intensidad del píxel está en

función de la distancia del área muestreada al centro
del píxel.
 ANTIALIASING

Solución 3: Muestreo de área ponderada

Función de ponderación
de cono W Píxel

Región de superposición Línea deseada

Según el porcentaje del área ponderada del píxel cubierto por

la línea, es el porcentaje del color negro.