Skip to main content

m06 · Triangle meshes, Laplace–Beltrami operators and geodesics

Warning

Education only. Not for diagnosis, treatment or any clinical decision.

In 60 seconds

A mapping system stores the chamber as a triangle mesh: vertices, edges and triangular faces, with activation times and voltages attached to the vertices. Three operations on that mesh come back again and again. The gradient on each triangle turns activation times into a conduction-velocity vector, and it is exact for a planar wave. The Laplace–Beltrami operator, the Laplacian on a curved surface, drives smoothing, interpolation and simulation; its standard discretization weights each edge by the cotangents of the two angles opposite it, and those weights turn negative on badly shaped triangles. Geodesic distance, the shortest path that stays on the surface, is needed for “how far from this point” questions; adding up edge lengths along the mesh overestimates it by up to 15% however fine the mesh is, while methods that solve a differential equation on the surface converge. The mesh is part of the measurement.

From the field

  • Velocity needs both density and accurate timing. Sparse, unevenly spaced and uncertain data make conduction velocity hard to compute, and many methods exist (Cantwell et al. 2015). In lab part B, 1 ms of timing noise gives a median speed error of 47% at 1-mm spacing and 9% at 8-mm spacing: closer points need better timing, not less.
  • Open tools work on the mesh. OpenEP provides functions for chamber geometry, activation mapping and conduction-velocity mapping on exported data; its area and volume were correlated with those of the clinical platform (Williams et al. 2021). The face areas in this module (Equation 2) are the same building block.
  • Shortest paths along edges are biased. On a regular triangle lattice, the edge path is longer than the straight line by up to \(2/\sqrt3\), 15.5%, at every resolution (demo m06-d1). Fast marching on triangulated domains (Kimmel and Sethian 1998) and the heat method (Crane et al. 2012) compute distances that converge as the mesh is refined.
  • Triangle shape matters. Slivers and obtuse angles give negative cotangent weights (demo m06-d2), which can make smoothing produce values outside the range of the data. In lab part C, a strongly jittered flat patch has 58 of its 1121 edges with negative weights.

Derivations

Symbols used throughout. \(V\), \(E\), \(F\) numbers of vertices, edges and faces; \(g\) genus (number of handles). \(u_i\) a value at vertex \(i\); \(T\) local activation time (ms). \(A_f\) area of face \(f\); \(\mathbf N_f\) its unit normal; \(\mathbf e_i\) the edge of a face opposite vertex \(i\), oriented counterclockwise about \(\mathbf N_f\). \(\mathbf v\) conduction-velocity vector (mm/ms = m/s). \(\alpha_{ij}\), \(\beta_{ij}\) the two angles opposite edge \(ij\); \(A_i\) the area assigned to vertex \(i\) (one third of each incident face); \(L_C\) the cotangent matrix, \(\mathbf A\) the diagonal matrix of \(A_i\). \(\Delta\) the Laplace–Beltrami operator; \(\lambda\), \(\phi\) an eigenvalue and eigenfunction; \(R\) sphere radius; \(l\) degree. \(t\) diffusion time, \(h\) mean edge length, \(\boldsymbol\delta_s\) a unit value at the source.

Meshes

A closed mesh that is topologically a sphere obeys Euler’s formula; every closed triangle mesh also shares each edge between two faces:

\[ \chi = V - E + F = 2 - 2g, \qquad 2E = 3F \tag{1}\]

So a closed chamber surface without holes has \(\chi = 2\) and about twice as many faces as vertices. Cutting a hole, for example at a valve or vein opening, adds a boundary loop and lowers \(\chi\) by one; a single flat patch, a disk, has \(\chi = 1\). A test that \(\chi\) is what you expect catches duplicated vertices, cracks and flipped faces before any map is computed. Lab part A builds subdivided icosahedra (icospheres): 12 vertices with five neighbors and every other vertex with six.

Key takeaways

  • \(V - E + F\) is a cheap check of mesh topology; a closed surface without handles gives 2.
  • A closed triangle mesh has about twice as many faces as vertices.

Gradients and conduction velocity

Values at the three vertices of a face define one linear function on it. Its gradient lies in the plane of the face:

