# 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                                                                                                                                                     | 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)       |