Algoritmo de Bresenham

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Ejemplo de aplicación del algoritmo de Bresenham.

El Algoritmo de Bresenham es un método rápido para el trazado de líneas en dispositivos gráficos, cuya cualidad más apreciada es que solo realiza cálculos con enteros.

Se puede adaptar para rasterizar también circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican columnas de pixel.

Actualmente se usa el nombre de algoritmos de Bresenham a toda una familia de algoritmos basado en modificaciones o ampliaciones del original aquí descrito.

Introducción[editar]

El trazador rotatorio Calcomp 565.

El algoritmo inicialmente fue desarrollado por Jack Elton Bresenham al comienzo del verano de 1962, para dibujar sobre un plóter de Calcomp, operado desde un IBM. Por aquella época era común compartir libremente los programas, y en la empresa era normal que otros compañeros dispusieran de copias. No fue el propio Bresenham quien publicó su algoritmo, sino otros que le pidieron permiso para presentarlo en su nombre en la convención naconal de ACM, en Denver (Colorado) en 1963. Y en 1965 fue impreso por vez primera.

Cabe señalar que los plóter de Calcomp, fueron de los primeros dispositivos con salida gráfica a la venta, allá por 1959.

El algoritmo, finalmente ha encontrado un uso masivo en los gráficos de ordenador, debido a su velocidad y sencillez. También es notable la no necesidad de una unidad de coma flotante para realizar los cálculos necesarios.

Problemática del trazado de las líneas rectas[editar]

Al trazar una línea recta sobre papel con un lápiz, no existen impedimentos para colocar una regla y seguir una línea completamente recta.

En cambio cuando se opera sobre un sistema mapeado (como es la propia representación pixelada) en filas y columnas (cuadriculado), una línea siempre seguirá un trazado imperfecto, ya que la propia línea imaginaria trazada entre dos puntos, (excepto para las líneas horizontales y verticales), siempre cortará los cuadrados por donde pase, dividiendo al punto mínimo en dos áreas de diferente tamaño.

Sobre una rejilla de 7x11, se observa la línea ideal trazada en rojo, se perciben los errores al seguir las líneas en verde. Los cuadros marcados en amarillo, serían una posible solución de la línea.

Es decir el trazado de una línea sobre un soporte mapeado donde forzosamente debe ocuparse como unidad mínima un cuadro del mapa como equivalente de un punto siempre será una aproximación de la línea ideal y por tanto siempre contiene errores. Errores que son la consecuencia del paso de valores contínuos a valores discretos, el paso de lo analógico a lo digital.

La aproximación del dibujado de los puntos que describen la línea presenta dos claros problemas:

  • Qué puntos pasan por la recta (en lo sucesivo, diremos píxeles).
  • De los puntos que pasen por la recta, cuáles deben dibujarse.


Qué puntos pasan por la recta[editar]

Dados dos puntos que describen el punto inicial y final de la recta, se conoce las medidas básicas de la línea, ancho y alto que abarca la línea.

Un modo sencillo de saber cuáles pasan por la línea consiste en dividir una medida entre la otra. Por ejemplo si la línea queda descrita por los dos siguientes puntos cordenados: G3-C9 restando el valor inicial, del valor final para cada dimensión, obtenemos las medidas en dichas dimensiones respectivamente. Sobre el eje vertical tendremos: C-G = -4 y sobre el eje horizontal tendremos: 9-3 = 6

Ahora sabremos que por cada punto que avance sobre la vertical debe avanzar 1'5 sobre la horizontal. Aunque 1'5 sea una medida cómoda, trabajar con decimales cuando operamos sobre unidades enteras, es parte del problema.

Cuáles se deben dibujar[editar]

Es evidente que en función del grosor de la línea, tocará a más o menos píxeles a lo largo de la misma. Supongamos que la línea ideal es mucho más fina que la unidad del punto (píxel).

La solución para cuáles dibujar, podría optarse por iluminar cada opíxel que toca al trazarse la línea ideal, también podría optarse por iluminar aquellos píxeles que queden cortados por un determinado porcentaje del área de cada píxel (al que se la supuesto idealizado como una caja mucho mayor que el grosor de la línea ideal).

En base a dicho percentaje, pueden darse diferentes artefactos... si la línea pasa muy cerca de la esquina donde se tocan 4 píxeles, podrían quedar huecos en la línea si no se dibujan, o quedar muy ancha la línea si se dibujan.

Estado del arte previo[editar]

El problema existe desde la afamada cuadratura del circulo (que es un problema clásico de geometría), pero en este artículo nos ceñimos exclusivamente a la problemática gráfica.

Hasta la fecha aunque se trabajaba con cuadrículas, los trazados solían hacerse con maquinaria analógica, por lo que los trazados, simplemente solían discurrir los límites que un brazo mecánico permitía, ya fueran estos límites líneas rectas o curvas y que en su movimiento arrastraban algún tipo de pincel, o un sistema impulsado que escupe la pintura o tinta.

