A Survey on Discrete Laplacians
for General Polygonal Meshes

Astrid Bunge & Mario Botsch
🚀 by Decker

Problem Setting

Solve PDEs on surface meshes and volume meshes

images/vw.pngSurface triangle mesh images/bunny-tets.pngVolume tetrahedral mesh

Laplacian is a central operator

  • Gradient (direction of steepest ascent) \[ \grad f(u,v) \;=\; \vector{ \pdiff{f}{u} \\ \pdiff{f}{v} } \]
  • Divergence (magnitude of source or sink) \[ \func{div} \vector{f_0(u,v) \\ f_1(u,v)} \;=\; \pdiff{f_0}{u} + \pdiff{f_1}{v} \]
  • Laplace (difference to average of local neighborhood) \[ \laplace f(u,v) \;=\; \func{div} \grad f \;=\; \frac{\partial^2 f}{\partial u^2} + \frac{\partial^2 f}{\partial v^2} \]

Diffusion Equation: \(\dot f = \lambda \laplace f\)

Laplace Equation: \(-\laplace f = 0\)

Discrete Laplacian has various applications

  • Mean Curvature
  • Smoothing & Fairing
  • Parameterization
  • Deformation
  • Geodesics Distances
images/swiss-army-knife.png
Find their presentation here

Discrete Laplacians for Polygonal/Polyhedral Meshes

images/vw.pngSurface Meshes: Triangles Polygons images/bunny-tets.pngVolume Meshes: Tetrahedra Polyhedra

Artist-Made Polygon Meshes

Hexagons are the Bestagons

Flatland

images/flatland.jpg
Higher-degree polygons are more noble 😄

Adaptive Refinement

Adaptive Refinement

Cutting & Fracturing

Cutting Simulation

Discrete Laplacians for Polygonal Meshes

images/vw.pngSurface Meshes: Triangles Polygons images/bunny-tets.pngVolume Meshes: Tetrahedra Polyhedra

Triangulate the Polygons?

images/quad.svg
Given polygon
images/bad_quad.svg
Breaks symmetry
images/good_quad.svg
Introduces new DoFs

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

Triangle Meshes

images/triangle-mesh-0.svg
  • Connectivity / Topology
    • Vertices \(\mathcal{V} = \{ v_1, \dots, v_n \}\)
    • Edges \(\mathcal{E} = \{ e_1, \dots, e_k \}\), \(e_i \in \mathcal{V} \times \mathcal{V}\)
    • Faces \(\mathcal{F} = \{ f_1, \dots, f_m \}\), \(f_i \in \mathcal{V} \times \mathcal{V} \times \mathcal{V}\)

images/triangle-mesh-1.svg
  • Geometry
    • Vertex positions \(\{ \vec{x}_1, \dots, \vec{x}_n \}\), \(\vec{x}_i \in \R^3\)

Functions on Triangle Meshes

  • Define a piecewise linear function on a triangle mesh as \[f(\vec{x}) = \sum_{i \in \set{V}} f_i \varphi_i(\vec{x})\]
    • Assign function values \(f_i\) to vertices \(v_i\) with positions \(\vec{x}_i\)
    • Assign linear “hat” basis functions \(\varphi_i(\vec{x})\) to vertices \(v_i\)
    • Equivalent to barycentric interpolation of \(f_i\) within triangles
      images/barycoord-1.svg

Barycentric Coordinates as Shape Functions

  • Piecewise linear functions
  • Interpolate nodal data: \(\varphi_i\of{\vec{x}_j} = \delta_{ij}\)
  • Partition of unity: \(\sum_i \varphi_i\of{\vec{x}} = 1\)
  • Barycentric property: \(\sum_i \varphi_i\of{\vec{x}} \vec{x}_i = \vec{x}\)
  • \(C^0\) across elements, \(C^1\) within elements

Laplace Matrix & Mass Matrix

images/cotanLaplace.png