\[ \nabla u\big|_f = \frac{1}{2A_f}\sum_{i \in f} u_i\,(\mathbf N_f \times \mathbf e_i), \qquad \mathbf v = \frac{\nabla T}{\lvert\nabla T\rvert^2} \tag{2}\]

Each term rotates the opposite edge by 90° in the plane, and its length over \(2A_f\) is one over the triangle’s height. For activation times \(T\), the wavefront moves along \(\nabla T\) at speed \(1/\lvert\nabla T\rvert\), which gives \(\mathbf v\). The formula reproduces any linear function exactly, on any triangle shape, so a planar wave gives the exact speed and direction (lab part B). Its error comes from the data: a timing error \(\delta T\) over a triangle of height \(h_i\) changes the gradient by about \(\delta T/h_i\), so small triangles amplify timing noise. m25 compares the velocity methods built on this formula with fitting methods (Cantwell et al. 2015).

Key takeaways

  • The per-face gradient is exact for linear data; its error comes from timing error divided by triangle size.
  • Conduction velocity is \(\nabla T/\lvert\nabla T\rvert^2\), in mm/ms (= m/s) when distances are in mm.

The Laplace–Beltrami operator

On a surface, the Laplacian of \(u\) is the divergence of its surface gradient. The standard discretization is the cotangent formula (Pinkall and Polthier 1993):

\[ (\Delta u)_i \approx \frac{1}{A_i}\sum_{j \in \mathcal N(i)} \frac{\cot\alpha_{ij} + \cot\beta_{ij}}{2}\,(u_j - u_i) \tag{3}\]

where \(\mathcal N(i)\) is the set of neighbors of \(i\). It follows from the energy \(\tfrac12\int\lvert\nabla u\rvert^2\) of the piecewise-linear function: the derivative of that energy with respect to \(u_i\) is minus the sum. The edge weights depend only on angles. On a flat mesh the formula maps every linear function to zero at interior vertices, and on a regular equilateral lattice it gives exactly 4 for \(x^2 + y^2\) (lab part C). On the unit sphere \(\Delta z = -2z\): the typical (median) error falls about fourfold per refinement, from \(1.4\times10^{-2}\) to \(2.2\times10^{-4}\) over three levels, but the worst error, at the 12 vertices with five neighbors, stays near 0.25 with these vertex areas. Errors concentrate where the mesh is irregular.

The weight of an edge is negative when its two opposite angles add up to more than 180°, that is, when the edge is not locally Delaunay. Negative weights break the property that a smoothed value lies between its neighbors.

Exact

Assumptions

  • Model: the weight \((\cot\alpha + \cot\beta)/2\) of one interior edge shared by two triangles (Equation 3), with the triangles drawn on a common edge. Tested against epml.meshes.edge_cotan_weight.
  • Parameters: the two opposite angles, 20–160° each; free choices for illustration.
  • What it ignores: the rest of the mesh, vertex areas and boundaries.

The Laplacian’s eigenfunctions are the surface’s natural vibration modes. On a sphere they are the spherical harmonics:

\[ -\Delta \phi = \lambda\,\phi, \qquad \lambda_l = \frac{l(l+1)}{R^2}\ \ (l = 0, 1, 2, \dots,\ \text{multiplicity } 2l + 1), \qquad -L_C\,\boldsymbol\phi = \lambda\,\mathbf A\,\boldsymbol\phi \tag{4}\]

The last form is the mesh version, a generalized eigenproblem with the sparse matrices \(L_C\) and \(\mathbf A\). On a level-4 icosphere (2562 vertices), the first eigenvalues on the unit sphere come out as 0, 2 (three times), 5.991 (five times) and about 11.96 (seven times) (lab part D). Low modes describe smooth shape and smooth maps; the graph neural networks of m39 also mix values over mesh neighbors.

Key takeaways

  • The cotangent Laplacian uses only angles and areas; it is exact for linear data on flat meshes.
  • Its weights turn negative on non-Delaunay edges, and its error concentrates at irregular vertices.
  • Its eigenvalues converge to the surface’s; on a sphere they are \(l(l+1)/R^2\).

Distances on a surface

