IFT 6113 - Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
IFT 6113 - Assignment 3, 100 pts
November 3, 2022
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.
Reference images
Figure 1: Biharmonic deformations (left) and ARAP (right) for bar2 .off
2022-12-09