Last updated on - October 3, 2002 @ 8 PM
Team Apathy
Members:
- Meghan Byrne - gte705u@prism.gatech.edu
- David Mullen - gte963e@prism.gatech.edu
Objective:
The purpose of this project is to apply the "Butterfly Subdivision" scheme to a three-dimensional triangle mesh. After this is done, the same scheme will be applied to a mesh with vertices varying over time, appearing as an animation.
We plan to use Java and C as the programming
language, Linux as the operating system, and OpenGL as the graphic API for this
project. Java will be used to handle the computations of the object, reading in
the bare data for it, and outputting the subdivided data. The C program will
read in that new output, and use OpenGL to draw it to screen.
Part A: Preliminaries
# this program implements the
butterfly subdivision scheme for a triangle mesh
read k;
allocate(X[4k], Y[4k], Z[4k]); for i:=0 to k-1 do read(X[i], Y[i], Z[i]);
# k = original # of vertices
read t, allocate(V[3t]); for i:=0 to 3t-1 do
read(V[i]); # t = original # of
triangles
allocate(O[3t], F[3t], M[3t], W[12t]); # F = visited marker for corners, M = table of
midpoints
# compute table of
opposite corners
for c:=0 to 3t-2 do for b:=c+1 to 3t-1
do
if(c.n.v==b.p.v) &&
(c.p.v==b.n.v) then {O[c]:=b; O[b]:=c}; # compute
the midpoint vertex and point to it from the midpoint
table
i:=k-1; for c:=0 to 3t-1 do
{M[c]:=M[c.o]:=++i;
(X[i], Y[i],
Z[i]):=(c.n.v+c.p.v)/2+((c.v+c.o.v)/2-(c.l.v+c.r.v+c.o.l.v+c.o.r.v)/4)/4);
# compute the new V table of
triangles
i:=0; for c:=0 to 3t-1 do if c.f then
{
F[c]:=F[c.n]:=F[c.p]:=false; # to avoid repeating the
triangle
W[i++]:=c.v;
W[i++]:=c.p.m.v; W[i++]:=c.n.m.v; # W = new table
of triangle
vertices
W[i++]:=c.p.m.v;
W[i++]:=c.n.v;
W[i++]:=c.m.v;
W[i++]:=c.n.m.v;
W[i++]:=c.m.v;
W[i++]:=c.p.v;
W[i++]:=c.m.v;
W[i++]:=c.n.m.v; W[i++]:=c.p.m.v};
write(4k, X, Y, Z, 4t, W);
We plan on improving the efficiency of the code that calculates
the opposite table by checking to see if O[c] is already assigned before
entering the loop on b.
Our implementation will be fundamentally similar
to the reference code, plus the above efficiency improvement.
Part B: Implementation of Subdivision
The subdivision program was split up into two files. The first, written in Java, performs the actual "Butterfly Subdivision" algorithm. The second, written in OpenGL, draws the 3D object.
The input files are of the format:
<# of vertices>
x1 y1 z1
x2 y2 z2...
<# of triangles>
1 2 3
2 3 4
The "x1 y1 z1" is the xyz coordinate of every vertex that makes up the 3-D object. "1 2 3" is the arrangement of vertices that make up a surface triangle. The triangles are all arranged in a common arrangement (for our project, counter-clockwise), so that the "next", "opposite", etc. commands will yield the correct result.
Subdivision works by adding adjusted midpoints to an existing 3-D object's edges, according to a set formula. This adds a new vertex for every edge, and also new triangles that make up the surface. The result after running subdivision on an object a number of times is a new object with "rounded" surfaces. Here's the code that actually computes the new midpoints from the existing vertices, after the terminology such as "next" (.n) and "opposite" (.o) have been defined.
/** * This function calculates the midpoints based on the formula: * m.c = (c.n.v + c.p.v) / 2 + ((c.v + c.o.v)/2 -* (c.l.v + c.r.v + c.o.l.v + c.o.r.v)/4)/4
* The new vertices are appended to the x,y,z array, and * the M array references the vertex in these arrays */ public void calcMid() {int i = k - 1; //start adding vertices after the existing ones
for(int c=0; c<3*t; c++) {if (M[c] == -1) { //if the midpoint hasn't already been found
i++;M[c] = i; //a corner and its opposite have the same
M[O[c]] = i; //midpoint
// calculates the new x,y,z X[i] = ((X[V[ct.next(c)]] + X[V[ct.prev(c)]]) / 2.0f) +((((X[V[c]] + X[V[O[c]]]) / 2.0f) -
((X[V[ct.left(c)]] + X[V[ct.right(c)]]
+ X[V[ct.left(O[c])]] + X[V[ct.right(O[c])]]) / 4.0f)) / 4.0f); Y[i] = ((Y[V[ct.next(c)]] + Y[V[ct.prev(c)]]) / 2.0f) +((((Y[V[c]] + Y[V[O[c]]]) / 2.0f) -
((Y[V[ct.left(c)]] + Y[V[ct.right(c)]]
+ Y[V[ct.left(O[c])]] + Y[V[ct.right(O[c])]]) / 4.0f)) / 4.0f); Z[i] = ((Z[V[ct.next(c)]] + Z[V[ct.prev(c)]]) / 2.0f) +((((Z[V[c]] + Z[V[O[c]]]) / 2.0f) -
((Z[V[ct.left(c)]] + Z[V[ct.right(c)]]
+ Z[V[ct.left(O[c])]] + Z[V[ct.right(O[c])]]) / 4.0f)) / 4.0f);}
} }
Here are the shapes that were chosen, and how they look as they go through 3 consecutive phases of subdivision. The name of each shape links to the input file used to draw the original shape.
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
|
|
| |
|
|
|
|
Part C: Smooth Shading and Video
This program calculates the surface normal vectors of the triangle mesh, and uses those for adding lighting and shading effects to the models chosen above.
The subdivision program takes in the input file, subdivides the object, and outputs the resulting file as usual, but it was modified to also calculate the surface normal vector for each vertex, and outputs a table of the normals. Here is the code that calculates the normals.
/** * This function takes in an integer which indicates a corner and * computes the normal at that vertex. * For each corner that represents the same vertex, it determines * the two vectors from that corner to the other two corners in the * triangle, computes the cross product of those two vectors, and* sums up these cross products, to obtain the vertex normal. It
* then normalizes it and sets the value in the normal array. */ public void vertexNormal(int c) { int b = c; float[] n = {0, 0, 0}; do {float[] v = new float[3];
float[] w = new float[3];
float[] cross;
v[0] = ct.X[ct.V[ct.next(c)]] - ct.X[ct.V[c]];
v[1] = ct.Y[ct.V[ct.next(c)]] - ct.Y[ct.V[c]];
v[2] = ct.Z[ct.V[ct.next(c)]] - ct.Z[ct.V[c]];
w[0] = ct.X[ct.V[ct.prev(c)]] - ct.X[ct.V[c]];
w[1] = ct.Y[ct.V[ct.prev(c)]] - ct.Y[ct.V[c]];
w[2] = ct.Z[ct.V[ct.prev(c)]] - ct.Z[ct.V[c]];
cross = crossProduct(v, w);
n[0] += cross[0];
n[1] += cross[1];
n[2] += cross[2];
c = ct.next(ct.O[ct.next(c)]);
} while(c != b); float len = (float)Math.sqrt(n[0] * n[0] + n[1] * n[1] + n[2] * n[2]); n[0] = n[0] / len; n[1] = n[1] / len; n[2] = n[2] / len; normals[ct.V[b]] = n; }
After outputting, the drawing program reads in the subdivision output and the normal table. The object is drawn from the subdivision output, and the normal table is used to determine how the object is lighted and shaded. This is handled by special OpenGL functions. Here is some sample code of how this is set up and done.
/* OpenGL init function
* Clears the background, creates a display list,
* and draws the triangles by interating on the tArray */void init(void) { int i; /* defines the ambient and specular components of the polygon material */ GLfloat mat_ambient[] = { 0.0, 0.5, 0.5, 1.0 }; GLfloat mat_specular[] = { 1.0, 1.0, 1.0, 1.0 }; GLfloat mat_shininess[] = { 25.0 }; /* defines the positions and colors of two lights */ GLfloat light_position[] = { 1.0, 1.0, 1.0, 0.0 }; GLfloat light_position2[] = {-3.5, -3.5, -1.0, 0.0}; GLfloat light_color1[] = {1, 0, 0, 1}; GLfloat light_color2[] = {0, 0, 1, 1}; /* set the clear color to black */ glClearColor (0.0, 0.0, 0.0, 0.0); /* set the shading model to smooth */ glShadeModel(GL_SMOOTH); /* set the material components to the values defined above */ glMaterialfv(GL_FRONT, GL_AMBIENT_AND_DIFFUSE, mat_ambient); glMaterialfv(GL_FRONT, GL_SPECULAR, mat_specular); glMaterialfv(GL_FRONT, GL_SHININESS, mat_shininess); /* set the light characteristics to the values defined above */ glLightfv(GL_LIGHT0, GL_POSITION, light_position); glLightfv(GL_LIGHT0, GL_SPECULAR, light_color1); glLightfv(GL_LIGHT1, GL_POSITION, light_position2); glLightfv(GL_LIGHT1, GL_SPECULAR, light_color2); glLightfv(GL_LIGHT1, GL_DIFFUSE, light_color2); /* enable the two lights */ glEnable(GL_LIGHTING); glEnable(GL_LIGHT0); glEnable(GL_LIGHT1); glEnable(GL_DEPTH_TEST);displist = glGenLists(1); /* start display list */
glNewList(displist, GL_COMPILE);glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); /* fill the triangles */
glBegin(GL_TRIANGLES); /* Each iteration defines one triangle */ for (i=0; i<t; i++) { /* set the normal at each vertex and then set the vertex */ glNormal3f(normals[tArray[i].v1].x, normals[tArray[i].v1].y, normals[tArray[i].v1].z); glVertex3f(vArray[tArray[i].v1].x, vArray[tArray[i].v1].y, vArray[tArray[i].v1].z);
glNormal3f(normals[tArray[i].v2].x, normals[tArray[i].v2].y,normals[tArray[i].v2].z);
glVertex3f(vArray[tArray[i].v2].x, vArray[tArray[i].v2].y, vArray[tArray[i].v2].z);
glNormal3f(normals[tArray[i].v3].x, normals[tArray[i].v3].y,normals[tArray[i].v3].z);
glVertex3f(vArray[tArray[i].v3].x, vArray[tArray[i].v3].y, vArray[tArray[i].v3].z);
} glEnd();glEndList(); /* ends the display list */
}
Here are pictures of the surfaces chosen above, after taking the last subdivision displayed and shading its surface.
|
Tetrahedron |
|
|
Cube |
|
|
Torus |
|
|
Non-convex |
|
Part D: Animation
Here are links to the final versions of the source code for this project.
The Butterfly subdivision code can be found here.
The
triangle mesh code can be found here.
The
surface normal vector code can be found here.
The
vertex timed movement code can be found here.
The
main controlling program can be found here.
The
drawing source code can be found here.
(Makefile is here)
A
script file used to pass input files to the drawing program, and outputs PPM
files in numerical order can be found here.
- The animation for the cube can be found here. (Input file is here)
- The animation for the non-convex shape can be found here. (Input file is here)
The input files are of the format:
<# of vertices>
x1,t1 y1,t1 z1,t1
x1,t2 y1,t2 z1,t2
x1,t3 y1,t3 z1,t3
x1,t4 y1,t4 z1,t4
x2,t1 y2,t1 z2,t1...
<# of triangles>
1 2 3
2 3 4
The "x1,t1" is the x coordinate of vertex 1, at time 1. There are four time positions for each vertex, which are used to create a "path" for the vertices to follow to create an animation.
In order to create the path, each similar vertex in time is used as points in a control polygon, which is passed 5 times through the B-spline code in Curves.java. This creates 128 points in time.
Next, a triangle mesh is created from all the vertices at each of the 128 points in time. Each mesh is subdivided 4 times by using the Butterfly subdivision code in Subdivision.java. Then, normals are calculated for the subdivided mesh by using the surface normal vector code in Normals.java. Each mesh and list of normals is outputted to an individual text file.
/** * This function constructs a new CornerTable for each triangle mesh* at each point in time. It then performs butterfly subdivision
* on the mesh four times and outputs the resulting mesh to text file. * Finally it calculates the normals of all the vertices in the * subdivided mesh, and outputs those to another file. */ public void constructMeshes(String fileStart) { for(int i=0; i<X.length; i++) {CornerTable ct = new CornerTable(X[i], Y[i], Z[i], V, k, t);
Subdivision mesh = new Subdivision(ct);
for(int j=0; j<4; j++) {
mesh.subdivide();}
mesh.writeFile(fileStart + (i+1) + ".txt");
Normals norm = new Normals(ct);
norm.calcNormals();
norm.writeFile(fileStart + (i+1) + "-norm.txt");
} }
The shell script, drawscript, iterates through all of the text files and passes them to drawing.c, which outputs the frame buffer to a .PPM file. The script then converts all of them to JPEGs. Finally, we use the program Slide Show Movie Maker to compile all of the JPEGs into an AVI file.
Summary
Our animation tool is
computationally elegant in design, but is based on a strictly constrained set of
inputs. The movement of the points in time must be statically defined in the
input file. The use of Java for the computational code made for a clean and
easily implemented solution, but the computation is also very slow. The use of
intermediate text files between the Java code and the OpenGL drawing code
requires sufficient temp space, as does the generation of 128 PPM files. Also,
the Slide Show Movie Maker program is Windows based, so creating the AVI movies
out of the JPEGs required switching computers, which is kind of inconvenient.
Basically, it looks nice and it works well for this project, but it wouldn't be
very useful for much else.