Algoritmo de la línea de Bresenham: Representación eficiente de líneas con píxeles perfectos para visión por computadora

Por Fouad Sabry

¿Qué es el algoritmo de líneas de Bresenham?

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 línea cercana. aproximación a una línea recta entre dos puntos. Se usa comúnmente para dibujar líneas primitivas en una imagen de mapa de bits, ya que solo usa suma, resta y desplazamiento de bits de números enteros, todas las cuales son operaciones muy baratas en arquitecturas informáticas 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 de punto medio para dibujar círculos.

Cómo se beneficiará

(I) Información y validaciones sobre los siguientes temas:

Capítulo 1: Algoritmo de líneas de Bresenham

Capítulo 2: Algoritmo de dibujo de líneas

Capítulo 3: Algoritmo de líneas de Xiaolin Wu

Capítulo 4: Analizador diferencial digital (algoritmo gráfico)

Capítulo 5: Algoritmo del círculo del punto medio

Capítulo 6: Regla de la cadena

Capítulo 7: Derivada

Capítulo 8: Pendiente

Capítulo 9: Cálculo diferencial

Capítulo 10: Trazado de algoritmos para el conjunto de Mandelbrot

(II) Respondiendo al público Preguntas principales sobre el algoritmo de la línea de Bresenham.

(III) Ejemplos del mundo real para el uso del algoritmo de la línea de Bresenham en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o la información básica para cualquier tipo de algoritmo de línea de Bresenham.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 5 may 2024

Vista previa del libro

Capítulo 1: Algoritmo de línea de Bresenham

El algoritmo de líneas de Bresenham es un procedimiento de dibujo lineal que identifica los puntos ráster n-dimensionales que deben seleccionarse para aproximar una línea recta entre dos puntos. Se usa con frecuencia para dibujar primitivas de línea en una imagen de mapa de bits (por ejemplo, en la pantalla de una computadora), ya que solo requiere suma de enteros, resta y desplazamiento de bits, que son operaciones bastante económicas en arquitecturas de computadoras históricamente prevalentes. Es uno de los primeros algoritmos creados en el campo de los gráficos por computadora y es un algoritmo de error incremental. Se puede utilizar una modificación del algoritmo original para crear círculos.

Si bien las técnicas con capacidad de antialiasing, como el algoritmo de Wu, también se utilizan ampliamente en los gráficos por computadora modernos, el algoritmo de línea de Bresenham sigue siendo importante debido a su velocidad y simplicidad. El algoritmo se utiliza en plotters y chips gráficos de tarjetas gráficas contemporáneas. También está presente en numerosas bibliotecas de gráficos de software. Debido a la simplicidad del algoritmo, se implementa con frecuencia en el hardware gráfico o firmware de las tarjetas gráficas actuales.

Hoy en día, el término Bresenham se refiere a una familia de algoritmos que amplían o alteran el enfoque original de Bresenham.

El algoritmo de línea de Bresenham lleva el nombre de Jack Elton Bresenham, el empleado de IBM que lo creó en 1962. En 2001, Bresenham publicó:

Estaba trabajando en el laboratorio de computación del laboratorio de desarrollo de IBM en San José. A través del terminal de la máquina de escribir 1407, se conectó un plotter Calcomp a un IBM 1401. El algoritmo se utilizó en producción en el verano de 1962, o posiblemente un mes antes. Calcomp (Jim Newland y Calvin Heft) tenía copias de los programas porque las corporaciones los compartían abiertamente en ese momento. Cuando regresé a Stanford en el otoño de 1962, doné una copia a la biblioteca del centro de computación de Stanford. En la convención nacional de la ACM de 1963 en Denver, Colorado, se aceptó una descripción de la rutina de dibujo lineal para su presentación. En ese año, solo la agenda de ponentes y temas se publicó en un número de Comunicaciones de la ACM. Después de mi presentación, alguien del IBM Systems Journal preguntó si podían publicar el trabajo. Acepté gustosamente y se publicó en 1965.

El enfoque 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 curvas.

Se utilizarán las siguientes convenciones:

La coordenada superior izquierda es (0,0), de modo que las coordenadas de los píxeles crecen en las direcciones derecha y hacia abajo (por ejemplo, el píxel en (7,4) está directamente encima del píxel en (7,5)), mientras que la coordenada inferior derecha es (1,1).

Los centros de los píxeles tienen coordenadas enteras.

Los extremos de la línea son los píxeles en (x_{0},y_{0}) y (x_{1},y_{1}) , donde la primera coordenada representa la columna y la segunda coordenada representa la fila.

