Project 2: Surface Subdivision and Animation for CS4451B

Last Updated: 10/03/2002

Introduction

The Challenge: Project Description

This page describes the implementation of a project assigned to our CS4451B class. The goal of the assignment is the construction and display of a smoothly animated and shaded solid starting from nothing.

This ambitious project was the vehicle for understanding

Who is responsible: Team Description and Biographies

Process Overview


Create an algorithm for performing butterfly subdivision on a triangle mesh. Illustrate the effects of this subdivision by performing a rendering of the mesh. Create movement paths for the original vertices of the mesh and animate the mesh along these paths. The project was divided among 4 parts, A - D. Each part is given its own section below.

Process Tools

Acknowledgements

Part A: Preliminaries

The Given Pseudocode

The following pseudo-FORTRAN-C-PASCAL-ish code was our first taste of triangle mesh subdivision. Professor Rossignac asked us to check it for mistakes, comment it and then possibly improve on it: 

 
 # this program takes a T-mesh as input and 
# computes a subdivided T-mesh using the 
# butterfly subdivision algorithm as output
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 vertices
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 = true/false it has been fourthed, M = midpoints
# compute the Opposite table
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 each point's midpoint and its opposite point's midpoint (the same)
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 triangles for new surface
i:=0; for c:=0 to 3t-1 do if c.f then {
        F[c]:=F[c.n]:=F[c.p]:=false;   # to avoid recalculating a new triangle
        W[i++]:= c.v; W[i++]:= c.p.m.v; W[i++]:= c.n.m.v; # W = array of new 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 above basically loads a file filled with vertices and triangle orientation information into a series of arrays. Then when referring to triangles in the mesh we use a corner table representation of the following oper ations:

Improvement on the above Pseudocode

Our improvement was a speed optimization. The above code contains a routine that calculates the opposites of all the corners in the triangle mesh. The code above performs a matching of corners that has a running time of O(n*lgn). Opposites are invaluable in both butterfly subdivision and rendering so there is no real way to just get rid of them. What our team noticed was that triangle subdivision allows us to perform the pairing of opposites in linear time along with the subdivision. The only consequence of this is that we decided to save the opposite information along with the model. This is the motivation for the following change in the code: 

 # this program takes a T-mesh as input and
 # computes a subdivided T-mesh using the
 # butterfly subdivision algorithm as output
 
 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 vertices
 
 read t, allocate(V[3t], O[3t]); for i:=0 to 3t-1 do read(V[i]); # t = number of triangles
 
for i:=0 to 3t-1 do read(O[i]); #read in opposites from file
 
 allocate(nO[12t], F[3t], M[3t], W[12t]); # M = midpoints, nO is new Opposite array
 
 #it is impplied that nO and F are initialized to -1
 #F is both to prevent redundancy and to index between the new corner table and the old
 
 # compute each point's midpoint and its opposite point's midpoint (the same)
 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 triangles and opposite table for new surface
i:=0; for c:=0 to 3t-1 do if c.f then {
   if(F[c] != -1)
        F[c] = i;
        W[i++]:= c.v;
        W[i++]:= c.p.m.v;
        W[i++]:= c.n.m.v;# W = array of new triangles
        W[i++]:= c.p.m.v;
        F[c.n] = i;
        W[i++]:= c.n.v; 
        W[i++]:= c.m.v;
        W[i++]:= c.n.m.v;
        W[i++]:= c.m.v;
        F[c.p] = i;
        W[i++]:= c.p.v;
        W[i++]:=  c.m.v;  
        W[i++]:= c.n.m.v;
        W[i++]:= c.p.m.v;
   }
 
#loop to compute opposites
i:=0; for c:=0 to 3t-1 do if c.f then {
   #don't be redundant!
   if(nO[c] != -1)
   {
        # compute opposites for inside the current triangle        
        j = F[c]
        nO[j] = j+9;
        nO[j+9] = j;
        nO[j+8] = j+11;
        nO[j+11] = j+8;
        nO[j+4] = j+10;
        nO[j+10] = j+4;
 
        #compute opposites for triangle opposite to point
        if(F[c.o] % 12 == 0) # first
             nO[j+3]=F[c.
o]+6;
             nO[F[c.o]+6]=j+3;
             nO[j+6]=F[c.o]+3; 
             nO[F[c.o]+3]=j+6;
        if(F[c.o] % 12 == 4) # second
             nO[j+3]=F[c.o.p]+1;
             nO[F[c.o.p]+1]=j+3;
             nO[j+6]=F[c.o.p]+7;
             nO[F[c.o.p]+7]=j+6;        
        if(F[c.o] % 12 == 8) # third
             nO[j+3]=F[c.o.n]+5;
             nO[F[c.o.n]+5]=j+3;
             n
O[j+6]=F[c.o.n]+2;
             nO[F[c.o.n]+2]=j+6;        
   }
}
 write (4k, X, Y, Z, 4t, W, nO);
 
end

Part B: Implementation of Subdivision

Data Structures

Now that the above refinement to the pseudocode was complete, it was time to create actual functioning code (which is a different animal altogether!). Everything was done in C and we used dynamic memory.

Subdivision Algorithm

The subdivision function became a bit lengthy, so we will split it into two parts, the actual subdivision part algorithm and the optimization part of the algorithm.

Optimization Algorithm

As we mentioned before, this keeps a mapping variable while creating all the new triangles from the new vertices and later uses this variable to find the correct opposites of the new triangle. As a result, subdivision is performed in linear time.

Drawing Algorithm

Having correctly coded the new algorithm it was time to actually visualize it it. Using the example code, we whipped up the following simple drawing algorithm for rendering triangle edges. And yes, we are aware that it draws each edge twice.

Wireframe Pictures

We were asked to draw and subdivide 4 different kinds of shapes. These are pictures of the original and after 3 subdivisions. Click on the model name for the model input data.

Tetrahedron

Cube

Torus

Nonconvex Solid

Part C: Smooth Shading

Normals

The next task is straighforward: take all the triangles we have created using our models and subdivision algorithms and smoothly shade them. So, how do you do that?
First, you must have oriented triangles, that is triangles whose vertices are fed into the rendering library either clockwise or counterclockwise. This lets the renderer know which way the triangle is facing! Luckily, our algorithm from parts A and B keeps track of this information after subdivision and passes it on to the derived surfaces.
Second, you must compute the normal at each vertex in the T-Mesh! This is performed by "walking" around the vertex using the triangle orientation kno wledge. Here are three pictures of a tetrahedron's triangle edges (in red) and the normals (in green).



The algorithm for walking, in pseudocode could be as follows

for all triangle points c
if c.vertex.normal != 0        #only compute necesary 
        test = c;  #get starting vertex
        do
               #sum all the crossproducts
               totalvector += crossproduct(vector(c.v, c.n.v), vector(c.v, c.p.v));
               c = c.p.o.p;
        while c != test #loop until we reach the starting vertex again
 
        c.vertex.normal = normalize(totalvector) #normalize vector


The actual C code (in all its hairy optimal glory) is here.

Part 2: OpenGL Rendering


Rendering in OpenGL is a cinch. You merely have to perform the following:

1. Set up your viewport


This is done using the glOrtho function and the current boundaries of the window. This should be called every time you redraw. glOrtho "sets up an orthographic projection matrix and defines a viewing volume that is a right paralellepiped." (Angel, 72)

2. Set up your lighting and materials


Next you want to introduce some lighting for your scene. We used OpenGL to configure the ambient, diffuse and specular properties of our lights. Every object in our scene associated with each type of light "has [the] reflectivity properties for each type of light" (Angel, 124). We added multiple lights with various properties and locations for interesting effects. The lighting code can be viewed here.

3. Render


Paradoxically, the rendering part is the simplest part of all of this. OpenGL uses the Phong model for its shading calculations. In our init callback function you can specify the shade model that openGL will use when rendering your triangles. This can be GL_SMOOTH or GL_FLAT. GL_FLAT only shades a triangle using the information about the first vertex normal. This isn't what we want. Instead we would rather have smooth shading and so we say glShadeModel(GL_SMOOTH), which ensures a very smooth surface (sidenote: when the triangle count becomes astronomical, the two shading models are nearly indistinguishable. Why? Because the variance of normals among vertices in a triangle becomes negligible!).
After setting the model, we simply loop through the triangles and draw them using the GL_TRIANGLES mode. One must only remember to precede each vertex by its normal. Here is the C code.

 

Part 3: Pictures of Part2, Source code deliverables, and references


Pictures of Tetrahedron after 3 successive subdivisions:

Pictures of Cube after 3 successive subdivisions:

Pictures of Torus (0 diffuse light) after 3 successive subdivisions:

Pictures of Nonconvex solid after 3 successive subdivisions:

 

REFERENCES



OpenG L: A PRIMER Edward Angel. Addison-Wesley 2002.
We also employed the friendly help of Mitch Parry, TA for CS4451B

Part C: Animation

Movement Paths

The final task of this project is to animate a solid. For simplicity's sake, consider animating the tetrahedron. This solid consists of 4 points. In order to make the solid move, we need to make these points move. To make these points move, we need to tell them where and how to move. In this project, our method for doing this is to define 4 places for these points to be a 4 different times. One of the implications of this is that we will have to define a new file format, where every vertex has 4 entries. Click here for the file of the example we show below. The illustration below shows the tetrahedron and a polygon defined by each of the 4 points at which each of the 4 points should be. Note: three of the polygons have no area.

Split and Tweak

If we animated using these polygons as control paths for the vertices, the animation would be over in 4 frames and would be very jerky. In order to make the animation smooth, we will perform a series of "Split and Tweak" subdivisions on these polygons. The result is a series of smooth curves. The number of frames = 4 * 2^n, where n is the number of subdivisions performed on the polygon. Here is the code to perform these subdivisions and here result of 5 of these:

< u>Simple animation

We now defined a routine to cycle the tetrahedron points through each of animation paths, and for each of the points along these paths, we subdivide the solid 5 times and perform a smooth rendering. Here is the code and here is a mpeg of the result. Be sure to set your MPEG player to loop the animation for a nice effect.

Production Animation

Our team's subdivision routine was fast enough to perform this animation in real-time. This gave us time to create the following video which includes sound and a visual exploration of the entire project process.

Project Conclusions

Butterfly subdivision is a computationally inexpensive way to make rigidly constructed T-mesh models smooth. As long as the corner table is manifold and correctly oriented, the algorithm can perform in linear time and performance can be tuned by decreasing the number of subdivisions performed. Even a mere 3 subdivisions increases the number of triangles by a factor of 64 and generates a very smooth image using the Phong shading model.

An important consequence of the cheapness of computation is that interesting effects, such as animation, can be implemented on the rigid and simple models. Then the results can be subdivided before rendering for attractive output. This saves both computing time and space.