\[ \small \begin{eqnarray*} \mat{L}_{ij} &=& -\int \grad \varphi_i \cdot \grad \varphi_j &=& \begin{cases} \frac{\cot\alpha_{ij}+\cot\beta_{ij}}{2} & \text{if } j\in\set{N}\of{i} \,, \\[0.5em] \displaystyle -\sum_{k\in\set{N}\of{i}} \mat{L}_{ik} & \text{if } j=i \,, \\[0.3em] 0 & \text{otherwise}. \end{cases} \\[1em] \mat{M}_{ij} &=& \int \varphi_i \, \varphi_j &=& \begin{cases} \frac{\abs{t_{ijk}} + \abs{t_{jih}}}{12} & \text{if } j\in\set{N}\of{i}\,, \\[0.5em] \displaystyle \sum_{k\in\set{N}\of{i}} \mat{M}_{ik} & \text{if }j=i \,,\\[0.3em] 0 & \text{otherwise}. \end{cases} \end{eqnarray*} \]

Local to Global Assembly

images/local_Lf.svg images/global_L.svg

Properties

  • Symmetry
    • Continuous Laplacian is selfadjoint
  • Locality
    • Laplacian of a function \(u\) at point \(\vec{x}\) should only depend on small neighborhood
  • Linear precision
    • Laplacian of linear functions should be zero on planar regions
  • Negative semi-definiteness
    • Ensures that Dirichlet energy does not switch signs
  • Null property
    • Kernel of the Laplacian should only contain constant functions
  • Positive weights
    • Sufficient condition for maximum principle

Quiz

Which property does the cotangent Laplacian not satisfy?

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

code-51558f66.gnuplot.svg

Poisson System on 2D Triangle Meshes

images/triangle_plane1.png images/triangle_plane2.png images/triangle_plane3.png images/triangle_plane4.png images/triangle_plane5.png

Poisson System on 2D Triangle Meshes

7.28224, 14.5124, 28.9698, 57.8831, 115.709
Cotan Laplacian, 0.0184139, 0.00457148, 0.00115444, 0.000291485, 7.33316E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        }
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        }
      }
    }
  }
}
-->

Poisson System on 2D Triangle Meshes

7.28224, 14.5124, 28.9698, 57.8831, 115.709
Cotan Laplacian, 0.0184139, 0.00457148, 0.00115444, 0.000291485, 7.33316E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

Barycentric Coordinates

  • Piecewise linear functions
  • Interpolate nodal data: \(\varphi_i\of{\vec{x}_j} = \delta_{ij}\)
  • Partition of unity: \(\sum_i \varphi_i\of{\vec{x}} = 1\)
  • Barycentric property: \(\sum_i \varphi_i\of{\vec{x}} \vec{x}_i = \vec{x}\)
  • \(C^0\) across elements, \(C^1\) within elements

Generalized Barycentric Coordinates

  • Piecewise linear functions
  • Interpolate nodal data: \(\varphi_i\of{\vec{x}_j} = \delta_{ij}\)
  • Partition of unity: \(\sum_i \varphi_i\of{\vec{x}} = 1\)
  • Barycentric property: \(\sum_i \varphi_i\of{\vec{x}} \vec{x}_i = \vec{x}\)
  • \(C^0\) across elements, \(C^1\) within elements

Generalized Barycentric Coordinates

  • Wachspress Coordinates
    • Wachspress, Warren
  • Mean Value Coordinates
    • Floater, Hormann, Ju, Wicke
  • Maximum Entropy Coordinates
    • Sukumar, Hormann
  • Harmonic Coordinates
    • Joshi, Martin

images/harmonic-coordinates-1.png

Harmonic Coordinates

  • Definition
    • Interpolate nodal data: \(\varphi_i(\vec{x}_j) = \delta_{ij}\)
    • Linear (=harmonic) on edges
    • Harmonic in interior: \(\laplace\varphi_i = 0\)
  • Computation
    • Method of fundamental solutions
    • Approximate shape functions \(\varphi_i\) by RBFs \(\psi_k\) \[\varphi_i(\vec{x}) = \sum_k w_k \, \psi_k\of{\vec{x}} + \pi_1\of{\vec{x}}\]
images/harmonic-coordinates-2.png

Quiz

