Algoritmo de línea de Bresenham

Algoritmo de línea de Bresenham es un algoritmo de dibujo de línea que determina los puntos de un ráster n-dimensional que debe seleccionarse para formar una aproximación cercana a una línea recta entre dos puntos. Se usa comúnmente para dibujar primitivas de línea en una imagen de mapa de bits (por ejemplo, en una pantalla de computadora), ya que solo usa sumas, restas y cambios de bits enteros, todas las cuales son operaciones muy económicas en conjuntos de instrucciones de computadora de uso común como x86_64. Es un algoritmo de error incremental y uno de los primeros algoritmos desarrollados en el campo de los gráficos por computadora. Se puede usar una extensión del algoritmo original para dibujar círculos.

Si bien los algoritmos como el algoritmo de Wu también se usan con frecuencia en los gráficos por computadora modernos porque pueden admitir el antialiasing, el algoritmo de línea de Bresenham sigue siendo importante debido a su velocidad y simplicidad. El algoritmo se utiliza en hardware como trazadores y en los chips gráficos de las tarjetas gráficas modernas. También se puede encontrar en muchas bibliotecas de gráficos de software. Debido a que el algoritmo es muy simple, a menudo se implementa en el firmware o en el hardware de gráficos de las tarjetas gráficas modernas.

La etiqueta "Bresenham" se utiliza hoy en día para una familia de algoritmos que amplían o modifican el algoritmo original de Bresenham.

Historia

El algoritmo de línea de Bresenham lleva el nombre de Jack Elton Bresenham, quien lo desarrolló en 1962 en IBM. En 2001, Bresenham escribió:

Estaba trabajando en el laboratorio de computación en el laboratorio de desarrollo de San José de IBM. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter consola. [El algoritmo] estaba en uso de producción para el verano de 1962, posiblemente un mes o así antes. Los programas en esos días se intercambiaron libremente entre las corporaciones, por lo que Calcomp (Jim Newland y Calvin Hefte) tenían copias. Cuando volví a Stanford en otoño de 1962, puse una copia en la biblioteca del centro de computación de Stanford. Se aceptó una descripción de la rutina de dibujo de línea para su presentación en la convención nacional ACM de 1963 en Denver, Colorado. Fue un año en que no se publicó ningún procedimiento, sino el programa de oradores y temas en una cuestión de las comunicaciones de la ACM. Una persona del IBM Systems Journal me preguntó después de hacer mi presentación si podían publicar el documento. Acepté felizmente, y lo imprimieron en 1965.

El algoritmo de Bresenham se ha ampliado para generar círculos, elipses, curvas Bézier cúbicas y cuadráticas, así como versiones nativas suavizadas de estas.

Método

Ilustración del resultado del algoritmo de línea de Bresenham. (0,0) está en la esquina superior izquierda de la red, (1,1) está en el extremo superior izquierdo de la línea y (11, 5) está en el extremo inferior derecho de la línea.

Se utilizarán las siguientes convenciones:

• el top-left es (0,0) tal que las coordenadas pixel aumentan en las direcciones derecha y baja (por ejemplo, que el píxel a (7,4) está directamente por encima del píxel a (7,5)), y
• los centros pixel tienen coordenadas enteros.

