Algoritmo de línea de Bresenham

Algoritmo de dibujo de líneas

El algoritmo de línea de Bresenham es un algoritmo de dibujo de líneas que determina los puntos de un ráster n -dimensional que deben seleccionarse para formar una aproximación cercana a una línea recta entre dos puntos . Se utiliza comúnmente para dibujar primitivas de línea en una imagen de mapa de bits (por ejemplo, en una pantalla de computadora ), ya que utiliza solo suma, resta y desplazamiento de bits de números enteros , todas las cuales son operaciones muy económicas en arquitecturas de computadora históricamente comunes. Es un algoritmo de error incremental y uno de los primeros algoritmos desarrollados en el campo de los gráficos de computadora . Se puede utilizar una extensión del algoritmo original llamada algoritmo de círculo de punto medio para dibujar círculos .

Aunque algoritmos como el de Wu también se utilizan con frecuencia en gráficos informáticos modernos porque pueden soportar antialiasing , el algoritmo de línea de Bresenham sigue siendo importante debido a su velocidad y simplicidad. El algoritmo se utiliza en hardware como los trazadores y en los chips gráficos de las tarjetas gráficas modernas . También se puede encontrar en muchas bibliotecas de software de gráficos . Debido a que el algoritmo es muy simple, a menudo se implementa en el firmware o en el hardware gráfico 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 recibe su nombre de Jack Elton Bresenham, quien lo desarrolló en 1962 en IBM . En 2001, Bresenham escribió: ^[1]

Yo trabajaba en el laboratorio de computación del laboratorio de desarrollo de IBM en San José. Se había conectado un trazador Calcomp a una IBM 1401 a través de la consola de la máquina de escribir 1407. [El algoritmo] ya estaba en producción en el verano de 1962, posiblemente un mes antes. En aquellos días, los programas se intercambiaban libremente entre corporaciones, de modo que Calcomp (Jim Newland y Calvin Hefte) tenía copias. Cuando regresé a Stanford en el otoño de 1962, dejé una copia en la biblioteca del centro de computación de Stanford. Se aceptó una descripción de la rutina de dibujo de líneas para su presentación en la convención nacional de la ACM de 1963 en Denver, Colorado. Fue un año en el que no se publicaron las actas, solo la agenda de los oradores y los temas en un número de Communications of the ACM. Una persona del IBM Systems Journal me preguntó después de que hice mi presentación si podían publicar el artículo. Acepté con gusto y lo imprimieron en 1965.

Método

Ilustración del resultado del algoritmo de línea de Bresenham. (0,0) está en la esquina superior izquierda de la cuadrícula, (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:

• la parte superior izquierda es (0,0) de modo que las coordenadas de los píxeles aumentan en las direcciones derecha y abajo (por ejemplo, que el píxel en (7,4) está directamente encima del píxel en (7,5)), y
• Los centros de píxeles tienen coordenadas enteras.

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

El algoritmo se presentará inicialmente solo para el octante en el que el segmento desciende y se dirige hacia la derecha ( y ), y su proyección horizontal es más larga que la proyección vertical (la línea tiene una pendiente positiva menor que 1). En este octante, para cada columna x entre y , hay exactamente una fila y (calculada por el algoritmo) que contiene un píxel de la línea, mientras que cada fila entre y puede contener múltiples píxeles rasterizados. ${\displaystyle x_{0}\leq x_{1}}$ ${\displaystyle y_{0}\leq y_{1}}$ ${\displaystyle x_{1}-x_{0}}$ ${\displaystyle y_{1}-y_{0}}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle y_{0}}$ ${\displaystyle y_{1}}$

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

${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}$.

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

${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}$.

La pendiente depende únicamente de las coordenadas del punto final y se puede calcular previamente, y la y ideal para valores enteros sucesivos de x se puede calcular a partir de la pendiente y sumándola repetidamente. ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$ ${\displaystyle y_{0}}$

En la práctica, el algoritmo no lleva un registro de la coordenada y, que aumenta en m = ∆y/∆x cada vez que x aumenta en uno; mantiene un límite de error en cada etapa, que representa el negativo de la distancia desde (a) el punto donde la línea sale del píxel hasta (b) el borde superior del píxel. Este valor se establece primero en (debido al uso de las coordenadas centrales del píxel), y se incrementa en m cada vez que la coordenada x se incrementa en uno. Si el error se vuelve mayor que 0,5 , sabemos que la línea se ha movido hacia arriba un píxel y que debemos incrementar nuestra coordenada y y reajustar el error para representar la distancia desde la parte superior del nuevo píxel, lo que se hace restando uno al error. ^[2] ${\displaystyle y_{0}-0.5}$