El algoritmo se presentará inicialmente solo para el octante en el que el segmento va hacia abajo y hacia la derecha ( x_{0}\leq x_{1} y y_{0}\leq y_{1} ), y su proyección horizontal x_{1}-x_{0} es más larga que la proyección vertical y_{1}-y_{0} (la recta tiene una pendiente positiva menor que 1).

En este octavo, para cada columna x entre x_{0} y x_{1} , la técnica calcula exactamente una fila y que contiene un píxel de la línea, mientras que cada fila entre y_{0} y y_{1} puede contener varios píxeles rasterizados.

La técnica de Bresenham selecciona el entero y que corresponde al centro del píxel más cercano al ideal (fraccionario) y para la misma x; En las columnas sucesivas, y puede permanecer igual o aumentar en 1. La ecuación general de la recta que pasa por los extremos es:

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

Como tenemos la columna x, podemos obtener la fila del píxel, y, redondeando este número al entero más cercano:

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

.

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

En la práctica, el algoritmo no mantiene la información de las coordenadas y, que aumenta en m = ∆y/∆x cada vez que la x aumenta en uno; Mantiene un límite de error en cada nivel, que muestra la distancia entre (a) el punto donde la línea sale del píxel y (b) el borde superior del píxel.

Este valor se establece primero en {\displaystyle y_{0}-0.5} (debido al uso de las coordenadas centrales del píxel), cada vez que la coordenada x se incrementa en uno, se agrega m.

Siempre que la inexactitud sea mayor que 0.5, somos conscientes de que la línea se ha movido un píxel hacia arriba, debemos incrementar la coordenada y y restar uno al error para reflejar la distancia desde la parte superior del nuevo píxel.

El algoritmo de Bresenham debe derivarse en dos pasos. La primera etapa consiste en traducir la forma pendiente-intersección de la ecuación de una recta en una forma diferente, y luego usar esta nueva ecuación para dibujar una recta basada en el concepto de acumulación de errores.

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

y=f(x)=mx+b

donde m es la pendiente y b es la intersección con el eje y.

Debido a que esta es una función de solo x , no puede simbolizar una línea vertical.

Por lo tanto, sería útil hacer que esta ecuación se escriba como una función de ambos x y y , capaz de dibujar líneas en cualquier ángulo.

El ángulo (o pendiente) de una recta se puede expresar como elevación sobre corrida o \Delta y/\Delta x .

Luego, usando operaciones algebraicas,

{\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 una función de x y y , también se puede escribir como

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

donde se encuentran 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}

A continuación, se define la línea para algunas constantes A , B y C en cualquier lugar f(x,y)=0 .

Es decir, para cualquiera que (x,y) no esté en la línea, f(x,y)\neq 0 .

Esta forma involucra solo números enteros si x y y son enteros, ya que las constantes A , B , y C se definen como números enteros.

Por ejemplo, la línea {\textstyle y={\frac {1}{2}}x+1} podría escribirse como f(x,y)=x-2y+2 .

El punto (2,2) está en juego.

f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0

Además, el punto (2,3) no está en la línea.

f(2,3)=(2)-2(3)+2=2-6+2=-2

Ninguno de los dos es el punto (2,1)

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úan como positivos o negativos.

Una recta divide un plano en mitades y el semiplano que tiene un negativo f(x,y) se puede llamar semiplano negativo, la otra mitad se conoce como semiplano positivo.

Esta observación es crucial para el resto de la derivación.

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

f(x_{0},y_{0})=0

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

Teniendo en cuenta que la pendiente es como máximo 1 , el problema ahora se presenta en cuanto a si el siguiente punto debe estar en (x_{0}+1,y_{0}) o (x_{0}+1,y_{0}+1) .

Tal vez intuitivamente, el punto debería elegirse en función de cuál está más cerca de la línea en x_{0}+1 .

Si está más cerca del punto anterior, agréguelo en la línea, si es el segundo, entonces el segundo.

Para solucionar esto, evalúe la función de línea entre estas dos ubicaciones:

{\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 (x_{0}+1,y_{0}+1) ; En consecuencia, la coordenada y se ha movido hacia adelante.

De lo contrario, la recta óptima está situada en la mitad o por encima de ella, además, la coordenada y no se ha movido; en este caso elija el punto (x_{0}+1,y_{0}) .

En este punto medio, el valor de la función de recta es el único determinante de qué punto debe elegirse.

La figura de la derecha representa el punto seleccionado (2,2) en azul, junto con dos puntos potenciales (3,2) en verde (3,3). El punto negro (3, 2,5) se encuentra en el medio de los dos puntos candidatos.

En lugar de evaluar f(x,y) en los puntos medios, alternativamente, se puede emplear la