Assignment 5 (Written): Geodesic Distance

Here’s the writeup for your final assignment, which is due on Thursday, December 14th. 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.

11 thoughts on “Assignment 5 (Written): Geodesic Distance”

  1. As pointed out by a couple of students, the slide “Discrete Boundary Conditions – Neumann” in the Laplace-Beltrami slides has a slightly wrong formula for the Neumann boundary conditions. The correct version is

    \(\mathcal A_if_i = \frac{1}{2}(g_a + g_b) + \frac{1}{2}\sum_{j \in \mathcal N} (\cot \alpha_{ij} + \cot \beta_{ij})(u_j – u_i).\)

    In particular, when summing over the neighborhood of a vertex, include boundary vertices, but do not add the angles that does not exist (i.e., assume \(\alpha_{ij} = 0\)). In particular, modulo the boundary terms, your matrices should look quite similar to what you built for the coding assignments.

      1. 1. This is the discretization of the equation $\Delta u = f$ with Neumann boundary conditions. The LHS does represent $Mf$, but the RHS has other terms you need to build the discrete equation.
        2. Good catch! Yes assume \(\cot \alpha_{ij} = 0.\)

  2. I am stuck in the question 5.
    0) First, I am already lost with the idea of discretizing the vector field.
    (a) I thought it meant integrating the vectors of X over the edge-vectors, which would result in values for each edge (slides 13-14 of lecture 6) . In this case, what is $X_j$?
    (b) However, the handout defines X in the discrete setting as a constant vector field on each face. In this case, what is the vector at the vertex $X_j$? The vertex will be between faces with different constant vector fields.
    1) I think that the question is referring to the “integrated divergence of $X$ out of the dual cell for the vertex $i$. In this case, shouldn’t the expression be “$(\nabla \cdot X)_i$?
    2) What are the edges $e_1$ and $e_2$?
    (a) the two parts of boundary edge of the dual area in respect to the edge $ij$
    (b) the two other edges on the faces divided by the edge $ij$ connected to $j$
    3) When we use the Stokes theorem we end up with a normal relative to the vertex $i$. Which definition of the discrete normal should we adopt?
    4) Is there any other information you could provide to help me understanding this problem?

      1. I’m also confused about this. I don’t know why the divergence has no dependence on i, but it still is with respect to a vertex i. Also, is “integrated divergence” supposed to be $\int_\Omega\nabla\cdot X\, dA$ or just $\nabla\cdot X$?

        1. It is the integrated divergence. Think about it, for each point in a triangle mesh, which area should you integrate the divergence over?
          The divergence has a dependence on $i$ because the sum in the formula in the paper is taken on all the incident triangles ie all the faces adjacent to $i$. Each $e_1,e_2$ depends on the face $j$.
          Hopefully that helps

    1. 0) In the paper $X_j$ is a vector on each face. The $X$’s themselves are the vectors. The vertices and edges use separate notation.
      1) Yes, the expression you are computing is for the vertex $i$
      2) $e_1$ and $e_2$ are two consecutive edges coming out of vertex $i$, they bound face $j$.
      3) You are applying Stokes theorem “in” the surface, so the normals will be in the plane of the faces (assume they are pointing “out”).
      4) Part of the challenge of the problem is understanding the notation in the paper. I hope these comments help.

  3. In Exercise 2, it seems that one also has to assume that $\langle X,n\rangle=0$ along the boundary to make the identity true. Alternatively, instead of imposing Neumann boundary conditions for both vector fields $\nabla\phi$ and $X$, one should require Dirichelet boundary condition for $\phi=0$ along the boundary.

Leave a Reply