For which property is the polynomial term \(\pi_1\of{\vec{x}}\) crucial? \[\varphi_i(\vec{x}) = \sum_k w_k \, \psi_k\of{\vec{x}} + \pi_1\of{\vec{x}}\]

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Laplace Matrix & Mass Matrix

\[ \small \begin{eqnarray*} \mat{L}_{ij} &=& -\int \grad \varphi_i \cdot \grad \varphi_j &=& \color{red}{\xcancel{ \begin{cases} \frac{\cot\alpha_{ij}+\cot\beta_{ij}}{2} & \text{if } j\in\set{N}\of{i} \,, \\[0.5em] \displaystyle -\sum_{k\in\set{N}\of{i}} \mat{L}_{ik} & \text{if } j=i \,, \\[0.3em] 0 & \text{otherwise}. \end{cases} }} \\[1em] \mat{M}_{ij} &=& \int \varphi_i \, \varphi_j &=& \color{red}{\xcancel{ \begin{cases} \frac{\abs{t_{ijk}} + \abs{t_{jih}}}{12} & \text{if } j\in\set{N}\of{i}\,, \\[0.5em] \displaystyle \sum_{k\in\set{N}\of{i}} \mat{M}_{ik} & \text{if }j=i \,,\\[0.3em] 0 & \text{otherwise}. \end{cases} }} \end{eqnarray*} \]

On triangles, harmonic coordinates reproduce barycentric coordinates

Harmonic Finite Elements

Demo: Parameterization

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Poisson System on 2D Voronoi Meshes

images/voronoi_plane1.png images/voronoi_plane2.png images/voronoi_plane3.png images/voronoi_plane4.png images/voronoi_plane5.png

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
Martin08,	0.00951959,	0.00236579,	0.000699382,	0.000188646,	5.46139E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Expected convergence rate 😄 Expensive to compute, evaluate, and integrate 😢

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

DEC Polygon Laplacians

  • Generalize DEC to non-planar polygons
  • Both have to tune a hyper-parameter \(\lambda\) \[\small \laplace \vec{u} \;\approx\; \mat{M}_0^{-1} \underbrace{\mat{d}\T \mat{M}_1 \mat{d}}_{\mat{L}} \, \vec{u}\]
    • Inner product matrix \(\mat{M}_1\) has to be positive definite
    • Regularization fills up the kernel 👍
    • Regularization affects the results 👎
images/alexa-laplace.png

\(k\)-Forms

  • Function that takes in \(k\)-simplex and assigns integrated value at output
  • Values stored at each element of the mesh

\(k\)-Forms

  • Function that takes in \(k\)-simplex and assigns integrated value at output
  • Values stored at each element of the mesh
    • 0-simplex: Vertices
images/0-form.svg
0-simplex

\(k\)-Forms

  • Function that takes in \(k\)-simplex and assigns integrated value at output
  • Values stored at each element of the mesh
    • 0-simplex: Vertices
    • 1-simplex: Edges
images/1-form.svg
1-simplex

\(k\)-Forms

  • Function that takes in \(k\)-simplex and assigns integrated value at output
  • Values stored at each element of the mesh
    • 0-simplex: Vertices
    • 1-simplex: Edges
    • 2-simplex: Faces
images/2-form.svg
2-simplex

\(k\)-Forms

  • Function that takes in \(k\)-simplex and assigns integrated value at output
  • Values stored at each element of the mesh
    • 0-simplex: Vertices
    • 1-simplex: Edges
    • 2-simplex: Faces
  • Inner product matrix \(\mat{M}_k\) defines a dot product \[ \left\langle \vec{u}, \vec{v} \right\rangle := \vec{u}\tp \mat{M}_k \vec{v} \]
images/2-form.svg
2-simplex

Strategy I: Maximum Orthogonal Projection

Inner Product Matrix

  • \(\mat{B}_f = (\vec{b}_1,\dots,\vec{b}_{n_f})^{\mathsf{T}} \in \R^{n_f \times 3}\)
    • Rows are barycenters \(\vec{b}_i = \frac{1}{2}\left(\mat{x}_{i+1}+\vec{x}_i\right)\) of each edge \(\vec{e}_i\).
  • $|f| $ is vector area of polygon \(f\)
  • Define local inner product matrix for 1-forms
    • \(\mat{\tilde{M}}_f = \frac{1}{|f|}\mat{B}_f \mat{B}_f ^{\mathsf{T}}\)
    • Encodes the polygon’s geometry
