Algoritmo Incremental básico:
La estrategia más sencilla para discretizar líneas es calcular la pendiente ,n como z e incrementar x en 1 a partir del punto del extremo izquierdo para calcular y, = mx + B de cada x, e intensificar el pixel en (x, round(y,)), donde round(y,) = floor(0.5 + y,). Con este cálculo se obtiene el pixel más cercano, o sea, aquel cuya distancia a la línea verdadera sea menor. Sin embargo, esta estrategia burda no es muy eficiente, ya que cada iteración requiere una multiplicación y una suma de punto flotante (o de fracción binaria), además de invocar afloor. Podemos eliminar la multiplicación al observar que
yi+1 = mxi+1 + B = m(xi+ Δ x) + B = yi + mΔx
y que si x = Δx, entonces yi+1 = yi + m
De esta manera, un cambio unitario en x cambia y por m, que es la pendiente de la línea. Para todos los puntos (xi, yi) en la línea (no los puntos en la versión de trama de la línea), sabemos que si xi+1 = xi + 1, entonces yi+1 = yi + m; es decir, los valores de x y y se definen en función de sus valores anteriores. Esto es lo que define un algoritmo incremental: en cada paso se realizan cálculos incrementales basados en el paso anterior.
Comenzamos el cálculo incremental en (x0, y0), las coordenadas enteras de un punto extremo. Observe que esta técnica incremental evita la necesidad de tratar con la intersección del eje y, es decir, B. Si |m| > 1, un incremento en x crea un incremento en y mayor que 1. Por lo tanto, tenemos que invertir los papeles de x y y asignando un incremento unidad a y y aumentando x en Δx = Δy/m = l/m. La función línea del programa 3.1 implanta la técnica incremental. El punto de partida debe ser el punto extremo de la izquierda. Así mismo, está limitado al caso -1 <=m <=1, pero las otras pendientes pueden acomodarse por simetría. Se omite la revisión de los casos especiales de líneas horizontales, verticales o diagonales.
La función escribir_pixel, que utiliza línea, es una función de bajo nivel proporcionada por el software de la pantalla que coloca un valor en un lienzo para un pixel cuyas coordenadas se especifican como los dos primeros argumentos. Supondremos aquí que únicamente discretizamos en modo de reemplazo; para los otros modos de escritura de SRGP tenemos que usar una función de bajo nivel leer_pixel para leer el pixel en la localidad destino, combinar lógica mente este valor con el del pixel fuente y escribir el resultado en el destino con escribir pixel.
Este algoritmo se conoce como algoritmo analizador diferencial digital (DDA, digital differential analyzer). El DDA es un dispositivo mecánico que resuelve ecuaciones diferenciales usando métodos numéricos: rastrea valores (x, y) sucesivos incrementando simultáneamente x y y en pequeñas cantidades proporcionales a la primera derivada de x y de y. En nuestro caso, el incremento de x es 1 y el incremento de y es dy/dx =m. Como las variables reales tienen precisión limitada, la suma repetida de una m inexacta produce una acumulación de errores y por último una desviación con respecto a un valor round(y0) verdadero; esta situación no ocasionará problemas en la mayoría de las líneas (cortas).
void Linea(int x0, int y0, intx1, int y1, int valor)
{
int x;
float dy, dx, y, m;
dy=y1-y0;
dx=x1-x0;
m=dy/dx,
y=y0;
for(x=x0;x<= x1;x++){
escribirpixel(x,(int)floor(y+0.5,valor);
y+=m;
}
}
Algoritmo de línea de punto medio
Las desventajas de la función línea son que el redondeo de y a un entero requiere tiempo y que las variables y y m deben ser reales o binarias fraccionarias, ya que la pendiente es una fracción. Bresenham desarrolló un algoritmo clásico que resulta atractivo porque sólo emplea aritmética entera con lo cual se evita el empleo de la función round, y permite efectuar incrementalmente el cálculo de (x i+1, yi+1 ), es decir, usando el cálculo efectuado para (x i, yi ). Se puede aplicar una versión de punto flotante de este algoritmo a líneas con coordenadas de puntos extremos con valores arbitrarios de punto flotante. Así mismo, la técnica incremental de Bresenham se puede aplicar también al cálculo entero de círculos, aunque no es fácil de generalizar a cónicas arbitrarias. Por ello usaremos una formulación un poco distinta, la técnica de punto medio, publicada por primera vez por Pitteway y adaptada por Van Aken y otros investigadores. En el caso de líneas y círculos enteros, la formulación de punto medio, como demuestra Van Aken se reduce a la formulación de Bresenham y por ende genera los mismos pixeles. Bresenham demostró que sus algoritmos de líneas y círculos enteros ofrecen las aproximaciones de mejor ajuste a las líneas y los círculos verdaderos, minimizando el error (distancia) a la primitiva verdadera.
Suponemos que la pendiente de la línea está entre 0 y 1. Las demás pendientes se pueden manejar con una reflexión adecuada respecto a los ejes principales. Al punto extremo inferior izquierdo lo llamaremos (x 0, y0) y al superior derecho, (x 1, y1).
Considere la línea que se presenta en la figura 3.6, donde el pixel previa mente seleccionado aparece como un círculo negro y los dos pixeles de los cuales podemos escoger en la etapa siguiente se presentan como círculos huecos. Suponga que acabamos de seleccionar el pixel P en (xp, yp) y ahora tenemos que elegir entre el pixel que está un incremento a la derecha (llamado pixel este, E) el pixel que se halla un incremento hacia la derecha y un incremento hacia arriba (llamado pixel noreste, NE). Sea Q el punto de intersección de la línea que se discretiza y la línea de malla x = xp+ 1. En la formulación de Bresenham se calcula la diferencia entre las distancias verticales de E y NE a Q, y se usa el signo de la diferencia para seleccionar como mejor aproximación de la línea el pixel cuya distancia de Q sea la menor. En la formulación de punto medio se observa a qué lado de la línea se encuentra el punto medio M. Es fácil ver que si el punto medio está por encima de la línea, el pixel E es el más cerca no a la línea; si el punto medio está debajo, el pixel NE es el más cercano. La línea puede pasar entre E y NE o ambos pixeles pueden estar del mismo lado; en cualquier caso, la prueba de punto medio elige el más cercano. Además, el error (la distancia vertical entre el pixel elegido y la línea real) siempre es menor o igual que ½.
El algoritmo escoge NE como el siguiente pixel para la línea presentada en la figura 3.6. Ahora lo que necesitamos es una forma de calcular en qué lado de la línea se encuentra el punto medio. Representemos la línea por medio de una función implícita con coeficientes a, b y c: F(x, y) = ax + by + c = 0 (el coeficiente b de y no está relacionado con la intersección B del eje y en la forma de intersección de pendiente). Si dy = y1 - y0 y dx = x1- x0 la forma de intersección de pendiente se puede escribir como y=dy·x/dx+B por lo tanto, F(x,y) = dy·x— dx·y + B·dx = 0.
Aquí, a = dy, b = -dx y c = B·dx en la forma implícita.
Es sencillo verificar que F(x, y) es cero en la línea, positiva para los puntos debajo de la línea y negativa para los puntos encima de la línea. Para aplicar el criterio del punto medio, sólo tenemos que calcular F(M) = F(xp+1, yp + ½) y evaluar su signo. Como nuestra decisión se basa en el valor de la función en (xp + 1, yp + ½), definimos una variable de decisión d = F(xp + 1, yp + ½). Por definición, d = a·(xp + 1) + b(yp + ½) + c. Si d > 0, elegimos el pixel NE; si d < O, escogemos E; y si d = 0, podemos elegir cualquiera y seleccionamos E.
Después nos preguntamos qué sucede con la ubicación de M y por ende con el valor de d para la siguiente línea de la trama; por supuesto, los dos valores dependen de la elección de E o de NE. Si elegimos E, M se incrementa una vez en la dirección x. Por lo tanto,
dnuevo=F(xp + 2, yp + ½) = a(xp + 2) + b(yp + ½) + c
Pero
dviejo=a(xp + 1) + b(yp + ½) + c
Al restar d de dnuevo para obtener la diferencia incremental, escribimos dnuevo= dviejo+ a.
El incremento que se usa después de elegir E se denomina ΔE; ΔE= a = dy. En otras palabras, con sólo sumar ΔE podemos obtener en forma incremental el valor de la variable de decisión en el siguiente paso a partir del valor en el paso actual, sin tener que calcular F(M) directamente.
Si elegimos NE, M se incrementa una unidad tanto en la dirección x como
en la y. Entonces,
dnuevo=F(xp + 2, yp +3/2) = a(xp + 2) + b(yp + 3/2) + c .
Al restar dviejo a dnuevo para obtener la diferencia incremental, escribimos
dnuevo= dviejo+ a+b.
El incremento que sumamos a d después de elegir NE se llama ΔNE; ΔNE= a +b = dy -dx.
Resumamos la técnica incremental del punto medio. En cada paso, el algoritmo escoge entre dos pixeles con base en el signo del cálculo de la variable de decisión en la iteración anterior; después la variable de decisión se actualiza su mando ΔE o ΔNE al valor anterior, dependiendo de la elección del pixel.
Como el primer pixel es el primer punto extremo (x0, y0) y podemos calcular en forma directa el valor inicial de d eligiendo entre E y NE. El primer punto medio está en (x0+1, y0+½) y
F(x0+1, y0+½) = a(x0+1) + b( y0+½) + c=a·x0 +b·y0+c+ a+ b/2=F(x0, y0)+a+b/2
Sin embargo, (x0, y0) es un punto en la línea y F(x0, y0) y es por lo tanto 0; entonces, dinicio es simplemente a + b/2 = dy - dx/2. Con base en dinicio elegimos el segundo pixel, etcétera. Para eliminar la fracción en dinicio redefinimos nuestra F original multiplicándola por 2; F(x, y) = 2(ax + by + c). Así se multiplican por 2 cada constante y la variable de decisión (así como los incrementos ΔE y ΔNE) pero no se afecta el signo de la variable de decisión, que es lo que nos interesa para la prueba del punto medio.
La aritmética necesaria para evaluar dnuevo para cualquier iteración es una suma entera sencilla. No se requieren multiplicaciones que consuman mucho tiempo. Además, el ciclo interior es bastante sencillo, como se ve en el algoritmo de punto medio del programa 3.2. El primer enunciado en el ciclo, la evaluación de d, determina la elección del pixel, pero en realidad incrementamos x y y a la posición de ese pixel después de actualizar la variable de decisión (por cuestiones de compatibilidad con los algoritmos para círculos). Observe que esta versión del algoritmo sirve únicamente para líneas con pendiente entre O y 1; la generalización del algoritmo queda como tarea para el lector en el ejercicio 3.2. En [ Sproull ofrece una elegante derivación de la formulación de Bresenham del algoritmo como una serie de transformaciones de programa a partir del burdo algoritmo original. Aún no se ha presentado ningún equivalen te de la derivación para los círculos, pero sí se puede generalizar la técnica de punto medio, como veremos más adelante.
Void línea_punto_medio (int x0, int y0, int x1, int y1, int valor)
{
int dx, dy, inca_E, inca_NE, d, x, y;
dx=x1-x0;
dy=ty1-y0;
d=dy*2-dx;
inca_E=dx*2;
inca_ne=(dy-dx)*2;
y=x0;
y=y0;
escribir_pixel(x,y,valor)
While(x
If (d<=0){
d+=incr_E;
x++;
}else{
d+=inca_NE;
x++;
y++,
}
escribir_pixel(x,y,valor);
}
}
Para una línea que parte del punto (5, 8) al punto (9, 11), los valores sucesivos de d son 2, 0, 6 y 4, con lo cual se obtiene la selección de NE, E, NE y luego NL respectivamente, como se ilustra en la figura 3.7. La línea tiene una fuerte apariencia de escalera por la escala muy amplificada del dibujo y el espaciado artificialmente grande entre los pixeles que se usa para que quede clara la geometría del algoritmo. Por la misma razón, los dibujos en las secciones siguientes también hacen que las primitivas aparezca más irregulares que como se verían en realidad en la pantalla.
No hay comentarios:
Publicar un comentario