El algoritmo de Bresenham, por tanto encabeza los algoritmos para el dibujado en los llamados gráficos vectoriales, que requieren básicamente líneas y arcos.


Descripción[editar]

Antes de entrar en detalles de su descripción entramos en algunas consideraciones que servirán para entender con facilidad el porqué de cada cosa del algoritmo.

Consideraciones previas[editar]

Trazado de una simple línea sobre un octante, reflejando la línea ideal y la línea que se obtiene con el algoritmo.

Dados dos puntos y obtenido la distancia en el eje vertical y horizontal que los separa, se utilizan dichos valores para sobre uno de los ejes suponer un bucle de avance unitario y sobre el otro eje, preparar otro bucle anidado dentro del primero y cuyo avance es relativo, esto es, a veces avanza una unidad y a veces no.

Conviene también entender que la línea puede tener cualquier orientación. Al caso conviene considerar un círculo e imaginar el centro como el punto inicial. Y el punto final, considerar situarlo en cualquier punto que pase por la línea del círculo. Es decir estamos definiendo para cualquier línea así trazada un radio idéntico, pero que en función del ángulo descrito por la línea trazada (o a trazar) respecto de la normal varían en ancho y alto.

Una vez considerado el círculo, se observa que básicamente puede ser subdividido en octantes (8 partes iguales). Basándonos en que en para cada octante, la medida vertical es menor o igual que la horizontal, más las consideraciones de valores positivos y negativos para cada eje (2x4=8 posibilidades). Resumiendo todas las líneas caen en una de 8 posibilidades distinta (aparte del punto, cuando ambos puntos ocupan la misma posición). Véase dichas características en la imagen adjunta más abajo.



Una última considereación, es que los valores de las medidas de ancho o alto, pueden ser:

  • Mayor que 0.
  • De valor 0.
  • Menor que 0.

Descripción del algoritmo[editar]

Bresenham, no realizó una descripción clara del algoritmo, si no tan solo dejó comentarios sobre el código máquina que escribió y dado lo peculiar de dicho lenguaje hace difícil de interpretar correctamente sin un conocimiento expreso del mismo. Por lo que la descripción que procede es la interpretación del código y ampliado a una generalización para todos los octantes.

Es probable que no alcance la explicación para terminar de entender por completo el algoritmo, pero con el pseudocódigo y un ejemplo paso a paso, viéndolo operar, se acaba de comprender.

La primera consideración es medir la distancia de la línea para cada eje. Esto es, la distancia que separa ambos puntos que definen los límites de la línea.

Una vez conocida la distancia que se va a recorrer en cada eje, se trata de saber cual de los dos es la medida mayor. Así el eje de mayor medida avanzará siempre una unidad.

El trazado se realiza sobre un bucle, elegido para el eje de mayor medida hallado en el paso previo. Y en cada ciclo (el eje de mayor medida) avanzará siempre una unidad en la dirección hacia el punto final en dicho eje.

En cambio para el otro eje, el avance será a veces una unidad y a veces cero. Esto es, cuando recorra un tramo 'recto' el avance será cero, y cuando recorra un tramo 'inclinado' el avance será una unidad.

Son básicamente dos problemas a resolver:

  • Valores de avance según el ángulo de la recta (el octante donde se localiza la línea).
  • Avance específico para el eje menor (solución de Bresenham).

Valores de avance según el octando donde cae la línea[editar]

Repartición de los octantes alrededor del círculo y asignación de los valores de incremento que los ejes 'x' e 'y', tomarán en cada octante.

Los valores de avance se calculan antes de comenzar el bucle, puesto que ya entonces se conoce cual de las medidas es la de mayor recorrido.

Las menciones al avance de una unidad, tanto para uno como otro eje, también son calculados con anterioridad al bucle una vez conocidas las medidas.

A tales efectos, observando la imagen previa (del círculo con los octantes), se advierte que en función del ángulo que tenga la línea, los valores de incremento (avance) caerán en positivo o negativo tanto para el eje 'x' como al eje 'y'. Al restar el punto final, del punto inicial, obtenemos valores positivos o negativos (o valor 0, que describiría una recta vertical u horizontal, o un punto si ambos valen 0).

Solución de Bresenham para el avance específico del eje menor[editar]

Si el bucle itera sobre el eje de mayor medida (ver imagen debajo para determinar esto) con la unidad, es claro que el otro eje, o bien mide lo mismo o menos (incluso 0), luego su avance puede ser 1 ó 0 en cada cilo, esto es 'inclinado' o 'recto', valor de incremento que debe ser actualizado en cada ciclo.

