Author: Keenan

Assignment 6 [Coding]: Vector Field Decomposition and Design (due 5/6)

Note: For the final assignment, you can do either this assignment or A5. Overall, you just need to be sure you completed A0 and A1, as well as 3 of the assignments A2–A6 (your choice which ones. See this Piazza post for more details.) Also, you cannot use late days on this assignment since it’s the last one.

Please implement the following routines in:

  1. projects/vector-field-decomposition/tree-cotree.[js|cpp]:
    1. buildPrimalSpanningTree
    2. inPrimalSpanningTree
    3. buildDualSpanningCotree
    4. inDualSpanningCotree
    5. buildGenerators
  2. projects/vector-field-decomposition/harmonic-bases.[js|cpp]:
    1. buildClosedPrimalOneForm
    2. compute

In addition, please implement either Hodge Decomposition, or Trivial Connections (on surfaces of genus 0):

Hodge Decomposition: Please implement the following routines in

  1. projects/vector-field-decomposition/hodge-decomposition.js:
    1. constructor
    2. computeExactComponent
    3. computeCoExactComponent
    4. computeHarmonicComponent

Trivial Connections on Surfaces of Genus 0: Please implement computeConnections in projects/direction-field-design/trivial-connections.js. This file has function signatures for trivial connections on arbitrary surfaces, but for this assignment we are only requiring you to compute the connection form on simply-connected surfaces where you don’t have to worry about the period matrix. You are, of course, welcome to implement the general algorithm if you would like to!

Notes:

  • Recall that homology generators are a set of loops which somehow describe all of the interesting loops on a surface. For example, here are the two homology generators for the torus.
  • Your buildGenerators function should implement the Tree-Cotree algorithm, which is Algorithm 5 of section 8.2 of the notes.
  • In tree-cotree.js the trees are stored using the dictionaries vertexParent and faceParent. You should store the primal spanning tree by storing the parent of vertex v in vertexParent[v]. The root should be its own parent. Similarly, you should store the dual spanning cotree by storing the parent of face f in faceParent[f].
  • The Tree Cotree algorithm finds homology generators on the dual mesh. That is to say, you should take each dual edge which is not in either spanning tree, and form a loop by following its endpoint back up the dual cotree until they meet at the root of the dual cotree. Even though we’re thinking of these homology generators as loops on the dual mesh, we still store them as lists of ordinary halfedges, since edges in the dual mesh are in 1-1 correspondence with edges in the primal graph.
  • buildClosedPrimalOneForm should use a homology generator to construct a closed primal 1-form as described in section 8.22 of the notes.
  • The compute function in HarmonicBases should compute a harmonic basis using Algorithm 6 in section 8.2 of the notes. If you choose to implement Hodge decomposition for the assignment, you are welcome to use your Hodge decomposition code to solve for $d\alpha$. Otherwise, you can just ignore the hodgeDecomposition parameter and directly solve the linear system $\Delta \alpha = \delta \omega$ to find $\alpha$. (Recall that $\delta$ is the codifferential, which we talked a lot about in the Discrete Exterior Calculus assignment).

