Autor Tema: Algoritmo de Bressenham  (Leído 8126 veces)

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« en: Mayo 20, 2004, 11:50:30 pm »
Bueno, aqu? teneis una implementaci?n del Algoritmo de Bressenham, que sirve para rasterizar rectas y representarlas por pantalla.

Doy el ejecutable, ya que voy a preparar un documento explic?ndolo un poco,  aunque si quereis os pongo el c?digo para que lo veais antes.
El c?digo es muy simple en realidad, lo que pasa que para entender lo que hace y porqu? lo hace, necesita una m?nima base matem?tica, pero tampoco es nada del otro mundo (anal?tica matem?tica de rectas, lo dicho muy f?cil)

Est? en SDL y se incluye la dll correspondiente a la versi?n 1.2.6 (con el que est? compilado) con el boton izquierdo pulsas en una parte de la pantalla, y con una segunda pulsaci?n dibujar? una recta entre esos dos puntos.
Con doble clic derecho o cerrando la ventana se sale de la aplicaci?n.

A ver qu? os parece :)

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #1 en: Mayo 21, 2004, 07:04:59 pm »
Bueno, aqu? est? el documento con el algoritmo un poco m?s explicado. En el rar teneis incluido el c?digo fuente para que funcione en SDL y el archivo de proyecto para Dev-C++ y MinGW Developer Studio.

Ahora no est? incluida la documentaci?n en el .zip, s?lo el c?digo. El documento est? aparte en el siguiente post

Pongo aqu? el fuente de la funci?n BresenHam:
Código: [Seleccionar]
int BresenHam(punto A, punto B){

    //En SDL la coordenada Y est? invertida, esto es, el punto (0.0)
    //est? en la esquina superior izquierda de la superficie de la pantalla.
    
      
    //Declaramos la funci?n que dibujar? el pixel en la pantalla
    void putpixel(SDL_Surface *surface, int x, int y, Uint32 pixel);
    
    //Variables /////////////////////////////////////////////////////////////
    int W, H;           //diferencia entre las componentes x e y de cada punto y su valor
    int W2, H2;         //valores anteriores multiplicados por 2
    int temp;           //para ahorramos multiplicaciones en casa paso
    int x,y;            //punto de partida
    int F;              //funci?n punto medio
    int inc_x, inc_y;   //Valores que utilizaremos para incrementar la variable
    
    
    //puntero a la pantalla de video
    SDL_Surface* pantalla;
    //pixel a dibujar (color))
    Uint32 pixel;
    
    //obtenemos la pantalla
    pantalla = SDL_GetVideoSurface();
    
    //Seleccionamos color blanco para los pixels
    pixel = SDL_MapRGB (pantalla->format, 0xff,0xff,0xff);
    
    //comenzamos el algoritmo
  
    W = B.x - A.x;
    H = B.y - A.y;  
  
    x = A.x;
    y = A.y;
    
    if (W < 0) {        //l?nea a la derecha
        inc_x = -1;
        //usamos el valor absoluto
        W = -W;
    }
    else inc_x = 1;     //l?nea a la izquierda
    
    if (H < 0){         //l?nea hacia arriba
        inc_y = -1;
        //usamos el valor absoluto
        H = -H;    
    }      
    else inc_y = 1;     //l?nea hacia abajo

    W2 = W << 1;
    H2 = H << 1;

    
    if (SDL_MUSTLOCK (pantalla) )
        SDL_LockSurface (pantalla);  
        
        
    if (W == 0){             //Recta vertical
        while (y!= B.y){
            putpixel(pantalla, A.x, y, pixel);
            y += inc_y;
        }    
            
    }//Fin recta vertical
        
    else if (H == 0){        //Recta horizontal
        while(x != B.x){
            putpixel(pantalla, x, A.y, pixel);
            x+=inc_x;
        }    
    }//fin recta horizontal
    
    
   else if (  W > H ){      
      
        F = H2 - W;
        temp = (W-H)<<1;
        
        while (x != B.x){
            putpixel(pantalla, x, y, pixel);
            
            if (F<0)
                F += H2;
            else{
                y += inc_y;
                F -= temp;
            }    
            x += inc_x;
        }
}

else{  //H > W
    
        F = W2 - H;
     temp =(H-W)<<1
    
     while (y != B.y){
            putpixel(pantalla, x, y, pixel);
            if (F<0)
                F += W2;
            else{
                x += inc_x;
                F -= temp;
            }    
            y += inc_y;
     }    
    
}    

    if (SDL_MUSTLOCK (pantalla) )
        SDL_UnlockSurface (pantalla);
        
    SDL_UpdateRect(pantalla, 0,0,0,0);
  
    return 1;
}

Espero que os sea ?til. Recordad darme todo tipo de cr?tica o comentario, bien sea aqui o al mail.

Huelga decir que debereis tener la biblioteca SDL 1.2.6 al menos para poder compilarlo. ;)

