//
//  bspline.m
//  Bspline
//
//  Created by Grant Gruetzmacher on Mon Aug 26 2002.
//  Assisted by Woo, Mason "OpenGL Programming Guide - Third Edition" Addison Wesley Boston, 1999
//  Assisted by Cristi Jones
//  
// This program implements two refinement techniques as described by Prof. Rossignac in cs4451
// at Georgia Tech, Atlanta, GA, called B-Spline and Four-Points, used to smooth the edges of
// polygons.  Both take as input a control polygon P with n vertices and produce a smoother
// control polygon with 2n vertices.  Both techniques start by inserting a new vertex in the middle
// of each edge P.  Then the B-Spline method pulls each original vertex half-way towards the average 
// of its two neighbors.  The four-point method pushes the newly inserted midpoints by 1/4 away from
// the average of the their neigboring midpoints on the left and right.  Repeating these smoothing
// methods on a polygon will become smoother.  Using these methods on vertex arrays from multiple 
// polygons, a surface may be created by first smoothing the polygons then smoothing and displaying 
// each cooresponding set of vertices from each polygon.
//

#include <GLUT/glut.h>
#include <stdio.h>
#include <stdlib.h>

#define numVertices 5
#define numPolygons 1
#define BDEBUG 0

typedef struct _point 
{
    float x;
    float y;
    float z;
} point;


/* polygonX, bsplineX, and fourptsX are arrays of pointers to
 * the point structure which holds the coordinates for each vertex
 * of the polygon; together these vertices create
 * the model data of the polygon.
 */
point** polygon0;
point** polygon1;
point** polygon2;
point** polygon3;
point** polygon4;
point** polygon5;
point** testpolygon;

point** bspline0;
point** bspline1;
point** bspline2;
point** bspline3;
point** bspline4;
point** bspline5;

point** fourpts0;
point** fourpts1;
point** fourpts2;
point** fourpts3;
point** fourpts4;
point** fourpts5;

/* Creates and returns pointer to a point structure created from the three
 * float parameters x, y, and z respectively
 */
point* makePoint( float pX, float pY, float pZ)  {
    point* temp = (point*)malloc(sizeof(point));
    if (temp == NULL)
	{ 
	    exit(EXIT_FAILURE); 
    } else {
	temp->x = pX;
	temp->y = pY;
	temp->z = pZ;
    }
    return temp;
}


/* Initializes the global polygons 0 thru 4.  Once called
 * the global polygon0 thru 4 will have vertex data within them. 
 */
