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

Robust Laplacians on Triangle Meshes

Sven D. Wagner

TU Dortmund

Astrid Bunge

AutoForm Engineering

Mario Botsch

TU Dortmund

🚀 by Decker

A Wild Problem Appears!

images/wildDDG/smoothing_issue.png — Exhibit A: Use Laplacian in explicit smoothing

images/wildDDG/holefilling_issue.png — Exhibit B: Use Laplacian in fairing of filled hole

Let’s see…

Quiz

Why does the parametrization and hole filling fail?

Coding Bugs
Mesh Quality
Wrong algorithm
Mesh too big

What’s the Problem?

Short answer: Mesh quality! What’s that exactly? 🤔

Many different definitions exist (depending on who you ask)
- FEM literature often talks about bad triangle shapes (e.g., Shewchuk 2002, Sorgente et al. 2023)

Needles

Large discretization error
Bad stiffness matrix conditioning

Can result in unstable Laplacians 😢

Caps

Large interpolation error
Can introduce negative weights into stiffness matrix

Can result in inaccurate Laplacians 😢

Back to our Problem

🛠️ Fix: Small changes in implementation 🛠️

Robustness of cotangent Laplacian majorly depends on implementation 🤔

How Robust is the Cotangent Laplacian?

First goal: Compare the implementations of the regular cotangent Laplacian

Choose selection of most popular general purpose geometry processing libraries
Categorize based on implementation type
Benchmark their robustness

Chosen Libraries

CGAL
CinoLib
Geogram

Geometry-Central
libigl
OpenMesh

PMP
VCGLib

How to Implement a Cotangent Laplacian?

\[\cot(\alpha_i) = \frac{\cos(\alpha_i)}{\sin(\alpha_i)}\]

\[= \frac{\langle \vec e_{ij}, \vec e_{ik} \rangle}{2|t_{ijk}|}\]

\[= \frac{||\vec e_{ij}||^2 + ||\vec e_{ik}||^2 - ||\vec e_{jk}||^2}{4|t_{ijk}|}\]

Trigonometric

Get corner angles \(\to\) Apply trigonometric functions to get cotangent

CinoLib, Geogram, OpenMesh, and VCGLib

Extrinsic

Calculate cotangent using formulas based on edge vectors

CGAL and Geometry-Central

Intrinsic

Calculate cotangent using formulas based on edge lengths

libigl and PMP

Stability Trick (Optional)

Ignore cotangent weights of triangles with zero area

CGAL and PMP

←

Must be good then, right? 🤔

Synthetic Benchmark Dataset

Isolated

Banded

Clustered

Banded (Spheres)

❗ Disclaimer: These meshes have really bad mesh quality ❗

But similar to mesh quality in the wild

Poisson Reconstruction, Marching Cubes, Thingi10k, …

Benchmark Results

Solve different PDEs to evaluate robustness and accuracy on ~1000 test meshes

Trigonometric

<!-- { "data": {
  "datasets": [
    {
      "backgroundColor": "#84b819ff"
    },
    {
      "backgroundColor": "#f5631fff"
    }
  ] },
    "options": {
      "plugins": {
      "legend": {
        "display": true
      },
      "tooltip": {
        "enabled": false
      }
      },
        "x": {
            "ticks": {
                "font": {
                    "size": 16
                }
            }
        },
        "y" : {
            "ticks": {
                "format": {
                    "style": "percent",
            "minimumFractionDigits": 0,
            "maximumFractionDigits": 0
                }
            }
        }
    }
} -->
Geogram, OpenMesh, VCGLib, CinoLib
Success, 0.088, 0.099, 0.097, 0.588
Fail, 0.912, 0.901, 0.903, 0.412

Intrinsic

<!-- { "data": {
  "datasets": [
    {
      "backgroundColor": "#84b819ff"
    },
    {
      "backgroundColor": "#f5631fff"
    }
  ] },
    "options": {
      "plugins": {
      "legend": {
        "display": false
      },
      "tooltip": {
        "enabled": false
      }
      },
        "x": {
            "ticks": {
                "font": {
                    "size": 16
                }
            }
        },
        "y" : {
            "ticks": {
                "format": {
                    "style": "percent",
            "minimumFractionDigits": 0,
            "maximumFractionDigits": 0
                }
            }
        }
    }
} -->
libigl, PMP
Success, 0.312, 0.467
Fail, 0.688, 0.533

Extrinsic

<!-- { "data": {
  "datasets": [
    {
      "backgroundColor": "#84b819ff"
    },
    {
      "backgroundColor": "#f5631fff"
    }
  ] },
    "options": {
      "plugins": {
      "legend": {
        "display": false
      },
      "tooltip": {
        "enabled": false
      }
      },
        "x": {
            "ticks": {
                "font": {
                    "size": 16
                }
            }
        },
        "y" : {
            "ticks": {
                "format": {
                    "style": "percent",
            "minimumFractionDigits": 0,
            "maximumFractionDigits": 0
                }
            }
        }
    }
} -->
GC, CGAL
Success, 0.484, 0.549
Fail, 0.516, 0.451

