A Hands-On Introduction to Discrete Differential Operators on Polygon Meshes

Laplacian on Triangle Meshes

Sven D. Wagner

TU Dortmund

Astrid Bunge

AutoForm Engineering

Mario Botsch

TU Dortmund

🚀 by Decker

Triangle Meshes

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}\)

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

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

\[\begin{eqnarray*} \mat{L}_{ij} &=& \int \grad \varphi_i \cdot \grad \varphi_j &=& \begin{cases} - w_{ij} & \text{if } j\in\set{N}\of{i} \,, \\[0.5em] \displaystyle \sum_{k\in\set{N}\of{i}} w_{ik} & \text{if } j=i \,, \\[0.3em] 0 & \text{otherwise}. \end{cases} \\[1em] &&&&\text{ with } w_{ij} = \frac{\cot\alpha_{ij}+\cot\beta_{ij}}{2} \\[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

Positive 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

continous L has a set of key properties that discrete L must able emulate
correlation (for triangles) discussed by Wardetzky et al., equally holds for polygons.
Symmetry: contionus L selfadjoint, and every selfadjoint operator is symmetric, so discrete L should be a symmetric matrix.
Locality: The L of a function u at a point x should only depend on other points in an small epsilon environement around that point.
Linear Precision: on planar regions, the L of linear functions should be zero. So, the discrete equivalent should also hold for planar meshes.
NSD/PSD: dirichlet energy, (can be expressed with the help of S), remains greater equal zero.
null Property: kernel should be 1D -> only constant functions.
Positive weights: sufficent, but not necessary for the maximum principle.
solutions of diffusion problem flow from higher potnentials to lower ones.
not all props are always satisfied on all meshes!

Properties

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"
      }
    }
  }
}
-->

References

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.

Triangle Meshes

Functions on Triangle Meshes

Barycentric Coordinates as Shape Functions

Laplace Matrix & Mass Matrix

Local to Global Assembly

Properties

Quiz

Properties

Poisson System on 2D Triangle Meshes

Poisson System on 2D Triangle Meshes

Poisson System on 2D Triangle Meshes

References