Project 1 : Curving Techniques

Grant P. Gruetzmacher
Prof. Rossignac
cs4451 - Project 1

Curve and Refinement Techniques:

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 neighboring midpoints on the left and right. Repeating these smoothing methods on a polygon will become smoother. See figure 1.1 and figure 2.1 for three time repeated B-Spline refinement and a three time repeated four-point refinement on the same polygon respectively. Each refinement is shown in a different color: original is black, refinement 1 is red, refinement 2 is green, final refinement 3 is blue. To force a B-Spline curve to have a sharp edge you can repeat a vertex 3 times (see figure 1.3). A four-point curve with 3 repeated vertices results in bubbles around that vertex (see figure 2.3). If there is a wide inner angle in the polygon, the curve will swing outside that vertex in B-Spline curves (see figure 1.4) and the curve will swing inside that vertex in four-point curves (see figure 2.4). A four-pts curve interpolates the original vertices while a B-Spline does not (see figure 0.1, original polygon is black, Four-Pts curve is green, B-Spline curve is red).

Implementation:

B-Spline is passed the pPolygon by an array of pNumVertices
I have implemented this approach by creating additional arrays midPoints and newPoints as intermediate arrays before merging the two to create finalPoints which is an array of vertices creating the returned smoother polygon. Follow these snips of commented code: 

    /*
     * 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++;
    }
Now, finalPoints is the new polygon.

Similarly, Four-pts is passed the pPolygon by an array of pNumVertices
I have implemented this approach by creating one additional array midPoints as an intermediate array before merging the midPoints and the original parameter polygon array to create finalPoints which is an array of vertices creating the returned smoother polygon. Follow these snips of commented code: 

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

The sample polygons have 5 vertices. The polygon arrays should have 3 or more vertices for the code to function without flaw.

I used the OpenGL graphics API version 1.2.1 on Mac OS X 10.1.5 to render polygons. The windows were set up using glut. Follow this snip of code for creating a window:

    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);


Follow this snip of code for rendering a polygon:

    glColor3f(pR, pG, pB); 
    glBegin(GL_LINE_LOOP);
    for (i = 0; i < pNumVertices; i++) {
	t = pPolygon[i];
	if (t != NULL) {
	    glVertex3f(t->x,t->y, t->z );
	}
    }
    glEnd();
    glFlush();


Surfaces:

Using the above 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. Follow this snip of code using the above algorithm for drawing a surface:
/* 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);

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


Examine figures 1.2 and 2.2 for examples of surfaces made using BSpline smoothing and Four-pt smoothing respectively.

The complete source files are:
bspline.m
Bspline.pbproj
English.lproj/InfoPlist.strings
English.lproj/MainMenu.nib


These project files were developed using Project Builder Version 1.1.1 (December 2001 Developer Tools) on Mac OS X 10.1.5 and OpenGL 1.2.1.



figure 0.1 B-Spline vs Four-Pts comparison - Polygon smoothing



figure 1.1 B-Spline technique - Polygon smoothing


figure 1.2 B-Spline technique - Surface smoothing


figure 1.3 B-Spline technique - 3 repeated vertices


figure 1.4 B-Spline technique - one wide angle


figure 2.1 Four-Pts Technique - Polygon smoothing


figure 2.2 Four-Pts technique - Surface smoothing


figure 2.3 Four-Pts technique - 3 repeated vertices


figure 2.4 Four-Pts technique - one wide angle