Este algoritmo se encarga de determinar los puntos que deben ser usados en un raster n-dimensional con el fin de obtener una aproximacion lo mas cercana a una linea recta entre dos puntos. Su principal caracteristica es realizar calculos con los numeros enteros.


Bresenham ejemplo

Algo de historia…

Jack Elton Bresenham desarrollo este algoritmo en 1962 para IBM, con el fin de poder dibujar sobre un ploter de Calcomp (es de los primeros dispositivos con salida grafica que estuvo a la venta). El uso libre de copias de los programas entre empleados de la misma empresa permitio que algunos compa;eros de Bresenham le pidieran permiso para presentarlo en nombre de el en una convencion de la ACM que se realizaria en Denver (CO) en 1963, a lo cual acepto y para 1965 salio impreso el paper por primera vez.
El algoritmo de Bresenham fue extendido con el fin de no solo producir lineas, si no tambien circulos.

Algoritmo

Podemos trazar una linea recta con un lapiz en un pedazo de papel sin problemas, sin preocupaciones de como la podemos representar, pero si estamos en un sistema que consiste de pixeles en donde la minima unidad que podemos pintar es un pixel, representar nuestra linea se vuelve algo complejo pues ya no va a ser una linea perfecta y adicionalmente tenemos que tomar la decision de que pixeles debemos pintar con el fin de que se parezca lo mejor posible a la linea imaginaria que deseamos hacer.

Ahora bien, de que manera determinamos que pixeles pintar?

Consideremos el proceso de conversion para lineas con pendiente positiva 0 < m < 1, comenzando desde el punto mas a la izquierda de la linea en cuestion, y mediante un proceso secuencial vamos a ir mirando que pixel pintar en la siguiente columna (esto se determina mirando que pixel esta mas cerca a la linea trazada). Para lo ultimo, es necesario que que realicemos un muestreo en x y en y (pueden ser los valores medios de cada pixel) con el fin de obtener otra cuadricula y asi facilitar la determinacion de que pixel esta mas cerca para un punto en especifico.

Comencemos asumiendo que el pixel que acabamos de pintar esta en la coordenada




y ahora tenemos que decidir que pixel pintar, entre


Es decir, tendriamos algo como se muestra en la siguiente imagen


Bresenham trazado

Ahora, calculemos la coordenada de y de la linea en la columna de los pixeles x_k + 1



De ahi obtenemos d_1 y d_2 realizando aritmetica sobre la ecuacion de la linea presentada anteriormente




La diferencia entre las dos separaciones entonces es



Para definir un parametro de decision p_k para la iteracion k en el algoritmo, se obtiene si se reorganiza la ecuacion de tal manera que solo se tengan que realizar calculos enteros. Esto se logra expresando la pendiente m, segun su definicion, como la division entre la diferencia de y y la diferencia de x, asi




Con esto, el signo de p_k es igual que el de la diferencia entre d_1-d_2, por lo tanto podemos definir lo siguiente



Por ultimo, si intentamos buscar el parametro para pasos siguientes podemos expresar p_k+1 como sigue



Entonces de esta manera ponemos saber que pixeles vamos pintando con el uso de operaciones que no requieren divisiones, y en donde se pueden definir facilmente los parametros.

1
2
3
4
5
6
7
8
9
10
11
// Ensure that x0 <= x1 holds.
void lineBresenham( int x0, int y0, int x1, int y1 ) {
  int dx = abs(x1-x0);
  int dy = abs(y1-y0);
  int p = 2*dy - dx;
  for( int x = x0, y = y0; x <= x1; x++ ) {
    // Draw the point (x, y)
    if( p < 0 ) p = p + 2*dy;
    else        p = p + 2*(dy-dx), y = y + 1;
  }
}

Bibliografia