El 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 deben 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 suma, resta y desplazamiento de bits de enteros , todas las cuales son operaciones muy baratas en arquitecturas de computadora estándar . Es un algoritmo de error incremental . Es uno de los primeros algoritmos desarrollados en el campo de los gráficos por computadora.. Una extensión [ ¿cuál? ] al algoritmo original se puede utilizar para dibujar círculos .
Si bien los algoritmos como el de Wu también se utilizan con frecuencia en los gráficos por computadora modernos porque pueden admitir el antialiasing , la velocidad y la simplicidad del algoritmo de línea de Bresenham significa que sigue siendo importante. 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 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 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 en el laboratorio de desarrollo de IBM en San José. Se había conectado un trazador Calcomp a un IBM 1401 a través de la consola de la máquina de escribir 1407. [El algoritmo] estaba en producción en el verano de 1962, posiblemente un mes antes. Los programas en esos días 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 computación de Stanford. Se aceptó una descripción de la rutina del dibujo de líneas para su presentación en la convención nacional ACM de 1963 en Denver, Colorado. Fue un año en el que no se publicaron actas, solo la agenda de ponentes y temas en un número de Comunicaciones de la 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é felizmente y lo imprimieron en 1965.
El algoritmo de Bresenham se ha ampliado para producir círculos, elipses, curvas Bézier cúbicas y cuadráticas, así como versiones nativas anti-alias de las mismas. [2]
Método
Se utilizarán las siguientes convenciones:
- la parte superior izquierda es (0,0) de modo que las coordenadas de 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.
El algoritmo se presentará inicialmente solo para el octante en el que el segmento desciende y hacia la derecha ( y ), y su proyección horizontal es más largo 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 varios píxeles rasterizados.
El algoritmo de Bresenham elige el entero y correspondiente al centro del píxel más cercano al ideal (fraccional) y 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 extremos está dada por:
- .
Como conocemos la columna, x , la fila del píxel, y , se obtiene redondeando esta cantidad al número entero más cercano:
- .
La pendiente depende solo 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 y agregando repetidamente la pendiente.
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 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 superior a 0,5 , sabemos que la línea se ha movido hacia arriba un píxel, y que debemos incrementar nuestra y coordinar y reajustar el error para representar la distancia desde la parte superior del nuevo píxel - que se realiza restando uno error. [3]
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 forma típica pendiente-intersección en 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
La forma pendiente-intersección de una línea se escribe como
donde m es la pendiente y b es la intersección con el eje y. Esta es una función de solo x y sería útil escribir esta ecuación como una función tanto de x como de y. Usando la manipulación algebraica y el reconocimiento de que la pendiente es la "subida sobre la carrera" o luego
Dejando que esta última ecuación sea una función de xey, entonces se puede escribir como
donde están las constantes
Luego, la línea se define para algunas constantes A, B y C en cualquier lugar . Para cualquier no en la linea entonces . Todo lo relacionado con esta forma implica solo números enteros si xey son números enteros, ya que las constantes son necesariamente números enteros.
Como ejemplo, la línea entonces esto podría escribirse como . El punto (2,2) está en la línea
y el punto (2,3) no está en la línea
y tampoco el punto (2,1)
Observe que los puntos (2,1) y (2,3) están en lados opuestos de la línea y que f (x, y) se evalúa como positivo o negativo. Una línea divide un plano en mitades y el semiplano que tiene una f (x, y) negativa 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.
Algoritmo
Claramente, el punto de partida está en la línea
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).
Teniendo en cuenta que la pendiente es menor o igual a uno, ahora se presenta el problema de si el siguiente punto debe estar en o . Quizás intuitivamente, el punto debe 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 último, entonces el segundo. Para responder a esto, evalúe la función de la línea en el punto medio entre estos dos puntos:
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. ; en efecto, la coordenada y ha avanzado. De lo contrario, la línea ideal pasa a través o por encima del punto medio y la coordenada y no ha avanzado; en este caso elija el punto. ¡Esta observación es crucial de entender! El valor de la función de línea en este punto medio es el único determinante de qué punto debe elegirse.
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 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 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:
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:
Al igual que con el método del punto medio, si D es positivo, elija , de lo contrario elige .
Si se elige, el cambio en D será:
Si se elige el cambio en D será:
Si la nueva D es positiva, entonces es elegido, de lo contrario . Esta decisión se puede generalizar acumulando el error en cada punto posterior.
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 ninguna consecuencia.
Esto da como resultado un algoritmo que usa solo aritmética de números enteros.
plotLine (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 terminara si D = D + 2 * dy
Ejecutando este algoritmo para de (0,1) a (6,4) produce las siguientes diferencias con dx = 6 y dy = 3:
D = 2 * 3-6 = 0Bucle de 0 a 6 * x = 0: trazar (0, 1) , D≤0: D = 0 + 6 = 6 * x = 1: gráfica (1, 1) , D> 0: D = 6-12 = -6, y = 1 + 1 = 2, D = -6 + 6 = 0 * x = 2: trama (2, 2) , D≤0: D = 0 + 6 = 6 * x = 3: graficar (3, 2) , D> 0: D = 6-12 = -6, y = 2 + 1 = 3, D = -6 + 6 = 0 * x = 4: grafica (4, 3) , D≤0: D = 0 + 6 = 6 * x = 5: graficar (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 llenando cuadros de píxeles (cuadrados amarillos). Independientemente, la trama es la misma.
Todos los casos
Sin embargo, como se mencionó anteriormente, esto es solo para el octante cero, es decir, las líneas que comienzan en el origen con un gradiente entre 0 y 1, donde x aumenta exactamente 1 por iteración ey aumenta en 0 o 1.
El algoritmo se puede ampliar para cubrir gradientes 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 <0 yi = -1 dy = -dy terminara 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 terminara si
Al cambiar los ejes xey, una implementación para pendientes pronunciadas 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 terminara si D = (2 * dx) - dy x = x0 para y de y0 a y1 trama (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)si x0> x1 plotLineLow (x1, y1, x0, y0) demás plotLineLow (x0, y0, x1, y1) end if else if y0> y1 plotLineHigh (x1, y1, x0, y0) demás plotLineHigh (x0, y0, x1, y1) terminar si terminar si
En implementaciones de bajo nivel que acceden a la memoria de video directamente, sería típico que los casos especiales de líneas verticales y horizontales se manejen por separado, ya que pueden estar altamente optimizados.
Algunas versiones utilizan los principios de error incremental de enteros de Bresenham para realizar todos los trazos de línea de octante, equilibrando el error positivo y negativo entre las coordenadas xey. [2] Tenga en cuenta que el pedido no está necesariamente garantizado; en otras palabras, la línea puede trazarse de (x0, y0) a (x1, y1) o de (x1, y1) a (x0, y0).
plotLine (int x0, int y0, int x1, int y1) dx = abs (x1-x0); sx = x01: -1; ?> dy = -abs (y1-y0); sy = y01: -1; ?> err = dx + dy; / * valor de error e_xy * / while (verdadero) / * bucle * / plot (x0, y0); si (x0 == x1 && y0 == y1) romper; e2 = 2 * err; si (e2> = dy) / * e_xy + e_x> 0 * / err + = dy; x0 + = sx; finaliza si si (e2 <= dx) / * e_xy + e_y <0 * / err + = dx; 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 es necesario 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 raster de polígonos mapeados con texturas. [4] Los motores de procesamiento de software de mapas de altura de voxel 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:
5,815,163 | Método y aparato para dibujar cortes de línea durante el cálculo. | |
5.740.345 | Método y aparato para mostrar datos de gráficos por computadora almacenados en un formato comprimido con un sistema de indexación de color eficiente | |
5,657,435 | Ejecute el motor de dibujo de líneas de corte con capacidades de escalado no lineal | |
5,627,957 | Ejecute el motor de dibujo de línea de corte con capacidades de procesamiento mejoradas | |
5,627,956 | Ejecute el motor de dibujo de líneas de corte con capacidades de estiramiento | |
5,617,524 | Ejecute el motor de dibujo de líneas de corte con capacidades de sombreado | |
5,611,029 | Ejecute el motor de dibujo de línea de corte con capacidades de sombreado no lineal | |
5.604.852 | Método y aparato para mostrar una curva paramétrica en una pantalla de video. | |
5,600,769 | Ejecute el motor de dibujo de línea de corte con técnicas de recorte mejoradas |
Alan Murphy en IBM creó una extensión del algoritmo que maneja líneas gruesas. [5]
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ínea 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
- ^ Paul E. Black. Diccionario de algoritmos y estructuras de datos, NIST . https://xlinux.nist.gov/dads/HTML/bresenham.html
- ^ a b Zingl, Alois "Un algoritmo de rasterización para dibujar curvas" (2012) http://members.chello.at/~easyfilter/Bresenham.pdf
- ^ 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 .
- ^ [1] , "Aparato y método para realizar una interpolación de perspectiva correcta en gráficos por computadora", publicado el 31 de mayo de 1995
- ^ "Algoritmo de línea de Bresenham modificado de Murphy" . homepages.enterprise.net . Consultado el 9 de junio de 2018 .
Referencias
- Bresenham, JE (1965). "Algoritmo para el control informático de un plotter digital" (PDF) . Revista de sistemas de 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 gráfica 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 ensamblado 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
Otras lecturas
- La tesis de Patrick-Gilles Maillot es 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 del MICAD '87 sobre CAD / CAM y gráficos por computadora, página 591 - ISBN 2-86601-084-1 .
- Engrosamiento de línea por modificación del algoritmo de Bresenham , AS Murphy, IBM Technical Disclosure Bulletin, vol. 20, No. 12, mayo de 1978.
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 rápido es bueno
- El algoritmo de dibujo lineal de Bresenham de 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 simple para trazar líneas, círculos, elipses y curvas de Bézier