Los puntos finales de la línea son los píxeles en ()x0,Sí.0){displaystyle (x_{0},y_{0}} y ()x1,Sí.1){displaystyle (x_{1},y_{1}}, donde la primera coordenadas del par es la columna y la segunda es la fila.

El algoritmo se presentará inicialmente sólo para el octante en el que el segmento baja y a la derecha (x0≤ ≤ x1{displaystyle x_{0}leq x_{1}} y Sí.0≤ ≤ Sí.1{displaystyle Y... Y...), y su proyección horizontal x1− − x0{displaystyle x_{1}-x_{0} es más largo que la proyección vertical Sí.1− − Sí.0{displaystyle Y... (la línea tiene una pendiente positiva menos de 1). En este octant, para cada columna x entre x0{displaystyle x_{0} y x1{displaystyle x_{1}}, hay exactamente una fila Sí. (computado por el algoritmo) que contiene un píxel de la línea, mientras que cada fila entre Sí.0{displaystyle Y... y Sí.1{displaystyle Y... puede contener píxeles rasterizados múltiples.

El algoritmo de Bresenham elige el número entero y correspondiente al centro del píxel más cercano al ideal (fraccional) y para el mismo x; en columnas sucesivas y puede permanecer igual o aumentar en 1. La ecuación general de la recta que pasa por los extremos está dada por:

Sí.− − Sí.0Sí.1− − Sí.0=x− − x0x1− − x0{fnMicroc} {y-y_{0} {y_{1}-y_{0}={frac} {x-x_{0} {x_{1}-x_{0}}}.

Dado que conocemos la columna, x, la fila del píxel, y, se obtiene redondeando esta cantidad al entero más cercano:

Sí.=Sí.1− − Sí.0x1− − x0()x− − x0)+Sí.0{displaystyle y={frac {y_{1}-y_{0} {x_{0}}(x-x_{0})+y_{0}.

La pendiente ()Sí.1− − Sí.0)/()x1− − x0){displaystyle (y_{1}-y_{0})/(x_{1}-x_{0} depende de las coordenadas de endpoint sólo y puede ser precomputado, y el ideal Sí. para valores enteros sucesivos x puede ser calculado a partir de Sí.0{displaystyle Y... y añadiendo repetidamente la pendiente.

En la práctica, el algoritmo no mantiene el seguimiento de la y coordenadas, que aumenta por m = vocay/ejox cada vez x aumenta por uno; mantiene un error ligado a cada uno etapa, que representa el negativo de la distancia de (a) el punto donde la línea sale del píxel a (b) el borde superior del píxel. Este valor se establece por primera vez Sí.0− − 0.5{displaystyle Y... (debido a usar las coordenadas centrales del píxel), y es incrementado por m cada vez x coordenadas se aumenta por uno. Si el error se hace mayor que 0.5, sabemos que la línea se ha movido hacia arriba un pixel, y que debemos aumentar nuestro Sí. coordine y reajuste el error para representar la distancia desde la parte superior del nuevo píxel – que se hace restando uno del error.

Derivación

Para derivar el algoritmo de Bresenham, se deben seguir dos pasos. El primer paso es transformar la ecuación de una línea de la típica forma pendiente-intersección en algo diferente; y luego usar esta nueva ecuación para dibujar una línea basada en la idea de acumulación de error.

Ecuación de línea

y=f(x)=.5x+1 o f(x,y)=x-2y+2

Planes medio positivos y negativos

La forma pendiente-intersección de una línea se escribe como

Sí.=f()x)=mx+b{displaystyle y=f(x)=mx+b}

donde m es la pendiente y b es el intercepto y. Porque esta es una función de sólo x{displaystyle x}No puede representar una línea vertical. Por lo tanto, sería útil hacer esta ecuación escrita como una función de ambos x{displaystyle x} y Sí.{displaystyle y}Para poder dibujar líneas en cualquier ángulo. El ángulo (o la pendiente) de una línea se puede decir como "rise over run", o Δ Δ Sí./Δ Δ x{displaystyle Delta y/Delta x}. Entonces, usando la manipulación algebraica,

Sí.=mx+bSí.=()Δ Δ Sí.)()Δ Δ x)x+b()Δ Δ x)Sí.=()Δ Δ Sí.)x+()Δ Δ x)b0=()Δ Δ Sí.)x− − ()Δ Δ x)Sí.+()Δ Δ x)b{displaystyle {begin{aligned}y limitada=mx+b\y reducida={frac} {Delta y)}{(Delta x)}}x+b(Delta x)y correspond=(Delta y)x+(Delta x)b limit=(Delta y)x-(Delta x)y+(Delta x)bend{aligned}}}

Dejar que esta última ecuación sea una función de x{displaystyle x} y Sí.{displaystyle y}, puede ser escrito como

f()x,Sí.):=Ax+BSí.+C=0{displaystyle f(x,y):=Ax+By+C=0}

donde están las constantes

• A=Δ Δ Sí.=Sí.1− − Sí.0{displaystyle A=Delta Sí.
• B=− − Δ Δ x=− − ()x1− − x0){displaystyle B=-Delta x=-(x_{1}-x_{0}
• C=()Δ Δ x)b=x1Sí.0− − x0Sí.1{displaystyle C=(Delta x)b=x_{1}y_{0}-x_{0}y_{1}

La línea se define entonces para algunas constantes A, B y C en cualquier lugar f()x,Sí.)=0{displaystyle f(x,y)=0}. Es decir, para cualquier ()x,Sí.){displaystyle (x,y)} no en la línea, f()x,Sí.)ل ل 0{displaystyle f(x,y)neq 0}. Esta forma implica solamente enteros si x{displaystyle x} y Sí.{displaystyle y} son enteros, ya que las constantes A, B y C se definen como enteros.

