Algoritmo de la línea de Bresenham

Algoritmo de dibujo de líneas

El algoritmo de líneas de Bresenham es un algoritmo de dibujo de líneas que determina los puntos de un ráster de n dimensiones que deben seleccionarse para formar una aproximación cercana a una línea recta entre dos puntos . Se utiliza comúnmente para dibujar líneas primitivas en una imagen de mapa de bits (por ejemplo, en la pantalla de una computadora ), ya que solo utiliza 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 por computadora . Se puede utilizar una extensión del algoritmo original llamado algoritmo del círculo del punto medio para dibujar círculos .

Si bien algoritmos como el algoritmo de Wu también se utilizan con frecuencia en los gráficos por computadora modernos porque pueden admitir 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ó: ^[1]

Estaba trabajando 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] estaba en uso en producción en el verano de 1962, posiblemente un mes antes. En aquellos días, los programas se intercambiaban libremente entre corporaciones, por lo que Calcomp (Jim Newland y Calvin Hefte) tenía copias. Cuando regresé a Stanford en el otoño de 1962, puse una copia en la biblioteca del Centro de Compensación de Stanford. Se aceptó una descripción de la rutina de dibujo lineal 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 actas, sólo la agenda de ponentes y temas en un número de Comunicaciones de la JCA. Una persona del IBM Systems Journal me preguntó después de hacer mi presentación si podían publicar el artículo. Acepté felizmente y lo imprimieron en 1965.

Método

Ilustración del resultado del algoritmo lineal 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 e inferior (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 sólo para el octante en el que el segmento desciende hacia abajo y hacia la derecha ( y ), y su proyección horizontal es más larga que la proyección vertical (la recta 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 número entero y correspondiente al centro del píxel más cercano al y ideal (fraccional) para el mismo 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 , viene dada 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 comenzando y sumando repetidamente la pendiente. ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$ ${\displaystyle y_{0}}$

En la práctica, el algoritmo no realiza un seguimiento de la coordenada y, que aumenta en m = ∆y/∆x cada vez que x aumenta en uno; mantiene un error limitado 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 es mayor que 0,5 , sabemos que la línea se ha movido un píxel hacia arriba y que debemos incrementar nuestra coordenada y y reajustar el error para representar la distancia desde la parte superior del nuevo píxel, lo cual se hace restando uno de error. ^[2] ${\displaystyle y_{0}-0.5}$

Derivación

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

Ecuación lineal

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

Semiplanos positivos y negativos

La forma pendiente-intersección de una recta 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 únicamente , no puede representar una línea vertical. Por lo tanto, sería útil escribir esta ecuación en función de ambos y , para poder dibujar líneas en cualquier ángulo. El ángulo (o pendiente) de una línea se puede expresar como "ascenso sobre recorrido", o . Luego, usando 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}}}$

Dejando que esta última ecuación sea 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}$

