In this homework you will implement two deformation tools: biharmonic deformation and As-Rigid-As-Possible (ARAP).

Submission

Deadline: Friday, November 18th, 23:59

Submit you work via private post in Piazza with zip archive with your code and name  (i.e.  hw3 python john .zip).   It should contain:  (1) your code;  (2) derivations required in problem 1.1;  (3) screenshots of deformed surfaces; (4) instructions on how to use your code

Make sure you understand every line of the code you write.

Requirements

You  are  allowed  use  built-in  linear  algebra  solvers  and  decompositions, sparse matrix operations, cotangent laplacian, and mass matrix.

❼ C++: use libigl and Eigen

❼ Python: use scipy .linalg and scipy .sparse .linalg (link)

Code templates

Course github: github.com/ivanpuhachov/ift6113 2022

Bonus points - Bug bounty (5 points max)

Same rules apply for bug bounty bonus points. Add them to your report.

Problem 0 (5 pts)

Implement a way to specify user anchor constraints, i.e. user would somehow select a subset of vertices and specify their target coordinates. Some vertices may remain on the same position (fixed points), some other are moved to new location. This can be done as an input text files or command line interface. Make it easy to try deformations on several models.

For  example,  you  may  store  constraints  for  dino .off 1   in  two  files:          indices-dino.off.txt has indices of points from mesh, positions-dino .off .txt has positions for specified vertices.

Provide instructions on how to use your code.

Problem 1 (35 pts)

Your task is to derive a solution to optimization problem (on paper), imple- ment it and show the results.

We formulate our deformation as an optimization for a displacement vec- tor field d : M → R3 , discretized2  on mesh vertices d = (dx , dy , dz )T  ∈ R3 ×m with dx  ∈ Rm .  Biharmonic deformation algorithm looks for the vector field minimizing the following quadratic energy with the linear user con- straints:

min      |∆d|2 dΩ

d        Ω

s .t .    duser  = user

where duser  = user  stands for fixing the displacement of certain vertices.

To  approximate  this  problem  in  discrete  variables,  we  use  cotangent Laplacian matrix L, mass matrix M , and K = LT Mz1L as the discretiza- tion of the squared Laplacian (bi-Laplacian). We end up with the following coordinate-wise quadratic optimization problem with constraints:

d(mi)n  Ω |∆d|2 dΩ ≈ d(mi)n dx(T)Kdx + dy(T)Kdy + dz(T)Kdz

s .t .    duser  = dˆuser

1. How to solve this optimization problem?  What algorithm should you use? Attach your derivations to the submission.

Hint:  Start with a simple arbitrary 2 × 2 matrix K. How would you solve it? Now try 3 × 3 with one constraint.

Hint: You can shuffle the indices and to simplify the problem

2. Implement this solution and show your results on armadillo 1k .off. Add screenshots to your submission, save the displacement settings to reproduce quickly.

Problem 2 (60 pts)

Your task is to implement ARAP deformation and show how it works (in- cluding both final result and intermediate iterations). Save the displacement settings to reproduce quickly.

Please, refer to our course slides (lecture on Shape Deformations), and the original paper:  Olga Sorkine and Marc Alexa, ”As-rigid-as-possible surface modeling”, 2007. igl.ethz.ch/projects/ARAP/

In short, to minimize ARAP energy by local-global algorithm, we alter- nate between two steps:

❼ (local step) finding the optimal rotations Ri  assuming the vertex posi-

tions p are fixed

❼ (global step) finding the optimal vertex positions p assuming all rota-

tions Ri  are fixed

Run several iterations (until you are satisfied with deformation result). Show intermediate states of your mesh.

Hint: Initialize rotation matrices to identities and implement the global solve. Run it once, without the local step. Debug your code on simple meshes like bar-2 .off

Debug hint: try setting only 1 user constraint: move 1 point to a new location.  What is the expected behavior?  Does your algorithm behave as expected?

Debug hint: try three point constraints specifying a single perfect rota- tion.

Bonus points:  Since for each iteration you are solving a linear system with the same matrix, you have a chance to improve the efficiency.  Find a way to pre-factorize (precompute) the matrix before iterations and show how it improves computation time.