Algoritmo de dibujo lineal: Dominar técnicas para la representación de imágenes de precisión

Por Fouad Sabry

¿Qué es el algoritmo de dibujo lineal?

En gráficos por computadora, un algoritmo de dibujo lineal es un algoritmo para aproximar un segmento de línea en medios gráficos discretos, como pantallas basadas en píxeles y impresoras. En tales medios, el dibujo lineal requiere una aproximación. Los algoritmos básicos rasterizan las líneas en un color. Una mejor representación con múltiples gradaciones de color requiere un proceso avanzado, suavizado espacial.

Cómo se beneficiará

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

Capítulo 1: Algoritmo de dibujo lineal

Capítulo 2: Algoritmo lineal de Bresenham

Capítulo 3: Algoritmo lineal de Xiaolin Wu

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

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

Capítulo 6: Gráficos por computadora 2D

Capítulo 7: Geometría digital

Capítulo 8: Transformada de Hough

Capítulo 9: Transmisión de rayos

Capítulo 10: Función gaussiana

(II) Respondiendo a las principales preguntas del público sobre el algoritmo de dibujo lineal.

(III) Ejemplos del mundo real para el uso del algoritmo de dibujo lineal 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 información básica para cualquier tipo de algoritmo de dibujo lineal.

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

Vista previa del libro

Capítulo 1: Algoritmo de dibujo lineal

Un algoritmo de dibujo lineal en gráficos por ordenador es un algoritmo que se aproxima a un segmento de línea en medios gráficos discretos, como pantallas e impresoras basadas en píxeles. En tales superficies, el dibujo lineal requiere una aproximación (en casos no triviales). Los algoritmos simples rasterizan las líneas en un solo tono. El suavizado espacial es un procedimiento avanzado que es necesario para una representación más precisa de numerosas gradaciones de color.

En medio continuo, dibujar una línea no requiere un algoritmo. Por ejemplo, los osciloscopios de rayos catódicos hacen líneas y curvas utilizando fenómenos analógicos.

La siguiente es una lista parcial de algoritmos para el dibujo lineal:

Algoritmo ingenuo

Analizador diferencial digital (algoritmo gráfico): comparable al algoritmo ingenuo de dibujo lineal, con algunas ligeras diferencias.

El algoritmo de línea de Bresenham está ajustado para emplear solo sumas (es decir, sin división o multiplicación) y evita los cálculos de punto flotante.

El algoritmo de línea de Xiaolin Wu, que puede hacer anti-aliasing espacial, parece complicado debido a la fluctuación del brillo a lo largo de la línea; Sin embargo, este efecto se puede minimizar significativamente compensando previamente los valores de píxel para la curva gamma de la pantalla de destino, por ejemplo, Out = In (1/2.4).

Fórmula de Gupta-Spruill

Esbozar directamente la ecuación que determina la línea es el método más simple de cribado.

dx = x2 − x1

dy = y2 − y1

para x de x1 a x2 do

y = y1 + dy × (x − x1) / dx

parcela (x, y)

Es aquí donde ya se han ordenado los puntos para que x_{2}>x_{1} .

Este algoritmo funciona bien cuando {\displaystyle dx\geq dy} (es decir, el gradiente es menor o igual que 1), pero si dx

El algoritmo primitivo para dibujar líneas es ineficiente y, en consecuencia, lento en una computadora digital. La cantidad de operaciones y el uso de cálculos de punto flotante contribuyen a sus ineficiencias. En cambio, se favorecen algoritmos como el algoritmo de línea de Bresenham o el algoritmo de línea de Xiaolin Wu.

Basado en el algoritmo de línea de Bresenham, el algoritmo de Gupta-Sproll agrega antialiasing.

El pseudocódigo para una forma optimizada del algoritmo de Gupta-Sproull es el siguiente:

DrawLine(x1, x2, y1, y2) {

x = x1;  y = y1;  dx = x2 − x1;  dy = y2 − y1;  d = 2 * dy − dx; Discriminador

Distancia euclidiana del punto (x,y) a la recta (con signo)

D = 0;  Distancia euclidiana entre puntos (x1, y1) y (x2, y2)

longitud = sqrt(dx * dx + dy * dy);  sin = dx / longitud;  cos = dy / longitud;  while (x <= x2) {

IntensifyPixels(x, y − 1, D + cos);  IntensifyPixels(x, y, D);  IntensifyPixels(x, y + 1, D − cos);  x = x + 1

if (d <= 0) {

D = D + pecado;  d = d + 2 * dy;  } else {

D = D + seno − cos;  d = d + 2 * (dy − dx);  y = y + 1; } }}

La función IntensifyPixel(x,y,r) toma una transformación de línea radial y establece la intensidad del píxel (x,y) con un polinomio cúbico cuyo valor depende de la distancia del píxel r a la línea.

{Fin del capítulo 1}

Capítulo 2: 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