images/poly_bary.png

Inner Product Matrix

  • Laplace matrix \(\tilde{\mat{L}}_f = \mat{d}_f^{\mathsf{T}} \mat{\tilde{M}}_f \mat{d}_f\)
    • Matrix \(\mat{d}_f\) is the difference operator on polygon \(f\)
  • Gives gradient of vector area \[ \grad_{\vec{x}_i}\abs{f} = \left(\tilde{\mat{L}}_f \mat{X}_f\right)_i \]
  • Connection to cotan formula:
    • Derived as the gradient of triangle surface area 👍
images/poly_baryvect.png
\(\mat{B}_f\T \mat{d}\)

On some polygons \(\mat{\tilde{M}}_f\) is only positive semi-definite 😢

Quiz

Which property is lost through a positive semi-definite inner product matrix \(\mat{M}_1\)?

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Fill up the Kernel

  • \(\mat{E}_f = (\vec{e}_1,\dots,\vec{e}_{n_f})^{\mathsf{T}} \in \R^{n_f \times 3}\)
    • Rows are edge vectors of polygon \(f\). images/alexa_ef.svg
  • \(\mathbf{E}_f\T\) has maximal rank 3
  • \(\mat{E}_{\bar{f}} = (\bar{\vec{e}}_1,\dots,\bar{\vec{e}}_{n_f})^{\mathsf{T}} \in \R^{n_f \times 3}\)
    • Rows are edge vectors of maximal projection \(\bar{f}\). images/alexa_ebar_single.svg
  • \(\mat{E}\T_{\bar{f}}\) has rank 2 \(\rightarrow\) non-trivial kernel

Regularizer

  • Add regularizer matrix \(\mat{R}_f\) to fill up kernel
    • Adds missing rank \(n_f-2\)
    • Built from orthonormal kernel of \(\mat{E}_{\bar{f}}^{\mathsf{T}}\)

\[\mat{M}_{f} = \mat{\tilde{M}}_f + \lambda\mat{R}_f\]

Laplace and Mass Matrices

  • Local Laplace matrix per polygon \[ {\mat{L}}_f = \mat{d}\T \mat{M}_{f} \mat{d} \]
    • Assemble local matrices into global Laplace matrix \(\mat{L}\)
  • Global mass matrix \(\mat{M}\) with
    \[\mat{M}_{ii} = \sum_{f \ni v_i} \frac{|\bar{f}|}{n_f}\]

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
Alexa11; λ=2,	0.00838748,	0.00209687,	0.000476346,	0.000127937,	3.30444E-05
Alexa11; λ=1,	0.00456036,	0.0010483,	0.000382806,	8.53325E-05,	1.84683E-05
Alexa11; λ=0.5,	0.00800984,	0.00193734,	0.000621653,	0.000143936,	3.19937E-05
Alexa11; λ=0.1,	0.0144414,	0.00337097,	0.000947331,	0.000221091,	5.14271E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Strategy II: Cogradient Operator

Quiz

Which part of the integrals causes problems for non-planar polygons? \[\iint_f \grad u(\vec{x}) \d{A} = \oint_{\partial f} u(\vec{x}) \vec{t}(\vec{x}) \times \vec{n}(\vec{x}) \d{\vec{x}} \]

  • Tangent vector \(\vec{t}(\vec{x})\) at point \(\vec{x}\)
  • Surface normal \(\vec{n}(\vec{x})\) at point \(\vec{x}\)
  • The integral over the boundary of the polygon
  • The function values \(u(\vec{x})\) at the boundary of the polygon

