Assignment 3
Mesh Deformation

Submission date: Friday, 11/18/16, 23:59


Develop and implement a mesh deformation tool. Implement the ARAP or another mesh deformation method or vaiation of it.  Experiment with using 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(s).
  4. Develop a user friendly API/visualization mechanism for your algorithm.


  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 Cartel (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.
  7. While you should work independently, it is a good idea to compare your results with other students , to verify code correctness.

Selection and Deformation:

Selection of multiple vertices is already implemented in ControlState and main. Selection is done while the right mouse button is pressed. Remember that clearing selection is a menu item and bound to the key 'C'. You may want to change that code slightly to allow for multiple (different) selections, or create events to save the current selection in EditMesh for different purposes (anchor(s), ROI).
You will need to create controls to drive the deformation itself. You have several options, a few suggestions are:


Eigen is very easy to use, and you are already familiar with many of its types (they are used throughout Cartel). The most important thing to be aware of when solving a system 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, we recommend LDLT or LLT
  Eigen::SimplicialLDLT< Eigen::SparseMatrix<double> > solver(A);
  x = solver.solve();

  // alternatively you can pass the matrix to solve to the solve function
  // instead of initializing it.


Send an email to Giorgio with the subject "DGP assign3" containing a zip file with your code. Submit your sources only.
Don't forget to include a README file explaining how to run your code.
In the email write your name and contact e-mail address.
All email should be received by Friday, 11/18/16, 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.