Geodesic distances
Distance along the surface of a mesh, from one seed or many. The methods, what each gets wrong, and how far trueform lands from the exact answer and how fast, in C++, Python and JavaScript.
A geodesic distance is the length of the shortest path that stays on the surface. Every method that computes it on a mesh buys speed with error. Dijkstra on the edges is fast and runs long. The heat method is smooth and smears. Exact MMP is right and takes minutes. The useful question is not which method is fastest, but how far from exact each one lands for the time it takes. This page answers it with measurements against an exact reference, then shows how trueform gets its place on that chart. Drop seeds on a dragon in the live example.
Along the surface, not through it
Measured from a set of seeds, it gives one number per point: zero at a seed, growing as you walk away, and always to the nearest seed.
The difference from straight-line distance is easy to see. Both pictures below start from the dragon's snout. On the left, the rings are straight-line distance. They slice through the body like parallel planes, and the front claw counts as close because it sits under the jaw. On the right, the rings are geodesic. They wrap around the neck and run down the body, and the claw is far, because the only way there is the long way round.
People search for this as surface distance, distance along a mesh or a geodesic distance field. They also search by method: the heat method, fast marching, Dijkstra on a mesh, exact MMP. All of these answer the same question. They differ in how wrong the answer is and how long it takes.
The methods, and what each gets wrong
Dijkstra on the edge graph. The shortest path through mesh edges. It is simple and robust, but a path on a mesh does not follow edges. It cuts across triangles. On a flat grid, Dijkstra measures a zigzag instead of a straight line, so it always overestimates. VTK's geodesic field is this kind of method.
The flat case shows the error plainly, because there the true answer is the straight line. Both pictures are the same synthetic flat grid and the same seed. The edge path draws its rings as polygons whose corners follow the grid's edge directions. Across the diagonals it runs 41 % long, and its median point is 7.7 % long. trueform's rings are circles: on this grid every distance matches the straight line to rounding.
The heat method. Diffuse heat from the seeds for a short time, normalise the gradient, and solve a Poisson equation for the distance. Two sparse linear solves. The result is smooth, but it is smoothed: distances blur near the seeds and over fine detail, and how much depends on the time step. libigl, CGAL and potpourri3d ship it.
Approximate fronts. Fast marching and its relatives sweep a front out from the seeds and update each point from the triangle it lies in. They are fast and close, but the error depends on the update rule and on the triangles. MeshLib's surface distance is in this family.
Exact window propagation (MMP). Track every interval of an edge that a shortest path can cross, and unfold it across the faces. The answer is exact up to floating point. It is the reference other methods are measured against. It is also slow: the exact answer for one mesh of up to 1.3M faces took up to 14 minutes.
Median relative error per point against exact MMP, averaged over the meshes. The heat-method figures are from the C++ run, the rest from the Python run.
Error against time
A time without an error says nothing. A method that returns zeros is fast. So we measure both, on the same meshes and the same seeds.
The corpus is 28 closed meshes from Thingi10K, from 10K to 3.2M faces. Each library runs from the same seeds, one and 32. The reference is exact MMP, on every mesh small enough to compute it. Apple M4 Max, 16 threads, trueform 0.10.8.
Lower left is better. In Python, on the 22 meshes where every library finished and an exact reference exists, trueform sits at 0.61 % median error in 5.8 ms. MeshLib is six times slower at four times the error. VTK's Dijkstra is five times slower at fifteen times the error, and from 32 seeds it has to run once per seed. PyMeshLab is the only peer that matches the error. It takes about twenty times as long.
Two things in the chart are worth reading twice. First, 32 seeds are faster than one. Each seed's front only has to reach the points nearer to it than to any other seed, so the fronts are short. Second, the error drops to 0.2 % from 32 seeds, because the paths are shorter and each crosses fewer faces.
The same story holds in every language. Times are geometric means over all 28 meshes.
On the largest mesh, 3,154,110 faces, one seed takes 135 ms in C++, 119 ms in Python and 196 ms in WebAssembly.
Every trueform benchmark, by module and language, is on the trueform benchmarks page.
How trueform lands near exact
trueform runs a label-correcting front with a triangle-unfolding update. It is not the heat method, and it is not exact. Here is the idea.
Paths cross faces. The points around each seed start at their straight-line distance. From there, a point is reached across a triangle, not along an edge: the two known corners of the triangle are unfolded into its plane, a virtual source is placed where the two distances meet, and the third corner reads its distance to that source. Where the source falls outside the triangle's angle at that corner, the path runs along an edge instead. On a flat mesh the result is the straight line. On a curved one it is shorter than any edge path.
The update is local and cheap: a few lengths and one square root per triangle. Each point keeps only its distance, and each triangle rebuilds a source from two of them, so small errors add up over the faces a path crosses. That is the 0.57–0.61 % median error measured above, and 0.2 % from 32 seeds, where paths are shorter. Exact MMP keeps every window of an edge that a shortest path can cross, which is where its minutes go.
Points are corrected. A label-correcting front does not settle a point once. If a shorter path arrives later, the point is lowered and its neighbours are updated again.
Clear values. A seed is zero. A point no front reaches, on another piece of the mesh or past a given radius, is infinity, not a large number. Distances use the stored coordinates; a transformation set on the mesh does not enter them. The result comes back in the mesh's type, float or double.
One seed, many seeds, a radius
The call takes point ids. Pass one id for a field from a point. Pass many and each point gets the distance to its nearest seed. Pass a radius and the front stops there, which turns a whole-mesh solve into a local one.
#include <trueform/trueform.hpp>
auto mesh_buffer = tf::read_stl("part.stl");
auto mesh = mesh_buffer.polygons();
std::vector<int> seeds{0, 120, 4711};
auto d = tf::make_geodesic_distances(mesh, seeds);
// d: tf::buffer<float>, one distance per point, to the nearest seed
auto near = tf::make_geodesic_distances(mesh, seeds, 0.5f); // within a radius
import trueform as tf
mesh = tf.Mesh(*tf.read_stl("part.stl"))
d = tf.geodesic_distances(mesh, [0, 120, 4711])
# d: np.ndarray, shape (num_points,), the mesh's dtype
near = tf.geodesic_distances(mesh, [0], radius=0.5) # inf past the radius
import * as tf from "@polydera/trueform";
import { readFileSync } from "node:fs";
const mesh = tf.readStl(readFileSync("part.stl"));
const seeds = tf.ndarray(new Int32Array([0, 120, 4711]), [3]);
const d = tf.geodesicDistances(mesh, seeds);
// d: NDArray, shape [numberOfPoints]
const near = tf.geodesicDistances(mesh, seeds, { radius: 0.5 });
When a seed is a position, such as a click, a probe or a landmark, snap it to the nearest mesh point first with a closest point query. When a seed is a curve, pass all of its points. Install with pip install trueform, npm install @polydera/trueform, or CMake, conan or nuget for C++. Geodesic distances need version 0.10.8 or later.
What the field is for
A distance field is an input. Rings of equal distance are offsets on a curved surface: a margin around a trim line, a falloff from a seam, an allowance along a cut. The patch within a distance is a region to select, paint or remove. The point farthest from every seed is the spot the seeds cover least.
That last fact builds a sampler. Take the farthest point, add it to the seeds, and run again. Each call is one multi-seed field. Forty rounds spread forty samples evenly over the surface, by distance along it. Run one field per sample and take the nearest, and the surface splits into regions, one per sample.
import numpy as np
import trueform as tf
mesh = tf.Mesh(*tf.read_stl("part.stl"))
seeds = [0]
for _ in range(39):
d = tf.geodesic_distances(mesh, seeds)
seeds.append(int(np.argmax(np.where(np.isfinite(d), d, -1))))
fields = np.stack([tf.geodesic_distances(mesh, [s]) for s in seeds])
region = fields.argmin(axis=0) # nearest sample, per point
Isocontours draw the rings at chosen distances. Isobands cut the patch out as its own mesh, with its boundary on the exact ring and each face mapped back to its source face.
d = tf.geodesic_distances(mesh, seeds)
rings, ring_points = tf.isocontours(mesh, d, [0.1, 0.2, 0.3])
(faces, points), _, face_ids = tf.isobands(mesh, d, [0.5], selected_bands=[0]) # within 0.5
The tutorials show both in each language.
Where to go next
Tutorials. C++, Python and JavaScript. Each covers one seed, many seeds, the radius, precision, and rings and patches.
Related operations. Rings and patches with isocontours. The shape of the surface with principal curvatures. Positions to seeds with closest point queries.
Documentation. Geodesic distances in the geometry module, in C++, Python and TypeScript.
Geodesics are one module of trueform. The same engine does mesh booleans, spatial queries, topology and remeshing, in C++, Python and the browser.
@article{polydera:geodesic-distances,
title={Geodesic distances},
author={Sajovic, {\v{Z}}iga, Polydera},
year={2026},
url={https://polydera.com/algorithms/geodesic-distances},
organization={Polydera}
}