Cogradient

  • Cogradient operator \[\grad u^{\bot}(\vec{x}) := \vec{n}(\vec{x}) \times \grad u(\vec{x}),\]
    • Gradient of \(u(\vec{x})\) locally rotated by 90 degrees around normal \(\vec{n}(\vec{x})\)
  • Use Stoke’s theorem \[\iint_f \grad u^{\bot}(\vec{x}) \d{A} = \oint_{\partial f} u(\vec{x}) \vec{t}(\vec{x}) \d{\vec{x}}\]
    • \(\vec{t}(\vec{x})\) is unit tangent vector at boundary point \(\vec{x}\)
    • Well-defined along polygon boundary
    • Can be exactly evaluated for linear functions!
  • Gives expression for polygon gradient operator \(\vec{G}_f\)

Musical Operators

  • Flat \((\flat)\) and sharp \((\sharp)\) operators important components of DEC
  • Given a metric:
    • Flat \((\flat)\) operator transforms vector to 1-form
    • Sharp \((\sharp)\) operator transforms 1-form to vector
  • Continuous relation for any scalar function \(u\) \[ \grad u = (\d u)^{\sharp}\]
  • Use polygon gradient \(\vec{G}_f\) to define musical operators \(\mat{V}_f^{\flat}\) and \(\mat{V}_f^{\sharp}\)

First Part Inner Product Matrix

\[\mat{\tilde{M}}_f = \abs{\bar{f}} \, \mat{V}_f^{\sharp \mathsf{T}} \, \mat{V}_f^{\sharp}\]

  • \(\mat{V}_f^{\sharp}\) maps discrete 1-form to tangent vector per polygon
  • \(\mat{\tilde{M}}_f\) gives dot product of projected tangent vectors
  • Mapping \(n_f\) values to tangent vector leads to loss of information 😢
    • Add regularizer for kernel dimension 👍

Regularizer

  • Add regularizer matrix \(\mat{R}_f\) to fill up kernel
    • Adds missing rank \(n_f-2\)
    • Eliminates part of the discrete 1-form that would result in tangent vector

\[\mat{M}_{f} = \mat{\tilde{M}}_f + \lambda\mat{R}_f\]

Laplace and Mass Matrices

  • Local Laplace matrix per polygon \[ {\mat{L}}_f = \mat{d}\T \mat{M}_f\mat{d} \]
    • Assemble into global matrix \(\mat{L}\)
  • Global mass matrix \(\mat{M}\) same as Alexa and Wardetzky

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
deGoes20; λ=2,	  0.00965471,	0.00245388,	  0.000542276,	0.000145297,	3.74297E-05
deGoes20; λ=1,	  0.00435302,	0.000996788,	0.000354402,	7.95537E-05,	1.73643E-05
deGoes20; λ=0.5,	0.00747841,	0.00182759,	  0.00059557,	  0.000138136,	3.05869E-05
deGoes20; λ=0.1,	0.0139834,	0.00327528,	  0.00092799,	  0.000217473,	5.03785E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Demo: Curvature

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

Virtual Simplicial Refinement

images/poly11.svg images/poly21.svg images/poly31.svg images/poly41.svg

Prolongation Operator

images/poly11.svg \[ {\Huge \downarrow} \; \mat{P} \] images/poly31.svg

  • Insert virtual vertex as affine combination \[ \small \matrix{ \sum_i w_i \vec{x}_{i}\\ \vec{x}_{1}\\ \vec{x}_{2}\\ \vec{x}_{3}\\ \vec{x}_{4}\\ \vec{x}_{5}\\ \vec{x}_{6} } = \underbrace{ \matrix{ w_1 & w_2 & w_3 & w_4 & w_5 & w_6\\ 1 & & & & & \\ & 1 & & & & \\ & & 1 & & & \\ & & & 1 & & \\ & & & & 1 & \\ & & & & & 1 } }_{\mat{P}} \matrix{ \vec{x}_{1}\\ \vec{x}_{2}\\ \vec{x}_{3}\\ \vec{x}_{4}\\ \vec{x}_{5}\\ \vec{x}_{6} } \]

Restriction Operator

images/poly11.svg \[ {\Huge \uparrow} \; \mat{R} = \mat{P}\T \] images/poly41.svg

  • Redistribute values back to original nodes \[ \mat{R} = \mat{P}\T \]

