code

10 files changed, 478 insertions, 103 deletions

diff --git a/.idea/.gitignore b/.idea/.gitignore
new file mode 100644
index 0000000..a9d7db9
--- /dev/null
+++ b/.idea/.gitignore
@@ -0,0 +1,10 @@
+# Default ignored files
+/shelf/
+/workspace.xml
+# Editor-based HTTP Client requests
+/httpRequests/
+# Datasource local storage ignored files
+/dataSources/
+/dataSources.local.xml
+# GitHub Copilot persisted chat sessions
+/copilot/chatSessions
diff --git a/.idea/.name b/.idea/.name
new file mode 100644
index 0000000..5cdd4fc
--- /dev/null
+++ b/.idea/.name
@@ -0,0 +1 @@
+arap
\ No newline at end of file
diff --git a/.idea/QtSettings.xml b/.idea/QtSettings.xml
new file mode 100644
index 0000000..dd42746
--- /dev/null
+++ b/.idea/QtSettings.xml
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="QtSettings">
+    <option name="myCurrentProfile" value="Release" />
+    <option name="mySettingsPerProfile">
+      <map>
+        <entry key="Debug">
+          <value>
+            <PerProfileState>
+              <option name="myQmlPath" value="$USER_HOME$/Qt/6.5.2/macos/./qml" />
+              <option name="myQtBinPath" value="$USER_HOME$/Qt/6.5.2/macos/bin" />
+            </PerProfileState>
+          </value>
+        </entry>
+        <entry key="Release">
+          <value>
+            <PerProfileState>
+              <option name="myQmlPath" value="$USER_HOME$/Qt/6.5.2/macos/./qml" />
+              <option name="myQtBinPath" value="$USER_HOME$/Qt/6.5.2/macos/bin" />
+            </PerProfileState>
+          </value>
+        </entry>
+      </map>
+    </option>
+  </component>
+</project>
\ No newline at end of file
diff --git a/.idea/arap-sotech117.iml b/.idea/arap-sotech117.iml
new file mode 100644
index 0000000..f08604b
--- /dev/null
+++ b/.idea/arap-sotech117.iml
@@ -0,0 +1,2 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<module classpath="CMake" type="CPP_MODULE" version="4" />
\ No newline at end of file
diff --git a/.idea/misc.xml b/.idea/misc.xml
new file mode 100644
index 0000000..79b3c94
--- /dev/null
+++ b/.idea/misc.xml
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="CMakeWorkspace" PROJECT_DIR="$PROJECT_DIR$" />
+</project>
\ No newline at end of file
diff --git a/.idea/modules.xml b/.idea/modules.xml
new file mode 100644
index 0000000..31fded7
--- /dev/null
+++ b/.idea/modules.xml
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="ProjectModuleManager">
+    <modules>
+      <module fileurl="file://$PROJECT_DIR$/.idea/arap-sotech117.iml" filepath="$PROJECT_DIR$/.idea/arap-sotech117.iml" />
+    </modules>
+  </component>
+</project>
\ No newline at end of file
diff --git a/.idea/vcs.xml b/.idea/vcs.xml
new file mode 100644
index 0000000..b4ed0ad
--- /dev/null
+++ b/.idea/vcs.xml
@@ -0,0 +1,7 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="VcsDirectoryMappings">
+    <mapping directory="" vcs="Git" />
+    <mapping directory="$PROJECT_DIR$/Eigen" vcs="Git" />
+  </component>
+</project>
\ No newline at end of file
diff --git a/README.md b/README.md
index d583d15..765c344 100644
--- a/README.md
+++ b/README.md
@@ -33,12 +33,12 @@ This sums to **95 points**. To score **100 points** (or more!), you’ll need to
 
 1. Set an initial value for the new vertex positions $p'$. Use the previous vertex positions $p$ for this. **(0 points)**
 2. Build the $L$ matrix. **(25 points)**
-   - Determine the one-ring neighbors of each vertex;
-   - Calculate the cotangent weight $w$ for each vertex;
-   - Fill in the $L$ matrix entries.
+    - Determine the one-ring neighbors of each vertex;
+    - Calculate the cotangent weight $w$ for each vertex;
+    - Fill in the $L$ matrix entries.
 3. Apply user constraints by deleting rows/columns from $L$. **(5 points)**
 4. Precompute the decomposition of the $L$ matrix. **(5 points)**