Luego, la línea se define para algunas constantes , y en cualquier lugar . Es decir, para cualquiera que no esté en la línea . Esta forma involucra sólo 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 esto podría escribirse como . El punto (2,2) está sobre la recta. ${\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 lo 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 se evalúan como positivos o negativos. Una línea divide un plano en mitades y el semiplano que tiene un negativo se puede llamar semiplano negativo y la otra mitad se puede llamar semiplano positivo. Esta observación es muy importante en el resto de la derivación. ${\displaystyle f(x,y)}$ ${\displaystyle f(x,y)}$

Algoritmo

Es evidente que el punto de partida está en la línea

${\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 como máximo , ahora se presenta el problema de si el siguiente punto debe estar en o . Quizás 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, entonces el último. Para responder a esto, evalúe la función de 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 esto es positivo entonces la línea ideal está 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 del mismo, y la coordenada y debe permanecer igual; en cuyo caso se elige el punto . El valor de la función lineal en este punto medio es el único determinante de qué punto se debe elegir. ${\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 enteros

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

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

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

${\displaystyle {\begin{array}{rclcl}D&=&\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, elija , de lo contrario elija . ${\displaystyle D}$ ${\displaystyle (x_{0}+1,y_{0}+1)}$ ${\displaystyle (x_{0}+1,y_{0})}$

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

${\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 en D será: ${\displaystyle (x_{0}+1,y_{0}+1)}$

${\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 entonces se elige, en caso contrario . Esta decisión se puede generalizar acumulando el error en cada punto posterior. ${\displaystyle (x_{0}+2,y_{0}+1)}$ ${\displaystyle (x_{0}+2,y_{0})}$

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

Se realiza toda la derivación del algoritmo. Un problema de rendimiento es el factor 1/2 en el valor inicial de D. Dado que todo esto se trata del signo de la diferencia acumulada, entonces todo se puede multiplicar por 2 sin consecuencias.

Esto da como resultado un algoritmo que utiliza sólo aritmética de enteros.

líneatrama(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 D = 2*dy - dx y = y0 para x de x0 a x1 trazar (x, y) si D > 0 y = y + 1 D = D - 2*dx terminara 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: trazar(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: trazar(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: trazar(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: trazar(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). De todos modos, 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).

tramaLíneaBaja(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 yi = 1 si dy < 0 yi = -1 dy = -dy terminara si D = (2 * dy) - dx y = y0 para x de x0 a x1 trazar (x, y) si D > 0 y = y + yi D = D + (2 * (dy - dx)) demás D = D + 2*dy terminara si

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

tramaLíneaAlta(x0, y0, x1, y1) dx = x1 - x0 dy = y1 - y0 xi = 1 si dx < 0 xi = -1 dx = -dx terminara si D = (2 * dx) - dy x = x0 para y de y0 a y1 trazar (x, y) si D > 0 x = x + xi D = D + (2 * (dx - dy)) demás D = D + 2*dx terminara 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 tramaLíneaBaja(x1, y1, x0, y0) demás tramaLíneaBaja(x0, y0, x1, y1) terminar si  no  si y0 > y1 tramaLíneaAlta(x1, y1, x0, y0) demás tramaLíneaAlta(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 pueden optimizarse altamente.

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

líneatrama(x0, y0, x1, y1) dx = abs(x1-x0) sx = x0 < x1 ? 1: -1 dy = -abs(y1 - y0) sy = y0 < y1 ? 1: -1 error = dx + dy  si bien es cierto trazar (x0, y0) si x0 == x1 && y0 == y1 romper e2 = 2 * error si e2 >= dy si x0 == x1 romper error = error + dy x0 = x0 + sx terminar si  si e2 <= dx si y0 == y1 romper error = 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 (utilizando 0,5 como umbral de error en lugar de 0, que se requiere para la rasterización de polígonos no superpuestos).

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 ráster de polígonos mapeados de textura. ^[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 principal, la variación Run-Slice realiza un bucle en sentido contrario. ^[5] Este método ha estado representado en varias patentes estadounidenses:

El algoritmo se ha ampliado a:

• Dibuja líneas de espesor arbitrario, un algoritmo creado por Alan Murphy en IBM. ^[6]
• Dibuje 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]

Ver también

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

Notas

1. Paul E. Negro. Diccionario de algoritmos y estructuras de datos, NIST . https://xlinux.nist.gov/dads/HTML/bresenham.html
2. Alegría, 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) (Reporte).
   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 una interpolación perspectivamente correcta en gráficos por computadora", publicado el 14 de abril de 1998, asignado a Canon KK 
5. "Edición especial del Libro negro de programación de gráficos de Michael Abrash: lo bueno, lo malo y lo ejecutado". www.phatcode.net . Consultado el 13 de febrero de 2024 .;
6. "Algoritmo de la línea de Bresenham modificado de Murphy". páginas de inicio.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 de mayo de 1978, páginas 5358-5366.)

Referencias

• Bresenham, JE (1965). «Algoritmo para el control informático de un trazador digital» (PDF) . Revista de sistemas IBM . 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 lineal de Bresenham", por Colin Flanagan
• Abrash, Michael (1997). Libro negro de programación de gráficos de Michael Abrash . Albany, Nueva York: Coriolis. págs. 654–678. ISBN 978-1-57610-174-2.Una versión muy optimizada del algoritmo en C y ensamblador para su uso en videojuegos con todos los detalles de su funcionamiento interno
• Zingl, Alois (2012). "Un algoritmo de rasterización para dibujar curvas" (PDF) ., La belleza de los algoritmos de Bresenham

Otras lecturas

• Tesis de Patrick-Gillesbanda, que contiene una extensión del algoritmo de dibujo lineal 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íneas mediante modificación del algoritmo de Bresenham, AS Murphy, IBM Technical Disclosure Bulletin, vol. 20, núm. 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 27 ​​de enero de 1964 -11- Algoritmo circular TR-02-286 IBM San Jose Lab

enlaces externos

• Edición especial del Libro negro de programación de gráficos de Michael Abrash: Capítulo 35: Bresenham es rápido y lo rápido es bueno
• El algoritmo de dibujo de líneas de Bresenham por Colin Flanagan
• Página del Instituto Nacional de Estándares y Tecnología sobre el algoritmo de Bresenham
• Información del 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