Como ejemplo, la línea Sí.=12x+1{displaystyle y={frac {1}{2}x+1} entonces esto podría ser escrito como f()x,Sí.)=x− − 2Sí.+2{displaystyle f(x,y)=x-2y+2}. El punto (2,2) está en la línea

f()2,2)=x− − 2Sí.+2=()2)− − 2()2)+2=2− − 4+2=0{displaystyle f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0}

y el punto (2,3) no está en la recta

f()2,3)=()2)− − 2()3)+2=2− − 6+2=− − 2{displaystyle f(2,3)=(2)-2(3)+2=2-6+2=-2}

y tampoco el punto (2,1)

f()2,1)=()2)− − 2()1)+2=2− − 2+2=2{displaystyle f(2,1)=(2)-2(1)+2=2-2+2=2}

Observe que los puntos (2,1) y (2,3) están en lados opuestos de la línea y f(x,y) se evalúa como positivo o negativo. Una línea divide un plano en dos mitades y el semiplano que tiene un f(x,y) negativo puede llamarse semiplano negativo, y la otra mitad puede llamarse semiplano positivo. Esta observación es muy importante en el resto de la derivación.

Algoritmo

Claramente, el punto de partida está en la línea

f()x0,Sí.0)=0{displaystyle f(x_{0},y_{0}=0}

solo porque la línea está definida para comenzar y terminar en coordenadas enteras (aunque es completamente razonable querer dibujar una línea con puntos finales no enteros).

Punto candidato (2,2) en azul y dos puntos candidatos en verde (3,2) y (3,3)

Teniendo en cuenta que la pendiente es al máximo 1{displaystyle 1}, el problema ahora se presenta en cuanto a si el siguiente punto debe ser ()x0+1,Sí.0){displaystyle (x_{0}+1,y_{0}} o ()x0+1,Sí.0+1){displaystyle (x_{0}+1,y_{0}+1)}. Tal vez intuitivamente, el punto debe ser elegido basado en el cual está más cerca de la línea en x0+1{displaystyle x_{0}+1}. Si está más cerca del primero, entonces incluya el primer punto en la línea, si el segundo entonces el segundo. Para responder a esto, evaluar la función de línea en el punto medio entre estos dos puntos:

f()x0+1,Sí.0+12){displaystyle f(x_{0}+1,y_{0}+{tfrac {1}{2}}}}

