Assignment 1

Introduction

For this assignment, you will be implementing two algorithms covering: 1. Loop Subdivision 2. Quadratic Error Mesh Decimation over any 3D object.

We have made available a visualization tool using the Three.js library implemented in "./js/assignment1.js" and an example implementation located in "./assignments/assignment1.py". Your objective is to create implementations for both "subdivision_loop" and "simplify_quadric_error". You are encouraged to use a programming language with which you are comfortable. The output results should be in the obj format, and you must visualize your outcomes accordingly.

How to Submit: Please submit this template file along with your implementation as a zip file. The zip file should contain your source code, the generated results in OBJ mesh format, and a report that has been modified using this HTML file. The report should comprise your results and a concise explanation of your implementation. Alternatively, you may choose to create a GitHub repository containing all these elements and provide a link for submission.

Grading: The grading is based on the correctness of your implementation. You are encouraged to use the visualization tool to debug your implementation. You can also use the visualization tool to test your implementation on other 3D models. You can find an example of 3D model in the "./assets" folder.

Original Cube Mesh:

Loop Subdivision

Method Overview:

My Loop subdivision algorithm consists of the following broad steps:

  1. Get Vertices and Faces: Extract vertices and faces from the mesh.
  2. Generate Odd Vertices: Calculate odd vertices from the edges using the formula from the slides handling the general and boundary cases.
  3. Generate Even Vertices: Compute even vertices from the original vertices using the formula from the slides handling the general and boundary cases.
  4. Create New Mesh: Compose a new mesh using the calculated odd and even vertices and new faces created from the new vertices.

Please refer to the code comments for more details about the implementation of the individual steps.
For my particular implementation, I use dictionaries extensively. I use dictionaries keyed by the edges (a tuple of vertex indices) to map the edges to the odd vertices that were generated using it. I use a dictionary to map the original vertices in the mesh that are used to generate the even vertices. I use a dictionary to index the newly generated vertices to an index for fast lookup when creating new faces. Most of my processing is done by iterating over faces and sometimes vertices.
My implementation takes kess than a minute to run for less than three iterations and about 4 minutes on my computer to run for 5 iterations.

Loop Subdivision with iterations = 1

Loop Subdivision with iterations = 3

Loop Subdivision with iterations = 5

Quadric Error Mesh Decimation

Method Overview:

Quadratic Error involves a three-step process:

  1. Quadric Matrix Calculation: Compute quadric matrices for each vertex and use them to calculate the matrices for each edge.
  2. Cost Minimization: Identify the edge with the lowest cost (least error) and determine the corresponding new vertex.
  3. Edge Collapse and Recalculation: Collapse the identified edge to the new vertex and update the vertices and faces accordingly. Also update the values of the quadric matrix.

Please refer to the code comments for more details about the implementation of the individual steps.
Most of my processing is done by iterating over faces and sometimes vertices. Here also, I use dictionaries extensively. I use dictionaries keyed by the vertices (index of vertex in original mesh) and edges (a tuple of vertex indices) to store the quardric matrices. I loop over the edge quadrics dictionary to find the minimum cost edge to collapse. For collapsing the edges, I essentially create a new list of vertices using the old list and create new faces using the new vertex indices. I use a dictionary here as well to accelerate lookup of indices fo vertices.
My implementation takes kess than a minute to run for less than three iterations and about 4 minutes on my computer to run for 5 iterations.

Quadratic Mesh Decimation with face_count = 2

Quadratic Mesh Decimation with face_count = 4

Quadratic Mesh Decimation with face_count = 10