The geodesic distance \(\phi\) from a source solves the eikonal equation \(\lvert\nabla\phi\rvert = 1\) with \(\phi = 0\) at the source; m42 uses the same equation with a speed (eq-m42-eikonal). The simplest estimate is the shortest path along mesh edges (Dijkstra’s algorithm). On an equilateral lattice, the shortest edge path in direction \(\theta\) from a lattice direction is longer than the straight line by the factor \((\sin\theta + \sin(60^\circ - \theta))/\sin 60^\circ\), largest, \(2/\sqrt3 \approx 1.155\), at 30°. The factor does not depend on the edge length, so refining the mesh does not remove it.

Exact

Assumptions

  • Model: the shortest path along the edges of an infinite equilateral triangle lattice compared with the straight line, for a direction you choose. The ratio is a closed form, checked against Dijkstra on a 41 × 41 lattice in tests/test_m06_meshes.py.
  • Parameters: direction 0–120°; the ratio repeats every 60°.
  • What it ignores: irregular meshes and curvature; on real meshes the bias varies from point to point.

Methods that treat the mesh as a surface converge instead. Fast marching extends a front from the source in order of arrival and handles triangulated domains in \(O(M\log M)\) steps for \(M\) points (Sethian 1996; Kimmel and Sethian 1998). The heat method solves two sparse linear systems (Crane et al. 2012):

\[ (\mathbf A - t\,L_C)\,\mathbf u = \boldsymbol\delta_s, \qquad \mathbf X = -\frac{\nabla u}{\lvert\nabla u\rvert}, \qquad L_C\,\boldsymbol\phi = \nabla\!\cdot\mathbf X \tag{5}\]

Heat diffused for a short time \(t\) from the source points away from it, so its normalized gradient gives the direction in which distance grows; the last step finds the function whose gradient best matches that direction. The authors use \(t = h^2\) (Crane et al. 2012). On the unit sphere, the edge-path error stays near 0.19 at every refinement, while the heat method’s mean error falls from 0.045 at level 2 to 0.0086 at level 5 (lab part E).

Key takeaways

  • Edge paths overestimate distance by up to 15.5% on a regular lattice, at any resolution.
  • Fast marching and the heat method solve the eikonal equation on the surface and converge.

Clinical correlate

NotePending clinical review

This section describes published findings only. It is not guidance for patient care, and it has not yet been reviewed by an EP physician.

Where this shows up in EP. Conduction velocity is computed from activation times recorded at scattered points on the chamber surface, and a survey of the methods describes how sparse, unevenly spaced and uncertain data make this hard (Cantwell et al. 2015). OpenEP, an open data format and analysis platform for exported mapping data, provides functions for geometry, activation and conduction-velocity mapping on the chamber mesh; its surface area and volume were correlated with the clinical platform’s, and when the authors investigated a systematic bias between the two, OpenEP recovered accurate values better than the clinical platform (Williams et al. 2021). Every one of these numbers depends on the mesh and the operators in this module.

What the evidence is. A methods survey (Cantwell et al. 2015), a software validation study on clinical mapping data (Williams et al. 2021), and the numerical-methods literature (Pinkall and Polthier 1993; Kimmel and Sethian 1998; Crane et al. 2012).

What a reader should ask:

  • How was the velocity computed? Per-triangle gradients, fits or another method; and how timing error was handled (Equation 2).
  • How fine and how regular is the mesh? Thin triangles amplify timing error and give negative Laplacian weights (Equation 3).
  • How were distances measured? Along edges or by a geodesic method (Equation 5).

Visual summary

Schematic

V − E + F = 2 − 2g gradient per face: v = ∇T / |∇T|² αβ weight (cot α + cot β)/2 edge paths are longer
Figure 1: Four mesh operations behind every map: counts, gradients, Laplacian weights and distances.

Assumptions

How experts think

Before trusting a map computed on a mesh, ask:

  1. Is the mesh what it claims to be? Count \(V - E + F\) and boundaries (Equation 1).
  2. How big are the triangles compared with the timing error? Velocity error scales as timing error over triangle height (Equation 2).
  3. Are the triangles well shaped? Obtuse and sliver triangles give negative weights (Equation 3).
  4. Which distance is used? Edge paths are biased; geodesic methods converge (Equation 5).
  5. Does the result change when the mesh is refined or remeshed? If it does, the mesh is part of the answer.

One sentence to keep: every map computed on a mesh inherits the mesh’s resolution, regularity and topology.

Cheat sheet

