Tracer des segments.

Utilisation de l'algorithme de Bresenham

Bresenham

Voir version :

Pas de dépendances

Télécharger :

#include <sdl/sdl.h>

#ifdef WIN32
#pragma comment(lib,"sdl.lib")
#pragma comment(lib,"sdlmain.lib")
#endif

void UpdateEvents(Sint32* mousex,Sint32* mousey,char boutons[8],char key[SDLK_LAST])
{
    SDL_Event event;
    while(SDL_PollEvent(&event))
    {
        switch (event.type)
        {
        case SDL_KEYDOWN:
            key[event.key.keysym.sym]=1;
            break;
        case SDL_KEYUP:
            key[event.key.keysym.sym]=0;
            break;
        case SDL_MOUSEMOTION:
            *mousex=event.motion.x;
            *mousey=event.motion.y;
            break;
        case SDL_MOUSEBUTTONDOWN:
            boutons[event.button.button]=1;
            break;
        case SDL_MOUSEBUTTONUP:
            boutons[event.button.button]=0;
            break;
        }
    }
}

void SDL_PutPixel32(SDL_Surface *surface, int x, int y, Uint32 pixel)
{
    Uint8 *p = (Uint8*)surface->pixels + y * surface->pitch + x * 4;
    *(Uint32*)p = pixel;
}

Uint32 SDL_GetPixel32(SDL_Surface *surface, int x, int y)
{
    Uint8 *p = (Uint8*)surface->pixels + y * surface->pitch + x * 4;
    return *(Uint32*)p;
}

void Line(SDL_Surface* surf,int x1,int y1, int x2,int y2,Uint32 couleur)  // Bresenham
{
  int x,y;
  int Dx,Dy;
  int xincr,yincr;
  int erreur;
  int i;

  Dx = abs(x2-x1);
  Dy = abs(y2-y1);
  if(x1<x2)
    xincr = 1;
  else
    xincr = -1;
  if(y1<y2)
    yincr = 1;
  else
    yincr = -1;

  x = x1;
  y = y1;
  if(Dx>Dy)
    {
      erreur = Dx/2;
      for(i=0;i<Dx;i++)
        {
          x += xincr;
          erreur += Dy;
          if(erreur>Dx)
            {
              erreur -= Dx;
              y += yincr;
            }
        SDL_PutPixel32(surf,x, y,couleur);
        }
    }
  else
    {
      erreur = Dy/2;
      for(i=0;i<Dy;i++)
        {
          y += yincr;
          erreur += Dx;
          if(erreur>Dy)
            {
              erreur -= Dy;
              x += xincr;
            }
        SDL_PutPixel32(surf,x, y,couleur);
        }
    }
    SDL_PutPixel32(surf,x1,y1,couleur);
    SDL_PutPixel32(surf,x2,y2,couleur);
}


int main(int argc,char** argv)
{
    Sint32 mousex = 0;
    Sint32 mousey = 0;
    char boutons[8] = {0};
    char key[SDLK_LAST] = {0};
    SDL_Surface* screen;
    int xs,ys;
    int en_train_d_ecrire = 0;
    SDL_Init(SDL_INIT_VIDEO);
    screen=SDL_SetVideoMode(800,600,32,SDL_SWSURFACE|SDL_DOUBLEBUF);  
    SDL_ShowCursor(1);
    xs=ys=0;
    while(!key[SDLK_ESCAPE])
    {
        UpdateEvents(&mousex,&mousey,boutons,key);
        if (SDL_MUSTLOCK(screen))
            SDL_LockSurface(screen);
        if (boutons[SDL_BUTTON_LEFT])
        {
            en_train_d_ecrire=1;
        }
        if (!boutons[SDL_BUTTON_LEFT])
        {
            if (en_train_d_ecrire  && (xs!=mousex || ys!=mousey))
                Line(screen,xs,ys,mousex,mousey,0xFFFFFF);
            xs = mousex;
            ys = mousey;
            en_train_d_ecrire = 0;
        }

        if (boutons[SDL_BUTTON_RIGHT])
        {
            SDL_SaveBMP(screen,"out.bmp");
        }
        if (SDL_MUSTLOCK(screen))
            SDL_UnlockSurface(screen);        
        SDL_Flip(screen);
    }
    return 0;
}





Commentaires


  Utilisation : cliquez et maintenant a un endroit de l'écran.
  Quand vous relachez, une ligne est tracée.

  Le main est facile a comprendre.

  Ici, on va parler du traçage de lignes.


Comment Tracer une ligne :
**************************

  Il existe plusieurs façons de tracer une ligne.
  Parmi ces façons, on peut penser :


  - pour les lignes horizontales, verticales, voir, diagonales, un simple for pourrait faire l'affaire.
  - sinon calculer la pente d'une ligne, avec un cas particulier pour x = 0, et sinon, y = ax+b
  Ensuite, faire varier x avec un for, et tracer le y correspondant.
  Le résultat est un probleme : il peut y avoir des trous, et il peut y avoir des erreurs d'arrondis.

  Nous allons donc oublier tout ça, et utiliser THE ALGORITHM pour tracer des lignes : Bresenham

L'algorithme de Bresenham
*************************

  Quand on trace une ligne, on a 8 cas.

  
    \     |     /
     \  3 | 2  /
      \   |   /
       \  |  /     
     4  \ | /  1
         \|/
   --------------
         /|\
     5  / | \  8
       /  |  \
      /   |   \    
     /  6 |  7 \
    /     |     \


  Le point de départ de la ligne est le milieu de cette figure, et le point d'arrivée se trouve dans l'un de ces 8 octants

  Prenons le cas 1 : nous voulons tracer une ligne qui sera dans l'octant 1.

  La ligne aura cette allure :



                                (x2,y2)
                       *********
                 ******
        *********
  ******
(x1,y1)


  Dans ce cas, pour etre sur de ne pas en oublier, on va faire un for de x1 à x2.
  Au lieu de calculer le y associé, nous allons simplement voir si oui ou non on monte d'un cran.
  Car pour un x donné, (dans l'octant 1) nous n'avons que 2 choix :

  **

  ou

   *
  *

  Si on est capable de savoir si, pour un x donné, on doit monter ou pas, alors on réussit a tracer toute la ligne.
  Je vous laisse regarder l'algo (qui nécessite une démonstration mathématique que vous trouverez sur le net)
  Cet algo manipule des nombres entiers (ce qui est le plus rapide)

  Cas des autres octants :
  ------------------------

  Les autres octants s'obtiennent par symétrie.


          |
      B   |   A
          |   
          |
    -------------
          |
          |
      C   |   D
          |

  la ligne :
  if(x1<x2)
  ramene les cas du quartan B au cas A, et les cas de C a D.

  la ligne :
  if (y1<y2)
  ramene les cas du quartan D au quartan A.

  Une fois ces lignes passées, il suffit de savoir tracer les cas de l'octant 1 et 2.

  Le if(Dx>Dy)
  procede a l'octan 1
  le else a l'octan 2.



Laissez un commentaire / post a comment