Algoritmos de implementación en rectas

La computación gráfica es una área de las Ciencias de las computación, con el objetivo de establecer los principios, las  técnicas y los algoritmos para la generación de imágenes por computador. Las imágenes generadas pueden ser en dos dimensiones (2D) o incluso modelos en tres dimensiones (3D).

Según el tipo de gráfico, se usan algoritmos especializados que permiten notables ventajas con respecto al resultado que se desea obtener, en el presente caso se mencionan los algoritmos que son utilizados para imágenes rasterizadas, las cuales permiten mostrar transiciones suaves de colores y sombras.

Los modelos abstractos que se generan en 3D son transformados en imágenes visibles a través de esquemas o algoritmos gráficos. Dentro de los algoritmos más relevantes en la computación gráfica encontramos el Algoritmo de Bresenham y el Analizador Diferencial Digital (DDA).

Analizador diferencial digital (DDA)

El analizador diferencial digital (DDA), también llamado a veces computadora de integración digital, es una implementación digital de un analizador diferencial. Es el hardware o el software usado para la interpolación lineal de variables sobre un intervalo entre principio y punto final. Los DDA se usan para la rasterización de líneas, triángulos y polígonos. En su realización más simple, el algoritmo DDA interpola valores en el intervalo calculando para cada x las ecuaciones.

x = x+1/m, y = y + m, donde  ?x = x – x, ?y = y – y y m = ?y/?x

?x = x – x y ?y = y – y y m = ?y/?x

Para entender mejor el algoritmo se mencionara el funcionamiento y los pasos generales que se ejecutan para llegar al resultado final.

Es necesario definir 2 puntos los cuales están compuestos cada uno por 2 valores, que llevados al plano cartesiano corresponden a X y Y, visto en una imagen de papel nuestro X es el ancho y Y es el alto, con respecto a un punto de referencia se ubican ambos puntos.

El objetivo es unir los dos puntos para obtener una recta (línea), este concepto abstracto es fácilmente entendible por los humanos, pero una máquina no entiende de conceptos, es aquí donde entra el algoritmo DDA, que se encarga de generar una sucesión de puntos finita que le brinda a la máquina las instrucciones para “dibujar” la respectiva línea.

DDA es usado principalmente porque calcula la “posición” de la siguiente coordenada X y Y a nivel de píxel, una vez se alcanza el punto final, se forma la imagen “recta” que es interpretada por nuestro cerebro como una línea.

El siguiente video brinda una explicación más gráfica, explícita y “técnica” del funcionamiento  del algoritmo.

Algoritmo de Bresenham

El Algoritmo de Bresenham es un algoritmo creado para dibujar rectas en los dispositivos gráficos rasterizados, como por ejemplo un monitor de computadora, el cual determina qué píxeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

Es un algoritmo preciso para la generación de líneas de rastreo que convierte mediante rastreo las líneas, al utilizar solo cálculos incrementales con enteros que se pueden adaptar para desplegar circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican las columnas de pixel.

Es considerado uno de los algoritmos más efectivos para dibujar líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente píxel a dibujar en la generación de una línea, se describe a continuación:

1. Dependiendo del valor que tome el Parámetro Constante P se evalúa y determina la coordenada a dibujar.
2. Calcular los parámetros que permiten decidir cuál será el próximo pixel a dibujar (Delta X, Delta Y y Constante P).
3. Dibujar el primer píxel correspondiente al extremo izquierdo de la línea (P1).
4. Trazar el píxel cuyo valor de Y de la línea de rastreo se aproxima más a la trayectoria de la línea. Se capturan los dos extremos de la línea  P1(Xo, Yo) y P2(Xf, Yf).
5.  Se desplaza una columna (incrementando la posición en X).
6. Punto inicial  P1(Xo, Yf).

(X+1,Y) para Constante P < 0

Sino (X+1,Y+1)

*El proceso anterior debe repetirse 4DeltaX veces.

El algoritmo de Bresenham es el encargado de  escanear las coordenadas, tomando en cuenta el valor incremental sumando o restando y, por lo tanto, se puede utilizar para dibujar círculos y curvas.

El siguiente video brinda una explicación más gráfica, explícita y “técnica” del funcionamiento  del algoritmo.

Diferencias entre los Algoritmos DDA y Bresenham