Polygon Shape Functions

images/poly11.svg \[\downarrow\] images/poly31.svg \[\downarrow\] images/poly41.svg

  1. Insert center vertex through prolongation weights
  2. Compute standard linear shape functions \(\psi_j(\vec{x})\) on refined polygon
  3. Coarse shape function for polygon \((\vec{x}_1, \dots, \vec{x}_n)\) with virtual vertex \(\vec{x}_0\) become \[ \varphi_i(\vec{x}) = \psi_i(\vec{x}) + w_i\psi_0(\vec{x}) \,,\quad i \in \{1, \dots, n\} \]

Polygon Shape Functions

  • Piecewise linear functions
  • Interpolate nodal data: \(\varphi_i\of{\vec{x}_j} = \delta_{ij}\)
  • Partition of unity: \(\sum_i \varphi_i\of{\vec{x}} = 1\)
  • Barycentric property: \(\sum_i \varphi_i\of{\vec{x}} \vec{x}_i = \vec{x}\)
  • \(C^0\) across elements, not \(C^1\) within elements

images/basis/L.0.jpg images/basis/L.1.jpg images/basis/L.2.jpg images/basis/L.3.jpg images/basis/L.4.jpg images/basis/L.5.jpg

Choice of Virtual Vertex

images/centroid_good.svg
Centroid
images/centroid_bad.svg
Centroid
images/quadratic_good.svg
Minimize sum of squared areas

Solve linear system for affine prolongation weights 👍

Quiz

For which (planar) elements would the virtual vertex lead to flipped virtual triangles?

  • Star-shaped elements
  • Convex elements
  • Non-star-shaped elements
  • Concave elements

Laplace Matrix & Mass Matrix

images/poly41.svg
  • “Sandwiched” Laplace matrix for polygons \[\mat{L} = \mat{P}\T \, \mat{L}^\func{tri} \, \mat{P} \]
  • “Sandwiched” mass matrix for polygons \[\mat{M} = \mat{P}\T \, \mat{M}^\func{tri} \, \mat{P} \]
  • Laplacian can be factored into divergence and gradient \[ \mat{L} = \underbrace{\mat{P}\T \mat{D}^\func{tri}}_{\mat{D}} \cdot \underbrace{\mat{G}^\func{tri} \mat{P}}_{\mat{G}} \]

Virtual refinement is completely hidden in matrix assembly step!

Demo: Smoothing

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
Bunge20, 0.00768401,0.00193955,0.00057802,0.000152567,3.41754E-05

<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

Finite Volumes

Main idea: Consider the integral of differential in a small region

  • Divergence: \[\iint_{\Omega} \text{div} \vec{u}\ \d{A} = \oint_{\partial \Omega} \vec{u}\tp\vec{n} \d{s}\]
  • Gradient: \[\iint_\Omega \nabla u \d{A} = \oint_{\partial \Omega} u\, \mat{n} \d{s}\]
  • Laplacian: \[\iint_\Omega \Delta u \d{A} = \oint_{\partial \Omega} \nabla u\tp \mat{n} \d{s}\]

Discrete Duality Finite Volumes (DDFV)

Quiz

How do we get diamond cells on an arbitrary polygon mesh?

  • Subdivide into triangles
  • Subdivide into quads
  • Connect primal and dual vertices
  • Introduce third control mesh

images/poly_mesh_dual.svg images/poly_mesh_diamond.svg

2D DDFV

images/our_diamond.png

\[ \grad u|_D \;=\; \frac{1}{2 \abs{D}} \sum_{(i,j) \in \partial D} \vec{e}_{ij}^\perp \frac{u_i+u_j}{2} \]

Limitations of DDFV

  • Typically only primal mesh is given
  • Dual vertices increase DoF significantly
  • Only defined on 2D planar meshes, not on two-manifolds

Virtual Dual Vertices

images/poly11.svg \[\downarrow\] images/poly31.svg \[\downarrow\] images/poly41.svg

  • Combine ideas from DDFV and virtual refinement
  • Use virtual vertices as dual mesh
  • Compute DDFV operator on the “virtual diamonds”
    • Express diamond in an intrinsic 2D coordinate system
  • Restrict values back to the original mesh