Si el valor de esto es positivo entonces la línea ideal está por debajo del punto medio y más cerca del punto candidato ()x0+1,Sí.0+1){displaystyle (x_{0}+1,y_{0}+1)}; en efecto la coordenadas y ha avanzado. De lo contrario, la línea ideal pasa a través o por encima del punto medio, y la coordenadas no ha avanzado; en este caso elija el punto ()x0+1,Sí.0){displaystyle (x_{0}+1,y_{0}}. El valor de la función de línea en este punto medio es el único determinante de qué punto debe ser elegido.

La imagen adyacente muestra el punto azul (2,2) elegido para estar en la línea con dos puntos candidatos en verde (3,2) y (3,3). El punto negro (3, 2.5) es el punto medio entre los dos puntos candidatos.

Algoritmo para aritmética de enteros

Como alternativa, se puede usar la diferencia entre puntos en lugar de evaluar f(x,y) en los puntos medios. Este método alternativo permite la aritmética de solo números enteros, que generalmente es más rápida que usar la aritmética de punto flotante. Para derivar el método alternativo, defina la diferencia como sigue:

D=f()x0+1,Sí.0+12)− − f()x0,Sí.0){displaystyle D=f(x_{0}+1,y_{0}+{tfrac {1}{2})-f(x_{0},y_{0}}

Para la primera decisión, esta formulación es equivalente al método de punto medio desde entonces f()x0,Sí.0)=0{displaystyle f(x_{0},y_{0}=0} en el punto de partida. Simplificar esta expresión produce:

D=[A()x0+1)+B()Sí.0+12)+C]− − [Ax0+BSí.0+C]=[Ax0+BSí.0+C+A+12B]− − [Ax0+BSí.0+C]=A+12B=Δ Δ Sí.− − 12Δ Δ x{displaystyle {begin{array}{rcl}D presentarse= limiteleft[A(x_{0}+1)+Bleft(y_{0}+{frac {1}{2}right)+Cright] [Ax_{0}+By_{0}+Cright]\fnMicroc {1}{2}Bright] [Ax_{0}+By_{0}+Cright] 'Consiguiente= Con+{frac {1}{2}B=Delta y-{frac {1}{2}Delta xend{array}}

Como con el método de punto medio, si D{displaystyle D} es positivo, entonces elegir ()x0+1,Sí.0+1){displaystyle (x_{0}+1,y_{0}+1)}, de lo contrario elegir ()x0+1,Sí.0){displaystyle (x_{0}+1,y_{0}}.

Si ()x0+1,Sí.0){displaystyle (x_{0}+1,y_{0}} es elegido, el cambio en D será:

Δ Δ D=f()x0+2,Sí.0+12)− − f()x0+1,Sí.0+12)=A=Δ Δ Sí.{displaystyle {begin{array}{lclcl} Delta D Puls= Duef(x_{0}+2,y_{0}+{tfrac {1}{2})-f(x_{0}+1,y_{0}+{tfrac {1}{2}} {fn}}}}

Si ()x0+1,Sí.0+1){displaystyle (x_{0}+1,y_{0}+1)} es elegido el cambio en D será:

