Assignment 1 (Coding): Exterior Calculus (Due 2/26)

For the coding portion of your first assignment, you will implement the discrete exterior calculus (DEC) operators $\star_0, \star_1, \star_2, d_0$ and $d_1$. Once implemented, you will be able to apply these operators to a scalar function (as depicted above) by pressing the “$\star$” and “$d$” button in the viewer. The diagram shown above will be updated to indicate what kind of differential k-form is currently displayed. These basic operations will be the starting point for many of the algorithms we will implement throughout the rest of the class; the visualization (and implementation!) should help you build further intuition about what these operators mean and how they work

Getting Started

  • For this assignment, you need to implement the following routines:
    1. in core/geometry.js
      1. cotan
      2. barycentricDualArea
    2. in core/discrete-exterior-calculus.js
      1. buildHodgeStar0Form
      2. buildHodgeStar1Form
      3. buildHodgeStar2Form
      4. buildExteriorDerivative0Form
      5. buildExteriorDerivative1Form

In practice, a simple and efficient way to compute the cotangent of the angle $\theta$ between two vectors $u$ and $v$ is to use the cross product and the dot product rather than calling any trigonometric functions directly; we ask that you implement your solution this way. (Hint: how are the dot and cross product of two vectors related to the cosine and sine of the angle between them?)

In case we have not yet covered it in class, the barycentric dual area associated with a vertex $i$ is equal to one-third the area of all triangles $ijk$ touching $i$.

EDIT: You can compute the ratio of dual edge lengths to primal edge lengths using the cotan formula, which can be found on Slide 28 of the Discrete Exterior Calculus lecture, or in exercise 36 of the notes (you don’t have to do the exercise for this homework).

Submission Instructions

Please rename your geometry.js and discrete-exterior-calculus.js files to geometry.txt and discrete-exterior-calculus.txt (respectively) and submit them in a single zip file called solution.zip by email to Geometry.Collective@gmail.com.

19 thoughts on “Assignment 1 (Coding): Exterior Calculus (Due 2/26)”

  1. Is the dual area of a vertex its barycentric dual area? The notes don’t talk a lot about the discrete/diagonal Hodge star, and don’t really talk about how to get the dual area of a vertex.

        1. ok… Could you please explain the term: the barycentric dual area?
          Specifically,
          1. what is the barycentric dual of a vertex? or how to find each vertex on the dual cell?
          2. how to define the `area’ of a dual cell? Is it just the geometric area?

          1. 1. AFAIK the barycentric dual of a vertex is a dual 2-cell (with some area)—the “barycentric” part just defines how the dual cell is generated, there is also a circumcentric dual area in the code that probably defines a different way of generating dual cells for vertices. This dual 2-cell has area defined by 1/3 * (the sum of the area of all faces touching this vertex in the original mesh), as indicated in the comments.

            2. Therefore, the “area” of a dual cell varies based on which type of dual cell we are working with! The barycentric dual area defines the area of the dual cell generated if we operate using the barycentric method—which is exactly the geometric area of the dual cell. In other words, yes, the “area” of a dual cell is the geometric area.

  2. I’m also not sure where the values for each discrete differential k-form (i.e. the values of the underlying k-form integrated over each k-simplex in our mesh i.e. values for each vertex, edge, and face) can be found in the code. Am I correct in assuming that the “volume” of an edge is its length, and the volume of a face is its area?

    1. Yes, the volume of an edge is its length and the volume of a face is its area.

      Generally in your code you should store a discrete differential k-form as a column vector with one entry per k-simplex in your mesh. For example, a discrete 0-form would just be a |V|-dimensional vector.

      1. How would we find the values associated with each k-simplex in our mesh? Would that be the provided vertexIndex/edgeIndex/faceIndex argument, or is that used to define which k-simplex maps to which entry in our resulting column vector?

          1. Hm, does that define the value of the differential 0-form integrated over that 0-simplex (vertex)? I’m having a bit of trouble seeing how that expression relates.

        2. I see. My original comment was answering how to get `volume’ of edges, which is related to constructing $\star $ operator. (consider volume as the length of an edge). The length is just the geometric norm between two points.
          I am guessing your question is how to get the specific value of the k-form over space?

          If so, then, in short, you don’t need the values. It is because the method returns an operator instead of results. The $d$ and $\star$ operators depend and only depend on the mesh.

          Later when users define any k-form, the operator which methods ‘buildxxx’ spit out will apply to it.

  3. I’m currently working on buildExteriorDerivative1Form.

    I’m trying to give each edge a consistent orientation based on its halfedge, but I’m having trouble achieving this. I’ve tried using graph search by starting with a single edge and propogating its orientation to neighboring edges, but it doesn’t seem to be working.

    Is there an easier way of assigning a consistent orientation to each edge?

    1. You don’t have to worry about consistently orienting the edges. Remember that in an oriented simplicial complex, we just need *some* orientation for each edge – they don’t have to be compatible in any way. Information about how orientations align with each other is stored in these exterior derivative matrices. So you can just orient each edge using the orientation of its halfedge.

  4. What is “the corner opposite to a halfedge”? Is it the corner a halfedge form with its prev halfedge? But if so why is the vertex that the corner lies on halfedge.prev.vertex? Shouldn’t it just be halfedge.vertex?

  5. For buildHodgeStar1Form, iirc, hodge star applied to a vector in 2D is equivalent to a quarter rotation. Since we are just returning the “volume” of these differential forms, does that mean we should populate the sparse matrix with the corresponding edge lengths?

Leave a Reply