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 preciso para la generación de líneas de rastreo que utiliza solo cálculos incrementales 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.

Algoritmo[editar]

El algoritmo sería el siguiente:

Si 0<|m|<1
  *Se capturan los extremos de la línea y se almacena el extremo izquierdo en (x0,y0).
  *Se carga (x0,y0) en el bufer de estructura (se traza el primer punto)
  *Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el 
    parámetro de decisión p0=2Δy-Δx.
  Para j=0 mientras j<Δx
  *En cada xk a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente:
      Si pk<0
          *Trazamos (xk+1,yk). 
          *Asignamos pk+1= pk+2Δy.
      Si no
          *Trazamos (xk+1,yk+1). 
          *Asignamos pk+1= pk+2Δy-2Δx.
  Fin Para
Si |m|>1
   *Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos    
     de x que se aproximen más a la trayectoria de la línea.

Implementación en Java[editar]

Esta es la implementación del algoritmo:

public void Bresenham(Graphics g,int x0, int y0, int x1, int y1) { 
  int x, y, dx, dy, p, incE, incNE, stepx, stepy;
  dx = (x1 - x0);
  dy = (y1 - y0);

 /* determinar que punto usar para empezar, cual para terminar */
  if (dy < 0) { 
    dy = -dy; 
    stepy = -1; 
  } 
  else {
    stepy = 1;
  }

  if (dx < 0) {  
    dx = -dx;  
    stepx = -1; 
  } 
  else {
    stepx = 1;
  }

  x = x0;
  y = y0;
  g.drawLine( x0, y0, x0, y0);
 /* se cicla hasta llegar al extremo de la línea */
  if(dx>dy){
    p = 2*dy - dx;
    incE = 2*dy;
    incNE = 2*(dy-dx);
    while (x != x1){
      x = x + stepx;
      if (p < 0){
        p = p + incE;
      }
      else {
        y = y + stepy;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
  else{
    p = 2*dx - dy;
    incE = 2*dx;
    incNE = 2*(dx-dy);
    while (y != y1){
      y = y + stepy;
      if (p < 0){
        p = p + incE;
      }
      else {
        x = x + stepx;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
 }

Implementación en Gambas[editar]

Esta es la implementación del algoritmo:

Public Sub hacerlinea(x0 As Integer, y0 As Integer, x1 As Integer, y1 As Integer)

  Dim x, y, dx, dy, p, incE, incNE, stepx, stepy As Integer

  dx = x1 - x0
  dy = y1 - y0

 ' determinar que punto usar para empezar, cual para terminar
  If dy < 0 Then
    dy = - dy
    stepy = -1
  Else 
    stepy = 1
  Endif
  
  If dx < 0 Then
    dx = - dx
    stepx = -1
  Else
    stepx = 1
  Endif

  x = x0
  y = y0
  
  Draw.Begin(DrawingArea1)
  Draw.Point(x0, y0)
' se cicla hasta llegar al extremo de la l ínea
  If dx > dy Then
    p = 2 * dy - dx
    incE = 2 * dy
    incNE = 2 * (dy - dx)
    While x <> x1
      x = x + stepx
      If p < 0 Then
        p = p + incE
      Else 
        y = y + stepy
        p = p + incNE
      Endif
      Draw.Point(x, y)
    Wend 
  Else 
    p = 2 * dx - dy
    incE = 2 * dx
    incNE = 2 * (dx - dy)
    While y <> y1
      y = y + stepy
      If p < 0 Then
        p = p + incE      
      Else 
        x = x + stepx
        p = p + incNE
      Endif
       Draw.Point(x, y)
     Wend
  Endif
Draw.End
End

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. 

Enlaces externos[editar]