void initPolygons() {
    if (BDEBUG) printf("begin initPolygons()");

    fflush(stdout);
    if (( polygon0 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }	
    if (( polygon1 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }
    if (( polygon2 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }
    if (( polygon3 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }
    if (( polygon4 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }    
    if (( polygon5 = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    } 
    if (( testpolygon = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    } 
    polygon0[0] = makePoint(0.1, 0.2, 0.1);
    polygon0[1] = makePoint(0.2, 0.05, 0.1);
    polygon0[2] = makePoint(0.3, 0.1, 0.1);
    polygon0[3] = makePoint(0.4, 0.3, 0.1);
    polygon0[4] = makePoint(0.45, 0.4, 0.1);    
    polygon1[0] = makePoint(0.5, 0.1, 0.3);
    polygon1[1] = makePoint(0.6, 0.05, 0.3);
    polygon1[2] = makePoint(0.65, 0.2, 0.3);
    polygon1[3] = makePoint(0.6, 0.3, 0.3);
    polygon1[4] = makePoint(0.45, 0.4, 0.3);
    polygon2[0] = makePoint(0.2, 0.5, 0.5);
    polygon2[1] = makePoint(0.3, 0.4, 0.5);
    polygon2[2] = makePoint(0.4, 0.6, 0.5);
    polygon2[3] = makePoint(0.45, 0.5, 0.5);
    polygon2[4] = makePoint(0.45, 0.9, 0.5);
    polygon3[0] = makePoint(0.6, 0.6, 0.7);
    polygon3[1] = makePoint(0.5, 0.4, 0.7);
    polygon3[2] = makePoint(0.7, 0.6, 0.7);
    polygon3[3] = makePoint(0.65, 0.9, 0.7);
    polygon3[4] = makePoint(0.55, 0.6, 0.7);
    polygon4[0] = makePoint(0.7, 0.5, 0.9);
    polygon4[1] = makePoint(0.75, 0.4, 0.9);
    polygon4[2] = makePoint(0.85, 0.6, 0.9);
    polygon4[3] = makePoint(0.9, 0.95, 0.9);
    polygon4[4] = makePoint(0.75, 0.6, 0.9);
    polygon5[0] = makePoint(0.1, 0.3, 0.1);
    polygon5[1] = makePoint(0.4, 0.3, 0.1);
    polygon5[2] = makePoint(0.9, 0.4, 0.1);
    polygon5[3] = makePoint(0.7, 0.8, 0.1);
    polygon5[4] = makePoint(0.2, 0.8, 0.1);  
    testpolygon[0] = makePoint(0.1, 0.1, 0.1);
//    testpolygon[1] = makePoint(0.1, 0.3, 0.1);
    testpolygon[1] = makePoint(0.15, 0.4, 0.1);
//    testpolygon[2] = makePoint(0.1, 0.3, 0.1);
    testpolygon[2] = makePoint(0.8, 0.8, 0.1);
    testpolygon[3] = makePoint(0.7, 0.2, 0.1);
    testpolygon[4] = makePoint(0.2, 0.8, 0.1);        
    if (BDEBUG) printf("end initPolygons()");
}


/* Uses the parameter pPolygon and pNumVertices to draw that polygon using the parameter
 * floats R, G, and B as its color.  This method uses OpenGL calls.
 */
int showPolygon(point** pPolygon, int pNumVertices, float pR, float pG, float pB) {
    int i;
    point* t;
    glColor3f(pR, pG, pB); // parameters NOT checked!
    glBegin(GL_LINE_LOOP);
    if (BDEBUG) printf("pNumVertices: %d\n", pNumVertices);
    for (i = 0; i < pNumVertices; i++) {
	t = pPolygon[i];
	if (BDEBUG) printf("i: %d\n", i);
	if (t != NULL) {
	    if (BDEBUG) printf("x:%f y:%f z:%f\n",t->x,t->y, t->z );
	    glVertex3f(t->x,t->y, t->z );
	}
    }
    glEnd();
    glFlush();
    if (BDEBUG) printf("end showPolygon()\n");
    return 1;
}

/* Using the parameter pPolygon and pNumVertices, this method uses the bSpline technique
 * to smooth the polygon and returns a polygon with pNumVertices*2
 */
point** bSpline(point** pPolygon, int pNumVertices) {
    float x, y, z;
    int i, j;
    /* midPoints is the array which holds the vertices that are at the midpoint between
     * two adjacent vertices of the parameter polygon
     */
    point** midPoints;
    /* newPoints is the array, where each vertex of the paramter polygon is moved by 1/4
     * towards it neighbors in parameter polygon
     */ 
    point** newPoints;
    /* finalPoints is the array composed of merging midPoints and newPoints
     */
    point** finalPoints;
    if (( midPoints = (point**)malloc(sizeof(point*)* pNumVertices) ) == NULL) {
	printf("malloc err");
	exit(EXIT_FAILURE);
    }
    if (( newPoints = (point**)malloc(sizeof(point*)* pNumVertices) ) == NULL) {
	printf("malloc err");
	exit(EXIT_FAILURE);
    }
    if (( finalPoints = (point**)malloc(sizeof(point*)* pNumVertices*2) ) == NULL) {
	printf("malloc err");
	exit(EXIT_FAILURE);
    }
    
    /*
     * This iteration creates the midpoints between two adjacent vertices of the parameter
     * polygon to create the array midPoints
     */
    for (i = 0; i < pNumVertices; i++) {
	x = (pPolygon[i%pNumVertices]->x + pPolygon[(i+1)%pNumVertices]->x)/2;
    	y = (pPolygon[i%pNumVertices]->y + pPolygon[(i+1)%pNumVertices]->y)/2;
	z = (pPolygon[i%pNumVertices]->z + pPolygon[(i+1)%pNumVertices]->z)/2;
	midPoints[i] = makePoint(x,y,z);
    }
    
    /* 
     * This iteration creates the newPoints array described above.  This pulls the vertex inward
     * from its original location, making the angle wider.
     */
    for (i = 0; i < pNumVertices; i++) {
    
	x = (pPolygon[(i+pNumVertices-1)%pNumVertices]->x + pPolygon[(i+1)%pNumVertices]->x)/2;
	y = (pPolygon[(i+pNumVertices-1)%pNumVertices]->y + pPolygon[(i+1)%pNumVertices]->y)/2;
	z = (pPolygon[(i+pNumVertices-1)%pNumVertices]->z + pPolygon[(i+1)%pNumVertices]->z)/2;
    
	x = (pPolygon[i%pNumVertices]->x + x)/2;
	y = (pPolygon[i%pNumVertices]->y + y)/2;
	z = (pPolygon[i%pNumVertices]->z + z)/2;
	
	x = (pPolygon[i%pNumVertices]->x + x)/2;
	y = (pPolygon[i%pNumVertices]->y + y)/2;
	z = (pPolygon[i%pNumVertices]->z + z)/2;
	
	newPoints[i] = makePoint(x,y,z);
    }
    /*
     *  This iteration merges newPoints and midPoints starting with newPoints
     */
    j = 0;
    for ( i = 0; i < pNumVertices; i++) {
	finalPoints[j] = newPoints[i];
	j++;
	finalPoints[j] = midPoints[i];
	j++;
    }
    free(midPoints);
    free(newPoints);	
    return finalPoints;
}	

/* Driver to demonstrate the bSpline technique.  Call bSpline 3 times
 * to achieve a relatively smooth curve
 */
void buildBSplines() {
    point** temp;    
    point** temp2;
    glClear(GL_COLOR_BUFFER_BIT);
    showPolygon(polygon5, numVertices, 0.0, 0.0, 0.0);
    temp = bSpline(polygon5,numVertices);
    showPolygon(temp, (numVertices*2), 0.9, 0.1, 0.1);
    temp2 = bSpline(temp,numVertices*2);
    showPolygon(temp2, numVertices*4, 0.1, 0.9, 0.1);
    bspline5 = bSpline(temp2,numVertices*4);
    showPolygon(bspline5, numVertices*8, 0.1, 0.1, 0.9);
    free(temp);
    free(temp2);
}

point** fourPts(point** pPolygon, int pNumVertices) {
    float x, y, z;
    int i, j;
    /* midPoints is the array which holds the vertices that are at the midpoint between
     * two adjacent vertices of the parameter polygon
     */
    point** midPoints;
    /* finalPoints is constructed from the vertices of midPoints by pushing that point
     * outward from the edge by 1/8 the distance from that point to the midpoint between
     * the next two vertices adjacent to the vertices in question  
     */
    point** finalPoints; 

    if (( midPoints = (point**)malloc(sizeof(point*)* pNumVertices) ) == NULL) {
	printf("malloc err");
	exit(EXIT_FAILURE);
    }
    if (( finalPoints = (point**)malloc(sizeof(point*)* pNumVertices*2) ) == NULL) {
	printf("malloc err");
	exit(EXIT_FAILURE);
    }
    /*
     * This iteration creates the midpoints between two adjacent vertices of the parameter
     * polygon to create the array midPoints
     */       
    for (i = 0; i < pNumVertices; i++) {
	x = (pPolygon[i%pNumVertices]->x + pPolygon[(i+1)%pNumVertices]->x)/2;
    	y = (pPolygon[i%pNumVertices]->y + pPolygon[(i+1)%pNumVertices]->y)/2;
	z = (pPolygon[i%pNumVertices]->z + pPolygon[(i+1)%pNumVertices]->z)/2;
	midPoints[i] = makePoint(x,y,z);
    }
    
    /* 
     * This iteration pushes the midpoints outward by 1/8 away from its neighbors in midPoints
     */
    for (i = 0; i < pNumVertices; i++) {
	float dx, dy, dz;
	x = (pPolygon[(i+pNumVertices-1)%pNumVertices]->x + pPolygon[(i+2)%pNumVertices]->x)/2;
	y = (pPolygon[(i+pNumVertices-1)%pNumVertices]->y + pPolygon[(i+2)%pNumVertices]->y)/2;
	z = (pPolygon[(i+pNumVertices-1)%pNumVertices]->z + pPolygon[(i+2)%pNumVertices]->z)/2;
	
	/* dx, dy, dz are delta values from the midpoint 
	   to be added to the midpoint x, y, z in the next step */
	dx = (midPoints[i]->x - x)/8;
	dy = (midPoints[i]->y - y)/8;
	dz = (midPoints[i]->z - z)/8;

	midPoints[i]->x += dx;
	midPoints[i]->y += dy;
	midPoints[i]->z += dz;
    }	
    /*
     *  This iteration merges the original parameter polygon vertices and midPoints vertices
     *  starting with the parameter polygon
     */
    j = 0;
    for ( i = 0; i < pNumVertices; i++) {
	finalPoints[j] = pPolygon[i];
	j++;
	finalPoints[j] = midPoints[i];
	j++;
    }
    free(midPoints);
    return finalPoints;
}

/* Driver to demonstrate the four points technique.  Call fourPts 3 times
 * to achieve relatively smooth curve.  FourPts interpolates the original vertices.
 */
void buildFourPts() {
    point** temp;
    point** temp2;
    glClear(GL_COLOR_BUFFER_BIT);
    showPolygon(polygon5, numVertices, 0.0, 0.0, 0.0);
    temp = fourPts(polygon5,numVertices);
    showPolygon(temp, (numVertices*2), 0.9, 0.1, 0.1);
    temp2 = fourPts(temp,numVertices*2);
    showPolygon(temp2, numVertices*4, 0.1, 0.9, 0.1);
    fourpts5 = fourPts(temp2,numVertices*4);
    showPolygon(fourpts5, numVertices*8, 0.1, 0.1, 0.9);
    free(temp);
    free(temp2);
}

void buildCompare() {
    glClear(GL_COLOR_BUFFER_BIT);
    showPolygon(polygon5, numVertices, 0.0, 0.0, 0.0);
    showPolygon(bSpline(bSpline(bSpline(polygon5,numVertices),numVertices*2),numVertices*4),numVertices*8, 0.9, 0.1, 0.1);
    showPolygon(fourPts(fourPts(fourPts(polygon5,numVertices),numVertices*2),numVertices*4),numVertices*8, 0.1, 0.9, 0.1);
}


/* Driver to demonstrate the surface created from BSplines
 * Pre: Method FAILS if numVertices is not 5
 */
void buildBsplineSurface() {
    int i;
    point** temp, **temp2;
    glClear(GL_COLOR_BUFFER_BIT);
    
   /* bspline the polygons to create 5 large arrays */ 
    bspline0 = bSpline(bSpline(bSpline(polygon0,numVertices),numVertices*2),numVertices*4);
    bspline1 = bSpline(bSpline(bSpline(polygon1,numVertices),numVertices*2),numVertices*4);
    bspline2 = bSpline(bSpline(bSpline(polygon2,numVertices),numVertices*2),numVertices*4);
    bspline3 = bSpline(bSpline(bSpline(polygon3,numVertices),numVertices*2),numVertices*4);
    bspline4 = bSpline(bSpline(bSpline(polygon4,numVertices),numVertices*2),numVertices*4);
/*    
    showPolygon(bspline0, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(bspline1, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(bspline2, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(bspline3, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(bspline4, numVertices*8, 0.0, 0.0, 0.0);    
*/    
    if (( temp = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }
    
    /* create the surface by calling bSpline on the array of vertices created by 
     * taking the each cooresponding vertex from the arrays bsplineX
     */
    for (i = 0; i < numVertices*8; i++) {
	temp[0] = bspline0[i];
	temp[1] = bspline1[i];
	temp[2] = bspline2[i];
	temp[3] = bspline3[i];
	temp[4] = bspline4[i];
	temp2 = bSpline(bSpline(bSpline(temp,numVertices),numVertices*2),numVertices*4);
	showPolygon(temp2, numVertices*8, 0.1, 0.9, 0.1);
	free(temp2);
    }
    free(temp);
 
    /*  The original polygons used in the surface 
	(commented out to emphasize the surface)
    
    showPolygon(polygon0, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon1, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon2, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon3, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon4, numVertices, 0.0, 0.0, 0.0);
    */

}

/* Driver to demonstrate the surface created from BSplines
 * Pre: Method FAILS if numVertices is not 5
 */
void buildFourPtsSurface() {
    int i;
    point** temp, **temp2;
    glClear(GL_COLOR_BUFFER_BIT);
    
    /* fourpts the polygons to create 5 large arrays */ 
    fourpts0 = fourPts(fourPts(fourPts(polygon0,numVertices),numVertices*2),numVertices*4);
    fourpts1 = fourPts(fourPts(fourPts(polygon1,numVertices),numVertices*2),numVertices*4);
    fourpts2 = fourPts(fourPts(fourPts(polygon2,numVertices),numVertices*2),numVertices*4);
    fourpts3 = fourPts(fourPts(fourPts(polygon3,numVertices),numVertices*2),numVertices*4);
    fourpts4 = fourPts(fourPts(fourPts(polygon4,numVertices),numVertices*2),numVertices*4);
/*    
    showPolygon(fourpts0, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(fourpts1, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(fourpts2, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(fourpts3, numVertices*8, 0.0, 0.0, 0.0);
    showPolygon(fourpts4, numVertices*8, 0.0, 0.0, 0.0);
*/    
    
    if (( temp = (point**)malloc(sizeof(point*)*numVertices)) == NULL) {
	printf("Malloc err");
	exit(EXIT_FAILURE);
    }
    
    /* create the surface by calling fourPts on the array of vertices created by 
     * taking the each cooresponding vertex from the arrays fourptsX
     */
    for (i = 0; i < numVertices*8; i++) {
	temp[0] = fourpts0[i];
	temp[1] = fourpts1[i];
	temp[2] = fourpts2[i];
	temp[3] = fourpts3[i];
	temp[4] = fourpts4[i];
	temp2 = fourPts(fourPts(fourPts(temp,numVertices),numVertices*2),numVertices*4);
	showPolygon(temp2, numVertices*8, 0.1, 0.9, 0.1);
	free(temp2);
    }
    free(temp);
 
    /*  The original polygons used in the surface 
	(commented out to emphasize the surface)
    
    showPolygon(polygon0, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon1, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon2, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon3, numVertices, 0.0, 0.0, 0.0);
    showPolygon(polygon4, numVertices, 0.0, 0.0, 0.0);
    */

}

/* TEST Method used to experiment with sharp edges etc.
 * Not used in final application.
 */
void buildTest() {
    point** temp;    
    point** temp2;
    glClear(GL_COLOR_BUFFER_BIT);
    showPolygon(testpolygon, numVertices, 0.0, 0.0, 0.0);
    temp = bSpline(testpolygon,numVertices);
    temp2 = bSpline(temp,numVertices*2);
    bspline5 = bSpline(temp2,numVertices*4);
    showPolygon(bspline5, numVertices*8, 0.1, 0.1, 0.9);

    showPolygon(fourPts(fourPts(fourPts(testpolygon, numVertices), numVertices*2),numVertices*4), numVertices*8, 0.0, 0.0, 1.0);
    free(temp);
    free(temp2);
}


/*  This is the OpenGL driver of the program.  It opens a separate window for 
 *  each of the following: 
 *  1. BSpline smoothed curve
 *  2. Four-Point smoothed curve
 *  3. BSpline smoothed surface
 *  4. Four-Point smoothed surface
 */
int main(int argc, char** argv) {

    if (BDEBUG) printf("Main\n");
    initPolygons();   
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    
    glutInitWindowSize(800,600);
    glutInitWindowPosition(100,100);
    glutCreateWindow("BSpline");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildBSplines);

    glutInitWindowSize(800,600);
    glutInitWindowPosition(150,150);
    glutCreateWindow("FourPts");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildFourPts);  
    
    glutInitWindowSize(800,600);
    glutInitWindowPosition(100,100);
    glutCreateWindow("Comparison of BSpline and Four-Pts");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildCompare);    
    
    glutInitWindowSize(800,600);
    glutInitWindowPosition(200,200);
    glutCreateWindow("B-Spline Surface");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildBsplineSurface);  
    
    glutInitWindowSize(800,600);
    glutInitWindowPosition(250,250);
    glutCreateWindow("Four-Pts Surface");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildFourPtsSurface);  
/*      
    glutInitWindowSize(800,600);
    glutInitWindowPosition(300,300);
    glutCreateWindow("Test Window");
    glClearColor(1.0, 1.0, 1.0, 0.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0, 1.0, 0.0, 1.0, -1.0, 1.0);
    glutDisplayFunc(buildTest);   
 */   
    glutMainLoop();

    return (EXIT_SUCCESS);
}