Limitations of DDFV

  • Typically only primal mesh is given
  • Dual vertices increase DoF significantly
  • Only defined on 2D planar meshes, not on two-manifolds

Diamond Gradient Operator

  • The \(i\)-th column of the diamonds gradient matrix \(\mat{G}_D \in \R^{2 \times 4}\) \[ \mat{G}_D(:,i) = \frac{1}{2 \abs{D}} \sum_{(i,j) \in \partial D} \vec{e}_{ij}^\perp \]
  • Mesh gradient \(\hat{\mat{G}}\) is combined with prolongation \(\mat{P}\) to form global operator \[ \mat{G} = \hat{\mat{G}} \, \mat{P} \,\in\R^{2\abs{\mathcal{E}} \times \abs{\mathcal{V}}} \]

Diamond Divergence Operator

  • The diamond divergence matrix is defined as \[ \mat{D} = -\mat{P}\tp \hat{\mat{G}}\tp \hat{\mat{M}}_\diamond \]
  • \(\hat{\mat{M}}_\diamond\) is diagonal matrix of diamond areas

Laplace Operator

  • Laplacian matrix is defined as \[ \mat{L} \;=\; \underbrace{-\mat{P}\tp \hat{\mat{G}}\tp \hat{\mat{M}}_\diamond}_{\mat{D}} \cdot \underbrace{\hat{\mat{G}} \mat{P}}_{\mat{G}} \]
  • Mass matrix derived from standard DDFV mass matrix \(\mat{M}_\diamond\) \[ \mat{M} \;=\; \mat{P}\tp \mat{M}_\diamond \mat{P} \]

Demo: Geodesics

Properties

  • Symmetry
  • Locality
  • Linear precision
  • Negative semi-definiteness
  • Null property
  • Positive weights

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
Bunge21, 0.00610683,0.00155889,0.000413685,0.000105977,2.46064E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Poisson System on 2D Voronoi Meshes

13.5053,	28.5194,	58.8386,	119.78,	241.153
Martin08,	       0.00951959,	0.00236579,	0.000699382,	0.000188646,	5.46139E-05
Alexa11; λ=2,	0.00838748,	0.00209687,	0.000476346,	0.000127937,	3.30444E-05
Alexa11; λ=1,	0.00456036,	0.0010483,	0.000382806,	8.53325E-05,	1.84683E-05
Alexa11; λ=0.5,	0.00800984,	0.00193734,	0.000621653,	0.000143936,	3.19937E-05
Alexa11; λ=0.1,	0.0144414,	0.00337097,	0.000947331,	0.000221091,	5.14271E-05
deGoes20; λ=2,	0.00965471,	0.00245388,	0.000542276,	0.000145297,	3.74297E-05
deGoes20; λ=1,	0.00435302,	0.000996788,	0.000354402,	7.95537E-05,	1.73643E-05
deGoes20; λ=0.5,	0.00747841,	0.00182759,	0.00059557,	0.000138136,	3.05869E-05
deGoes20; λ=0.1,	0.0139834,	0.00327528,	0.00092799,	0.000217473,	5.03785E-05
Bunge20,	       0.00768401,	0.00193955,	0.00057802,	0.000152567,	3.41754E-05
Bunge21, 0.00610683,0.00155889,0.000413685,0.000105977,2.46064E-05
<!--
{
  "options": {
    "scales": {
      "x": {
        "title": {
          "text": "inverse mean edge length",
          "display": true
        },
        "type": "logarithmic"
      },
      "y": { 
        "title": {
          "text": "L2 error",
          "display": true
        },
        "type": "logarithmic"
      }
    }
  }
}
-->

Outline

  • Introduction
  • Laplacian for Triangle Meshes
  • Laplacian for Polygon Meshes
    • Martin et al., Polyhedral finite elements using harmonic basis functions, SGP 2008
    • Alexa & Wardetzky, Discrete Laplacians on general polygonal meshes, SIG 2011
    • de Goes et al., Discrete differential operators on polygonal meshes, SIG 2020
    • Bunge et al., Polygon Laplacian made simple, EG 2020
    • Bunge et al., The Diamond Laplace for polygonal and polyhedral meshes, SGP 2021
  • Comparisons & Conclusion

