Assignment 5 [Written]: Geodesic Distance (Due 5/2)

Here’s the writeup for your second to last assignment. This time, we’re taking off the “training wheels” and having you read a real paper, rather than course notes. Why? Because you’re ready for it! At this point you have all the fundamental knowledge you need to go out into the broader literature and start implementing all sorts of algorithms that are built on top of ideas from differential geometry. In fact, this particular algorithm is not much of a departure from things you’ve done already: solving simple equations involving the Laplacian on triangle meshes. As discussed in our lecture on the Laplacian, you’ll find many algorithms in digital geometry processing that have this flavor: compute some basic data (e.g., using a local formula at each vertex), solve a Laplace-like equation, compute some more basic data, and so on.

Your main references for this assignment will be:

  • this video, which gives a brief (18-minute) overview of the algorithm, and
  • this paper, which explains the algorithm in detail.

Written exercises for this assignment are found below.


Warning: The original version of this assignment had an unsolvable linear system in Exercise 7. I updated the assignment on Thursday, so hopefully the exercise is possible now.

31 thoughts on “Assignment 5 [Written]: Geodesic Distance (Due 5/2)”

  1. For Exercise 3, I don’t quite understand how “integrating by parts” lets us get rid of the integral, basically I do

    $$
    E(\phi) = \int_M ||\nabla \phi – X ||^2 dA = \int_M \langle \langle \nabla \phi, \nabla \phi \rangle \rangle – 2 \langle \langle X, \nabla \phi \rangle \rangle + \langle \langle X, X \rangle \rangle dA = …
    $$

    and I’m able to arrive at the desired result but I still have the integral over M and the dA—am I doing something wrong where expanding the inner product is part of integrating, or is my expansion of the inner product wrong overall?

    1. The “inner product” used in the exercise is the inner product that we talked about in the section on Green’s functions a few weeks ago – it’s defined to be the integral of the dot product of your vectors.

      1. That would mean that we would still end up with two integrals, right? One coming from the definition of $E(\phi)$ and one coming from the inner product $\langle \langle X, Y \rangle \rangle = \int_M X \cdot Y dA$?

        1. Ah, I see what you’re asking. The inner product inside of the integral in the definition of $E$ is just the regular dot product on vectors (without any more integration). Sorry for the confusing notation.

  2. I noticed a small typo in the writeup. The header for section 2 reads “Euler-Largrange Equation Derivation”, but I believe it should be “Euler-Lagrange Equation Derivation”.

  3. For Exercises 7-8, does the mesh have 3-4-5 as a face? I think it matters whether or not 3-4-5- is a face for the computation of the Laplace matrix.

    2. For Exercise 7, we got inconsistent equations when we tried to plug and chug the full 5×5 matrix multiplication—we were considering Neumann boundary conditions (implicitly) to be 0. Are the constants correct?

      1. There was a problem with the $f$ given in the assignment. I’ve updated the assignment, so you should be able to solve the system now. Let me know if it still gives you issues – it’s very possible that I made a mistake when updating the numbers.

        1. Alex and I aren’t having any luck with those numbers, but it could be that there’s something wrong with the equations we’re working with. We have
          $$
          -8 \phi_1 + 2 \phi_2 = 1
          $$
          $$
          2 \phi_1 – 6 \phi_2 + 4 = 0
          $$
          $$
          2 \phi_1 + 2 \phi_2 – 7 = -130/33
          $$
          $$
          2 \phi_1 + 10 = 108/11
          $$
          $$
          2 \phi_1 + 2 \phi_2 – 7 = -130/33
          $$

          2. Might be a bit late but on top of multiplying the RHS by the mass matrix, I think you also forgot to multiply the LHS by 1/2 when calculating C.

  4. Quick question about Exercise 5—is there any way we can say the boundary integrals are 0 (maybe of $\langle \langle N \cdot \nabla \psi, \phi \rangle \rangle_\partial$ or of $\int_{\partial M} \langle \langle \nabla \psi, \phi\rangle \rangle$)? There are a few pesky boundary integrals that are preventing us from turning the $\langle \langle \delta \psi, \phi \rangle \rangle$ into $\langle \langle \delta \phi, \psi \rangle \rangle$ in the expression
    $$
    -\langle \langle \delta \psi, \phi \rangle \rangle – \langle \langle \delta \phi, \psi \rangle \rangle + 2 \langle \langle \psi, \nabla \cdot X\rangle \rangle
    $$

    Both Green’s first identity as well as the integration by parts formula would allow us to do that, but only if the integral over the boundary is zero with $\langle \langle \nabla \psi, \phi \rangle \rangle$,

    1. Yes, feel free to make assumptions to make the boundary terms vanish. Just note what assumption you have to make at the beginning of your write up.

    1. Yes, you should use the boundary conditions for $\phi_3, \phi_4, \phi_5$. The idea is that you set up the Poisson equation $L \phi = M f$ for all 5 vertices like we normally do when there’s no boundary. Then you substitute in the known values for $\phi_3, \phi_4$ and $\phi_5$ to solve for $\phi_1$ and $\phi_2$.

  7. Hello,
    I have some confusion about Neumann boundary condition: I understand in the Laplace matrix, we need to add $(g_a + g_b)/2$ to $C_{ii}$ if i is on the boundary , but I am not sure what should we subtract from Mf on the RHS. Mf is a 5*1 column vector, but we have 3 values for $g$.
    Many thanks!

    1. You shouldn’t add anything to the Laplace matrix. Instead, you should subtract $(g_a + g_b)/2$ from entry $i$ of $M\!f$ on the right hand side. You should not subtract anything from the entries corresponding to interior vertices.

  8. Hi! I am confused about exercise 7 and 8, when we are finding the mass matrix M, i understand that each entry $M_{ii}$ is the barycentricDualArea of the vertex i, and the barycentricDualArea is $\frac{1}{3}$ of the total area of the faces touching the vertex i. However, I do remember we mentioned something like if a face in on the boundary loop, then the area of the face is 0. In that case, I am really confused about how to find the barycentricDualArea.
    Take the vertex 3 in the graph as an example, isn’t the barycentricDualArea $\frac{\sqrt{3}}{13}$ since the triangle 134 and 235 are on the boundary?

    1. The barycentric dual area at vertex $i$ is $\frac 13$ of the total area of the faces touching vertex $i$. So the barycentric dual area of vertex 3 should be $\frac{\sqrt 3}4$.

      When we talked about faces in a boundary loop earlier, that meant something different. Because having boundaries is often annoying, ddg-exercises-js actually fills in any holes in your input mesh with fake “boundary faces”. These faces aren’t really part of your mesh, so they should contribute area – they’re just convenient bookkeeping devices. These are the boundary faces which don’t contribute to area – not real faces which just happen to lie along the boundary.

      1. hmmm I set up the equations as follow and I don’t think they are solvable…
        \begin{align*}
        -4\phi_1+\phi_2 = 1 \\
        \phi_2-3\phi_2+2=0 \\
        \frac{2\phi_1+2\phi_2-7}{2}=\frac{-130}{44} \\
        \phi_1+5=\frac{216}{44} \\
        \frac{2\phi_1+2\phi_2-7}{2}=\frac{-130}{44}
        \end{align*}

        This is basically the system of equations that someone has posted above except that I multiply the RHS by the mass matrix and divide the LHS by 2

Leave a Reply