Derivación

Para obtener 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-ordenada al origen 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=0

Semiplanos positivos y negativos

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

${\displaystyle y=f(x)=mx+b}$

donde es la pendiente y es la intersección con el eje y. Debido a que esta es una función de solo , no puede representar una línea vertical. Por lo tanto, sería útil hacer que esta ecuación se escribiera como una función tanto de como de , para poder dibujar líneas en cualquier ángulo. El ángulo (o pendiente) de una línea se puede expresar como "elevación sobre recorrido", o . Luego, utilizando manipulación algebraica, ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \Delta y/\Delta x}$

${\displaystyle {\begin{aligned}y&=mx+b\\y&={\frac {\Delta y}{\Delta x}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}}$

Si esta última ecuación es una función de y , se puede escribir como ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle f(x,y):=Ax+By+C=0}$

donde están las constantes

• ${\displaystyle A=\Delta y=y_{1}-y_{0}}$
• ${\displaystyle B=-\Delta x=-(x_{1}-x_{0})}$
• ${\displaystyle C=(\Delta x)b=(x_{1}-x_{0})b}$

La línea se define entonces para algunas constantes , , y en cualquier lugar . Es decir, para cualquier valor que no esté en la línea, . Esta forma involucra solo números enteros si y son números enteros, ya que las constantes , , y se definen como números enteros. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle f(x,y)=0}$ ${\displaystyle (x,y)}$ ${\displaystyle f(x,y)\neq 0}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

Como ejemplo, la línea entonces podría escribirse como . El punto (2,2) está en la línea ${\textstyle y={\frac {1}{2}}x+1}$ ${\displaystyle f(x,y)=x-2y+2}$

