A continuación no se describirán los métodos, simplemente se harán algunas observaciones en cuanto a estos, tratando de hacer evidentes algunas características.
El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el calculo ya sea de y o x
Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.
El problema con este algoritmo es que se debe redondear números flotantes a enteros y hacer operaciones sobre números flotantes , lo cual toma tiempo.
Para líneas largas, la acumulación de errores de redondeo en adiciones sucesivas del incremento de punto flotante pueden provocar que las posiciones del píxel calculadas se desvíen de la trayectoria real de la línea.
Se puede mejorar el desempeño del algoritmo al separar los incrementos m y 1/m en partes enteras fraccionarias, de forma que todos los cálculos se reduzcan a operaciones de enteros.
Algoritmo de Línea Bresenham Básico
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 <>
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.
En resumen, los pasos son:
1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).
2. Se carga (x0,y0) en el bufer de estructura, o sea, se traza el primer punto.
3. Se calculan las constantes y, x, 2y, 2y-2x, y se obtiene el valor inicial para el parámetro de decisión
como p0 = 2 y - x.
4. En cada xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: si pk <>
que se debe trazar es (xk+1,yk) y pk +1 = pk + 2 y. De otro modo, el siguiente punto en trazarse es (xk+1,yk+1)
y pk +1 = pk + 2 y - 2x.
5. Se repite el paso 4 otras x veces.
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.
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 (y = 0), las líneas verticales (x = 0) y las diagonales | y | = | x | se pueden cargar en forma directa sin procesarlas mediante el algoritmo para el trazo de líneas.
Algoritmo de Punto Medio para
.
Para líneas y círculos de enteros, la formulación de punto medio, se reduce a la formulación de Bresenham y por lo tanto se generan los mismos pixeles.
Bresenham (1977) mostró que este algoritmo de línea y circulo de enteros proveen la mejor aproximación a líneas y círculos verdaderos al minimizar el error (distancia) a las primitivas reales.
Kappel (1985) discute los efectos de varios ¡criterios de error.
Se asume que la pendiente de la línea es entre 0 y 1.
Otras pendientes se pueden manejar como reflexiones sobre ejes principales.
Se define a (x0,y0) como el extremo inferior izquierdo y (x1,y1) como el extremo superior derecho.
La línea se representa con una función implícita (esta representación se extiende muy bien para la formulación decírculos) con coeficientes A, B, y C:
f(x,y) = Ax + By + C = 0
