/* Remplissage 2D d'une facette triangulaire    */
/*                                              */
/* Auteur: Nicolas JANEY                        */
/* nicolas.janey@univ-fcomte.fr                 */
/* Septembre 2012                               */

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

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

#include "Position3D.h"
#include "Direction3D.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 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 int aff = 0;
static int t = 0;
static int s = 0;
static int nb = 0;

static Position3D *p1;
static Position3D *p2;
static Position3D *p3;

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

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

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

static void remplissageTriangle(Position3D *p1,Position3D *p2,Position3D *p3) {
  switch (t) {
    case 0 :
      remplissageTriangle1(p1,p2,p3);
      break;
    case 1 :
      remplissageTriangle2(p1,p2,p3);
      break;
    case 2 :
      remplissageTriangle3(p1,p2,p3);
      break; }
}

/* Scene dessinee                               */

static void traceBord(Position3D *pi,Position3D *pf) {
  glPointSize(9.0F);
  glBegin(GL_POINTS);
  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);
  glVertex2i(x*11+4,y*11+4);
  if ( dx > dy ) {
    cumul = dx / 2;
    for ( i = 1 ; i <= dx ; i++ ) {
      x += xinc;
      cumul += dy;
      if ( cumul >= dx ) {
        cumul -= dx;
        y += yinc; }
      glVertex2i(x*11+4,y*11+4); } }
    else {
    cumul = dy / 2;
    for ( i = 1 ; i <= dy ; i++ ) {
      y += yinc;
      cumul += dx;
      if ( cumul >= dy ) {
        cumul -= dy;
        x += xinc; }
      glVertex2i(x*11+4,y*11+4); } }
  glEnd();
  glPointSize(1.0F);
}

static void outlineTriangle(Position3D *p1,Position3D *p2,Position3D *p3) {
  traceBord(p1,p2);
  traceBord(p1,p3);
  traceBord(p2,p3);
} 

static void scene1(void) {
  glPushMatrix();
  switch (aff) {
    case 0:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      break;
    case 1:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      glColor4fv(vert);
      outlineTriangle(p1,p2,p3);
      break;
    case 2:
      glColor4fv(jaune);
      remplissageTriangle(p1,p2,p3);
      break;
    case 3:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      glColor4fv(vert);
      remplissageTriangle(p1,p2,p3);
      break; }
  glPopMatrix();
}

static void scene2(void) {
  Position3D *p1 = new Position3D(29.0,14.0,0.0);
  Position3D *p2 = new Position3D(2.0,17.0,0.0);
  Position3D *p3 = new Position3D(15.0, 3.0,0.0);
  Position3D *p4 = new Position3D(18.0,29.0,0.0);
  glPushMatrix();
  switch (aff) {
    case 0:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      glColor4fv(rouge);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p4->c[0]*11+4,p4->c[1]*11+4);
      glEnd();
      break;
    case 1:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      glColor4fv(rouge);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p4->c[0]*11+4,p4->c[1]*11+4);
      glEnd();
      glColor4fv(vert);
      outlineTriangle(p1,p2,p3);
      glColor4fv(magenta);
      outlineTriangle(p2,p1,p4);
      break;
    case 2:
      glColor4fv(vert);
      remplissageTriangle(p1,p2,p3);
      glColor4fv(magenta);
      remplissageTriangle(p2,p1,p4);
      break;
    case 3:
      glColor4fv(jaune);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p3->c[0]*11+4,p3->c[1]*11+4);
      glEnd();
      glColor4fv(rouge);
      glBegin(GL_TRIANGLES);
      glVertex2d(p1->c[0]*11+4,p1->c[1]*11+4);
      glVertex2d(p2->c[0]*11+4,p2->c[1]*11+4);
      glVertex2d(p4->c[0]*11+4,p4->c[1]*11+4);
      glEnd();
      glColor4fv(vert);
      remplissageTriangle(p1,p2,p3);
      glColor4fv(magenta);
      remplissageTriangle(p2,p1,p4);
      break; }
  glPopMatrix();
  delete(p1);
  delete(p2);
  delete(p3);
  delete(p4);
}

static void fond(void) {
  glColor3fv(bleu);
  int tx = (glutGet(GLUT_WINDOW_WIDTH)+10)/11;
  int ty = (glutGet(GLUT_WINDOW_HEIGHT)+10)/11;
  for ( int x = 0 ; x <= tx ; x++ )
    for ( int y = 0 ; y <= ty ; y++ ) {
      glBegin(GL_LINE_LOOP);
      glVertex2i(x*11,y*11);
      glVertex2i(x*11+10,y*11);
      glVertex2i(x*11+10,y*11+10);
      glVertex2i(x*11,y*11+10);
      glEnd(); }
}

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

static void display(void) {
  glClearColor(0.8F,0.8F,0.8F,1.0F);
  glClear(GL_COLOR_BUFFER_BIT);
  glPushMatrix();
  fond();
  switch (s) {
    case 0 :
      scene1();
      break;
    case 1 :
      scene2();
      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 'n' :
      delete(p1);
      delete(p2);
      delete(p3);
      p1 = new Position3D(30.0,20.0,0.0);
      p2 = new Position3D( 5.0,29.0,0.0);
      p3 = new Position3D( 9.0, 3.0,0.0);
      glutPostRedisplay();
      break;
    case 'm' :
      delete(p1);
      delete(p2);
      delete(p3);
      p1 = new Position3D(2+rand()%28,2+rand()%28,0.0);
      p2 = new Position3D(2+rand()%28,2+rand()%28,0.0);
      p3 = new Position3D(2+rand()%28,2+rand()%28,0.0);
      glutPostRedisplay();
      break;
    case 's' :
      s = (s+1)%2;
      glutPostRedisplay(); 
      break;
    case 0x0D :
      t = (t+1)%3;
      glutPostRedisplay(); 
      break;
    case 0x20 :
      aff = (aff+1)%4;
      glutPostRedisplay(); 
      break;
    case 0x1B :
      delete(p1);
      delete(p2);
      delete(p3);
      exit(0); 
      break; }
}

/* Fonction principale                          */

int main(int argc,char **argv) {
  p1 = new Position3D(30.0,20.0,0.0);
  p2 = new Position3D( 5.0,29.0,0.0);
  p3 = new Position3D( 9.0, 3.0,0.0);
  glutInit(&argc,argv);
  glutInitDisplayMode(GLUT_RGBA|GLUT_DOUBLE);
  glutInitWindowSize(350,350); 
  glutInitWindowPosition(50,50); 
  glutCreateWindow("Remplissage 2D triangle"); 
  glutKeyboardFunc(keyboard);
  glutReshapeFunc(reshape);
  glutDisplayFunc(display);
  glutMainLoop();
  return(0);
}