Quantity Result
Euler (Equation 1) \(V - E + F = 2 - 2g\); closed triangle mesh: \(2E = 3F\), \(F \approx 2V\)
Gradient (Equation 2) exact for linear data; velocity \(\nabla T/\lvert\nabla T\rvert^2\), speed \(1/\lvert\nabla T\rvert\)
Cotangent Laplacian (Equation 3) edge weight \((\cot\alpha + \cot\beta)/2\), negative if \(\alpha + \beta > 180°\)
Spectrum (Equation 4) sphere: \(l(l+1)/R^2\), multiplicity \(2l+1\); mesh: \(-L_C\phi = \lambda\mathbf A\phi\)
Edge paths regular lattice: up to \(2/\sqrt3\) (15.5%) too long at any resolution
Heat method (Equation 5) heat, normalize, Poisson; \(t = h^2\)

Values used in this module

Value Source
Fast marching on triangulated domains in \(O(M\log M)\) steps Kimmel and Sethian (1998)
Heat-method time step \(t = h^2\) Crane et al. (2012)
Speed errors with timing noise, Laplacian and eigenvalue errors, path ratios, heat-method errors our own code

Interview questions

Try each question before you open its model answer. In a real interview, say which assumptions you are making.

Q1. A closed mesh has 1000 vertices and 2990 edges. Is something wrong?

Model answer

Probably. A closed triangle mesh without handles has \(2E = 3F\) and \(V - E + F = 2\), so \(E = 3(V - 2) = 2994\). A smaller count suggests boundaries, holes or non-manifold edges (Equation 1).

Q2. How do you compute the gradient of activation time on one triangle?

Model answer

Treat \(T\) as linear on the face: sum each vertex time times the opposite edge rotated 90° in the plane, divided by twice the area (Equation 2).

Q3. Why is conduction velocity \(\nabla T/\lvert\nabla T\rvert^2\) and not \(\nabla T\)?

Model answer

\(\lvert\nabla T\rvert\) is time per distance, the slowness; speed is its inverse. Dividing \(\nabla T\) by its squared length keeps the direction and gives length \(1/\lvert\nabla T\rvert\) (Equation 2).

Q4. Points 1 mm apart with 1 ms of timing error. What happens to velocity?

Model answer

The gradient error is about 1 ms/mm, as large as the gradient of a 1 m/s wave itself, so speed can be badly wrong; in lab part B (0.8 m/s, 1-mm spacing) the median error is 47%. Wider triangles or better timing are needed (Equation 2) (Cantwell et al. 2015).

Q5. Write the cotangent Laplacian.

Model answer

\((\Delta u)_i \approx \frac{1}{A_i}\sum_j \frac{\cot\alpha_{ij} + \cot\beta_{ij}}{2}(u_j - u_i)\), with \(\alpha\) and \(\beta\) the angles opposite edge \(ij\) (Equation 3) (Pinkall and Polthier 1993).

Q6. When is a cotangent weight negative, and why does it matter?

Model answer

When the two opposite angles add up to more than 180°, so the edge is not locally Delaunay. Smoothing can then push values outside their neighbors’ range (Equation 3; demo m06-d2).

Q7. Your Laplacian is accurate almost everywhere but bad at a few vertices. Where would you look?

Model answer

At irregular vertices, such as those with five or seven neighbors, and at poorly shaped triangles; on the icosphere the worst error sits at the 12 five-neighbor vertices (Equation 3; lab part C).

Q8. What are the Laplace–Beltrami eigenvalues of a sphere of radius 10 mm?

Model answer

\(l(l+1)/100\) mm⁻²: 0, 0.02 (three modes), 0.06 (five modes) and so on (Equation 4).

Q9. Why not compute surface distance with Dijkstra on the mesh edges?

Model answer

Paths are forced along edges, so they are too long, by up to \(2/\sqrt3\) on a regular lattice, and the bias does not shrink with refinement (demo m06-d1).

Q10. Describe the heat method in three steps.

Model answer

Diffuse heat from the source for a short time; normalize the negative gradient to unit length; solve a Poisson equation whose solution has that gradient (Equation 5) (Crane et al. 2012).

Q11. What does the time step \(t\) do in the heat method?

Model answer

