A Hands-On Introduction to Discrete Differential Operators on Polygon Meshes
Laplacians on Polygon Meshes
Sven D. Wagner
TU Dortmund
Astrid Bunge
AutoForm Engineering
Mario Botsch
TU Dortmund
Problem Setting
Solve PDEs on general surface meshes
So far: Triangles 
Now: Polygons!
Virtual Simplicial Refinement
Prolongation Operator
\[ {\Huge \downarrow} \; \mat{P} \]
- 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
\[ {\Huge \uparrow} \; \mat{R} = \mat{P}\T \]
- Redistribute values back to original nodes \[ \mat{R} = \mat{P}\T \]
Polygon Shape Functions
\[\downarrow\] \[\downarrow\]
- Insert center vertex through prolongation weights
- Compute standard linear shape functions \(\psi_j(\vec{x})\) on refined polygon
- 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
Easiest Choice of Virtual Vertex
Easiest Choice of Virtual Vertex
Laplace Matrix & Mass Matrix
- “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} \]
Virtual refinement is completely hidden in matrix assembly step!
Poisson System on 2D Voronoi Meshes
13.5053, 28.5194, 58.8386, 119.78, 241.153
LVR, 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"
}
}
}
}
-->
