Algoritmos De Relleno 2D

Taller de Computación Gráfica

Capítulo II.- Algoritmos Gráficos en 2
Dimensiones.
Un paquete gráfico raster aproxima las primitivas gráficas
matemáticas (ideales), descritas en términos de un plano cartesiano, a
un conjunto de pixeles de una determinada intensidad de gris o color.
Estos pixeles son almacenados como mapas de bits en un buffer de
memoria gráfica.

II.1.- Discretizaciónde líneas
Un algoritmo de discretización de líneas calcula las coordenadas
de los pixeles que están sobre o cerca de una línea ideal infinitamente
delgada sobrepuesta a una trama bidimensional.

Figura II.1. Relación de píxeles con línea “ideal”
En principio nos gustaría que la secuencia de píxeles estuviera lo
más cerca posible de la línea ideal y que además fuera lo más recta
posible.Consideremos por el momento líneas de 1 píxel de grosor que
tengan exactamente un pixel de dos niveles en cada columna (en cada
fila patra líneas de pendiente mayor o igual que ±1).

Para visualizar la geometría supondremos que mostraremos un
pixel como un punto circular centrado en la posición (x, y) de la trama.

Profesor : Javier Vidal Valenzuela

25

Taller de Computación GráficaII.1.1.-

Algoritmo incremental básico
La estrategia más sencilla para discretizar líneas es calcular la

pendiente m como Δy/Δx e incrementar x en 1 a partir del punto más a
la izquierda. Así se calculará :
yi = m * xi + B; ∀ xi
Así se obtendrá pares de puntos (xi, round(yi)) donde round (yi)
= floor (0,5 + yi).
En la práctica esta estrategia podría ilustrarse de la siguiente
forma:Figura II.2. Aplicación de algoritmo incremental básico
Esta estrategia, aunque es sencilla no es muy eficiente ya que
requiere realizar una multiplicación y una suma en punto flotante y
además invocar a la función floor por cada iteración (punto dibujado).
Observemos que
yi+1 = m * xi+1 + B = m * (xi + Δx) + B = yi + m * Δx
y como Δx es 1, entonces
yi+1 = yi + m.
Resumiendo, si xi+1 = xi+ 1, entonces yi+1 = yi + m.
Si |m| > 1, un incremento en x crea un incremento en y mayor
que 1. Por lo tanto, se debe invertir los papeles de x e y, es decir,

Profesor : Javier Vidal Valenzuela

25

Taller de Computación Gráfica
aumentar x en Δx = Δy /m = 1/m y asignarle un incremento unitario a
y.
Otros casos especiales corresponden a la discretización de líneas
con pendiente ∞ y0, los cuales deben tratarse en forma particular,
notar que el primer caso se da cuando Δx es 0 y el segundo cuando Δy
es 0.
El

siguiente

procedimiento

muestra

sólo

el

caso

de

discretización de líneas con pendiente |m| ≤ 1.
procedure linea (x0, y0, x1, y1, valor : integer);
var x : integer;
dx, dy, y, m : real;
begin
dy := y1 - y0;
dx := x1 - x0;
m := dy / dx;
y:= y0;
for x := x0 to x1 do begin
escribirPixel(x, int(floor(y+0,5)),valor);
y := y + m;
end;
end;

Ejercicios 1 :
1) Aplique el algoritmo incremental para obtener los valores de píxeles
en el siguientes caso:

2) Implemente en forma completa el algoritmo incremental para
discretización de líneas.

Profesor : Javier Vidal Valenzuela

25

Taller de Computación Gráfica

II.1.2.-Algoritmo de punto medio
El algoritmo anterior utiliza aritmética de punto flotante, lo que

hace lo hace tener cierta desventaja. Bresenhan desarrollo un algoritmo
que sólo emplea aritmética entera, es decir, que calcula (xi+1, yi+1) a
partir de (xi, yi).
Para ilustrarlo supondremos que la pendiente de la línea está
entre 0 y 1 (las líneas de otras pendientes se pueden obtener porreflexión). Al punto extremo inferior le denominaremos (x0,y0) y al
superior derecho (x1,y1).
Consideremos la situación ilustrada en la siguiente figura, en la
cual, según la formulación de Bresenhan, se calcula la diferencia entre
las distancias E y NE a Q y se usa el signo de la diferencia para
seleccionar la mejor aproximación de la línea al píxel cuya distancia
desde Q sea la menor....