|
CS 4451B - Project 2 - Team Greenlee
|
Charles Brian Quinn
gte430p@prism.gatech.edu
Brandon Yarbrough
gte055u@prism.gatech.edu
The goals of this project:
- Create 4 files (cube, tetrahedron, torus, and non-convex shape such as an
Lshape figure) 3D format.
- Perform the Butterfly Subdivision of Triangle meshes on the files to
create new (larger) files.
- Display these triangle meshes in OpenGL.
- Implement smooth shading and lighting using the calculated vector normals.
- Animate the objects by specifying a simple control polygon of 4 points for
each vertex, and subdividing using a uniform cubic B-spline to smooth the
animation.
- Create movie files of animations.
The objective of this portion of the project is to implement a simple subdivision
algorithm. The program will take in a file, and compute a new file that is
4 times longer, with 4 times as many triangles, each triangle is subdivided into
4 based on the butterfly subdivision algorithm.
We plan on using the C language, compiled on Linux, using OPENGL and
the GLUT library utilities.
The general algorithm employed to implement the butterfly subdivision on
triangle mesh surfaces is as follows:
# general algorithm for butterfly subdivision on triangle mesh surfaces
# this program will take in a three dimensional shape, and then subdivides into a smooth shape.
read k; allocate(X[4k], Y[4k], Z[4k]);
for i:=0 to k–1 do
read(X[i],Y[i],Z[i]); # k = number of points in shape
read t, allocate(V[3t]);
for i:=0 to 3t–1 do
read(V[i]); # t = number of triangles
allocate(O[3t], F[3t], M[3t], W[12t]); # F = first points nearest (f in the diagram), M = midedge points
# compute the o table (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 edges for each corner and the midpoint offset
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 entries in terms of c
i:=0;
for c:=0 to 3t–1 do if c.f then {
F[c]:=F[c.n]:=F[c.p]:=false; # to avoid unnecessary repetition
W[i++]:= c.v; W[i++]:= c.p.m.v; W[i++]:= c.n.m.v; # W = new V table with 4 times as many triangles
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);
The code, while accurate, is inefficient. Improvements could come in
saving some of the temporary stuff it sets up so that when it's run again (which
it will be), it will not have to compute as much of the O-table the second time.
There will be many changes in this code when it is redone in C. For
instance, use of features like realloc will make table expansion easier.
Also, reading and writing will be much more complex. A file specification
will be made to ensure valid input. There may be small optimizations
throughout.
| Part B: Implementation of Subdivision |
We created 4 files to implement subdivision. We created a cube, a tetrahedron,
an l-shaped figure, and a torus. The data files are
included below. We had some difficulties implementing the torus and
l-shaped figure, but have since been worked out. The l-shaped figure had a
misaligned corner (as detected by our subdivision algorithm). All files
are correct now. Updated page to reflect changes on Monday, September
29 2002. 23:38 EST
The program is divided into two parts. One part simply draws a triangle mesh representation of a shape in 3D space based on an input tgz
file (see specification of tgz file below).
The draw program uses the GLUT toolkit to set up the window and draw the
polygons for the triangle mesh representation.
To initialize the glut libraries and set up the window we make several
glutInit calls.
glutInit(&argc, argv); # initalizes glut
glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize (Vx_max-Vx_min, Vy_max-Vy_min);
glutInitWindowPosition (100, 100);
glutCreateWindow (argv[0]);
/* read in files and do usage checking */
init (); # init sets up the model for shading and lighting (implemented later) see below
glutDisplayFunc(display); # called to draw the shapes
glutReshapeFunc(reshape); # called when window is resized (and upon opening)
glutMouseFunc(mouse); # used to capture mouse events
glutMainLoop(); # goes into the main loop to keep image displayed and poll for mouse
To create the polygonal representation, we used the GL_TRIANGLES methods for
drawing in GLUT.
glBegin(GL_TRIANGLES);
glVertex3f(V1x, V1y, V1z); # specifying vertexes as floats
glVertex3f(V2x, V2y, V2z);
glVertex3f(V3x, V3y, V3z);
The usage for the draw program is:
./draw <inputfile>
You can superimpose one image over another by typing in two input files after
proj2.
The subdivision program is invoked from the command line. It takes in
file based on the specifications provided below, and outputs a file in those
same specifications, only with 4 times as many points, as a result of subdivison.
We first implemented a data structure to hold the shape information.
typedef struct Shape
{
int numVertices; /*we must know how many vertices*/
float *vTable; /*this is an array with numVertices*3 elements.
* It is a list of vertices and their 3D locations*/
int *tTable; /*this is an array with (2*numVertices - 3)*3
* elements. It is a list of triangles (counter-
* clockwise sides out)*/
int numTris;
} *Shape, Shape_Typ;
The subdivision is implemented as follows:
vTable = inShape->vTable;
for(c=0;c<vTable[counter*3]=0;
outShape->vTable[counter*3]=
(vTable[3*V(inShape,N(c))]
+ vTable[3*V(inShape,P(c))])/2;
outShape->vTable[counter*3]+=
(
( vTable[3*V(inShape,c)]
+ vTable[3*V(inShape,oTable[c])]
)/2
-
(
vTable[3*L(inShape,c,oTable)]
+ vTable[3*R(inShape,c,oTable)]
+ vTable[3*L(inShape,oTable[c],oTable)]
+ vTable[3*R(inShape,oTable[c],oTable)]
)/4
)/4;
outShape->vTable[counter*3+1]=
(vTable[3*(V(inShape,N(c)))+1]
+ vTable[3*(V(inShape,P(c)))+1])/2
+
(
( vTable[3*(V(inShape,c))+1]
vTable[3*(V(inShape,oTable[c]))+1]
)/2
-
(
vTable[3*(L(inShape,c,oTable))+1]
+ vTable[3*(R(inShape,c,oTable))+1]
+ vTable[3*(L(inShape,oTable[c],oTable))+1]
+ vTable[3*(R(inShape,oTable[c],oTable))+1]
)/4
)/4;
outShape->vTable[counter*3+2]=
(vTable[3*(V(inShape,N(c)))+2]+
vTable[3*(V(inShape,P(c)))+2])/2
+
(
( vTable[3*(V(inShape,c))+2] +
vTable[3*(V(inShape,oTable[c]))+2]
)/2
-
(
vTable[3*(L(inShape,c,oTable))+2]
+ vTable[3*(R(inShape,c,oTable))+2]
+ vTable[3*(L(inShape,oTable[c],oTable))+2]
+ vTable[3*(R(inShape,oTable[c],oTable))+2]
)/4
)/4;
The usage for the subdivision (curving) program is:
./curver <inputfile> <outputfile>
So, to subdivide and display a polygon, we do the following:
./curver cube1.tg1 cube2.tg1
./draw cube2.tg1
Here is the result of the cube after successive levels of subdivision:
Here is the result of the tetrahedron after successive levels of subdivision:
Here is the result of the torus after successive levels of subdivision:
The input data files (tetra1.tg1,
cube.tg1, torus.tg1, and
lshape.tg1) are of the following format:
---
<tag for our file>
<# of vertices>
<list of vertices coordinates in x y z>
<list of triangles>
---
Example data file (cube):
---
BSV1
8
0 0 0
2 0 0
2 2 0
0 2 0
0 0 2
2 0 2
2 2 2
0 2 2
3 1 2
0 1 3
7 5 4
7 6 5
7 3 2
2 6 7
1 4 5
4 1 0
2 1 5
6 2 5
7 4 0
3 7 0
---
The complete tar ball for Part B (including the makefile, shapes, and images)
can be obtained here:
http://www.seebq.com/cs4451/project2/team_greenlee_prj2_a.tar
We added smooth shading to our models using OpenGL and the GLUT toolkit.
We first calculated the normals for each vertex and inserted them into the code
that draws the shape. Essentially the only thing we had to add was the
OpenGL command to set the normals before each glVertex3f() comand.
glNormal3fv( vertex normal array );
glVertex3f(vertex_x, vertex_y, vertex_z);
The normal was calculated using the corner table data structure to go around
a vertex and sum up cross products of pairs of leading edge vectors. Using
this method we can get an estimate for the surface normal at that vertex.
When we found each pair, we simply added up the normals and then called:
glEnable(GL_NORMALIZE);
This enabled us to normalize the vectors to unit length one.
We used different views and added some ambient and positioned lighting to
obtain better angles of our models.
To set up the shading and lighting, in the init() procedure:
GLfloat mat_specular[] = { 1.0, 1.0, 1.0, 1.0 };
GLfloat mat_shininess[] = { 50.0 };
GLfloat light_position[] = { 1.0, 1.0, 1.0, 0.0 };
glClearColor (0.0, 0.0, 0.0, 0.0);
glShadeModel (GL_SMOOTH);
glMaterialfv(GL_FRONT, GL_SPECULAR, mat_specular);
glMaterialfv(GL_FRONT, GL_SHININESS, mat_shininess);
glLightfv(GL_LIGHT0, GL_POSITION, light_position);
glEnable(GL_LIGHTING);
glEnable(GL_LIGHT0);
glEnable(GL_DEPTH_TEST);
Below are all 4 subdivisions on the 4 models.
We applied some ambient blue lighting to the torus, just for fun by using:
/* blue color in RGB */
GLfloat light1_color[] = { 0.0, 0.0, 1.0, 1.0 };
glLightfv(GL_LIGHT1, GL_AMBIENT, light1_color);
The updated tar ball for part C (including make and the shapes with usage) is located here:
http://www.seebq.com/cs4451/project2/team_greenlee_prj2_c.tar
In order to implement animation, we first extended the input files so that
each vertex is represented by 4 points. The total number of coordinates is
now 12. For the first of the four vertices, we simply use the first point.
We then moved the other 3 points by a small amount, to create a "bulging" or
transformation of the object.
The input data files (tetra1.tg3,
cube.tg3, torus.tg3, and
Lshape.tg3) are now of the following format:
---
<tag for our file>
<# of vertices>
<# of triangles>
<vertex1 coordinates in x y z for frame 1>
<vertex1 coordinates in x y z for frame 2>
<vertex1 coordinates in x y z for frame 3>
<vertex1 coordinates in x y z for frame 4>
<vertex2 coordinates in x y z for frame 1>
<vertex2 coordinates in x y z for frame 2>
...
<list of triangles>
---
Example data file (tetrahedron):
---
BSV3
4
4
0 0 0
-1 0 0
-2 0 0
-3 0 0
1 0 0
1.5 0 0
3 0 0
4.5 0 0
1.5 0 1
1.5 0 1
1.5 0 1
1.5 0 1
1 1 0
1 2 0
1 3 0
1 4 0
3 0 1
3 1 2
3 2 0
1 0 2
---
We are essentially defining a control polygon to move the vertices. We
then subdivided this control polygon using a uniform cubic B-spline subdivision
algorithm to create a smooth motion through the vertices.
Point bspline_find_new_point (Point pt1, Point pt2, Point pt3, Point pt4) {
Point midPoint, midPointprime, toReturn;
// find new midpoint between 2 and 3
midPoint.x = (pt2.x + pt3.x) / 2;
midPoint.y = (pt2.y + pt3.y) / 2;
midPoint.z = (pt2.z + pt3.z) / 2;
// find midpoint of p1 and p4
midPointprime.x = (pt1.x + pt4.x) / 2;
midPointprime.y = (pt1.y + pt4.y) / 2;
midPointprime.x = (pt1.z + pt4.z) / 2;
// find length of new midpoint and other midpoint
// take 1/8 of this length
// add to new midpoint
toReturn.x = midPoint.x + (midPoint.x - midPointprime.x)/8;
toReturn.y = midPoint.y + (midPoint.y - midPointprime.y)/8;
toReturn.z = midPoint.z + (midPoint.z - midPointprime.z)/8;
return toReturn;
}
The B-spline helper function above uses the 4-point method, to interpolate
the vertices. It is only calculated when displaying the 128 points.
We had to reformat our shape structure in order to accommodate these changes:
typedef struct Shape
{
int numVertices; /*we must know how many vertices*/
float *vTable; /*this is an array with numVertices*3 elements.
* It is a list of vertices and their 3D locations*/
int *tTable; /*this is an array with (2*numVertices - 3)*3
* elements. It is a list of triangles (counter-
* clockwise sides out)*/
int numTris;
int curVTable; /* the current index that the vTable is set to*/
int numTables; /* the number of vTables*/
float **vTables; /* an array of vTables*/
} *Shape, Shape_Typ;
We subdivided this control polygon a total of 5 times, to create 128 frames
of motion.
/* last step - B-spline control point subdivision 5 times */
/* this executes 5 times to turn the 2^2 points to 2^(2+5), or 128, points. */
bSpline(shape);
bSpline(shape);
bSpline(shape);
bSpline(shape);
bSpline(shape);
Because the only difference between the new shapes is the location, we do not
recalculate the vtables for each frame. We only store 4 different vtables,
when we display, we have 128 tables. The O-table and T-tables are only
calculated once, allowing for optimization.
Our animation program is simply an update to the draw program. We used
the
movie-win.c files found on the
CS4451: Computer
Graphics home page. We created 128 .ppm files by capturing the
frameBuffer and writing it to disk. We then converted these .ppms to an
mpeg using a program called mjpeg (http://mjpeg.sourefourge.net/).
|
Interesting Animations / Models
|
|
Lshape Animation without rotating camera angle
|
Squirrel Model
(source obtained from Brandon B
modified to BSV3 format) |
|
Project Potentials & Limitations
The project can generate complex, unique, smooth animations from relatively
very little information. The files used to create these animations are a
few lines long, yet the program can generate thousands of lines of new point
information. The draw program is robust and can perform many calculations
to display these new complex shapes with lighting and shading and even rotating
of the view. This program could potentially be used to generate complex
models from simple representations in a short amount of time.
The project is limited in that we can only use non-convex objects.
Also, the objects can only be triangle meshes, that have to be aligned.
Figuring out this alignment can be tricky. Most objects used in 3D
animation can be constructed using triangles, but often times a polygonal
approach for the primitives is used. Also, the animations require a
knowledge in advance of the tweaking, and the points can only move a small bit.
We cannot specify more complex paths for movement of points, since we only start
from 4. The objects must also be watertight.
While the computations are not that intensive, we tried our program on a
model that contained over 9000 vertices. The object was a squirrel, and
the subdivision and animation took almost an hour to complete (before we gave
up). Given more time, we could implement more optimizations, and perhaps
generate code for special hardware to speed it up.
Code & Files
Makefile
shape.h
shape.c
curver.c
proj2.c
--
Lshape.tg3
torus.tg3
tetra.tg3
cube.tg3
The complete code can be found at:
http://www.seebq.com/cs4451/project2/team_greenlee_final.tar.gz
Last updated: Tuesday, Oct 4 2002. 13:10 EST
