Commentaires

L'implantation de la fonction de tracé d'un segment de droite est la pure implantation de l'algorithme de Bresenham.

La fonction de rasterisation d'un triangle fait appel à la fonction auxiliaire cote destinée à "rasteriser" un coté. Cette fonction n'a pas pour but de faire quelque dessin que ce soit, mais plutôt de déterminer une abscisse xmin et une abscisse xmax pour chaque ordonnée y où il y a au moins un pixel sur le coté, ces abscisses étant destinées à servir d'abscisses extrêmes initiale et finale pour chaque trame horizontale de pixels du triangle. Cette fonction prend en paramètres les coordonnées des pixels initiaux et finaux du coté ainsi que les tableaux xmin et xmax destinés à recueillir les abscisses minimales et maximales. Les y peuvent directement servir d'indices dans ce tableau. L'implantation de le fonction cote est basée en tout point sur l'algorithme de Bresenham sauf qu'au lieu d'allumer des pixels, elle fait des écritures de valeurs d'abscisse dans xmin (resp. xmax) aux indices y si des valeur trouvées par rasterisation sont plus petites (resp. plus grandes) que celles qui s'y trouvent.
La fonction triangle prend en paramètre, dans l'ordre, les coordonnées (x1,y1), (x2,y2) et (x3,y3) des sommets P1, P2 et P3 définissant le triangle à rasteriser. Un point essentiel au bon fonctionnement de la fonction triangle est que les 3 sommets P1, P2 et P3 doivent être triés par ordre d'ordonnées croissantes. La fonction triangle débute par la déclaration des tableaux xmin et xmax destinés à recevoir les abscisses minimales et maximales des trames horizontales de remplissage du triangle. Ces tableaux sont définis de taille 4096, autorisant une résolution en y de 4096 pixels comptée des indices 0 (en bas) à 4095 (en haut). xmax est initialisé à 0. xmin est initialisé à une valeur plus grande que la plus grande valeur envisagée pour une abscisse de pixel. Ensuite, elle procède à la rasterisation dans les tableaux xmin et xmax des cotés du triangle. Enfin, elle trace effectivement les pixels en itérant sur y entre y1 et y3 inclus pour parcourir toutes les trames horizontales et, sur chaque trame, en itérant entre xmin[y] et xmax[y] inclus pour allumer tous les pixels.

Remarque : Cette méthode de remplissage est bien adaptée au traitement de facettes triangulaires individuelles. Dans le cas où des ensembles de facettes adjacentes doivent être affichés. Les cotés partagés verront leurs pixels être affichés deux, une fois pour chaque facette. Il s'agit là d'une inoptimisation importante.

L'exécutable


 Figure (1) : Tracé des deux segments de droite


Figures (2) et (3) : Triangles rééls et rasterisés


Figures (4) et (5) : Triangles dessinés par leurs cotés réels et rastérisés


Figure (6) : Pixels extrèmes gauches et droits des trames horizontales des rectangles
-> derniers pixels sur la trame correspondant au bord dans le sens de son parcours de rasterisation


Figure (7) : Comparaison entre les pixels sélectionnés et les cotés rasterisés


Figure (8) : Superposition des triangles réels dessinés par leurs bords et obtenus par rasterisation

Fichier source : RemplissageTriangle2D-2.cpp

/* Trace du segment de droite entre le pixel          */
/* de coordonnees (xi,yi) et le pixel                 */
/* de coordonnees (xf,yf) au moyen de l'algorithme    */
/* de Bresenham                                       */

static void ligne(int xi,int yi,int xf,int yf) {
  int x = xi;
  int y = yi;
  int dx = xf - xi;
  int dy = yf - yi;
  int xinc = ( dx > 0 ) ? 1 : -1;
  int yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  pixel(x,y);
  if ( dx > dy ) {
    int cumul = dx >> 1;
    for ( int i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      pixel(x,y); } }
    else {
    int cumul = dy >> 1;
    for ( int i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      pixel(x,y); } }
}

/* Rasterisation du cote de sommet initial (xi,yi)    */
/* et de sommet final (xf,yf) en stockant             */
/* dans le tableau px le dernier x                    */
/* calcule pour chaque y                              */

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

static void pixel(int x,int y,int *xmin,int *xmax) {
  if ( x < xmin[y] )
    xmin[y] = x;
  if ( x > xmax[y] )
    xmax[y] = x;
}

/* Rasterisation du cote de sommet initial (xi,yi)    */
/* et de sommet final (xf,yf) en stockant             */
/* dans le tableau px le dernier x                    */
/* calcule pour chaque y                              */

static void cote(int xi,int yi,int xf,int yf,int *xmin,int *xmax) {
  int x = xi;
  int y = yi;
  int dx = xf - xi;
  int dy = yf - yi;
  int xinc = ( dx > 0 ) ? 1 : -1;
  int yinc = ( dy > 0 ) ? 1 : -1;
  dx = abs(dx);
  dy = abs(dy);
  pixel(x,y,xmin,xmax);
  if ( dx > dy ) {
    int cumul = dx >> 1;
    for ( int i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      pixel(x,y,xmin,xmax); } }
    else {
    int cumul = dy >> 1;
    for ( int i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      pixel(x,y,xmin,xmax); } }
}

/* Rasterisation d'un triangle 2D                     */
/* (x1,y1), (x2,y2) et (x3,y3) sont les coordonnees   */
/* des trois sommets du triangle et doivent respecter */
/* y1 <= y2 <= y3                                     */
/* Solution imparfaite car ne gerant pas le probleme  */
/* des cotes ou plus d'un pixel existe pour chaque y  */
/* avec l'obligation de choisir un et un seul         */
/* de ces pixels par y                                */
/* Consequences possibles :                           */
/* Non affichage sur les cotes de pixels qui auraient */
/* ete affiches si les cotes avaient ete rasterises   */
/* par affichage de segments de droite rasterises.    */
/* Apparition de trous entre deux facettes adjacentes */
/* car des pixels peuvent ne pas etre allumes         */
/* a la limite entre les deux facettes car allumes    */
/* pour aucune des deux facettes.                     */

static void triangle1(int x1,int y1,int x2,int y2,int x3,int y3) {
  int xd[4096];
  int xg[4096];
  if ( (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) > 0 ) {
    cote(x1,y1,x2,y2,xd);
    cote(x2,y2,x3,y3,xd);
    cote(x1,y1,x3,y3,xg); }
    else {
    cote(x1,y1,x2,y2,xg);
    cote(x2,y2,x3,y3,xg);
    cote(x1,y1,x3,y3,xd); }
  for ( int y = y1 ; y <= y3 ; y++ ) {
    for ( int x = xg[y] ; x <= xd[y] ; x++ ) {
      pixel(x,y); } }
} 

/* Rasterisation d'un triangle 2D                     */
/* (x1,y1), (x2,y2) et (x3,y3) sont les coordonnees   */
/* des trois sommets du triangle et doivent respecter */
/* y1 <= y2 <= y3                                     */

static void triangle2(int x1,int y1,int x2,int y2,int x3,int y3) {
  int xmin[4096];
  int xmax[4096];
  for ( int y = y1 ; y <= y3 ; y++ ) {
    xmin[y] = 8192;
    xmax[y] = -1; }
  cote(x1,y1,x2,y2,xmin,xmax);
  cote(x2,y2,x3,y3,xmin,xmax);
  cote(x1,y1,x3,y3,xmin,xmax);
  for ( int y = y1 ; y <= y3 ; y++ ) {
    for ( int x = xmin[y] ; x <= xmax[y] ; x++ ) {
      pixel(x,y); } }
}

RETOUR