# 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

To run my program, you use the basic clion run configuration. Use release mode for best performance.

There are two parameters you must modify:  1) the number of iterations and 2) the mesh to load. 
Both are modifiable on the first two lines in the arap.cpp's init function. 
Use an integer for the num iterations and a string to the path for the mesh.

2. _Briefly_, all the features your code implements, including any known bugs.

I implemented the basics of arap under the move() function. The order of the overall implementation is as follows:
- When the number of anchors changes:
  - Estimate pprime from p.
  - Compute the cotan weights.
  - Define the constraints map.
  - Compute the L matrix.
- For the number of iterations:
  - Estimate the rotation matrices.
  - Estimate the positions.
- Update the mesh vertices.

The number of iterations is statically defined as a parameter.

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

### Extra Feature: Parallelization

For the solving algorithm, I divided the dimensions and parallelized my code using the QTFramework to concurrently calculate the estimated positions.
See line 286 in arap.c for the implementation.
The video below shows both implementations (concurrent and normal) when deforming bunny.obj, a large mesh, at 1000 iterations. 
It appears the concurrent implementation is faster by only about a second.

| Program Specification                                             | Video                               |
|:------------------------------------------------------------------|:------------------------------------|
| Modifying Peter at 1000 iterations with no concurrent framework.  | ![](./readme-videos/bunny-conc.gif) |
| Modifying Peter at 1000 iterations using QTConcurrent map-reduce. | ![](./readme-videos/bunny-norm.gif) |