Algoritmo de Bresenham

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 coordenados: 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.

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 pí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 le ha supuesto idealizado como una caja mucho mayor que el grosor de la línea ideal).

Con base en dicho porcentaje, 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 ven.

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 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 consideración, es que los valores de las medidas de ancho o alto, pueden ser:

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

Bresenham, no realizó una descripción clara del algoritmo, sino 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).

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).

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 o 0 en cada ciclo, 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). Así 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 que 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 media del eje 'Y' en mayor medida que para el eje 'X'.

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) entonces
          IncYi = 1
      SiNo
          dY = -dY
          IncYi = -1
      Fin Si
    
      Si (dX >= 0) entonces
          IncXi = 1
      SiNo
          dX = -dX
          IncXi = -1
      Fin Si
    
      // 2 - Incrementos para las secciones con avance recto:
      Si (dX >= dY) entonces
          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) entonces
              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) y (Y = Y2) // NOTA: La condición de 'Repetir Hasta' se debe cambiar por (X <> X2) o (Y <> Y2) si se elige en su lugar 'Repetir Mientras'
   Fin funcion

NOTA: Falta añadir imágenes

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.

• 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