Un algoritmo preciso y efectivo para la generación de líneas de rastreo, desarrollado por Bresenham (1965),
convierte mediante rastreo las líneas utilizando solo cálculos incrementales con enteros que se pueden adaptar para
desplegar también curvas.
El algoritmo busca cual de dos pixeles es el que esta mas cerca según la trayectoria de la línea.
Consideremos el proceso de conversion para líneas con pendiente positiva 0 <
m < 1.
Las posiciones de pixel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de
x en
intervalos unitarios.
Si se inicia desde el extremo izquierdo (
x0,y0) de una línea determinada, se pasa a cada columna sucesiva y se traza
el pixel cuyo valor de
y se aproxima mas a la trayectoria de la línea de rastreo.
Si suponemos que se debe desplegar el pixel en (
xk,yk), a continuación se necesita decidir que pixel se debe
desplegar en la columna
xk+1.
Las alternativas son los pixeles (
xk+1,yk), y (xk+1,yk+1).
Al realizar el muestreo en la posición
xk+1 designamos la separación de pixeles verticales de la trayectoria de la
línea matemática como
d1 y d2.
x
k
y
k
y
i+1
x
k+1
y
d
1
d
2 }}
La coordenada de
y en la línea matemática en la posición de la columna de pixel xk+1 se calcula como
(10)
y = m (xk + 1) + b
Entonces
d
1 = y - yk = m (xk + 1) + b - yk
y
d
2 = (yk + 1) - y = yk + 1 - m (xk + 1) - b
Alfredo Weitzenfeld Gráfica: Línea
4
La diferencia entre estas dos separaciones es
(11)
d1 - d2 = 2 m (xk + 1) - 2 yk + 2 b - 1
Un parámetro de decisión
pk para el paso k en el algoritmo de línea se puede obtener al reordenar la ecuación
anterior, de modo que implique solo cálculos de enteros.
Esto se logra sustituyendo
m = Dy / Dx donde Dx y Dy son las separaciones horizontal y vertical de las posiciones
de los extremos de la línea y al definir:
(12)
pk = Dx (d1 - d2) = Dx (2 Dy / Dx (xk + 1) - 2 yk + 2 b - 1)
= 2
Dy xk - 2 Dx yk + 2 Dy + 2 b Dx - Dx
= 2
Dy xk - 2 Dx yk + c
El signo de
pk es el mismo que el de d1 - d2 puesto que Dx > 0 en el ejemplo.
El parámetro
c es un constante, donde c = 2 Dy + 2 b Dx - Dx, que es independiente del pixel.
Si el pixel
yk esta mas cerca de la trayectoria de la línea que el pixel yk + 1 (es decir d1 < d2), entonces el parámetro
de decisión
pk es negativo.
En ese caso, trazamos el pixel inferior; de otro mode, trazamos el pixel superior.
Los cambios de coordenadas a lo largo de la línea ocurren en pasos unitarios ya sea en la dirección de
x o en la de
y
.
Por tanto, es posible obtener los valores de parámetros de decisión sucesivos al utilizar cálculos incrementales en
enteros.
En el paso
k + 1, el parámetro de decisión se evalúa con base en la ecuación anterior como
p
k
+1 = 2 Dy xk+1 - 2 Dx yk+1 + c
Al sustraer la ecuación (12) de la anterior obtenemos
p
k
+1 - pk = 2 Dy (xk+1 - xk) - 2 Dx( yk+1 - yk)
Pero
xk+1 = xk + 1, de manera que
(13)
pk+1 = pk + 2 Dy - 2 Dx( yk+1 - yk)
donde el termino
yk+1 - yk es 0 o 1, dependiendo del signo del parámetro p.
Este calculo recurso de los parámetros de decisión se realiza en cada posición entera de
x, empezando en el
extremo izquierdo de las coordenadas de la línea.
El primer parámetro
p0 se evalúa a partir de la ecuación (12) en la posición del pixel inicial (x0,y0), sustituyendo
con b =
y0 - m x0 y m = Dy / Dx.
p
0 = Dx (2 Dy / Dx(x0 + 1) - 2 y0 + 2 (y0 - (Dy / Dx) x0) - 1)
= 2
Dy x0 + 2 Dy - 2 Dx y0 + 2 Dx y0 - 2 Dy x0 - Dx
donde se obtiene la siguiente ecuación:
(14)
p0 = 2 Dy - Dx
En resumen, los pasos son:
1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (
x0,y0).
Alfredo Weitzenfeld Gráfica: Línea
5
2. Se carga (
x0,y0) en el bufer de estructura, o sea, se traza el primer punto.
3. Se calculan las constantes
Dy, Dx, 2Dy, 2Dy-2Dx, y se obtiene el valor inicial para el parámetro de decisión
como
p0 = 2 Dy - Dx.
4. En cada
xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: si pk < 0, el siguiente punto
que se debe trazar es (
xk+1,yk) y pk +1 = pk + 2 Dy. De otro modo, el siguiente punto en trazarse es (xk+1,yk+1)
y
pk +1 = pk + 2 Dy - 2Dx.
5. Se repite el paso 4 otras
Dx veces.
Ejemplo
Para ilustrar el algoritmo, utilicemos la línea con extremos (20,10) y (30,18).
Esta línea tiene una pendiente de 0.8, con
D
x = 10, Dy = 8
El parámetro de decisión inicial tiene el valor
p
0 = 2 Dy - Dx = 6
y los incrementos para calcular parámetros de decisión sucesivos son
2
Dy = 16, 2Dy - 2Dx = -4
Trazamos el punto inicial (
x0,y0) = (20,10) y determinamos las posiciones de pixel sucesivos a lo largo de la
trayectoria de la línea a partir del parámetro de decisión como
k p
k
(xk+1,yk+1)
0 6 (21,11)
1 2 (22,12)
2 -2 (23,12)
3 14 (24,13)
4 10 (25,14)
5 6 (26,15)
6 2 (27,16)
7 -2 (28,16)
8 14 (29,17)
9 10 (30,18)
Un trazo de pixeles se genera a lo largo de la trayectoria de esta línea.
En la siguiente rutina, se presenta una implementación del trazo de líneas de Bresenham para pendiente en el
rango 0 < |
m | < 1, con trazo de izquierda a derecha en el caso de m positivo y de derecha a izquierda en el caso de
m
negativo.
void LineBres(Display* display, Window win, GC gc, int x0, int y0, int x1, int y1)
{
int x, y, dx, dy, xend, p, incE, incNE;
dx = abs(x1 - x0);
dy = abs(y1 - y0);
p = 2*dy - dx;
incE = 2*dy;
incNE = 2*(dy-dx);
/* determinar que punto usar para empezar, cual para terminar */
if (x0 > x1) {
x = x1;
y = y1;
xend = x0;
}
else {
x = x0;
y = y0;
xend = x1;
Alfredo Weitzenfeld Gráfica: Línea
6
}
/* se cicla hasta llegar al extremo de la línea */
while (x <= xend)
{
XDrawPoint(display,win,gc,x,y);
x = x + 1;
if (p < 0)
p = p + incE
else {
y = y + 1;
p = p + incNE;
}
}
}
El algoritmo de Bresenham se generaliza para líneas con una pendiente arbitraria al considerar la simetría entre
los diversos octantes y cuadrantes del plano de
xy.
Para una línea con una pendiente
m > 1, intercambiamos las funciones de las direcciones de x y y, o sea, pasamos a
lo largo de
y en pasos unitarios y calculamos los valores sucesivos de x que se aproximan mas a la trayectoria de la
línea.
Asimismo, podemos revisar el programa para trazar pixels iniciando desde cualquier extremo.
Si la posición inicial para una línea con una pendiente positiva es el extremo derecho, tanto
x como y disminuyen
conforme pasamos de derecha a izquierda.
Con el fin de asegurarnos de que los mismos pixeles se tracen sin que importe el extremo en que se comienza, se
seleccionara el pixel superior (o inferior) cuando se pase exactamente en el medio (
d1 = d2).
En el caso de pendientes negativas, los procedimientos son similares excepto que ahora, una coordenada decrece
conforme la otra aumenta.
Por ultimo, es posible manejar los casos especiales por separado.
Las líneas horizontales (
Dy = 0), las líneas verticales (Dx = 0) y las diagonales | Dy | = | Dx | se pueden cargar en
forma directa sin procesarlas mediante el algoritmo para el trazo de líneas.
No hay comentarios:
Publicar un comentario