• DDA usa puntos flotantes mientras que el algoritmo de Bresenham usa puntos fijos.
• DDA redondea las coordenadas al entero más cercano, pero el algoritmo de Bresenham no lo hace.
• El algoritmo de Bresenham es mucho más preciso y eficiente que DDA.
• El algoritmo de Bresenham puede dibujar círculos y curvas con mucha más precisión que DDA.
• DDA usa multiplicación y división de ecuaciones, pero el algoritmo de Bresenham solo usa resta y suma.

Aplicaciones de los algoritmos gráficos

Algoritmo DDA

El algoritmo DDA se implementó en diferentes campos uno de estos fue en la aviación ya que gracias a su desarrollo los aviones podían ser guiados por un camino fijo que era marcado por el algoritmo el cual básicamente lo que realizaba era una línea recta desde un punto hasta el otro. En Irak se desarrolló un robot el cual por medio del algoritmo DDA permitía la movilización en línea recta de un robot que se encargaba de organizar las cajas en un almacén este proyecto fue presentado en la convención de tecnología en el año 2018. 

Algoritmo de Bresenham

Su implementación se dio en el ejército argentino el cual creó un simulador donde por medio del algoritmo de Bresenham podían conocer o disponer de la localización de un tanque enemigo y si tenían acceso a este para atacar de forma directa. Otra aplicación de este algoritmo es la construcción de un sistema para la impresión 3D ya que facilitaba la manipulación por parte del operario. También gracias al algoritmo desarrollado por Bresenham diferentes motores de videojuegos pudieron tener una remasterización en sus juegos optimizando los recursos de los computadores.

Aplicación sobre un modelo 3D

Para el caso de las aplicaciones en modelos 3D, previamente cargados con un fichero que contenga la información se puede llegar a los siguientes resultados:

Un listado de puntos, vértices y triángulos formados a partir de líneas, sumado a valores predeterminados de altura y ancho de imagen obtienen un modelado 3D de un rostro.

Autores: Jenny Catalina Sua Quimbayo, Jorge Andrés Olaya Valdés, Stefhany Alfonso Rincón, Juan Camilo Ávila Diaz, Michael López Sierra

Editor: Carlos Pinzón

Código: UCCG-9

Universidad: Universidad Central

Fuentes:

Torres, G., Curiel, A., Monroy, J. (s.f.). GRAFICACIÓN Apuntes Digitales. CIDECAME. http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro23/232_algoritmo_dda.html

adlab13.  (2016). Algoritmo de Bresenham. GRAFICA2016A. https://grafica2016a.wordpress.com/2016/02/16/algoritmo-de-bresenham/

Morales, V. (2017). Desarrollo de un controlador básico de impresión 3D.  Desarrollo de un controlador básico de impresión 3D (upv.es)

Guaycochea, L., Kaltman, J., Galán, V. (2018). Simulador de tiro de tanques: NeoNahuel II. REPOSITORIO INSTITUCIONAL DE LA UNLP. Documento_completo.pdf-PDFA.pdf (unlp.edu.ar)

Ciencias de la Computación. (2015). Universidad Nacional Autónoma de México. http://www.fciencias.unam.mx/docencia/horarios/presentacion/256495

Diferencia entre DDA y algoritmo de Bresenham. (s.f.). STREPHONSAYS.
https://es.strephonsays.com/dda-and-vs-bresenham-algorithm-5881

Algoritmo de Bresenham. (2020, 12 de Febrero). en Wikipedia.
https://es.wikipedia.org/wiki/Algoritmo_de_Bresenham

Señorito PI. (2018). Motor render desde 0 parte 1 dibujando líneas con el algoritmo de bresenham [Imágen]. Señorito PI: https://www.señoritopi.com/wp-content/uploads/2018/08/render_triangulos-768x768.png

Edwin Duque. (1 de febrero 2019). Algoritmo para trazado de línea por computador DDA. [Video]. YouTube. https://youtu.be/5EAoxZGI5Y8

Edwin Duque. (1 de febrero 2019). Algoritmo para trazado de línea por computador Bresenham. [Video]. YouTube. https://youtu.be/2_BCYD_FwII

Moviendo la camara y Apuntando hacia un punto con Cambios de base. (2018). 
https://www.xn--seoritopi-m6a.com/motor-render-desde-0-parte-1-dibujando-lineas-con-el-algoritmo-de-bresenham/