Δ Δ D=f()x0+2,Sí.0+32)− − f()x0+1,Sí.0+12)=A+B=Δ Δ Sí.− − Δ Δ x{displaystyle {begin{array}{lclcl} Delta D Puls= Duef(x_{0}+2,y_{0}+{tfrac {3}{2})-f(x_{0}+1,y_{0}+{tfrac {1}{2}} {0}}

Si el nuevo D es positivo entonces ()x0+2,Sí.0+1){displaystyle (x_{0}+2,y_{0}+1)} es elegido, de lo contrario ()x0+2,Sí.0){displaystyle (x_{0}+2,y_{0}}. Esta decisión puede generalizarse acumulando el error en cada punto posterior.

Plotting la línea de (0,1) a (6,4) mostrando una trama de líneas de red y píxeles

Toda la derivación para el algoritmo está hecha. Un problema de rendimiento es el factor 1/2 en el valor inicial de D. Dado que todo esto tiene que ver con el signo de la diferencia acumulada, entonces todo se puede multiplicar por 2 sin ninguna consecuencia.

Esto da como resultado un algoritmo que usa solo aritmética de enteros.

plotLine(x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
D = 2*dy - dx
Sí.

 para x de x0 a x1
plot(x, y)
 si D ■ 0
y = 1
D = D - 2*dx
 terminar siD = D + 2*dis

Correr este algoritmo para f()x,Sí.)=x− − 2Sí.+2{displaystyle f(x,y)=x-2y+2} de (0,1) a (6,4) produce las siguientes diferencias con dx=6 y dy=3:

D=2*3-6=0
Ámbito de 0 a 6
* x=0: parcela(0, 1), D≤0: D=0+6=6
* x=1: parcela(1, 1), D titulada0: D=6-12=-6, y=1+1=2, D=-6+6=0
* x=2: parcela(2, 2), D≤0: D=0+6=6
* x=3: parcela(3, 2), D titulada0: D=6-12=-6, y=2+1=3, D=-6+6=0
* x=4: plot(4, 3), D≤0: D=0+6=6
* x=5: parcela(5, 3), D titulada0: D=6-12=-6, y=3+1=4, D=-6+6=0
* x=6: parcela(6, 4), D≤0: D=0+6=6

El resultado de este gráfico se muestra a la derecha. El trazado se puede ver trazando en la intersección de líneas (círculos azules) o rellenando cuadros de píxeles (cuadrados amarillos). Independientemente, la trama es la misma.

Todos los casos

Sin embargo, como se mencionó anteriormente, esto solo funciona para el octante cero, es decir, líneas que comienzan en el origen con una pendiente entre 0 y 1, donde x aumenta exactamente 1 por iteración e y aumenta en 0 o 1.

El algoritmo se puede ampliar para cubrir pendientes entre 0 y -1 comprobando si y necesita aumentar o disminuir (es decir, dy < 0)

plotLineLow(x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
Yi = 1
 si dy
yi = 1
dy
 terminar siD = (2 * dis) - dx
Sí.

 para x de x0 a x1
plot(x, y)
 si D ■ 0
yi
D = D + (2 * (dy - dx))
 másD = D + 2*dis
 terminar si

Al cambiar los ejes x e y, una implementación para pendientes empinadas positivas o negativas se puede escribir como

plotLineHigh(x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
xi = 1
 si dx 0
xi = 1
dx = dx
 terminar siD = (2 * dx) - dy
x = x0

 para Y de ti a y1
plot(x, y)
 si D ■ 0
x = x + xi
D = D + (2 * (dx - dy))
 másD = D + 2*dx
 terminar si

Una solución completa necesitaría detectar si x1 > x0 o y1 > y0 e invertir las coordenadas de entrada antes de dibujar, por lo tanto

plotLine(x0, y0, x1, y1)
 si abs(y1 - y0)
 si x0
plotLineLow(x1, y1, x0, y0)
 másplotLineLow(x0, y0, x1, y1)
 terminar si más si y0
plotLineHigh(x1, y1, x0, y0)
 másplotLineHigh(x0, y0, x1, y1)
 terminar si terminar si

En implementaciones de bajo nivel que acceden directamente a la memoria de video, sería típico que los casos especiales de líneas verticales y horizontales se manejen por separado, ya que se pueden optimizar en gran medida.

Algunas versiones utilizan los principios de error incremental de enteros de Bresenham para realizar todos los dibujos de líneas octantes, equilibrando el error positivo y negativo entre las coordenadas x e y. Tenga en cuenta que el pedido no está necesariamente garantizado; en otras palabras, la línea puede trazarse desde (x0, y0) hasta (x1, y1) o desde (x1, y1) hasta (x0, y0).

plotLine(x0, y0, x1, y1)
dx = abs(x1 - x0)
sx = x0, significa x1 ? 1: -1
dy = -abs(y1 - y0)
sy = y0
error = dx + dy

 mientras verdadero
plot(x0, y0)
 si x0 == x1 ", y0 == y1 descansoe2 = 2 * error
 si e2
 si x0 == x1 descansoerror = error + dy
x0 = x0 + sx
 terminar si si e2
 si Y0 == y1 descansoerror = error + dx
Y0 = y0 + sy
 terminar si terminar mientras

Algoritmos similares

El algoritmo de Bresenham se puede interpretar como un analizador diferencial digital ligeramente modificado (usando 0,5 como umbral de error en lugar de 0, que es necesario para la rasterización de polígonos que no se superponen).

El principio de usar un error incremental en lugar de operaciones de división tiene otras aplicaciones en gráficos. Es posible utilizar esta técnica para calcular las coordenadas U,V durante el escaneo de trama de polígonos mapeados con textura. Los motores de representación de software de mapa de altura de vóxel que se ven en algunos juegos de PC también utilizaron este principio.

Bresenham también publicó un algoritmo computacional Run-Slice (a diferencia del Run-Length). Este método ha sido representado en varias patentes estadounidenses:

Alan Murphy de IBM creó una extensión del algoritmo que maneja líneas gruesas.