Notes (Hodge Decomposition):

  • The procedure for Hodge Decomposition is given as Algorithm 3 in section 8.1 of the Notes.
  • Note that the SparseMatrix class has an invertDiagonal function that you can use to invert diagonal matrices.
  • For computeCoExactComponent, you should compute the coexact component $\delta \beta$ of a differential form $\omega$ by solving the equation $d\delta \beta = d\omega$. As stated in the notes, the most convenient way of doing this is to define a dual 0-form $\tilde \beta := *\beta$, and then to solve $d*d \tilde \beta = d \omega$. Then you can compute $\delta \beta$ using the fact that $\delta \beta = *d*\beta = *d\tilde\beta$. When doing these computations, you should keep tract of whether your forms are primal forms or dual forms, recalling that hodge stars take you from primal forms to dual forms, and hodge star inverses take you from dual forms to primal forms. (THis is discussed in detail in section 8.1.3 of the notes.
  • Note that the 2-form Laplacian B is not necessarily positive definite, so you should use an LU solver instead of a Cholesky solver when solving systems involving B.

Notes (Trivial Connections):

  • The trivial-connection-js file is structured for implementing the full trivial connections algorithm on arbitrary surfaces. Since that’s tricky, we’re only requiring that you compute connections on topological spheres. You should implement this in the computeConnections() function, and it should pass the tests labeled “computeConnections on a sphere”.
  • Even though we’re working with spheres, it is still helpful to use the formulation of Trivial connections given in section 8.4.1 of the notes. In particular, you should solve the optimization problem given in Exercise 8.21.
  • On a sphere, there are no harmonic 1-forms, so the $\gamma$ part of your Hodge decomposition will always be 0. Furthermore, the sphere has no homology generators, so the problem simplifies to \[\min_{\delta \beta} \;\|\delta\beta\|^2\;\text{s.t.}\; d\delta\beta = u\]
  • Following the notes, we observe that the constraint $d\delta\beta = u$ determines $\beta$ up to a constant, and that constant is annihilated by $\delta$. So you can find the connection 1-form $\delta \beta$ with a single linear solve.

Submission Instructions
Please submit all source files to Gradescope by 5:59pm ET on May 21, per the usual submission instructions.

Warning: You cannot use late days on this assignment!

The assignment is due on May 6, 2022 at 5:59:59pm Eastern (not at midnight!).

Assignment 6 [Written]: Vector Field Decomposition and Design (due 5/6)

Note: This last assignment serves as your “final”; we will not have any other kind of exam. Remember that you get a single “freebie” assignment, so if you already completed all the regular assignments: congratulations! You’re done, and can just relax during finals week (at least in this class). Or, if you’d like to get some extra credit—and have already completed the rest of the assignments—you can complete this assignment for up to one additional assignment’s worth of extra credit points.

In this assignment, you will investigate tools for working with tangent vector fields on surfaces. Tangent vector fields are central to classical differential geometry, and have many interesting applications. For this homework, we’ll look at one algorithm for designing vector fields, and along the way we’ll cover a lot of deep facts about surfaces.

There’s no PDF this week since the exercises are all from the notes. The notes will also give you all the background you’ll need to complete this assignment. It builds on a lot of the stuff we’ve already done in the class, especially discrete exterior calculus and the Laplacian.

Submit your written responses for Exercise 8.1 – Exercise 8.21 in the notes to Gradescope (per the usual submission instructions), except for Exercise 8.13.

Warning: You cannot use late days on this assignment!

The assignment is due on May 6, 2022 at 5:59:59pm Eastern (not at midnight!).

Reading 9—Choose Your Own Adventure (due 4/26)

There are way more topics and ideas in Discrete Differential Geometry than we could ever hope to cover in this course.  For this final reading assignment, you can choose from one of several options that we’ll cover in the remainder of our course:

  • Intrinsic Triangulations. In the next couple lectures we’ll revisit polyhedral surfaces through the powerful intrinsic perspective from differential geometry, where we no longer think about how a shape sits in space (i.e., no vertex positions) but instead only have measurements of local quantities like edge lengths and corner angles.  This simple twist provides a huge amount of flexibility for computation and algorithms, since there are infinitely many ways to intrinsically triangulate the same polyhedral surface without corrupting its geometry.  For this reading, you should read Sharp et al, “Geometry Processing with Intrinsic Triangulations”, pp. 1–29, plus one other chapter of your choice.  Summarize what you read, and say why you chose the chapter you did.
  • Repulsive Geometry. In our final lecture we’ll discuss a recent perspective on drawing/embedding/optimizing shapes using so-called repulsive energies. The basic starting point is to think about charged particles (like electrons) that try to repel each-other, often producing a nice, uniform distribution of particles.  Now imagine every point of a curve or surface is charged, and let it evolve to the most “self-avoiding” configuration… some very beautiful things emerge!  For this reading you should read Yu et al, “Repulsive Surfaces”, pp. 1–17.  Since this is a research paper, you shouldn’t be worried about understanding 100% of the details.  Rather, you should just get a general feeling for the problem motivation, the approach to the solution, and the potential applications of the method.
  • Tangent Direction Fields. Related to the final assignment (A6), you can choose to read one of two surveys on methods for tangent vector field processing—which should give you some additional perspective/context for this assignment.  Tangent vector fields, and more generally, symmetric n-direction fields are everywhere in physical and geometric applications, and a long-running question in DDG is: how should we represent tangent-valued data on discrete surfaces?  For this reading you can read either de Goes et al, “Vector Field Processing on Triangle Meshes”, pp. 5-21, and then choose two out of three of the remaining chapters: face-based, edge-based, and vertex-based vector fields.  Your writeup should compare and contrast these two choices: what are the basic pros and cons?  Alternatively, you can read Vaxman et al, “Directional Field Design, Synthesis, and Processing”, pp. 1–24.  Here again, your writeup should focus on the trade offs between different representations.

Your short 2-3 sentence summary is due by 10am Eastern on April 26, 2022.  Handin instructions can be found on the assignment page.

Lectures 21 & 22 — Geodesics

Our final lectures for the term focus on geodesics, which generalize the notion of “straight line” to curved spaces; this material also connects to your final assignment, on computing geodesic distance. Once again we’ll play “The Game” of discrete differential geometry, and see how two natural characterizations from the smooth setting (straightest and locally shortest) lead to two distinct, and fascinating definitions in the discrete setting. Along the way we’ll also encounter many rich topics from (discrete) differential geometry including the cut locus, the medial axis, the exponential/log map, the covariant derivative, and the Lie bracket! We’ll also see how all this stuff connects with practical algorithms for things like surface reconstruction from points, and give two different algorithms for tracing out geodesics on curved surfaces.

Note that the lecture video comprises about two lectures (about two hours total). If you need to watch the video instead of attending lecture (e.g., because you’re sick), we’d recommend watching it in two logical chunks:

  • Part I: Shortest Geodesics – 0:00—1:04
  • Part II: Straightest Geodesics – 1:04–1:55

Reading 8: Geodesic Algorithms (due 4/19)

This reading complements our lecture on algorithms for computing geodesic paths with an overview of algorithms for computing geodesic distances:

As with many of our readings, the point here is to just get a broader perspective of the material covered in lecture—you are not responsible for knowing every little detail. The algorithms discussed in Section 3 especially are well-connected to the perspective & tools we’ve been developing throughout the semester (e.g., the discrete Laplacian), and will help get you prepared for the assignment on computing geodesic distance.  For this reading you should summarize the high-level ideas from the first part of the survey, and any questions you might have.

Your short 2-3 sentence summary is due by 10am Eastern on April 19, 2022.  Handin instructions can be found on the assignment page.

Assignment 4 [Coding]: Conformal Parameterization (due 4/20)

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|cpp]:
    1. complexLaplaceMatrix
  2. projects/parameterization/spectral-conformal-parameterization.[js|cpp]:
    1. buildConformalEnergy
    2. flatten
  3. utils/solvers.[js|cpp]:
    1. solveInversePowerMethod
    2. residual

