Algoritmo de Bresenham y Algortimo de DDA

Algoritmo de Bresenham

El algoritmo de Bresenham, desarrollado por Bresenham (1965), es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo un monitor de computadora, que determina qué pixeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

El algoritmo busca cual de dos pixeles es el que está más cerca según la trayectoria de la línea.

Es un algoritmo preciso para la generación de lineas de ratreo 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 columnas de pixel.

Algoritmo:

Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1.

Las posiciones de pixel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.

Si se inicia desde el extremo izquierdo (x0,y0) de una línea determinada, se pasa a cada columna sucesiva y se traza el pixel cuyo valor de y se aproxima más a la trayectoria de la línea de rastreo.

Si suponemos que se debe desplegar el pixel en (xk, yk), a continuación se necesita decidir que pixel se debe desplegar en la columna xk+1.

Las alternativas son los pixeles (xk+1,yk), y (xk+1,yk+1).

Al realizar el muestreo en la posición xk+1 designamos la separación de pixeles verticales de la trayectoria de la línea matemática como d1 y d2.

Codificación a color del Algoritmo de Bresenham:

Codificación en texto plano del Algoritmo de Bresenham:

void LineasBresenham( float red, float green, float blue, int x0, int y0, int x1, int y1 )
{
 int x, y, dx, dy, xEnd, p, incE, incNE;
 dx = abs(x1 - x0);
 dy = abs(y1 - y0);
 p = 2*dy - dx;
 incE = 2*dy;
 incNE = 2*(dy-dx);

 /* determinar que punto usar para empezar, cual para terminar */
 if (x0 > x1) {
  x = x1;
  y = y1;
  xEnd = x0;
 }
 else {
  x = x0;
  y = y0;
  xEnd = x1;
 }

 /* se cicla hasta llegar al extremo de la línea */
 while ( x <= xEnd )
 {
  glBegin( GL_POINTS );
  glColor3f( red, green, blue );
  glVertex2f( x, y);
  glEnd();

  x = x + 1;
  if (p < 0)
   p = p + incE;
  else {
   y = y + 1;
   p = p + incNE;
  }
 }
}

Algoritmo de Línea DDA

El analizador diferenciador digital (DDA - Digital Differential Analyzer) es un algoritmo de conversión de rastreo que se basa en el cálculo ya sea de ∆y o ∆x por medio de las ecuaciones 

∆y=m∆x

o

∆x= ∆y/m

Se efectúa un muestreo de la línea en intervalos unitarios en una coordenada y se determina los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada.

Tomemos una línea con pendiente positiva, si la pendiente |m|≤1, se hace el muestreo en x en intervalos unitarios (∆x=1 y ∆y=m dado que m=∆y/∆x ) y se calcula cada valor sucesivo de y como:

y_(k+1)=y_k+m

El subíndice toma valores enteros a partir de 1 y aumenta a razón de 1 hasta alcanzar el valor final.

Ya que m puede ser cualquier número real entre 0 y 1, los valores calculados de y deben redondearse al entero más cercano. Para líneas con una pendiente |m| > 1, se revierten las funciones de x y y, o sea, se realiza un muestreo de y en intervalos unitarios (∆y=1 y ∆x=1/m dado que m=∆y/∆x) y se calcula cada valor sucesivo de x como:

x_(k+1)=x_k+1/m

Las ecuaciones anteriores se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al derecho. Si este procesamiento se revierte, entonces ∆x o ∆y serian -1, y

y_(k+1)=y_k-m o x_(k+1)=x_k-1/m

Codificación a color del Algoritmo DDA:

Codificación en texto plano del Algoritmo DDA:

void LiniaDDA( float red, float green, float blue, int x0, int y0, int x1, int y1)
{
 float x, y, xs, ys;
 int dx, dy, steps;
 dx = x1 - x0;
 dy = y1 - y0;
 
 /* se asigna el punto de donde se comenzara a dibujar la línea */
 x = x0;
 y = y0;
 
 /* verificar si la pendiente es mayor de x o y, para luego asignarla a steps */
 if (abs(dx) > abs(dy))
  steps = abs(dx);
 else
  steps = abs(dy);
 
 /* se divide por la pendiente mayor, para dar xs o ys igual a 1 (o -1) */
 if (steps == 0) {
  
  glBegin( GL_POINTS );
  glColor3f( red, green, blue );
  glVertex2f( redonder(x), redondear(y) );
  glEnd();
  
  printf( "Esta linea es un punto" );
  return;
 }
 
 xs = dx/steps;
 ys = dy/steps;
 
 /* se cicla uno a la vez hasta llegar al numero de steps máximo */
 for (i = 0; i <= steps; i++)
 {
  glBegin( GL_POINTS );
  glColor3f( red, green, blue );
  glVertex2f( redonder(x), redondear(y) );  /* redondear(x) -> x+0.5 */
  glEnd();
  x = x + xs;
  y = y + ys;
 }
}

Fuente:

http://technogy-2012.blogspot.mx/2012/05/blog-post.html

http://www.cannes.itam.mx/Alfredo/Espaniol/Cursos/Grafica/Linea.pdf

http://www.nosolounix.com/2010/04/algoritmo-dda-dibujar-linea.html