Assignment 3
Mesh Deformation

Submission date: Friday, 3/22/19, 23:59


  1. Develop and implement a mesh deformation tool.
  2. Implement the ARAP or another mesh deformation method or variation of it.
  3. Experiment with a linear solver library.


  1. Develop a linear mesh deformation tool based on local coordinates.
  2. In its basic form the method should use a single linear solve, in the more advanced version use an iterative method with a rotation update mechanism.
  3. Use an off-the-shelf linear solver to efficiently solve the resulting linear system/systems (using Eigen would perhaps be the easiest, since it is already being used inside minimesh).
  4. Develop a user friendly API/visualization mechanism for your algorithm (the class minimesh::Mesh_viewer now has all the functionality that is needed; it is up to you to use this functionality correctly in your code).


  1. Develop an anchor based mesh deformation tool for closed manifold meshes. You can use either an edge based (ARAP), Laplacian (vertex based) or transformation gradient (triangle based) one (I personally recommend ARAP). Start by implementing a method which has a single solve per anchor displacement (no rotation update). Only when this method works you can add support for iterated solver with rotation updates.
  2. For solving the linear system(s) you obtain you can use either the EIGEN library which comes with minimesh (see below) or another solver, as long as you are WELL familiar with it. Make sure the matrix you feed the solver is full rank. Pay attention to efficiency.
  3. You can limit your method to changing one anchor at a time (this way you can have a fixed rotation axis for you ROI  - think how this can simplify your updates).
  4. Bonus:
  5. Your API should support the following mesh operations, performed repeatedly and in any order (pay attention to API ease of use):
  6. To visualize the deformation process and ensure correctness you should provide a mechanism to highlight the ROI and anchor. You should provide an interface option (e.g. key-press) allowing the user to switch the visualization on and off. Minimesh::Mesh_buffer::set_colorful_spheres() can be helpful (see below).
  7. While you should work independently, it is a good idea to compare your results with other students , to verify code correctness.

Reading User Input for Deformation and Anchor Selection:

Download minimesh version 1.6 and later. You should then have the following functionality in minimesh::Mesh_viewer:


Eigen is quite easy to use, and you are already familiar with many of its types. The most important thing to be aware of when solving a system with more than ~1000 variables is that you should be using a Sparse solver. If you are solving the system Ax = b. You would proceed as below:

  Eigen::VectorXd b;
  Eigen::VectorXd x;
  Eigen::SparseMatrix<double> A(m, n);

  // populate b
  // populate A
  std::vector<Eigen::Triplet<double>> A_elem;
  for (non-zero elements) {
      A_elem.push_back( Eigen::Triplet<double>(row, column, value) );

  A.setFromTriplets(A_elem.begin(), A_elem.end());

  // solve using your prefered solver.
  // For symmetric systems use LDLT or LLT
  // For non-symmetric systems use PartialPivLU or FullPivLU
  Eigen::SimplicialLDLT< Eigen::SparseMatrix<double> > solver;

  // Call this only once for each value of A

  // Call this as many times as you want for one or different values of b,
  // as long as A is not changed.
  x = solver.solve(b);

  // Remember that calling solver.compute() is much more expensive that solver.solve().
  // Therefore, if the matrix A has not changed, be careful not to call solver.compute()
  // more than required.


Use the handin system similar to the previous assignments (this time using ``handin a3''). Submit your sources only.
Don't forget to include a README file explaining how to run your code and your name.

All assignments should be handed in by Friday, 3/22/19, at 23:59.

You can use your grace days (if you still have them). No late assignments, beyond those, will be accepted.

This assignment is 15% of your final grade.