Notes

  • Warning: In the notes, the residual is defined as the 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^* Ax}{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 in the JS framework has a boundaries variable which stores all the boundary loops; similarly in Geometry Central you can iterate directly over boundary loops.)
  • The flatten function returns a dictionary mapping each vertex to a vector 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 submit your source files to the course Gradescope by 5:59pm ET.

The assignment is due on April 20, 2022 at 5:59:59pm Eastern (not at midnight!).

Assignment 4 [Written]: Conformal Parameterization (due 4/20)


The written part of your next assignment, on conformal surface flattening, is now available below. Conformal flattening is important for (among other things) making the connection between processing of 3D surfaces, and existing fast algorithms for 2D image processing. You’ll have the opportunity to implement one of these algorithms in the coding part of the assignment.


Assignment 4

The assignment is due on April 20, 2022 at 5:59:59pm Eastern (not at midnight!).

Lecture 19: Conformal Geometry

A basic task in geometric algorithms is finding mappings between surfaces, which can be used to transfer data from one place to another. A particularly nice class of mappings (both from a mathematical and computational perspective) are conformal maps, which preserve angles between vectors, and are generally very well-behaved. In this first lecture we’ll take a look at smooth characterizations of conformal maps, which will ultimately inspire the way we talk about conformal maps in the discrete/computational setting.

The video covering both today and Thursday’s lecture (on discrete aspects of conformal maps) can be found here.

Lecture 19: Conformal Geometry

A basic task in geometric algorithms is finding mappings between surfaces, which can be used to transfer data from one place to another. A particularly nice class of algorithms (both from a mathematical and computational perspective) are conformal mappings, which preserve angles between vectors, and are generally very well-behaved. In this lecture we’ll take a look at smooth characterizations of conformal maps, which will ultimately inspire the way we talk about conformal maps in the discrete/computational setting.

The video covering both this and the next lecture (on discrete aspects of conformal maps) can be found here.