Assignment 4 [Coding]: Conformal Parameterization (Due 4/28)

For the coding portion of your assignment on conformal parameterization, you will implement the Spectral Conformal Parameterization (SCP) algorithm as described in the course notes.Please implement the following routines in

  1. core/geometry.js:
    1. complexLaplaceMatrix
  2. projects/parameterization/spectral-conformal-parameterization.js:
    1. buildConformalEnergy
    2. flatten
  3. utils/solvers.js:
    1. solveInversePowerMethod
    2. residual

Notes

  • I added a few tests for utils/solvers.js. They’re available in the git repository. If you’re familiar with git, you can pull the changes. If you’d prefer not to mess around with git, you can also just download the files and put them in tests/utils.
    • Warning: I fixed a problem with the residual test. In the notes, the residual is defined as a vector $Ax – \lambda x$. But your function residual should return a float. You should return $\frac{\|Ax – \lambda x\|_2}{\|x\|_2}$. Furthermore, you should compute $\lambda$ as $\frac{x^* A x}{x^* x}$ where $x^*$ is the conjugate transpose of $x$.
  • The complex version of the cotan-Laplace matrix can be built in exactly the same manner as its real counterpart. The only difference now is that the cotan values of our matrix will be complex numbers with a zero imaginary component. This time, we will work with meshes with boundary, so your Laplace matrix will have to handle boundaries properly (you just have to make sure your cotan function returns 0 for halfedges which are in the boundary).
  • The buildConformalEnergy function builds a $|V| \times |V|$ complex matrix corresponding to the conformal energy $E_C(z) = E_D(z) – \mathcal A(Z)$ where $E_D$ is the Dirichlet energy (given by our complex cotan-Laplace matrix) and $\mathcal A$ is the total signed area of the region $z(M)$ in the complex plane (Please refer to Section 7.4 of the notes for more details). You may find it easiest to iterate over the halfedges of the mesh boundaries to construct the area matrix (Recall that the Mesh object has a boundaries variable which stores all the boundary loops.
  • The flatten function returns a dictionary mapping each vertex to a vector (linear-algebra/vector.js) of planar coordinates by finding the eigenvector corresponding to the smallest eigenvalue of the conformal energy matrix. You can compute this eigenvector by using solveInversePowerMethod (described below).
  • Your solveInversePowerMethod function should implement Algorithm 1 in Section 7.5 of the course notes with one modification – after computing $Ay_i = y_{i-1}$, center $y_i$ around the origin by subtracting its mean. You don’t have to worry about the $B$ matrix or generalized eigenvalue problem. Important: Terminate your iterations when your residual is smaller that 10^-10.
  • The parameterization project directory also contains a basic implementation of the Boundary First Flattening (BFF) algorithm. Feel free to play around with it in the viewer and compare the results to your SCP implementation.

Submission Instructions

Please rename your geometry.js, spectral-conformal-parameterization.js and solvers.js files to geometry.txt, spectral-conformal-parameterization.txt and solvers.txt (respectively) and put them in a single zip file called solution.zip. These files and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG20A4.

17 thoughts on “Assignment 4 [Coding]: Conformal Parameterization (Due 4/28)”

  1. I’m confused by the calculation of $\lambda$ . Should the equation, $\frac{x^\dagger A x}{x^\dagger x}$ be $\frac{x^\dagger A x}{\|x^\dagger x\|}$? If that’s not a typo, how do you do division by a dense matrix?

    1. The quantity \(x^T x\) is a scalar (or if you want to be really pedantic: it’s a 1×1 matrix), given by
      \[
      x^T x = \sum_{i=1}^n x_i^2.
      \]
      Likewise, \(x^T A x\) is a scalar: it’s evaluation of a quadratic form, equal to
      \[
      x^T A x = \sum_{i=1}^n \sum_{j=1}^n A_{ij} x_i x_j
      \]
      (though for a sparse matrix \(A\), you do not need to sum over \(O(n^2)\) terms and can instead just do a sparse matrix-vector multiply \(Ax\), followed by a dense vector-vector inner product \(x^T(Ax)\)).

      Note that the symbol \(^T\) denotes the matrix transpose, whereas \(^\dagger\) typically denotes the pseudoinverse (a very different operation!).

  2. Possibly a silly question: my flatten timeout’s if I run the test from Chrome but works fine and passes if I run it in Firefox. Is that okay? Or do I need to make it faster somehow?

    My solveInversePowerMethod() stops after 7 iterations, if that helps.

    1. If it’s *really* slow in Chrome (like, you sit there waiting for a long time) then there could be something wrong. If it’s just a little slower than in Firefox (like, you don’t really notice when you’re just sitting there watching it), then you’re probably fine.

  3. Question irrelevent to this assignment: up to now I have only received the feedback from Assignment 0… is the grading still ongoing or have I missed something? Thanks!

  4. Question regarding some details:

    1. In this homework, the Laplace-Beltrami operator is defined as -*d*d (as in Exercise 7.6), which is a negative of what we have defined previously. Is it just for this homework or can we use it interchangeably?

    2. Also, I am a bit confused about when we use the mass matrix. Why can we ignore the mass matrix and use just the weak Laplacian matrix in this homework? Is our solution an approximation of the exact conformal parameterization or is it just a different normalization?

    1. 1. I think the one in the homework is a sign error. My solution has would require it to be consistent with what we have before. Does yours match?

      2. This is more so a matter of dimension. When we integrate the Laplacian on our mesh, we are integrating over 2-cells, so the result is a 2-form. However, applying the Laplacian to a function should return a scalar function (0-form). Thus, we must apply the dual 2-form Hodge star, which amounts to dividing by area (the Mass Matrix). In the math calculations, you will see this by the inverse mass matrices we multiply. However, in the programming, the Laplace Matrix you build is actually the zero form already. This means that we basically have $LM^{-1}$ when we build the matrix. Thus, when we multiply by M, we are just left with $L$ as desired. For example, in HW 3, for buildFlowOperator, this is precisely why you constructed $M+h\Delta$ and not $M+h\Delta M$.

      1. I don’t quite understand. For heat equations, we have $\frac{du}{dt} = \Delta u$ and we discrete it as $\frac{u_{k+1}-u_k}{h} = Lu_{k+1}$, $(I-hL)u_{k+1} = u_k $. Since $L = M^{-1}C$, we get $(M-hC)u_{k+1} = Mu_k$ I thought the Lapacian we built is -C and shouldn’ t it be a 2-form? And if we want to convert it into 0-form, we should multiply it by $M^{-1}$?

        1. Yes, that’s what I was trying to say. Sorry if I wasn’t clear about it. I was just trying to explain why sometimes equations may “appear” incorrect.

          1. Thanks for the answer but I don’t still understand question 2 that is about the mass matrix. As you mentioned, we need to multiply the mass matrix $M$ as well as the weak Laplacian matrix $C$ to make $L = MC$ as desired for Dirichlet energy $E_D$ (which I think would require the generalized eigenvalue problem in the end), but we didn’t multiply $M$ in this HW. Is it implicitly handled somewhere along the line or did I miss something?

  5. I’m confused about the signed area of the region z(M), what is the value of z at each vertex? I can’t find any complex values attached to the vertices, so I’m not sure what exactly I’m supposed to be using for $$\bar{z}_i z_j – \bar{z}_j z_i$$

    1. What we are doing here is to build a constant matrix A such that $$x^TAx$$ is equal to the quadratic form. If you look at exercise 7.14, it hints at why this is the correct method of discretization. The matrix only contains information for the terms of the map z that we want to compute, the boundary edges. This amounts to placing $$\pm \frac{i}{4}$$ in entry ij, if $$e_{ij}$$ is on the boundary.

Leave a Reply