{"id":2556,"date":"2022-03-25T01:05:23","date_gmt":"2022-03-25T05:05:23","guid":{"rendered":"http:\/\/brickisland.net\/DDGSpring2022\/?p=2556"},"modified":"2022-01-17T16:36:15","modified_gmt":"2022-01-17T21:36:15","slug":"assignment-3-coding-the-laplacian","status":"publish","type":"post","link":"https:\/\/brickisland.net\/DDGSpring2022\/2022\/03\/25\/assignment-3-coding-the-laplacian\/","title":{"rendered":"Assignment 3 [Coding]: The Laplacian (due 4\/6)"},"content":{"rendered":"<p><img loading=\"lazy\" class=\"alignnone size-full wp-image-1837\" src=\"http:\/\/brickisland.net\/DDGSpring2019\/wp-content\/uploads\/2019\/03\/poisson_bunny.png\" alt=\"\" width=\"886\" height=\"420\" \/><\/p>\n<p>For the coding portion of this assignment, you will build the so-called <em>\u201ccotan-Laplace\u201d<\/em> matrix and start to see how it can be used for a broad range of surface processing tasks, including the <em>Poisson equation<\/em> and two kinds of <em>curvature flow<\/em>.<\/p>\n<p><strong><span style=\"text-decoration: underline;\"><br \/>\nGetting Started<br \/>\n<\/span><\/strong><\/p>\n<p>Please implement the following routines in<\/p>\n<ol>\n<li><tt>core\/geometry.[cpp|js]<\/tt>:\n<ul>\n<li><tt>laplaceMatrix<\/tt><\/li>\n<li><tt>massMatrix<\/tt><\/li>\n<\/ul>\n<\/li>\n<li><tt>projects\/poisson-problem\/scalar-poisson-problem.[cpp|js]<\/tt>:\n<ul>\n<li>constructor<\/li>\n<li>solve<\/li>\n<\/ul>\n<\/li>\n<li><tt>projects\/geometric-flow\/mean-curvature-flow.[cpp|js]<\/tt>:\n<ul>\n<li>buildFlowOperator<\/li>\n<li><tt>integrate<\/tt><\/li>\n<\/ul>\n<\/li>\n<li><tt>projects\/geometric-flow\/modified-mean-curvature-flow.[cpp|js]<\/tt>:\n<ul>\n<li><tt>constructor<\/tt><\/li>\n<li><tt>buildFlowOperator<\/tt><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p><strong><span style=\"text-decoration: underline;\"><br \/>\nNotes<br \/>\n<\/span><\/strong><\/p>\n<ul>\n<li>Sections 6.4-6 of the <a href=\"http:\/\/www.cs.cmu.edu\/~kmcrane\/Projects\/DGPDEC\/paper.pdf\">course notes<\/a> describe how to build the cotan-Laplace matrix and mass matrices, and outline how they can be used to solve equations on a mesh. In these applications you will be required to setup and solve a linear system of equations $Ax=b$ where $A$ is the Laplace matrix, or some slight modification thereof. Highly efficient numerical methods such as <a href=\"https:\/\/en.wikipedia.org\/wiki\/Cholesky_decomposition\">Cholesky Factorization<\/a> can be used to solve such systems, but require A to be symmetric positive definite. Notice that the cotan-Laplace matrix described in the notes is <strong>negative semi-definite<\/strong>. To make it compatible for use with numerical methods like the Cholesky Factorization, your implementation of <tt>laplaceMatrix<\/tt> should instead produce a <strong>positive definite matrix<\/strong>, <em>i.e.<\/em>, it should represent the expression<br \/>\n$$(\\Delta u)_i=\\frac12 \\sum_{ij}(\\cot \\alpha_{ij}+\\cot \\beta_{ij})(u_i\u2013u_j).$$(Note that $u_i\u2212u_j$ is reversed relative to the course notes.) To make this matrix strictly positive definite (rather than semidefinite), you should also add a small offset such as $10^{-8}$ to the diagonal of the matrix (which can be expressed in code as a floating point value <tt>1e-8<\/tt>). This technique is known as <a href=\"https:\/\/en.wikipedia.org\/wiki\/Tikhonov_regularization\">Tikhonov regularization.<\/a><\/li>\n<li>The mass matrix is a diagonal matrix containing the barycentric dual area of each vertex.<\/li>\n<li>In the scalar Poisson problem, your goal is to discretize and solve the equation $\\Delta \\phi = \\rho$ where $rho$ is a scalar density on vertices and $\\Delta$ is the Laplace operator. Be careful about appropriately incorporating dual areas into the discretization of this equation (i.e., think about where and how the mass matrix should appear); also remember that the right-hand side cannot have a constant component (since then there is no solution).<\/li>\n<li>In your implementation of the implicit mean curvature flow algorithm, you can encode the surface $f:M \\to \\mathbb R^3$ as a single DenseMatrix of size $|V| \\times 3$, and solve with the same (scalar) cotan-Laplace matrix used for the previous part. When constructing the flow operator, you should follow section 6.6 of the notes. But be careful &#8211; when we discretize equations of the form $\\Delta f = \\rho$, we create systems of the form $A f = M \\rho$. So you&#8217;ll need to add in the mass matrix somewhere. Also, recall that our discrete Laplace matrix is the negative of the actual Laplacian.<\/li>\n<li>The <a href=\"http:\/\/www.cs.jhu.edu\/~misha\/MyPapers\/SGP12.pdf\">modified mean curvature flow<\/a> is nearly identical to standard mean curvature flow. The one and only difference is that you should <strong>not<\/strong> update the cotan-Laplace matrix each time step, i.e., you should always be using the cotans from the original input mesh. The mass matrix, however, must change on each iteration.<\/li>\n<\/ul>\n<p><strong><span style=\"text-decoration: underline;\"><br \/>\nSubmission Instructions<br \/>\n<\/span><\/strong><br \/>\nPlease only turn in the source files <tt>geometry.[cpp|js],\u00a0<tt>scalar-poisson-problem.[cpp|js], <tt>mean-curvature-flow.[cpp|js]\u00a0<\/tt><\/tt><\/tt>and <tt>modified-mean-curvature-flow.[cpp|js]\u00a0<\/tt>. These files\u00a0should be submitted via the usual mechanism, as described on the <a href=\"https:\/\/brickisland.net\/DDGSpring2022\/assignments\/\">assignments page<\/a>.<\/p>\n<p>The assignment is due on <strong>April 6, 2022 at 5:59:59pm Eastern<\/strong> (<em>not<\/em> at midnight!).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>For the coding portion of this assignment, you will build the so-called \u201ccotan-Laplace\u201d matrix and start to see how it can be used for a broad range of surface processing tasks, including the Poisson equation and two kinds of curvature flow. Getting Started Please implement the following routines in core\/geometry.[cpp|js]: laplaceMatrix massMatrix projects\/poisson-problem\/scalar-poisson-problem.[cpp|js]: constructor solve &hellip; <a href=\"https:\/\/brickisland.net\/DDGSpring2022\/2022\/03\/25\/assignment-3-coding-the-laplacian\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Assignment 3 [Coding]: The Laplacian (due 4\/6)&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_links_to":"","_links_to_target":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/posts\/2556"}],"collection":[{"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/comments?post=2556"}],"version-history":[{"count":5,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/posts\/2556\/revisions"}],"predecessor-version":[{"id":3401,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/posts\/2556\/revisions\/3401"}],"wp:attachment":[{"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/media?parent=2556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/categories?post=2556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/brickisland.net\/DDGSpring2022\/wp-json\/wp\/v2\/tags?post=2556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}