Un saludo.
« última modificación: Mayo 24, 2004, 12:13:27 am por Zheo »

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #2 en: Mayo 24, 2004, 12:14:39 am »
Se me olvidaba, cuando haya modificado el texto, en base a vuestras opiniones, lo enviar? a DeKiper para que lo meta en la Biblioteca, por eso me interesa que me lo comenteis para pulir errores y eso.

Os lo pongo aqu? aparte el PDF (comprimido con zip)
Nueva versi?n del documento, ahora no est? incluido en el zip anterior porque es una versi?n nueva

 

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #3 en: Junio 25, 2004, 11:29:15 am »
Aqu? os pongo la nueva versi?n del algoritmo de Bresenham, aunque para ser sincero, no hay mejora en el algoritmo propiamente dicho ;P (de la funci?n de Bresenham s?lo cambia la tercera l?nea empezando por el final, ya que se ha eliminado el SDL_UpdateRect() )
Ahora al hacer clic por primera vez y mover el rat?n la recta se va dibujando. Si pulsas el boton izquierdo del rat?n la recta quedar? fija, si pulsas el bot?n derecho no dibujar? nada. Para ello se usa un backbuffer donde se guarda la imagen que hab?a antes de empezar a dibujar la recta.

La siguiente actualizaci?n que pretendo hacer es prepararlo para que dibuje curvas (c?rculos y elipses, por ejemplo) Si alguien tiene informaci?n al respecto ser? bien recibida. ^^

mOloch

  • Visitante
Algoritmo de Bressenham
« Respuesta #4 en: Octubre 04, 2004, 05:07:09 pm »
Te dejo la primitiva de un circulo en C
Código: [Seleccionar]
void Circle(int cx, int cy, int radio, unsigned char color)
{
    float angulo=0;
    int x, y;

    do
    {
        x = cx + radio * cos(angulo);
        y = cy + radio * sin(angulo);

        if((x>=0) && (y>=0) && (x<320) && (y<200))  
            PutPixel(x, y , color);

        angulo+=0.005;
     } while(angulo<6.28);
}

El procedimiento es simple, coloca un pixel en la posicion (r*cos(angulo), r*sen(angulo)), que es la formula del circulo, tened en cuenta que esta dentro de un bulce que aumenta el angulo, que esta en radianes por cierto.

jpeeri

  • Visitante
Algoritmo de Bressenham
« Respuesta #5 en: Agosto 02, 2006, 12:42:06 pm »
Perdonad mi ignorancia pero, ?Me pod?is explicar para que sirve este algoritmo?

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #6 en: Agosto 02, 2006, 01:36:27 pm »
Para resterizar una l?nea (originalmente recta, pero se puede aplicar a curvas) a un dispositivo de trazado, como puede ser un plotter, o un monitor.

En otras palabras, para dibujar l?neas rectas en pantalla ;)

Tambi?n puedes baj?rte el ejecutable y probarlo  B)  

jpeeri

  • Visitante
Algoritmo de Bressenham
« Respuesta #7 en: Agosto 02, 2006, 02:52:28 pm »
Perd?n, no me he explicado bien jeje.

Para que sirve si que lo se. Lo he estado viendo y es algo que a m? me hubiese costado a?os hacer. Lo que no entiendo es c?mo se podr?a aplicar al mundo de la creaci?n de videojuegos.

Un Saludo  ;)  

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #8 en: Agosto 02, 2006, 04:18:41 pm »
En 3D hay que unir los v?rtices con l?neas para formas los pol?gonos. Lo hace la tarjeta, si, pero un algoritmo tiene que haber para hacerlo, ?no crees? ;)

Adem?s te puede servir para realizar efectos en juegos 2D m?smamente, para hacer editores, etc. No es algo que necesites saber en general, porque normalmente tienes todas las operaciones que permiten dibujar formas ya hechas (API de windows, DirectDraw y cosas as?) pero si que se usa, y el saber no ocupa lugar.

No creo que te costara mucho hacerlo, a mi me llev? un par de d?as, simplemente tienes que leer c?mo funciona el algoritmo y luego implementarlo. Es un buen ejercicio, y aunque parezca que no, te vas a encontrar con algunos peque?os problemas en los que no hab?as pensado, y esa es la mejor manera de aprender IMHO.

jpeeri

  • Visitante
Algoritmo de Bressenham
« Respuesta #9 en: Agosto 02, 2006, 10:51:22 pm »
Vale, es que no sab?a que te pod?as construir tu propio motor 3D...

Desconectado Zheo

  • Grupo_Moderadores
  • Miembro Imprescindible
  • *
  • Mensajes: 1.397
    • Ver Perfil
Algoritmo de Bressenham
« Respuesta #10 en: Agosto 03, 2006, 08:37:29 am »
Hombre claro que se puede, el ogre no se hizo solo :P

