1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
# 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). |  |
| Anchoring exactly two points, then rotating one point around the other at a fixed distance, results in perfectly rigid rotation. |  |
| 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. |  |
| You should be able to make the armadillo wave. |  |
| Attempting to deform `tetrahedron.obj` should not cause it to collapse or behave erratically. |  |
| Attempting to deform a (large) mesh like `bunny.obj` or `peter.obj` should not cause your code to crash. |  |
|
