/* Affichage d'un segment de droite                */
/* par algorithme de Bresenham                     */
/* Utilisation d'une variante de cet algorithme    */
/* pour implanter le remplissage d'un triangle 2D  */
/*                                                 */
/* Auteur: Nicolas JANEY                           */
/* nicolas.janey@univ-fcomte.fr                    */
/* Avril 2020                                      */

#include <stdlib.h>
#include <stdio.h>

#include <GL/glut.h>
#include <GL/gl.h>
#include <GL/glu.h>

/* Variables et constantes globales             */

static const float blanc[]        = { 1.0F,1.0F,1.0F,1.0F };
static const float jaune[]        = { 1.0F,1.0F,0.0F,1.0F };
static const float cyan[]         = { 0.0F,1.0F,1.0F,1.0F };
static const float magenta[]      = { 1.0F,0.0F,1.0F,1.0F };
static const float rouge[]        = { 1.0F,0.0F,0.0F,1.0F };
static const float vert[]         = { 0.0F,0.7F,0.0F,1.0F };
static const float bleu[]         = { 0.0F,0.0F,1.0F,1.0F };
static const float cyanFonce[]    = { 0.0F,0.8F,0.8F,1.0F };
static const float magentaFonce[] = { 0.8F,0.0F,0.8F,1.0F };

static int taillePixel = 16;
static int aff = 0;
static int methode = 0;
static int ordre = 0;
static int f1 = 1;
static int f2 = 1;
static int scn = 0;

/* Affichage d'un carre materialisant un pixel        */
/* place en coordonnees (x,y).                        */
/* Le pixel de coordonnees (0,0) est en bas a gauche. */
/* L'axe x est oriente vers la droite.                */
/* L'axe y est oriente vers le haut.                  */

static void pixel(int x,int y) {
  glBegin(GL_QUADS);
  glVertex2i(5+x*taillePixel,5+y*taillePixel);
  glVertex2i(5+x*taillePixel+taillePixel-1,5+y*taillePixel);
  glVertex2i(5+x*taillePixel+taillePixel-1,5+y*taillePixel+taillePixel-1);
  glVertex2i(5+x*taillePixel,5+y*taillePixel+taillePixel-1);
  glEnd();
}

/* Rasterisation du cote de sommet initial (xi,yi)    */
/* et de sommet final (xf,yf) en affichant            */
/* seulement les pixels correspondant au dernier x    */
/* calcule pour chaque y                              */

static void coteRasterise(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);
  if ( dx > dy ) {
    int cumul = dx >> 1;
    for ( int i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        pixel(x-xinc,y);
        cumul -= dx;
        y += yinc; } }
    pixel(x,y); }
    else {
    pixel(x,y);
    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); } }
}

////////////////////////////////////////////////////////

/* 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); } }
}
////////////////////////////////////////////////////////

static void triangle(int x1,int y1,int x2,int y2,int x3,int y3,int aff) {
  if ( !aff )
    return;
  switch (methode) {
    case 1 :
      triangle1(x1,y1,x2,y2,x3,y3);
      break;
    case 0 :
      triangle2(x1,y1,x2,y2,x3,y3);
      break; }
}

/* Affichage d'un quadrillage mimant un ecran bitmap  */
/* Les pixels sont carres et ont taillePixel pixels   */
/* de cote.                                           */

static void quadrillage(void) {
  int tx = (glutGet(GLUT_WINDOW_WIDTH)-10)/taillePixel;
  int ty = (glutGet(GLUT_WINDOW_HEIGHT)-10)/taillePixel;
  glBegin(GL_LINES);
  for ( int x = 0 ; x <= tx ; x++ ) {
    glVertex2i(5+x*taillePixel,5);
    glVertex2i(5+x*taillePixel,5+ty*taillePixel); }
  for ( int y = 0 ; y <= ty ; y++ ) {
    glVertex2i(5,5+y*taillePixel);
    glVertex2i(5+tx*taillePixel,5+y*taillePixel); }
  glEnd();
}

/* Affichage du triangle reel defini par les sommets  */
/* de coordonnees (x1,y1), (x2,y2) et (x3,y3)         */

static void triangleReel(int x1,int y1,int x2,int y2,int x3,int y3,int aff) {
  if ( !aff )
    return;
  glBegin(GL_TRIANGLES);
  glVertex2i(5+x1*taillePixel+taillePixel/2,5+y1*taillePixel+taillePixel/2);
  glVertex2i(5+x2*taillePixel+taillePixel/2,5+y2*taillePixel+taillePixel/2);
  glVertex2i(5+x3*taillePixel+taillePixel/2,5+y3*taillePixel+taillePixel/2);
  glEnd();
}

/* Affichage des cotes rasterises du triangle défini  */
/* par les sommets de coordonnees                     */
/* (x1,y1), (x2,y2) et (x3,y3)                        */

static void triangleCotesSegments(int x1,int y1,int x2,int y2,int x3,int y3,int aff) {
  if ( !aff )
    return;
  ligne(x1,y1,x2,y2);
  ligne(x2,y2,x3,y3);
  ligne(x1,y1,x3,y3);
}

/* Affichage des cotes rasterises du triangle défini  */
/* par les sommets de coordonnees                     */
/* (x1,y1), (x2,y2) et (x3,y3)                        */

static void triangleCotesRasterises(int x1,int y1,int x2,int y2,int x3,int y3,int aff) {
  if ( !aff )
    return;
  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++ ) {
    pixel(xmin[y],y);
    pixel(xmax[y],y); }
}