Me refiero a algo m?s simple, claro, pero esas cosas se hacen mucho m?s de lo que crees.
si bien es cierto que se puede dise?ar un motor 3D y licenciarlo (Quake / Doom, unreal engine, torque) tambi?n lo puedes hacer t? mismo, normalmente reutiliz?ndolo o mejor?ndolo (Halo /Halo2 y pr?ximamente halo 3) Y otra veces no te queda m?s remedio, porque no hay alternativas, por ejemplo en programaci?n de sistemas port?tiles no SUELE haber mucho, o incluso m?viles, como el juego ONE de Digital Legends (espa?oles, oeeee) que tienen un motor 3D para la N-GAGE, completamente en ensamblador.

Ten en cuenta que en 3D vas a  tener que estudiar matem?ticas (geometr?a y trigonometr?a) Si lo que quieres es hacer un juego, lo mejor que puedes hacer es trabajar con un motor ya hecho, si quieres aprender, intenta hacer uno   ;)  

DEMOCRITO

  • Visitante
Algoritmo de Bressenham 3D
« Respuesta #11 en: Agosto 10, 2010, 11:02:08 am »
Te pongo un algoritmo de Bresenham 3D en Basic. Traducir el programa a otro lenguaje de programación es bien sencillo.

La fuente de este código lo encontrarás aquí:

http://sites.google.com/site/proyectosroboticos/bresenham-3d

en el que además expone un Algoritmo de Bresenham hasta 6D. Parece ser que este algoritmo tiene otras aplicaciones además de hacer líneas.

Espero te sirva. Saludos.

Código: [Seleccionar]

Dim As Integer Cont, dx, dy, dz, Adx, Ady, Adz, x_inc, y_inc, z_inc,_
               err_1, err_2, dx2, dy2, dz2, xxx, yyy, zzz, Xold, Yold, Zold,_
               Xnew, Ynew, Znew
               
Screen 12
                           
While 1

   Input "X: ",  Xnew
   Input "Y: ",  Ynew
   Input "Z: ",  Znew

   xxx=Xold
   yyy=Yold
   zzz=Zold
 
   dx = xnew - Xold
   dy = ynew - Yold
   dz = znew - Zold
   
   If (dx < 0) Then
     x_inc = -1
   Else
     x_inc =  1
   EndIf
   
   If (dy < 0) Then
     y_inc = -1
   Else
     y_inc =  1
   EndIf
   
   If (dz < 0) Then
     z_inc = -1
   Else
     z_inc =  1
   EndIf
   
   Adx = Abs(dx)
   Ady = Abs(dy)
   Adz = Abs(dz)
   
   dx2 = Adx*2
   dy2 = Ady*2
   dz2 = Adz*2
   
   If ((Adx>= Ady) And (Adx>= Adz)) Then
   
      err_1 = dy2 - Adx
      err_2 = dz2 - Adx
     
      For Cont = 0 To Adx-1
       
         If (err_1 > 0) Then
             yyy+= y_inc
             err_1 -= dx2
         EndIf
         
         If (err_2 > 0) Then
             zzz+= z_inc
             err_2 -= dx2
         EndIf
         
         err_1 += dy2
         err_2 += dz2
         xxx+= x_inc
         
         print xxx, yyy, zzz
         
      Next
     
   EndIf
   
  If ((Ady> Adx) And (Ady>= Adz)) Then
   
     err_1 = dx2 - Ady
     err_2 = dz2 - Ady
     
     For Cont = 0 To  Ady-1
       
       If (err_1 > 0) Then
            xxx+= x_inc
            err_1 -= dy2
        EndIf
         
        If (err_2 > 0) Then
            zzz+= z_inc
            err_2 -= dy2
        EndIf
       
        err_1 += dx2
        err_2 += dz2
        yyy+= y_inc
   
        print xxx, yyy, zzz
       
     Next

   EndIf
   
   If ((Adz> Adx) And (Adz> Ady)) Then
   
      err_1 = dy2 - Adz
      err_2 = dx2 - Adz
     
      For Cont = 0 To Adz-1
         
         If (err_1 > 0) Then
             yyy+= y_inc
             err_1 -= dz2
         EndIf
         
         If (err_2 > 0) Then
             xxx+= x_inc
             err_2 -= dz2
         EndIf
         
         err_1 += dy2
         err_2 += dx2
         zzz+= z_inc
       
         print xxx, yyy, zzz
       
    Next
   
   EndIf
   
   Xold=xnew
   Yold=ynew
   Zold=znew
Wend

End



Desconectado HQH

  • Administrator
  • Miembro Imprescindible
  • *****
  • Mensajes: 1.856
    • Ver Perfil
Re: Algoritmo de Bressenham
« Respuesta #12 en: Agosto 12, 2010, 12:37:57 pm »
Gracias or aporte, asi tenemos mas material :)