L'exécutable

Trois solutions sont proposées:
  - Parcours simple du bord (problème possible au cas où l'onsouhaite dessiner deux facettes ayant un coté commun: pixels non tracé)
  - Parcours du bord de manière que chaque coté soit toujours parcouru dans le même sens (recollage possible de deux facettes ayant un bord en commun)
  - Prétraitement pour déterminer et extraire les bords gauche et droit (dessin de tous les pixels obtenus par traçage des cotés de la facette)

Solution 1: Le bord n'est pas entièrement recouvert.

Solution 1: Des trous peuvent apparaître entre facettes adjacentes.

Solution 2: Plus de trou entre facettes adjacentes

Solution 3: Les cotés sont entièrement recouverts.

Solution 3: Les cotés sont entièrement recouverts.

• Enter pour switcher entre les 3 solutions
• Espace pour switcher entre les différents modes d'affichage
• s pour switcher entre affichage d'une seule facette et affichage de 2 facettes adjacentes
• m pour générer aléatoirement une nouvelle facette (Mode d'affichage à une seule facette)

Fichier source : RemplissageTriangle.cpp

/* Remplissage 2D d'un triangle                 */
/* Solution imparfaite car presentant           */
/* des problemes lors du collage                */
/* deux facettes adjacentes:                    */
/* Apparition possible de trous car des pixels  */
/* peuvent ne pas etre allumes a la limite      */
/* entre les deux facettes car allumes          */
/* pour aucune des deux facettes                */

static void bord(int *px,Position3D *pi,Position3D *pf) {
  int xi = pi->c[0];
  int yi = pi->c[1];
  int xf = pf->c[0];
  int yf = pf->c[1];
  int dx,dy,i,xinc,yinc,cumul,x,y;
  x = xi;
  y = yi;
  dx = xf - xi;
  dy = yf - yi;
  xinc = ( dx > 0 ) ? 1 : -1;
  yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  px[y] = x;
  if ( dx > dy ) {
    cumul = dx / 2;
    for ( i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      px[y] = x; } }
    else {
    cumul = dy / 2;
    for ( i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      px[y] = x; } }
}

static void remplissageTriangle1(Position3D *p1,Position3D *p2,Position3D *p3) {
  int yi =(int) min(p1->c[1],min(p2->c[1],p3->c[1]));
  int yf =(int) max(p1->c[1],max(p2->c[1],p3->c[1]));
  int x1[4096];
  int x2[4096];
  if ( ( ( p1->c[1] == yi ) && ( p2->c[1] == yf ) ) ||
       ( ( p1->c[1] == yf ) && ( p2->c[1] == yi ) ) ) {
    bord(x1,p1,p2);
    bord(x2,p1,p3);
    bord(x2,p2,p3); }
    else
    if ( ( ( p1->c[1] == yi ) && ( p3->c[1] == yf ) ) ||
         ( ( p1->c[1] == yf ) && ( p3->c[1] == yi ) ) ) {
      bord(x1,p1,p3);
      bord(x2,p1,p2);
      bord(x2,p2,p3); }
      else {
      bord(x1,p2,p3);
      bord(x2,p1,p2);
      bord(x2,p1,p3); }
  glPointSize(9.0F);
  glBegin(GL_POINTS);
  for ( int y = yi ; y <= yf ; y++ ) {
    int xi = min(x1[y],x2[y]);
    int xf = max(x1[y],x2[y]);
    for ( int x = xi ; x <= xf ; x++ ) {
      glVertex2i(x*11+4,y*11+4); } }
  glEnd();
  glPointSize(1.0F);
} 

/* Remplissage 2D d'un triangle                 */
/* Resolution du probleme de collage            */
/* de facettes adjacentes                       */
/* Determination de chaque bord de maniere      */
/* que leurs extremites soient toujours         */
/* considerees dans le meme ordre               */

static void bordTri(int *px,Position3D *pi,Position3D *pf) {
  if ( pi->c[0] > pf->c[0] ) {
    Position3D *aux = pi;
    pi = pf;
    pf = aux; }
  if ( ( pi->c[0] == pf->c[0] ) && ( pi->c[1] > pf->c[1] ) ) {
    Position3D *aux = pi;
    pi = pf;
    pf = aux; }
  int xi = pi->c[0];
  int yi = pi->c[1];
  int xf = pf->c[0];
  int yf = pf->c[1];
  int dx,dy,i,xinc,yinc,cumul,x,y;
  x = xi;
  y = yi;
  dx = xf - xi;
  dy = yf - yi;
  xinc = ( dx > 0 ) ? 1 : -1;
  yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  px[y] = x;
  if ( dx > dy ) {
    cumul = dx / 2;
    for ( i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      px[y] = x; } }
    else {
    cumul = dy / 2;
    for ( i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      px[y] = x; } }
}

static void remplissageTriangle2(Position3D *p1,Position3D *p2,Position3D *p3) {
  int yi =(int) min(p1->c[1],min(p2->c[1],p3->c[1]));
  int yf =(int) max(p1->c[1],max(p2->c[1],p3->c[1]));
  int x1[4096];
  int x2[4096];
  if ( ( ( p1->c[1] == yi ) && ( p2->c[1] == yf ) ) ||
       ( ( p1->c[1] == yf ) && ( p2->c[1] == yi ) ) ) {
    bordTri(x1,p1,p2);
    bordTri(x2,p1,p3);
    bordTri(x2,p2,p3); }
    else
    if ( ( ( p1->c[1] == yi ) && ( p3->c[1] == yf ) ) ||
         ( ( p1->c[1] == yf ) && ( p3->c[1] == yi ) ) ) {
      bordTri(x1,p1,p3);
      bordTri(x2,p1,p2);
      bordTri(x2,p2,p3); }
      else {
      bordTri(x1,p2,p3);
      bordTri(x2,p1,p2);
      bordTri(x2,p1,p3); }
  glPointSize(9.0F);
  glBegin(GL_POINTS);
  for ( int y = yi ; y <= yf ; y++ ) {
    int xi = min(x1[y],x2[y]);
    int xf = max(x1[y],x2[y]);
    for ( int x = xi ; x <= xf ; x++ ) {
      glVertex2i(x*11+4,y*11+4); } }
  glEnd();
  glPointSize(1.0F);
} 

/* Remplissage 2D d'un triangle                 */
/* Recouvrement avec les pixels du bord         */
/* traces par l'algorithme de Bresenham         */
/* Determination effective des bords            */
/* droit et gauche                              */

static void bordDroit(int *px,Position3D *pi,Position3D *pf) {
  int xi = pi->c[0];
  int yi = pi->c[1];
  int xf = pf->c[0];
  int yf = pf->c[1];
  int dx,dy,i,xinc,yinc,cumul,x,y;
  x = xi;
  y = yi;
  dx = xf - xi;
  dy = yf - yi;
  xinc = ( dx > 0 ) ? 1 : -1;
  yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  px[y] = x;
  if ( dx > dy ) {
    cumul = dx / 2;
    for ( i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      if ( x > px[y] )
        px[y] = x; } }
    else {
    cumul = dy / 2;
    for ( i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      if ( x > px[y] )
        px[y] = x; } }
}

static void bordGauche(int *px,Position3D *pi,Position3D *pf) {
  int xi = pi->c[0];
  int yi = pi->c[1];
  int xf = pf->c[0];
  int yf = pf->c[1];
  int dx,dy,i,xinc,yinc,cumul,x,y;
  x = xi;
  y = yi;
  dx = xf - xi;
  dy = yf - yi;
  xinc = ( dx > 0 ) ? 1 : -1;
  yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  px[y] = x;
  if ( dx > dy ) {
    cumul = dx / 2;
    for ( i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      if ( x < px[y] )
        px[y] = x; } }
    else {
    cumul = dy / 2;
    for ( i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      if ( x < px[y] )
        px[y] = x; } }
}

static void remplissageTriangle3(Position3D *p1,Position3D *p2,Position3D *p3) {
  Position3D *c1;
  Position3D *c2;
  Position3D *c3;
  if ( ( p1->c[1] <= p2->c[1] ) && ( p1->c[1] <= p3->c[1] ) ) {
    c1 = p1;
    if ( p2->c[1] < p3->c[1] ) {
      c2 = p2;
      c3 = p3; }
      else {
      c2 = p3;
      c3 = p2; } }
    else {
    if ( p2->c[1] < p3->c[1] ) {
      c1 = p2;
      if ( p1->c[1] < p3->c[1] ) {
        c2 = p1;
        c3 = p3; }
        else {
        c2 = p3;
        c3 = p1; } }
      else {
      c1 = p3;
      if ( p1->c[1] < p2->c[1] ) {
        c2 = p1;
        c3 = p2; }
        else {
        c2 = p2;
        c3 = p1; } } }
  Direction3D *d1 = new Direction3D(c1,c3);
  Direction3D *d2 = new Direction3D(c1,c2);
  double z = d1->c[0]*d2->c[1]-d2->c[0]*d1->c[1];
  delete(d1);
  delete(d2);
  int t = (z < 0.0);
  int xi[4096];
  int xf[4096];
  for ( int y = c1->c[1] ; y <= c3->c[1] ; y++ ) {
    xi[y] = 4096;
    xf[y] = 0; }
  if ( t ) {
    bordGauche(xi,c1,c3);
    bordDroit(xf,c1,c2);
    bordDroit(xf,c2,c3); }
    else {
    bordGauche(xi,c1,c2);
    bordGauche(xi,c2,c3);
    bordDroit(xf,c1,c3); }
  glPointSize(9.0F);
  glBegin(GL_POINTS);
  for ( int y = c1->c[1] ; y <= c3->c[1] ; y++ ) {
    for ( int x = xi[y] ; x <= xf[y] ; x++ ) {
      glVertex2i(x*11+4,y*11+4); } }
  glEnd();
  glPointSize(1.0F);
}

RETOUR