-   - If you unnecessarily recompute this decomposition, you will lose points for inefficiency.
+    - If you unnecessarily recompute this decomposition, you will lose points for inefficiency.
 
 ### Iterative Solving
 
@@ -51,7 +51,7 @@ Your README **(5 points)** should describe:
 
 1. How to run your program, such as how to load a specific mesh; and
 2. _Briefly_, all the features your code implements, including any known bugs.
-   - E.g.: "I implemented ARAP ... and affine progressive meshes ... however, my program doesn't work in these specific cases: ..."
+    - E.g.: "I implemented ARAP ... and affine progressive meshes ... however, my program doesn't work in these specific cases: ..."
 
 You should also have all the [example videos](#example-videos) described in the next section embedded in your README.
 
@@ -59,106 +59,11 @@ You should also have all the [example videos](#example-videos) described in the
 
 For this project, we ask that you demonstrate to us that your program achieves the following behavior specifications. You will do so by providing ≥1 video(s) per specification point below.
 
-| Program Specification                                                                                                                                                     | Our Example                          |
-| :------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | :----------------------------------- |
+| Program Specification                                                                                                                                                     | My Example                           |
+| :------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |:-------------------------------------|
 | Anchoring exactly one point, then moving that point, results in perfectly rigid motion (mostly translation, though some rotation for smaller meshes is acceptable).       | ![](./readme-videos/sphere.gif)      |
 | Anchoring exactly two points, then rotating one point around the other at a fixed distance, results in perfectly rigid rotation.                                          | ![](./readme-videos/teapot.gif)      |
 | Deformations are "permanent"; i.e. un-anchoring previously moved points leaves the mesh in its deformed state, and further deformations can be made on the deformed mesh. | ![](./readme-videos/bean.gif)        |
 | You should be able to make the armadillo wave.                                                                                                                            | ![](./readme-videos/armadillo.gif)   |
 | Attempting to deform `tetrahedron.obj` should not cause it to collapse or behave erratically.                                                                             | ![](./readme-videos/tetrahedron.gif) |
 | Attempting to deform a (large) mesh like `bunny.obj` or `peter.obj` should not cause your code to crash.                                                                  | ![](./readme-videos/peter.gif)       |
-
-<details>
-  <summary>How should I generate these example videos?</summary>
-
-We suggest screen-recording the [interactive viewer](#interactive-viewer) provided in [the stencil code](#resources).
-
-To embed these videos into your READMEs, you can convert these into animated GIFs (using `ffmpeg` or an online tool like [ezgif](https://ezgif.com)), then embed them in Markdown like so:
-
-`![informative alt text](./path/to/mygif.gif)`
-
-</details>
-
-### Extra Features
-
-Each of the following features that you implement will earn you extra points. The features are ordered roughly by difficulty of implementation.
-
-- Parallelize your code **(5 points)**
-  - There are multiple opportunities to exploit parallelism. For instance, you could solve the linear systems for each coordinate (x, y, z) in parallel.
-- Improved interactivity **(8 points)**
-  - Implement some other way(s) to interact with the mesh beyond constraining/dragging single vertices.
-  - You could also look into allowing direct specification of rotations in addition to translations (see the "Rotation-Propagation" paragraph on page 6 of the paper).
-  - Please record a video of how you interact with the mesh.
-- Affine progressive meshes **(10 points)**
-  - The ARAP optimization can become slow for very high-resolution meshes. To get around this problem, one can try to solve the optimization on a lower-resolution mesh, and then interpolate the result back to the high-resolution mesh.
-  - See Section 3.2 of [this paper](https://www.dgp.toronto.edu/~hsuehtil/pdf/cubeStyle_high.pdf) for one way to do this. You will need to re-use your mesh simplification code from the Mesh assignment.
-  - You may find some example high-resolution meshes [here](https://graphics.stanford.edu/data/3Dscanrep/).
-  - Please record a video interacting with the high-resolution meshes.
-- Modified optimization objective **(15 points)**
-  - One can modify the basic ARAP optimization objective function to achieve other types of deformation.
-  - For example, [this paper](https://www.dgp.toronto.edu/~hsuehtil/pdf/cubeStyle_high.pdf) describes how adding an L1 regularizer to the objective produces 'cubified' meshes.
-  - Be aware that changing the objective may well change the method(s) you need to use to solve the resulting optimization problem.
-  - Please show at least 2 pairs of images comparing your modified ARAP results and the original results. 
-- Something else!
-  - This list is not meant to be exhaustive--if you’ve got another advanced feature in mind, go for it! (though you may want to ask a TA or the instructor first if you’re concerned about whether the idea is feasible)
-
-**Any extra features you implement must be mentioned in your README, and each feature must be demonstrated in one or more videos.**
-
-## Grading
-
-We will initially grade your project based solely on your README, example videos, and code.
-
-We will then follow up with a short in-person grading session to resolve any outstanding issues.
-
-You can help us make grading go smoother by providing excellent [example videos](#example-videos), to prove to us that your program meets our specifications~!
-
-## Resources
-
-The stencil code is quite bare-bones: besides the main function, it provides code to load `.obj` files into a simple mesh representation (a list of vertices and a list of faces) and save that representation back to an `.obj` file. It also provides an interactive viewer for visualizing (and manipulating the vertices of) meshes.
-
-You’ll have to implement everything else: building the sparse linear system, any supporting data structures you need, etc.
-
-To test your program, you may use the `.obj` files in `/meshes`. You may also use any other 3D models you like.
-
-<details>
-  <summary>Note about meshes with boundaries</summary>
-
-You do not need to support meshes with boundaries for any part of this assignment. That is to say, you can always assume that every edge has two adjacent faces, so you won't have to worry about special-casing for edges on the boundary.
-
-All the meshes provided in the stencil satisfy this property. If you choose to use any other meshes, it will be on you to make sure that this property is satisfied (else, your code might break).
-
-</details>
-
-### Where To Start
-
-You'll want to look at `src/arap.cpp` to get started, as that's the only file you'll (definitely) need to change. You might also want to look at `src/glwidget.cpp`, if you're interested in adding new interactivity/controls to the program.
-
-### Interactive Viewer
-
-Speaking of controls, here's how you can interface with the interactive viewer:
-
-- You start in first-person camera mode:
-  - `WASD` to move, `left-click` and drag to rotate
-  - `R` and `F` to move vertically up and down
-- `C` to change to orbit camera mode
-- `Right-click` (and, optionally, drag) to anchor/un-anchor points.
-  - `Left-click` an anchored point to move it around
-- Minus (`-`) and equal (`=`) keys (click repeatedly) to change the size of the vertices
-
-### Solving Sparse Linear Systems In Eigen
-
-You'll want to look at [this page](https://eigen.tuxfamily.org/dox/group__TopicSparseSystems.html) in the Eigen documentation. We recommend using either the `SimplicialLLT` or `SimplicialLDLT` solvers, as they are specialized to be faster for symmetric positive definite (SPD) matrices (which your $L$ matrix is).
-
-## Submission Instructions
-
-Submit your Github repository to the "ARAP" assignment.
-
-## Implementation & Debugging Tips
-
-- Use `const` and `assert` wherever possible.
-- Check for uninitialized values.
-- Use Qt Creator's debugger.
-- The cotangent function can be negative, be sure to use the **positive** cotangent weights (the absolute value of the cotangent).
-- Verify that your $L$ matrix is **positive semi-definite** (has eigenvalues and a determinant greater than or equal to zero)
-- We provided helper functions in `graphics/shape.h`, all the public member function should be enough for you to complete the minimum requirement without having to modify our helper classes.
-- **REMINDER: Your code will run much faster if you compile in Release mode ;)**
diff --git a/src/arap.cpp b/src/arap.cpp
index 06b8829..4ba3bc8 100644
--- a/src/arap.cpp
+++ b/src/arap.cpp
@@ -6,6 +6,11 @@
 #include <map>
 #include <vector>
 
+#include <Eigen/Core>
+#include <Eigen/Dense>
+#include <Eigen/Sparse>
+#include <Eigen/SVD>
+
 using namespace std;
 using namespace Eigen;
 
@@ -17,7 +22,7 @@ void ARAP::init(Eigen::Vector3f &coeffMin, Eigen::Vector3f &coeffMax)
     vector<Vector3i> triangles;
 
     // If this doesn't work for you, remember to change your working directory
-    if (MeshLoader::loadTriMesh("meshes/cactus.obj", vertices, triangles)) {
+    if (MeshLoader::loadTriMesh("meshes/sphere.obj", vertices, triangles)) {
         m_shape.init(vertices, triangles);
     }
 
@@ -31,15 +36,258 @@ void ARAP::init(Eigen::Vector3f &coeffMin, Eigen::Vector3f &coeffMax)
     coeffMax = all_vertices.colwise().maxCoeff();
 }
 
+
+
 // Move an anchored vertex, defined by its index, to targetPosition
 void ARAP::move(int vertex, Vector3f targetPosition)
 {
     std::vector<Eigen::Vector3f> new_vertices = m_shape.getVertices();
     const std::unordered_set<int>& anchors = m_shape.getAnchors();
 
+	std::cout << "anchors size" << anchors.size() << std::endl;
+	std::cout << "targetPosition" << targetPosition << std::endl;
+
     // TODO: implement ARAP here
     new_vertices[vertex] = targetPosition;
 
+	// make a copy of the vertices into the matrix points
+	typedef Matrix<float, 3, Dynamic> PM; // position matrix
+	PM p(3, m_shape.getVertices().size());
+	for (int i = 0; i < m_shape.getVertices().size(); ++i)
+	{
+		p.col(i) = m_shape.getVertices()[i];
+		// p.col(i) = new_vertices[i];
+	}
+	PM p_prime(3, m_shape.getVertices().size());
+	for (int i = 0; i < m_shape.getVertices().size(); ++i)
+	{
+		p_prime.col(i) = new_vertices[i];
+	}
+
+	// compute the cotan weights
+	typedef Triplet<float> Tri;
+	vector<Tri> triplets;
+	triplets.reserve(3 *  m_shape.getFaces().size());
+	for (DenseIndex f = 0; f < m_shape.getFaces().size(); ++f)
+	{
+		Vector3i face = m_shape.getFaces()[f];
+		Vector3f v0 = m_shape.getVertices()[face[0]];
+		Vector3f v1 = m_shape.getVertices()[face[1]];
+		Vector3f v2 = m_shape.getVertices()[face[2]];
+
+		Vector3f e0 = v1 - v0;
+		Vector3f e1 = v2 - v1;
+		Vector3f e2 = v0 - v2;
+
+		// protect against degen triangles
+		float s0 = e0.squaredNorm();
+		s0 = max(s0, 1e-8f);
+		float s1 = e1.squaredNorm();
+		s1 = max(s1, 1e-8f);
+		float s2 = e2.squaredNorm();
+		s2 = max(s2, 1e-8f);
+
+		s0 = sqrt(s0);
+		s1 = sqrt(s1);
+		s2 = sqrt(s2);
+
+		float semi_perimeter = (s0 + s1 + s2) * 0.5f;
+		float area = sqrt(semi_perimeter * (semi_perimeter - s0) * (semi_perimeter - s1) * (semi_perimeter - s2));
+		area = max(area, 1e-8f);
+
+		float cot0 = (-s0 * s0 + s1 * s1 + s2 * s2) / (4.0f * area);
+		cot0 = max(cot0, 1e-10f) * 0.5f;
+		float cot1 = (s0 * s0 - s1 * s1 + s2 * s2) / (4.0f * area);
+		cot1 = max(cot1, 1e-10f) * 0.5f;
+		float cot2 = (s0 * s0 + s1 * s1 - s2 * s2) / (4.0f * area);
+		cot2 = max(cot2, 1e-10f) * 0.5f;
+
+		pair<int, int> edge0 =
+			face[0] > face[1] ? make_pair(face[1], face[0]) : make_pair(face[0], face[1]);
+		pair<int, int> edge1 =
+			face[1] > face[2] ? make_pair(face[2], face[1]) : make_pair(face[1], face[2]);
+		pair<int, int> edge2 =
+			face[2] > face[0] ? make_pair(face[0], face[2]) : make_pair(face[2], face[0]);
+
+		triplets.push_back(Tri(edge0.first, edge0.second, cot0));
+		triplets.push_back(Tri(edge1.first, edge1.second, cot1));
+		triplets.push_back(Tri(edge2.first, edge2.second, cot2));
+		triplets.push_back(Tri(edge0.second, edge0.first, cot0));
+		triplets.push_back(Tri(edge1.second, edge1.first, cot1));
+		triplets.push_back(Tri(edge2.second, edge2.first, cot2));
+	}
+	// build the sparse matrix of edge weights
+	SparseMatrix<float, RowMajor> edge_weights(m_shape.getVertices().size(), m_shape.getVertices().size());
+	edge_weights.reserve(VectorXi::Constant(m_shape.getVertices().size(), 7));
+	edge_weights.setZero();
+	edge_weights.setFromTriplets(triplets.begin(), triplets.end());
+
+	// initialize the rotation matrices
+	typedef Matrix<float, 3, 3> R;
+	// TODO: move this to only init once
+	vector<R> rotations(m_shape.getVertices().size(), R::Identity(3, 3));
+//	rotations.clear();
+//	rotations.resize(m_shape.getVertices().size(), R::Identity(3, 3));
+
+	// make a map that reduces the constrained vertices (vtx -> free vtx)
+	vector<Index> vtx_to_free_vtx = vector<Index>(m_shape.getVertices().size(), -1);
+	// vtx_to_free_vtx.reserve(m_shape.getVertices().size());
+	Index count_free = 0;
+	for (int i = 0; i < m_shape.getVertices().size(); ++i)
+	{
+		if (!anchors.contains(i))
+		{
+			// if were not an anchor, we are free
+			vtx_to_free_vtx[i] = count_free;
+			count_free++;
+		}
+	}
+
+	// update pprime with the constraints into the linear system
+	for (Index i = 0; i < m_shape.getVertices().size(); ++i)
+	{
+		if (vtx_to_free_vtx[i] == -1)
+		{
+			// if we're an anchor, set this position
+			p_prime.col(i) = new_vertices[i];
+		}
+	}
+
+	// setup the linear system we will use to solve
+	SparseMatrix<float, RowMajor> L(count_free, count_free);
+	// L.resize(count_free, count_free);
+	L.reserve(VectorXi::Constant(count_free, 7));
+	L.setZero();
+
+	// setup bfixed
+	PM b_fixed = PM::Zero(3, count_free);
+	// b_fixed.resize(3, count_free);
+
+	// make the L matrix using triplet method
+	vector<Tri> triplets_L;
+	triplets_L.reserve(7 * count_free);
+	for (Index i = 0; i < edge_weights.outerSize(); i++)
+	{
+		Index free_index = vtx_to_free_vtx[i];
+		if (free_index == -1)
+		{
+			// do not add constraints to the linear system
+			continue;
+		}
+
+		for (SparseMatrix<float, RowMajor>::InnerIterator it(edge_weights, i); it; ++it)
+		{
+			Index j = it.col();
+			Index free_index_j = vtx_to_free_vtx[j];
+			float wij = it.value();
+			if (free_index_j == -1)
+			{
+				// if the neighbor is an anchor, add to b_fixed
+				Vector3f location = new_vertices[j];
+				b_fixed.col(free_index) += wij * location;
+			}
+			else
+			{
+				triplets_L.push_back(Tri(free_index, free_index_j, -wij));
+			}
+			triplets_L.push_back(Tri(free_index, free_index, wij));
+		}
+	}
+	// create and solve the L matrix
+	L.setFromTriplets(triplets_L.begin(), triplets_L.end());
+	SimplicialLDLT<SparseMatrix<float>> solver;
+	solver.compute(L);
+
+	for (int iter = 0; iter < 5; iter++)
+	{
+		// estimate the rotations
+		rotations.clear();
+		rotations.resize(m_shape.getVertices().size(), R::Identity(3, 3));
+		typedef Matrix<float, 3, 3> S;
+		for (Index i = 0; i < edge_weights.outerSize(); ++i)
+		{
+			const auto &pi = p.col(i);
+			const auto &ppi = p_prime.col(i);
+			S cov = S::Zero(3, 3);
+
+			for (SparseMatrix<float, RowMajor>::InnerIterator it(edge_weights, i); it; ++it)
+			{
+				// get the weight
+				float wij = it.value();
+
+				// get the neighbor vertex
+				const auto &pj = p.col(it.col());
+				const auto &ppj = p_prime.col(it.col());
+
+				Vector3f d = pi - pj;
+				Vector3f dp = ppi - ppj;
+
+				cov += wij * d * (dp.transpose());
+			}
+
+			JacobiSVD<S> svd(cov, ComputeFullU | ComputeFullV);
+			const S &v = svd.matrixV();
+			const S u_trans = svd.matrixU().transpose();
+
+			S I = S::Identity(3, 3);
+			I(2, 2) = (v * u_trans).determinant();
+			rotations[i] = v * I * u_trans;
+		}
+
+		// estimate the positions
+		// make a copy of b_fixed to modify
+		PM b = b_fixed;
+		for (Index i = 0; i < edge_weights.outerSize(); ++i)
+		{
+			// TODO add constraint check here
+			Index free_index = vtx_to_free_vtx[i];
+			if (free_index == -1)
+			{
+				// do not consider constraints
+				continue;
+			}
+
+			for (SparseMatrix<float, RowMajor>::InnerIterator it(edge_weights, i); it; ++it)
+			{
+				// get the weight
+				float wij = it.value();
+
+				// get the rotation matrices for the vertices
+				const S &R = rotations[i];
+				const S &Rj = rotations[it.col()];
+
+				// calculate the energy
+				Eigen::Matrix<float, 3, 1> pt = (R + Rj) * (p.col(i) - p.col(it.col()));
+				pt *= wij * 0.5f;
+				b.col(free_index) += pt;
+			}
+		}
+
+		// solve the linear system for each dimension
+		Matrix<float, Dynamic, 1> U;
+		for (int j = 0; j < 3; ++j)
+		{
+			U = solver.solve(b.row(j).transpose());
+
+			Index idx = 0;
+			for (int k = 0; k < m_shape.getVertices().size(); ++k)
+			{
+				if (vtx_to_free_vtx[k] != -1)
+				{
+					p_prime(j, k) = U(idx);
+					idx++;
+				}
+			}
+		}
+	}
+
+
+	// update the vertices with pprime
+	for (int i = 0; i < m_shape.getVertices().size(); ++i)
+	{
+		new_vertices[i] = p_prime.col(i);
+	}
+
     // Here are some helpful controls for the application
     //
     // - You start in first-person camera mode
diff --git a/stencil-readme.md b/stencil-readme.md
new file mode 100644
index 0000000..d583d15
--- /dev/null
+++ b/stencil-readme.md
@@ -0,0 +1,164 @@
+# Assignment 4: As-Rigid-As-Possible Surface Modeling (ARAP)
+
+**Released:** 3/18/24
+
+**Due:** 4/5/24 @ 11:59pm EST
+
+In this assignment, you will implement a system for user-interactive deformation of 3D meshes. In your system, mesh vertices can be re-positioned by clicking and dragging. Your system will update the rest of the mesh in response to these user interactions such that it moves as-rigidly-as-possible (i.e. the deformation it exhibits is close to a rigid transformation). The end result is a deformation that looks physically-plausible, as if the mesh has an underlying rig / skeletal armature.
+
+To achieve this goal, you will need to formulate the deformation process as an optimization problem, in which you will alternate between estimating the best-fit rigid transformation for each mesh vertex and solving a sparse linear system to find new mesh vertex positions.
+
+## Relevant Reading
+
+- The lecture slides!
+- [As-Rigid-As-Possible Surface Modeling](https://igl.ethz.ch/projects/ARAP/arap_web.pdf) on the mathematics behind the ARAP algorithm.
+
+## Requirements
+
+This assignment is out of **100 points**.
+
+Your must implement exactly one feature: the algorithm described in the ARAP paper. That means, for each user interaction, your program must perform the following steps:
+
+- [Initialization](#initialization) **(35 points)**
+- [Iterative solving](#iterative-solving) **(45 points)**
+
+You will be graded for inclusion of the following as well:
+
+- [README](#readme) **(5 points)**
+- [Example videos](#example-videos) **(10 points)**
+
+This sums to **95 points**. To score **100 points** (or more!), you’ll need to implement some [extra features](#extra-features).
+
+### Initialization
+
+1. Set an initial value for the new vertex positions $p'$. Use the previous vertex positions $p$ for this. **(0 points)**
+2. Build the $L$ matrix. **(25 points)**
+   - Determine the one-ring neighbors of each vertex;
+   - Calculate the cotangent weight $w$ for each vertex;
+   - Fill in the $L$ matrix entries.
+3. Apply user constraints by deleting rows/columns from $L$. **(5 points)**
+4. Precompute the decomposition of the $L$ matrix. **(5 points)**
+   - If you unnecessarily recompute this decomposition, you will lose points for inefficiency.
+
+### Iterative Solving
+
+1. Determine the best-fit rotation transformations $R$ for the moved points $p'$ from original points $p$. **(20 points)**
+2. Optimize the positions $p'$ given $p$ and $R$ by solving a sparse linear system. You will need to update the right-hand side of the equation accordingly. **(25 points)**
+
+### README
+
+Your README **(5 points)** should describe:
+
+1. How to run your program, such as how to load a specific mesh; and
+2. _Briefly_, all the features your code implements, including any known bugs.
+   - E.g.: "I implemented ARAP ... and affine progressive meshes ... however, my program doesn't work in these specific cases: ..."
+
+You should also have all the [example videos](#example-videos) described in the next section embedded in your README.
+
+### Example Videos
+
+For this project, we ask that you demonstrate to us that your program achieves the following behavior specifications. You will do so by providing ≥1 video(s) per specification point below.
+
+| Program Specification                                                                                                                                                     | Our Example                          |
+| :------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | :----------------------------------- |
+| Anchoring exactly one point, then moving that point, results in perfectly rigid motion (mostly translation, though some rotation for smaller meshes is acceptable).       | ![](./readme-videos/sphere.gif)      |
+| Anchoring exactly two points, then rotating one point around the other at a fixed distance, results in perfectly rigid rotation.                                          | ![](./readme-videos/teapot.gif)      |
+| Deformations are "permanent"; i.e. un-anchoring previously moved points leaves the mesh in its deformed state, and further deformations can be made on the deformed mesh. | ![](./readme-videos/bean.gif)        |
+| You should be able to make the armadillo wave.                                                                                                                            | ![](./readme-videos/armadillo.gif)   |
+| Attempting to deform `tetrahedron.obj` should not cause it to collapse or behave erratically.                                                                             | ![](./readme-videos/tetrahedron.gif) |
+| Attempting to deform a (large) mesh like `bunny.obj` or `peter.obj` should not cause your code to crash.                                                                  | ![](./readme-videos/peter.gif)       |
+
+<details>
+  <summary>How should I generate these example videos?</summary>
+
+We suggest screen-recording the [interactive viewer](#interactive-viewer) provided in [the stencil code](#resources).
+
+To embed these videos into your READMEs, you can convert these into animated GIFs (using `ffmpeg` or an online tool like [ezgif](https://ezgif.com)), then embed them in Markdown like so:
+
+`![informative alt text](./path/to/mygif.gif)`
+
+</details>
+
+### Extra Features
+
+Each of the following features that you implement will earn you extra points. The features are ordered roughly by difficulty of implementation.
+
+- Parallelize your code **(5 points)**
+  - There are multiple opportunities to exploit parallelism. For instance, you could solve the linear systems for each coordinate (x, y, z) in parallel.
+- Improved interactivity **(8 points)**
+  - Implement some other way(s) to interact with the mesh beyond constraining/dragging single vertices.
+  - You could also look into allowing direct specification of rotations in addition to translations (see the "Rotation-Propagation" paragraph on page 6 of the paper).
+  - Please record a video of how you interact with the mesh.
+- Affine progressive meshes **(10 points)**
+  - The ARAP optimization can become slow for very high-resolution meshes. To get around this problem, one can try to solve the optimization on a lower-resolution mesh, and then interpolate the result back to the high-resolution mesh.
+  - See Section 3.2 of [this paper](https://www.dgp.toronto.edu/~hsuehtil/pdf/cubeStyle_high.pdf) for one way to do this. You will need to re-use your mesh simplification code from the Mesh assignment.
+  - You may find some example high-resolution meshes [here](https://graphics.stanford.edu/data/3Dscanrep/).
+  - Please record a video interacting with the high-resolution meshes.
+- Modified optimization objective **(15 points)**
+  - One can modify the basic ARAP optimization objective function to achieve other types of deformation.
+  - For example, [this paper](https://www.dgp.toronto.edu/~hsuehtil/pdf/cubeStyle_high.pdf) describes how adding an L1 regularizer to the objective produces 'cubified' meshes.
+  - Be aware that changing the objective may well change the method(s) you need to use to solve the resulting optimization problem.
+  - Please show at least 2 pairs of images comparing your modified ARAP results and the original results. 
+- Something else!
+  - This list is not meant to be exhaustive--if you’ve got another advanced feature in mind, go for it! (though you may want to ask a TA or the instructor first if you’re concerned about whether the idea is feasible)
+
+**Any extra features you implement must be mentioned in your README, and each feature must be demonstrated in one or more videos.**
+
+## Grading
+
+We will initially grade your project based solely on your README, example videos, and code.
+
+We will then follow up with a short in-person grading session to resolve any outstanding issues.
+
+You can help us make grading go smoother by providing excellent [example videos](#example-videos), to prove to us that your program meets our specifications~!
+
+## Resources
+
+The stencil code is quite bare-bones: besides the main function, it provides code to load `.obj` files into a simple mesh representation (a list of vertices and a list of faces) and save that representation back to an `.obj` file. It also provides an interactive viewer for visualizing (and manipulating the vertices of) meshes.
+
+You’ll have to implement everything else: building the sparse linear system, any supporting data structures you need, etc.
+
+To test your program, you may use the `.obj` files in `/meshes`. You may also use any other 3D models you like.
+
+<details>
+  <summary>Note about meshes with boundaries</summary>
+
+You do not need to support meshes with boundaries for any part of this assignment. That is to say, you can always assume that every edge has two adjacent faces, so you won't have to worry about special-casing for edges on the boundary.
+
+All the meshes provided in the stencil satisfy this property. If you choose to use any other meshes, it will be on you to make sure that this property is satisfied (else, your code might break).
+
+</details>
+
+### Where To Start
+
+You'll want to look at `src/arap.cpp` to get started, as that's the only file you'll (definitely) need to change. You might also want to look at `src/glwidget.cpp`, if you're interested in adding new interactivity/controls to the program.
+
+### Interactive Viewer
+
+Speaking of controls, here's how you can interface with the interactive viewer:
+
+- You start in first-person camera mode:
+  - `WASD` to move, `left-click` and drag to rotate
+  - `R` and `F` to move vertically up and down
+- `C` to change to orbit camera mode
+- `Right-click` (and, optionally, drag) to anchor/un-anchor points.
+  - `Left-click` an anchored point to move it around
+- Minus (`-`) and equal (`=`) keys (click repeatedly) to change the size of the vertices
+
+### Solving Sparse Linear Systems In Eigen
+
+You'll want to look at [this page](https://eigen.tuxfamily.org/dox/group__TopicSparseSystems.html) in the Eigen documentation. We recommend using either the `SimplicialLLT` or `SimplicialLDLT` solvers, as they are specialized to be faster for symmetric positive definite (SPD) matrices (which your $L$ matrix is).
+
+## Submission Instructions
+
+Submit your Github repository to the "ARAP" assignment.
+
+## Implementation & Debugging Tips
+
+- Use `const` and `assert` wherever possible.
+- Check for uninitialized values.
+- Use Qt Creator's debugger.
+- The cotangent function can be negative, be sure to use the **positive** cotangent weights (the absolute value of the cotangent).
+- Verify that your $L$ matrix is **positive semi-definite** (has eigenvalues and a determinant greater than or equal to zero)
+- We provided helper functions in `graphics/shape.h`, all the public member function should be enough for you to complete the minimum requirement without having to modify our helper classes.
+- **REMINDER: Your code will run much faster if you compile in Release mode ;)**