Assignment 6: Direction Fields
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. Of course, since this is the end of the semester, you cannot use late days on this assignment!
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 course notes. In particular, you should complete Exercises 8.1–8.21, excluding Exercise 8.13. 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.
Please implement the following routines in:
- projects/vector-field-decomposition/tree-cotree.[js/cpp]:
- buildPrimalSpanningTree
- inPrimalSpanningTree
- buildDualSpanningCotree
- inDualSpanningCotree
- buildGenerators
- projects/vector-field-decomposition/harmonic-bases.[js/cpp]:
- buildClosedPrimalOneForm
- compute
- projects/vector-field-decomposition/hodge-decomposition.[js/cpp]:
- constructor
- computeExactComponent
- computeCoExactComponent
- computeHarmonicComponent
- Recall that homology generators are a set of loops which somehow describe all of the interesting loops on a surface. At right, for example, are the two homology generators \(\eta_1,\eta_2\) 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/cpp] 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).
- 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 := \star\beta\), and then to solve \(d\star d \tilde \beta = d \omega\). Then you can compute \(\delta \beta\) using the fact that \(\delta \beta = \star d \star \beta = \star 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.
- 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.