Quantitative Comparisons

  • Ensure fair comparisons
  • All methods (re)implemented in C++
  • Same meshes & test for all methods
  • Code checked by original authors (Thanks 👍)
  • Source code for all Laplace operators, quantitative tests, and interactive demos is available on github

Poisson System on 2D Planes

images/2dFranke.svg

Eigenvalues on Unit Spheres

images/evalues_bigger.png

Condition Number

images/tessellation.png

Non-planar Polygons

images/nonplanar2.png

Computational Performance

code-ef5dd762.tex.svg
Time for building and solving a Poisson system

Conclusion

Recommendations

  • DEC Approaches
    • Favorable numerical results
    • Many other operators (de Goes et al.)
    • Stabilization term has to be adjusted
  • Diamond Laplacian
    • Works on surfaces and volumes
    • Favorable numerical results
    • Longer solving times
  • Virtual Refinement Method
    • Works on surfaces and volumes
    • Slightly less accurate
    • Easy to implement
  • Harmonic shape functions
    • Work on surfaces and volumes
    • Generalize \(P1\) and \(Q1\) elements
    • Computationally expensive

💾   Source code of all methods available on github   💾

Conclusion

  • Presented recent progress for Polygon Laplacians
    • Discuss individual discretization strategies
    • Point out similarities and differences
    • Analyze individual strength and weaknesses
  • Extensions

images/qr-code.svg

  • Acknowledgments
    • Collaborators: Marc Alexa, Philipp Herholz, Misha Kazhdan, Olga Sorkine-Hornung
    • Code-Checkers: Fernando de Goes, Max Wardetzky

References

Alexa, Marc, and Max Wardetzky. 2011. Discrete Laplacians on General Polygonal Meshes.” ACM Transactions on Graphics 30 (4).
Brezzi, Franco, Konstantin Lipnikov, and Valeria Simoncini. 2005. “A Family of Mimetic Finite Difference Methods on Polygonal and Polyhedral Meshes.” Mathematical Models and Methods in Applied Sciences 15 (10).
Bunge, Astrid, and Mario Botsch. 2023. A Survey on Discrete Laplacians for General Polygonal Meshes.” Computer Graphics Forum.
Bunge, Astrid, Mario Botsch, and Marc Alexa. 2021. The Diamond Laplace for Polygonal and Polyhedral Meshes.” Computer Graphics Forum 40 (5).
Bunge, Astrid, Philipp Herholz, Misha Kazhdan, and Mario Botsch. 2020. Polygon Laplacian Made Simple.” Computer Graphics Forum 39 (2).
Bunge, Astrid, Philipp Herholz, Olga Sorkine-Hornung, Mario Botsch, and Michael Kazhdan. 2022. Variational Quadratic Shape Functions for Polygons and Polyhedra.” ACM Transactions on Graphics 41 (4).
deGoes, Fernando, Andrew Butts, and Mathieu Desbrun. 2020. Discrete Differential Operators on Polygonal Meshes.” ACM Transactions on Graphics 39 (4).
Hermeline, F. 2000. “A Finite Volume Method for the Approximation of Diffusion Operators on Distorted Meshes.” J. Comput. Phys. 160 (2).
Hormann, Kai, and N. Sukumar. 2017. Generalized Barycentric Coordinates in Computer Graphics and Computational Mechanics. Taylor & Francis.
Martin, Sebastian, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral Finite Elements Using Harmonic Basis Functions.” Computer Graphics Forum 27 (5).
Pinkall, Ulrich, and Konrad Polthier. 1993. Computing Discrete Minimal Surfaces and Their Conjugates.” Experim. Math. 2.
Wardetzky, Max, Saurabh Mathur, Felix Kälberer, and Eitan Grinspun. 2007. Discrete Laplace Operators: No Free Lunch.” In Proceedings of Eurographics Symposium on Geometry Processing.