La solución de Bresenham, trata sobre cuando aplicar el avance unitario o cero, para el eje de menor distancia, y es la parte que se describe ahora (la explicación viene dada por comodidad (y por simplicidad) para un solo octante donde ambas medidas son positivas, es decir para el octante marcado en la figura como nº1 (la numeración de los octantes es arbitraria, puede elegirse indistintamente, según convenga al código si se quieren usar numerados)):

Los 8 octantes en que se subdivide el círculo, se clasifican a su vez en dos grupos. Aquellos en los que cualquier línea trazado en ellos (en el octante), da como resultado que la altura (h) es mayor que la anchura (w) y los que no. Excepto las 4 diagonales donde 'w' y 'h' valen lo mismo.

Sean dX y dY la distancias que separan los puntos extremos de la línea sobre cada eje, y 'e' la relación entre el mayor y el menor (e = dX/dY). Entonces, para cada punto se verifica que el eje mayor aumenta 1 y el eje menor 'e'. Pero 'e' es un valor decimal, la decisión de cuando se toma un entero y cuando no, se basa en la acumulación de los decimales, cuando supera uno entero, se dibuja y se resta a dicho valor 1. Si bien esperar a que supere el valor 1, lo aleja del centro ideal de la línea y por ello se toma como valor más cercano al centro, el valor que se acerca en tanta cantidad como se aleja del centro... es decir el valor 0'5.

El valor de 'e' (de la división) no es un entero (salvo caso de una recta o diagonal). Asi los valores decimales son considerados como un 'error', que al inicio vale 0 y que luego en cada ciclo se le aumenta el valor de 'e', si el valor de 'error' es superior a 0'5, el valor unitario para el eje menor será en este caso 1, y se resta al 'error' global 1, si no el valor unitario para este ciclo será 0.

Para dejar atrás los valores decimales, se consideran dX y dY sin la división, mediando otros valores que en cada caso de avance unitario suman uno u otro.

En la siguiente imagen (a la derecha) se determina visualmente qué todas las líneas que caigan en los octantes rellenados de negro, el eje de mayor media será 'X', las líneas que caigan en los octantes blancos tiene la meddia del eje 'Y' en mayor medida que para el eje 'X'.


Pseudocódigo del algoritmo[editar]

El algoritmo para todos los octantes sería el siguiente:

   Funcion LineaBresenham( X1, Y1, X2, Y2)
      // 0 - Distancias que se desplazan en cada eje
      dY = (Y2 - Y1)
      dX = (X2 - X1)
    
      // 1 - Incrementos para las secciones con avance inclinado
      Si (dY >= 0) luego
          IncYi = 1
      Sino
          dY = -dY
          IncYi = -1
      Fin si
    
      Si (dX >= 0) luego
          IncXi = 1
      Sino
          dX = -dX
          IncXi = -1
      Fin si
    
      // 2 - Incrementos para las secciones con avance recto:
      Si (dX >= dY) luego
          IncYr = 0
          IncXr = IncXi
      Sino
          IncXr = 0
          IncYr = IncYi
    
          // Cuando dy es mayor que dx, se intercambian, para reutilizar el mismo bucle.
          // ver octantes blancos en la imagen encima del código
          k = dX: dX = dY: dY = k
      Fin si
    
      // 3  - Inicializar valores (y de error).
      X = X1: Y = Y1
      avR = (2 * dY)
      av = (avR - dX)
      avI = (av - dX)
    
      // 4  - Bucle para el trazado de las línea.
      Hacer
          DibujarPixel(X, Y, Color) // Como mínimo se dibujará siempre 1 píxel (punto).
          Mensaje(av + " ") // (debug) para ver los valores de error global que van apareciendo.
          Si (av >= 0) luego
              X = (X + IncXi)     // X aumenta en inclinado.
              Y = (Y + IncYi)     // Y aumenta en inclinado.
              av = (av + avI)     // Avance Inclinado
          Sino
              X = (X + IncXr)     // X aumenta en recto.
              Y = (Y + IncYr)     // Y aumenta en recto.
              av = (av + avR)     // Avance Recto
          Fin si
      Repetir hasta que (X = X2) // NOTA: La condición de 'Repetir Hasta', se debe cambiar si se elige 'Repetir Mientras'
   Fin funcion

NOTA: Falta añadir imágenes

Seguimiento con un ejemplo[editar]

El mejor modo de entender como funciona el algoritmo es servirse de un ejemplo, trazando una línea entre dos puntos, y luego remarcar como va operando el algoritmo.


Véase también[editar]

Referencias[editar]

Bibliografía[editar]

  • Watt, Alan (2000). «Rasterizing edges». 3D Computer Graphics (3ª edición). p. 184. ISBN 0-201-39855-9. 
  • Miguel Ángel Rodríguez-Roselló, Ediciones Anaya Multimedia (1992) "8088-8086/8087 Programación ENSAMBLADOR en entorno MS DOS" (5ª edición). págs: 821-826 ISBN 9788476141281 ISBN10: 84-7614-128-9

Enlaces externos[editar]

Wikilibros