So, just don’t use trigonometry and use the stability trick? 🤔

This Should be Robust Now, Right?

Well… 🫤

Can we maybe modify the cotangent Laplacian itself? 🤔

Intrinsic Delaunay Triangulation (iDT)

Improve cotangent Laplacian by improving triangle quality
- Flip edges where \(\alpha_{ij} + \beta_{ij} > \pi\)
- Keep geometry by only flipping intrinsically (recalculate edge lengths)

Positive weights
Locality
Does not necessarily improve robustness 😢

Intrinsic Mollification

Degenerate triangles are edge cases of triangle inequality
Triangle inequality should hold with significant inequality: \[\norm{\mathbf e_{ij}} + \norm{\mathbf e_{ik}} > \norm{\mathbf e_{jk}} + \delta\]
Calculate minimum edge length increase \(\varepsilon > 0\) necessary to satisfy this for all triangles
- Increase every edge length by \(\varepsilon\)

Does improve robustness of Laplacian 👍
Linear precision

Tempered Finite Element Method (TFEM)

Slightly modify computation of cotangent weights
- Clamp triangle area based on cubed mean edge length of the mesh

Does improve robustness of Laplacian 👍
Linear precision
Not scaling-invariant

Problems with Scaling

TFEM is built for very specific use case → Clamping is not scaling-invariant!

images/wildDDG/dynamic_dist_upscale.jpeg — Ground-Truth

images/wildDDG/local_refinement_tfem.png — Locally (Local Refinement)

images/wildDDG/static_dist_upscale_lines.jpeg — Globally (Up-Scaling)

We want clamping that only depends on individual triangle shapes

Extension to Scaling-Invariance → D-TFEM

Modify TFEM for scaling-invariance and more versatility

Cubed mean edge length → Squared mean edge length
- Global scaling-invariance
- Add constant representing triangle shape

Mean edge length of mesh → Mean edge length of individual element
- Local scaling-invariance

Also apply tempering to the mass matrix
- More robustness for higher-order PDEs

Scaling-Invariance Evaluation

images/wildDDG/local_refinement_dtfem.png — Local Refinement (D-TFEM)

images/wildDDG/dynamic_dist_upscale_lines.jpeg — Up-Scaling (D-TFEM)

What about Robustness?

Robustness in Numbers

<!-- { "data": {
  "datasets": [
    {
      "backgroundColor": "#84b819ff"
    },
    {
      "backgroundColor": "#f5631fff"
    }
  ] },
    "options": {
      "plugins": {
      "legend": {
        "display": false
      },
      "tooltip": {
        "enabled": false
      }
      },
        "x": {
            "ticks": {
                "font": {
                    "size": 20
                }
            }
        },
        "y" : {
        "min": 0.9,
        "max": 1,
            "ticks": {
                "format": {
                    "style": "percent",
            "minimumFractionDigits": 0,
            "maximumFractionDigits": 0
                }
            }
        }
    }
} -->
TFEM, iDT + Mollification, Mollification, D-TFEM
Success, 0.951, 0.976, 0.999, 1
Fail, 0.049, 0.024, 0.001, 0

D-TFEM works in every case! 👍

iDT and Mollification also quite robust, but only intrinsic differential operators

Let’s Get Back to Coding 💻

References

Bobenko, Alexander I., and Boris A. Springborn. 2007. “A Discrete Laplace–Beltrami Operator for Simplicial Surfaces.” Discrete & Computational Geometry 38 (4): 740–56.

Quiriny, Antoine, Václav Kučera, Jonathan Lambrechts, Nicolas Moës, and Jean-François Remacle. 2026. “The Tempered Finite Element Method.” Journal of Computational Physics 549.

Sharp, Nicholas, and Keenan Crane. 2020. “A Laplacian for Nonmanifold Triangle Meshes.” Computer Graphics Forum 39 (5). Wiley Online Library: 69–80.

Shewchuk, Jonathan Richard. 2002. “What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measures.” In International Meshing Roundtable (IMR).

Sorgente, Tommaso, Silvia Biasotti, Gianmarco Manzini, and Michela Spagnuolo. 2023. “A Survey of Indicators for Mesh Quality Assessment.” Computer Graphics Forum 42 (2). Wiley Online Library: 461–83.

Wagner, Sven Dominik, and Mario Botsch. 2025. “Robust Discrete Differential Operators for Wild Geometry.” In Vision, Modeling, Visualization.