${\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

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

y tampoco es el punto (2,1)

${\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 su resultado es positivo o negativo. Una línea divide un plano en dos mitades y la mitad del plano que tiene un valor negativo puede llamarse semiplano negativo, y la otra mitad puede llamarse semiplano positivo. Esta observación es muy importante para el resto de la derivación. ${\displaystyle f(x,y)}$ ${\displaystyle f(x,y)}$

Algoritmo

El punto de partida está en la línea

${\displaystyle f(x_{0},y_{0})=0}$

sólo 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 como máximo , ahora se presenta el problema de si el siguiente punto debería estar en o . Tal vez intuitivamente, el punto debería elegirse en función de cuál está más cerca de la línea en . Si está más cerca del primero, incluya el primer punto en la línea; si es el segundo, incluya el segundo. Para responder a esto, evalúe la función de la línea en el punto medio entre estos dos puntos: ${\displaystyle 1}$ ${\displaystyle (x_{0}+1,y_{0})}$ ${\displaystyle (x_{0}+1,y_{0}+1)}$ ${\displaystyle x_{0}+1}$

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

Si el valor de este es positivo, entonces la línea ideal está por debajo del punto medio y más cerca del punto candidato ; es decir, la coordenada y debería aumentar. De lo contrario, la línea ideal pasa por el punto medio o por encima de él, y la coordenada y debería permanecer igual; en cuyo caso se elige el punto. El valor de la función de línea en este punto medio es el único determinante de qué punto debe elegirse. ${\displaystyle (x_{0}+1,y_{0}+1)}$ ${\displaystyle (x_{0}+1,y_{0})}$

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 números enteros

Como alternativa, se puede utilizar la diferencia entre puntos en lugar de evaluar f(x,y) en los puntos medios. Este método alternativo permite realizar operaciones aritméticas con números enteros únicamente, lo que generalmente es más rápido que utilizar operaciones aritméticas de punto flotante. Para obtener el otro método, defina la diferencia de la siguiente manera:

${\displaystyle D_{i}=f(x_{i}+1,y_{i}+{\tfrac {1}{2}})-f(x_{0},y_{0})}$

Para la primera decisión, esta formulación es equivalente al método del punto medio, ya que en el punto de partida. Simplificando esta expresión se obtiene: ${\displaystyle f(x_{0},y_{0})=0}$

${\displaystyle {\begin{array}{rclcl}D_{0}&=&\left[A(x_{0}+1)+B\left(y_{0}+{\frac {1}{2}}\right)+C\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&\left[Ax_{0}+By_{0}+C+A+{\frac {1}{2}}B\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&A+{\frac {1}{2}}B=\Delta y-{\frac {1}{2}}\Delta x\end{array}}}$

Al igual que con el método del punto medio, si es positivo, entonces elija , de lo contrario elija . ${\displaystyle D_{0}}$ ${\displaystyle (x_{0}+1,y_{0}+1)}$ ${\displaystyle (x_{0}+1,y_{0})}$

Si se elige, el cambio será: ${\displaystyle (x_{0}+1,y_{0})}$ ${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {1}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{array}}}$

Si se elige el cambio será: ${\displaystyle (x_{0}+1,y_{0}+1)}$ ${\displaystyle D_{i}}$

${\displaystyle {\begin{array}{lclcl}\Delta D&=&f(x_{0}+2,y_{0}+{\tfrac {3}{2}})-f(x_{0}+1,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{array}}}$

Si la nueva D es positiva, se elige , en caso contrario . Esta decisión se puede generalizar acumulando el error en cada punto subsiguiente. ${\displaystyle (x_{0}+2,y_{0}+1)}$ ${\displaystyle (x_{0}+2,y_{0})}$

Trazando la línea de (0,1) a (6,4) mostrando un gráfico de líneas de cuadrícula y píxeles

Ya se ha realizado toda la derivación del algoritmo. Un problema de rendimiento es el factor 1/2 en el valor inicial de D. Como todo esto se trata del signo de la diferencia acumulada, todo se puede multiplicar por 2 sin consecuencias.

Esto da como resultado un algoritmo que utiliza únicamente aritmética de números enteros.

trazarLinea(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 D = 2*dy-dx y = y0 para x de x0 a x1 trama(x, y) si D > 0 y = y + 1 D = D - 2*dx terminar si D = D + 2*dy

Al ejecutar este algoritmo desde (0,1) hasta (6,4) se obtienen las siguientes diferencias con dx=6 y dy=3: ${\displaystyle f(x,y)=x-2y+2}$

D=2*3-6=0Bucle de 0 a 6 * x=0: gráfica(0, 1) , D≤0: D=0+6=6 * x=1: trazar(1, 1) , D>0: D=6-12=-6, y=1+1=2, D=-6+6=0 * x=2: gráfica(2, 2) , D≤0: D=0+6=6 * x=3: trazar(3, 2) , D>0: D=6-12=-6, y=2+1=3, D=-6+6=0 * x=4: gráfica(4, 3) , D≤0: D=0+6=6 * x=5: trazar(5, 3) , D>0: D=6-12=-6, y=3+1=4, D=-6+6=0 * x=6: gráfica(6, 4) , D≤0: D=0+6=6

El resultado de este gráfico se muestra a la derecha. El gráfico se puede ver trazando en la intersección de las líneas (círculos azules) o rellenando los cuadros de píxeles (cuadrados amarillos). En cualquier caso, el gráfico es el mismo.

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 0 o 1.

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

plotLineLow(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 y = 1 si dy < 0 y = -1 dy = -dy terminar si D = (2 * dy) - dx y = y0 para x de x0 a x1 trama(x, y) si D > 0 y = y + yi D = D + (2 * (dy - dx)) demás D = D + 2*dy terminar si

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

plotLineHigh(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 x1 = 1 si dx < 0 x1 = -1 dx = -dx terminar si D = (2 * dx) - dy x = x0 para y desde y0 hasta y1 trama(x, y) si D > 0 x = x + xi D = D + (2 * (dx - dy)) demás D = 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) < abs(x1 - x0) si x0 > x1 plotLineLow(x1, y1, x0, y0) demás plotLineLow(x0, y0, x1, y1) fin si  de lo contrario  si y0 > y1 plotLineHigh(x1, y1, x0, y0) demás plotLineHigh(x0, y0, x1, y1) fin si  fin 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 manejaran por separado, ya que pueden optimizarse en gran medida.

Algunas versiones utilizan los principios de error incremental entero de Bresenham para realizar todos los dibujos de líneas octales, equilibrando el error positivo y negativo entre las coordenadas x e y. ^[3]

trazarLinea(x0, y0, x1, y1) dx = abs(x1 - x0) sx = x0 < x1 ? 1 : -1 dy = -abs(y1 - y0) y = y0 < y1 ? 1 : -1 error = dx + dy  Aunque es cierto trama(x0, y0) si x0 == x1 && y0 == y1 romper e2 = 2 * error si e2 >= dy error = error + dy x0 = x0 + sx fin si  si e2 <= dx error = error + dx y0 = y0 + sy Fin si  fin mientras

Algoritmos similares

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

El principio de utilizar 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 raster de polígonos con textura mapeada. ^[4] Los motores de renderizado de software de mapas de altura de vóxeles que se ven en algunos juegos de PC también utilizaron este principio.

Bresenham también publicó un algoritmo computacional Run-Slice: mientras que el algoritmo Run-Length descrito anteriormente ejecuta el bucle en el eje mayor, la variación Run-Slice realiza el bucle en sentido inverso. ^[5] Este método ha sido representado en varias patentes estadounidenses:

El algoritmo se ha ampliado a:

• Dibujar líneas de grosor arbitrario, un algoritmo creado por Alan Murphy en IBM. ^[6]
• Dibujar múltiples tipos de curvas (círculos, elipses, curvas de Bézier cúbicas, cuadráticas y racionales) y líneas y curvas suavizadas; un conjunto de algoritmos de Alois Zingl. ^[3]

Véase también

• Analizador diferencial digital (algoritmo gráfico) , un método simple y general para rasterizar líneas y triángulos
• Algoritmo de línea de Xiaolin Wu , un método igualmente rápido para dibujar líneas con antialiasing
• Algoritmo del círculo de punto medio , un algoritmo similar para dibujar círculos

Notas

1. Paul E. Black. Diccionario de algoritmos y estructuras de datos, NIST . https://xlinux.nist.gov/dads/HTML/bresenham.html
2. Joy, Kenneth. "Algoritmo de Bresenham" (PDF) . Grupo de investigación en visualización y gráficos, Departamento de Ciencias de la Computación, Universidad de California, Davis . Consultado el 20 de diciembre de 2016 .
3. Zingl, Alois (2012). Un algoritmo de rasterización para dibujar curvas (PDF) (Informe).
   Resumen y demostración de HTML: Zingl, Alois (2016). "Bresenham". miembros.chello.at .
4. US 5739818, Spackman, John Neil, "Aparato y método para realizar interpolación de perspectiva correcta en gráficos de computadora", publicado el 14 de abril de 1998, asignado a Canon KK 
5. "Edición especial del libro negro de programación gráfica de Michael Abrash: lo bueno, lo malo y lo que se ejecuta en rodajas". www.phatcode.net . Consultado el 13 de febrero de 2024 .;
6. "Algoritmo de línea Bresenham modificado de Murphy". homepages.enterprise.net . Consultado el 9 de junio de 2018 .('Engrosamiento de línea mediante modificación del algoritmo de Bresenham' en el IBM Technical Disclosure Bulletin Vol. 20 No. 12 mayo de 1978 páginas 5358-5366.)

Referencias

• Bresenham, JE (1965). "Algoritmo para el control por ordenador de un trazador digital" (PDF) . IBM Systems Journal . 4 (1): 25–30. doi :10.1147/sj.41.0025. Archivado desde el original (PDF) el 28 de mayo de 2008.
• "El algoritmo de dibujo de líneas de Bresenham", de Colin Flanagan
• Abrash, Michael (1997). El libro negro de programación gráfica de Michael Abrash . Albany, NY: Coriolis. págs. 654–678. ISBN 978-1-57610-174-2.Una versión muy optimizada del algoritmo en C y ensamblaje para su uso en videojuegos con detalles completos de su funcionamiento interno.
• Zingl, Alois (2012). "Un algoritmo de rasterización para dibujar curvas" (PDF) .La belleza de los algoritmos de Bresenham

Lectura adicional

• Tesis de Patrick-Gillesbanda, que contiene una extensión del algoritmo de dibujo de líneas de Bresenham para realizar la eliminación de líneas ocultas en 3D
  • También publicado en las actas de MICAD '87 sobre CAD/CAM y gráficos por computadora, página 591 - ISBN 2-86601-084-1 . 
• Engrosamiento de línea mediante modificación del algoritmo de Bresenham, AS Murphy, IBM Technical Disclosure Bulletin, Vol. 20, No. 12, mayo de 1978.
• Bresenham, Jack (febrero de 1977). "Un algoritmo lineal para la visualización digital incremental de arcos circulares". Comunicaciones de la ACM . 20 (2): 100–106. doi :10.1145/359423.359432.– también Informe técnico 1964 27 de enero de 2011 Algoritmo circular TR-02-286 Laboratorio IBM San José

Enlaces externos

• Edición especial del libro negro de programación gráfica de Michael Abrash: Capítulo 35: Bresenham es rápido y rápido es bueno
• El algoritmo de dibujo de líneas de Bresenham de Colin Flanagan
• Página del Instituto Nacional de Estándares y Tecnología sobre el algoritmo de Bresenham
• Información sobre el trazador incremental Calcomp 563
• Algoritmo de Bresenham en varios lenguajes de programación
• La belleza del algoritmo de Bresenham: una implementación sencilla para trazar líneas, círculos, elipses y curvas de Bézier