/* Fonction executee lors d'un rafraichissement       */
/* de la fenetre de dessin                            */

static void display(void) {
  int f1x1 = 15;
  int f1y1 = 2;
  int f1x2 = 2;
  int f1y2 = 4;
  int f1x3 = 19;
  int f1y3 = 14;
  int f2x1 = 1;
  int f2y1 = 6;
  int f2x2 = 18;
  int f2y2 = 16;
  int f2x3 = 4;
  int f2y3 = 19;
  if ( scn == 1 ) {
    f1x1 = f2x2 = 1;
    f1y1 = f2y2 = 5;
    f1x2 = f2x3 = 33;
    f1y2 = f2y3 = 8;
    f1x3 = 18;
    f1y3 = 12;
    f2x1 = 13;
    f2y1 = 1; }
  glClearColor(0.8F,0.8F,0.8F,1.0F);
  glClear(GL_COLOR_BUFFER_BIT);
  glPushMatrix();
  glColor3fv(bleu);
  quadrillage();
  switch(aff) {
    case 0 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      break;
    case 1 :
      glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);
      glLineWidth(5.0F);
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      glLineWidth(1.0F);
      glPolygonMode(GL_FRONT_AND_BACK,GL_FILL);
      break;
    case 2 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangleCotesSegments(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangleCotesSegments(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangleCotesSegments(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangleCotesSegments(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      break;
    case 3 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangleCotesRasterises(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangleCotesRasterises(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangleCotesRasterises(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangleCotesRasterises(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      break;
    case 4 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangleCotesSegments(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangleCotesSegments(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyanFonce);
          triangleCotesRasterises(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magentaFonce);
          triangleCotesRasterises(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangleCotesSegments(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangleCotesSegments(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magentaFonce);
          triangleCotesRasterises(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyanFonce);
          triangleCotesRasterises(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      break;
    case 5 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangle(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangle(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          break;
        case 1 :
          glColor3fv(magenta);
          triangle(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangle(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          break; }
      break;
    case 6 :
      switch (ordre) {
        case 0 :
          glColor3fv(cyan);
          triangle(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magenta);
          triangle(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);
          glLineWidth(3.0F);
          glColor3fv(cyanFonce);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glColor3fv(magentaFonce);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glLineWidth(1.0F);
          glPolygonMode(GL_FRONT_AND_BACK,GL_FILL);
          break;
        case 1 :
          glColor3fv(magenta);
          triangle(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyan);
          triangle(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);
          glLineWidth(3.0F);
          glColor3fv(magentaFonce);
          triangleReel(f2x1,f2y1,f2x2,f2y2,f2x3,f2y3,f2);
          glColor3fv(cyanFonce);
          triangleReel(f1x1,f1y1,f1x2,f1y2,f1x3,f1y3,f1);
          glLineWidth(1.0F);
          glPolygonMode(GL_FRONT_AND_BACK,GL_FILL);
          break; }
      break; }
  glPopMatrix();
  glFlush();
  glutSwapBuffers();
  int error = glGetError();
  if ( error != GL_NO_ERROR )
    printf("Erreur OpenGL: %d\n",error);
}

/* Fonction executee lors d'un changement             */
/* de la taille de la fenetre OpenGL                  */
/* -> Ajustement de la camera de visualisation        */

static void reshape(int x,int y) {
  glViewport(0,0,x,y); 
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  glOrtho(0.0,x,0.0,y,-1000.0,1000.0);
  glMatrixMode(GL_MODELVIEW);
  glLoadIdentity();
}

/* Fonction executee lors de la frappe                */
/* d'une touche du clavier                            */

static void keyboard(unsigned char key,int x,int y) {
  switch ( key ) {
    case 43 :
      taillePixel++;
      glutPostRedisplay(); 
      break;
    case 45 :
      taillePixel--;
      if ( taillePixel < 2 )
        taillePixel = 2;
      glutPostRedisplay(); 
      break;
    case 0x0D :
      aff = (aff+1)%7;
      glutPostRedisplay(); 
      break;
    case 0x20 :
      methode = (methode+1)%2;
      glutPostRedisplay(); 
      break;
    case 'o' :
      ordre = (ordre+1)%2;
      glutPostRedisplay(); 
      break;
    case 's' :
      scn = (scn+1)%2;
      switch (scn) {
        case 0 :
          glutReshapeWindow(350,350);
          break;
        case 1 :
          glutReshapeWindow(570,250);
          break; }
      glutPostRedisplay(); 
      break;
    case 0x1B :
      exit(0); 
      break; }
}

/* Fonction executee lors de la frappe                */
/* d'une touche du clavier                            */

static void special(int code,int x,int y) {
  switch ( code ) {
    case GLUT_KEY_F1 :
      f1 = !f1;
      glutPostRedisplay(); 
      break;
    case GLUT_KEY_F2 :
      f2 = !f2;
      glutPostRedisplay(); 
      break;
    case 0x1B :
      exit(0); 
      break; }
}

/* Fonction principale                                */

int main(int argc,char **argv) {
  glutInit(&argc,argv);
  glutInitDisplayMode(GLUT_RGBA|GLUT_DOUBLE);
  glutInitWindowSize(350,350); 
  glutInitWindowPosition(50,50); 
  glutCreateWindow("Remplissage triangles"); 
  glutKeyboardFunc(keyboard);
  glutSpecialFunc(special);
  glutReshapeFunc(reshape);
  glutDisplayFunc(display);
  glutMainLoop();
  return(0);
}