Welcome to Thamine and Steven's CS283 Project 1 Page

Steps to decimation (written in order. An indent represents things that happen within that process): 
Initialize:
First, we initialize the 2D error lookup vector<vector<float>> (or 2D matrix).

Then read the .off file:
 Vertices:
 We push back each vertex into a vector<vec3> containing all vertices.
 For each vertex, we initialize an empty adjacency list. 
 We maintain the center of mass of the model by averaging all (X, Y, Z) vertices. This is used to center the model later by translation.

 Faces:
 We push back each face into a vector<int> of faces remaining (faces in the model).
 We also push back each v1, v2, v3 of a given face into a vector<vec3> of corresponding face vertices.
 Using our list of vertices, we compute face normals and push them into a vector<vec3>. 
 For each v1, v2, v3 of the face, we push the face into the respective adjacency lists.

Centering the model:
 We want to normalize the model to camera's viewpoint, which is looking at (0,0,0), so we calculate the distance d to the point furthest from the center of mass and we translate all the points by subtracting the center of mass to center the model at (0,0,0) and divide all vertices by distance d. Translation and scale do not affect the previously calculated normals. 

Calculating Vertex Normals:
 Iterate through each vertex.
 Using the adjacency list, we find all the faces adjacent to the vertex.
 Extract and average face normals and push them into a vector<vec3> of vertex normals.

Quadric Matrices:
 Iterate through each vertex V.
 Calculate plane equations for each face in the vertex adjacency list, where ax+by+cz+d = 0, (a,b,c) = normal N, N(x,y,z) + d = 0, and that means d = -N*V.
 For each adjacent face, we have (a,b,c,d). Our Q matrix requires 10 floating points, which are (aa,ab,ac,ad,bb,bc,bd,cc,cd,dd). We sum the 10 floating points for each adjacent face and store them in a vector<float[10]>.

Error Initialization:
Iterate through each face F.
Get v1, v2, v3 in F.
Calculate v' using equation in Garland 97. We proceed to store that in a map using make_pair(v1,v2) as keys, where v1 and v2 are ints. 
If the determinant equals 0, we just use v' = (v1+v2)/2 and recalculate error. 
Calculate error for v1-v2, v2-v3, v1-v3 using err = v'*Q*v', where Q = SUM of quadric matrices for v1 and v2. Store the error in a vector<vector<float>> using v1 and v2 as indices.

Decimation (Basic Algorithm):
Lookup v' in our map using make_pair(v1,v2).
Set the coordinates for v1 and v2 to v' in vector<vec3> vertices
Obtain adjacency list of faces for v1 and v2.
We iterate through each list and remove faces common to both adjacency lists.
For each Face F removed from both lists, we remove F from the third vertex's adjacency list, and we remove F from the list of face remaining. Since display iterates through faces remaining, time to display a model will decrease as we decimate.
For each face left in v2's adjacency list, we change any v2's to v1.
Append the adjacency list of v2 to the adjacency list of v1.
We create an empty set <int> which allows no duplicates.
For each face in v1's adjacency list, we recalculate the normal and we push the face vertices (v1,v2,v3) into the set.
We iterate through each vertex of the set, and we recalculate the vertex normals by averaging adjacent face normals.
Then we return the set. (We always decimate lowest err(v1,v2))

void Decimate():
Iterate through each face in faceRemaining.
Lookup error of v1-v2, v2-v3, v3-v1.
Keep track of lowest error pair (x,y)
Set returned = decimation algorithm(x,y) (noted above).
For each pair of vertices in returned, we recalculate error and the resulting v'.
Relevant information is stored into .txt files in order to repair mesh from decimation.

void Undecimate():
Look at .txt files.
Reconstruct the model prior to last decimation.

Heptoroid (Original 35,000)

Heptoroid 20000

Heptoroid 10000

Heptoroid 5000

Heptoroid 1000

Heptoroid 500

TROUBLES IN PART 1(Mesh Viewer):

None. We just talked about how to do it, and we took Ravi's advice and started with hw2's skeleton code from cs184. 

TROUBLES IN PART 2(Mesh Connectivity Data Structure):

We really flew by this part. This would be our adjacency list and it helped shape us up for part 3.

TROUBLES IN PART 3(Mesh Decimation):

To start off testing this part of the problem, we created a small 9 vertice 8 faced square with a diamond inside and wrote that into an .off file. We wanted to make sure that a small model would decimate correctly and that we were understanding the problem correctly before we moved onto the bigger models. It was a great debugging tool.

TROUBLES IN PART 4(Quadric Error):

None. Finished in about 5 hours, and our models began decimating correctly afterwards. The paper was a really good resource that guided us.

TROUBLES IN PART 5(Progressive Meshes):

For this last problem, we simply worked backwards from what we did for our decimation. So we drew on a blackboard the exact things we needed to store into a .txt file (we would read off the .txt file and recreate our model). 

Once we read in the .txt file, it was quite simple restoring the original vertices. What we ended up doing was creating a .txt file for each decimation (to keep track of what was deleted so we can use it later). So if it was a 2000 vertice model, we'd have 1000 .txt files. This might not be the most memory friendly way to go about it, since each decimation would produce a 1KB file, but it is the most efficient way, as our reconstruction restores our decimation in under 10 seconds and deletes every single .txt file along the way. Below is a video demonstrating the progressive mesh and final product. It reconstructs the cow in under 10 seconds.

TRIALS AND TRIBULATIONS:

Our program is limited by the amount of memory in our computers. For example, if we passed in 10,000 vertices, on O(V^2) memory, we'd end up with ~10^10 which is roughly about 10 gigabytes of memory(which depending on your computer space will execute or run out of memory).  

Also, some of the shading for the models are messed up/don't show because the adjacent faces were triangle fins and their normals just became 0 after decimation. We weren't able to remove these from the actual program. We left this portion of the program to the end, but were unable to figure it out (though we think it's extra credit).

Additionally, we were able to render all the images, including the brain, armadillo, bunny, and mountains. The brain, bunny, and armadillo are able to be decimated as well, but it just takes a long time (one edge collapse every 3 seconds for the bunny. It takes a much longer time for the brain.).

Here is the decimation of the cow! You can see parts of the triangle fins here near the end of decimation around the cow's eye.  

MooMoo

MooMoo 200

OVERALL:

We really enjoyed working on this project. We met up a lot and worked at Moffit's 4th floor with the blackboards, and it really helped us piece together what we needed to be done. We drew out a lot of simple pictures and wrote a lot of pseudocode that helped us layout what needed to be done. We felt like we understood the concepts taught in lecture, and by stepping through the problem with pseudocode, we knew that if we implemented the pseudocode, that everything would work. Once we got things working, then we focused on speed. If you have any questions, please refer to the source code, especially on quadric simplification. But we're confident that our implementation is correct.

EXAMPLES:

Video of the progressive mesh for hand. Quality is a bit worse than the previous videos, but you can still tell the level of detail changing as decimation and undecimation occurs.