It sets how far the heat spreads before its direction is read. The authors use \(t = h^2\) (Crane et al. 2012). In our code, on a level-4 unit sphere, \(t = 0.1h^2\) more than doubles the mean error (0.030 against 0.013); the end of the lab suggests trying \(t = 10h^2\).

Q12. Two teams compute velocity maps from the same data and disagree. What would you compare?

Model answer

Mesh resolution and quality, the velocity method (per-triangle or fitted), timing preprocessing, and how outliers were removed (Equation 2) (Cantwell et al. 2015).

Code lab

The lab tests each operation on meshes whose answer is known.

Part What you do Data
A Icospheres, counts and triangle quality (Equation 1) synthetic
B Gradients, a planar wave and timing noise (Equation 2) synthetic
C The cotangent Laplacian on flat and spherical meshes; negative weights (Equation 3) synthetic
D Eigenvalues of the sphere (Equation 4) synthetic
E Edge paths against the heat method (Equation 5) synthetic

Each part ends with checks: lines that pass with the code as given. If you change something and a check fails, that is information, not an error to hide.

Self-check

Short checks you can do in your head. Open each answer after you have tried it.

S1. A closed mesh without handles has 5120 faces. How many vertices?

Answer

\(E = 7680\), so \(V = 2 + E - F = 2562\) (Equation 1).

S2. Activation time increases by 2 ms per mm. Speed?

Answer

0.5 mm/ms = 0.5 m/s (Equation 2).

S3. Both angles opposite an edge are 60°. Its weight?

Answer

\(\cot 60^\circ = 1/\sqrt3\), so the weight is \(1/\sqrt3 \approx 0.58\) (Equation 3).

S4. Opposite angles 120° and 70°. Sign of the weight?

Answer

Negative: they add up to more than 180° (Equation 3).

S5. How many independent modes has the sphere at eigenvalue \(6/R^2\)?

Answer

Five (\(l = 2\), \(2l + 1 = 5\)) (Equation 4).

S6. On an equilateral lattice, in which direction are edge paths most biased?

Answer

At 30° from a lattice direction, by \(2/\sqrt3\) (demo m06-d1).

Literature figures

These figures are worth looking at alongside this module. We link to them instead of copying them: some licenses do not allow reuse here, and others we could not confirm. Each entry says what to look for and where this module explains it.

  • Geodesics in heat. Crane and colleagues show the three steps of the heat method on surface meshes and compare it with fast marching (Crane et al. 2012). This module: distances on a surface.
  • Geodesic paths on triangulated surfaces. Kimmel and Sethian show distance maps and shortest paths computed by fast marching on triangulated domains (Kimmel and Sethian 1998). This module: distances on a surface.
  • Conduction-velocity methods. Cantwell and colleagues illustrate triangulation and fitting methods on mapping data (Cantwell et al. 2015). This module: gradients and conduction velocity.

Further reading

References

Cantwell, C D, C H Roney, F S Ng, et al. 2015. “Techniques for Automated Local Activation Time Annotation and Conduction Velocity Estimation in Cardiac Mapping.” Computers in Biology and Medicine 65: 229–42. https://doi.org/10.1016/j.compbiomed.2015.04.027.
Crane, Keenan, Clarisse Weischedel, and Max Wardetzky. 2012. Geodesics in Heat. arXiv preprint arXiv:1204.6216. https://doi.org/10.48550/arXiv.1204.6216.
Kimmel, R, and J A Sethian. 1998. “Computing Geodesic Paths on Manifolds.” Proceedings of the National Academy of Sciences of the USA 95 (15): 8431–35. https://doi.org/10.1073/pnas.95.15.8431.
Pinkall, Ulrich, and Konrad Polthier. 1993. “Computing Discrete Minimal Surfaces and Their Conjugates.” Experimental Mathematics 2 (1): 15–36. https://doi.org/10.1080/10586458.1993.10504266.
Sethian, J A. 1996. “A Fast Marching Level Set Method for Monotonically Advancing Fronts.” Proceedings of the National Academy of Sciences of the USA 93 (4): 1591–95. https://doi.org/10.1073/pnas.93.4.1591.
Williams, Steven E. et al. 2021. “OpenEP: A Cross-Platform Electroanatomic Mapping Data Format and Analysis Platform for Electrophysiology Research.” Frontiers in Physiology 12: 646023. https://doi.org/10.3389/fphys.2021.646023.