Closest point on a mesh

A scan holds two million points. The model holds a million triangles. The question is how far each point lies from the surface, and where on the surface it lands. That is a closest-point query, run two million times. This page is about running it at that scale: what it costs, how to pay the cost once, and how far to trust the answer. Move a probe around a dragon in the live example.

One query, three answers

Give the query a point. It returns the nearest face of the mesh, the nearest point on that face, and the squared distance between them. The point can sit inside a face, on an edge or on a vertex. The distance comes squared because most uses compare distances, and a comparison needs no square root.

Which of the three it is depends only on where the query sits. Every point in the plane above is coloured by where its closest point lands on the triangle. In the bands beside each edge, the answer slides along that edge. In the wedges past each corner, every query lands on the corner itself. The query works this out for each triangle it tests.

The operation goes by many names: point-to-mesh distance, nearest point on a mesh, projecting a point onto a surface, snapping. Each name points at one of three jobs.

• Deviation. How far is each scan point from the model? Inspection, quality control, as-built against as-designed.
• Registration. Which model point does each scan point pair with? Iterative alignment asks this for every point, every iteration.
• Snapping. Where on the surface does a click, a probe or a sensor reading land? Picking, measuring, attaching annotations.

All three run the query in bulk, against a mesh that does not change between queries. That is the case this page is about.

Build the tree once

A brute-force query tests every face. On a million-face mesh, a hundred thousand queries make a hundred billion point-triangle tests. Nobody runs that.

The fix is a spatial tree: faces grouped into boxes, boxes into larger boxes, up to one box around the mesh. A query walks down the tree, keeps the best distance found so far, and skips every box already farther than that. Most of the mesh is never touched.

The diagram is in 2D, where every box can be seen. The curve stands in for the mesh; its segments stand in for faces. The boxes are a schematic tree, split down the middle; the answer is trueform's. The query opens the box nearest to it first and finds a good candidate there. From then on, the dotted circle is the distance to beat. Any box that lies wholly outside the circle cannot hold a closer segment, so it is skipped with everything inside it. Ten segments of 160 were tested. On a million faces the ratio is far smaller, because the tree is deeper and each skip drops more.

The tree has a cost. On the Stanford dragon at about one million faces, from a mesh in memory to a query-ready tree:

Apple M4 Max, 16 threads, trueform 0.10.10.

Pay it once. The tree depends only on the mesh, so every batch after the first runs against the same tree. In C++, the tree over the 1,025,766-face dragon takes 7.87 ms; a batch of 100,000 queries against a ~1M-face mesh takes 94.1 ms. The build is about a twelfth of the first batch, and nothing after that.

Three rules keep the tree alive:

• Queries do not touch it. A query only reads the tree. In C++, run queries from as many threads as you like. In Python and JavaScript, one call takes the whole batch.
• Moving the mesh does not rebuild it. Give the mesh a 4×4 transformation and queries run in world space against the same tree. The points are not rewritten.
• Python and JavaScript cache it on the mesh. The first query builds it. build_tree() in Python, and buildTree() or tf.async.buildTree() in JavaScript, build it at a time you choose. Change the mesh data and the next query rebuilds it.

Throughput

The query benchmark runs 100,000 points against each of 160 Thingi10K meshes, 40 at each of ~100K, ~250K, ~500K and ~1M faces. The points fill each mesh's bounding box grown by 5 %, so some sit far from the surface.

Apple M4 Max, 16 threads, trueform 0.10.10, 160 Thingi10K meshes.

Read the numbers as a rate. A 131 ms batch is about 760,000 closest points a second, from one Python call, on a ~1M-face mesh.

Language

C++PythonTypeScript

Closest point · C++2.2× faster than MeshLib

Spatial tree build · C++up to 22× faster

Closest point · Python1.4× faster than MeshLib

Spatial tree build · Python4.1× faster than MeshLib

Spatial tree build · TypeScript23× faster

The nearest face, not a near one

Some fast methods trade accuracy for speed. They stop the search early, or search a sampled point cloud instead of the faces. trueform does neither.

A box is skipped only when it cannot hold a closer face than the best one found, so the face returned is the nearest face. The closest point is then computed on that triangle, wherever it falls: inside the face, on an edge or on a vertex. A point equally close to two faces gets one of them, with the same distance either way.

Precision is that of your coordinates. Meshes are float32 by default. In C++ and Python, a float64 mesh is queried in float64. Query points must match the mesh type; Python raises a TypeError on a mismatch instead of converting silently.

Deviation maps

A deviation map colours each scan point by its distance to the model. The closest-point query gives the size of the deviation. The sign, out of the model or into it, needs one more step.

signed_distance gives both at once: negative inside, positive outside. The size is the closest-point distance. The sign comes from the generalized winding number, which counts how much of the surface wraps around the query: about 1 inside, about 0 outside. It finds the side on meshes with holes and on triangle soups, so a scan or an export with gaps signs correctly.

The scan above is synthetic: the public Stanford dragon at a coarser tessellation, pushed out at the head, pushed in at the body, with fine noise added. Each of its vertices is one query against the 250K-face model. The colour is the signed distance: teal in, orange out, sand within the tolerance.

From the arrays to a report is NumPy:

• the largest deviation is abs(d).max();
• the points out of tolerance are abs(d) > tol;
• the face ids index per-face labels, so deviation can be summed per feature of the model.

Registration

Iterative closest point alignment moves the scan toward the model in steps. Each step pairs every scan point with its closest model point, then solves for the motion that brings the pairs together.

The model stays still, so its tree is built once and serves every iteration. Only the scan points move, and the scan points need no tree: they are the batch. Each iteration is one batch call.

To align the other way, give the model a transformation instead. The tree still does not rebuild.

In Python, two calls: fit_obb_alignment for the coarse pose, then fit_icp_alignment to refine it.

scan = tf.PointCloud(scan_points)
model = tf.PointCloud(model_points)

scan.transformation = tf.fit_obb_alignment(scan, model)                          # coarse
scan.transformation = tf.fit_icp_alignment(scan, model) @ scan.transformation    # refine

Drag one dragon away from another and align it back in the live registration example.

Snapping

Snapping asks a smaller question: the surface point near a click or a probe, if one is near enough.

Within a radius. Pass a radius and the search ignores anything farther. A single query returns nothing when no face is in range. A batch marks misses with −1 for the face id and infinity for the distance, so the mask is one comparison. A tight radius also prunes the search.

k nearest. Pass k and each query returns its k nearest faces, sorted by distance. With a radius, a query can find fewer than k; Python returns the count per query.

Per-face data. The face id indexes anything stored per face. A normal, a material label or a colour at the snapped point is one array lookup.

Distance only. When the point and the face do not matter, distance and distance2 take the same inputs and return one array.

Tuning the query

• Points far from the surface. Pass the largest distance that matters as the radius, and the search drops everything beyond it.
• A shape that changes. Moving the mesh keeps the tree. Changing its points or faces rebuilds it on the next query; in C++, mod_tree updates only the faces that changed.
• Coordinates far from the origin. A float32 mesh in survey coordinates, kilometres from the origin, keeps fewer digits near its surface. Subtract one offset from the mesh and the queries before you start, or use float64 in C++ and Python.

Closest point in code

Each example builds the tree on the model and runs a batch of points against it.

#include <trueform/trueform.hpp>

auto model_buffer = tf::read_stl("model.stl");
auto model = model_buffer.polygons();
tf::aabb_tree<int, float, 3> tree(model, tf::config_tree(4, 4));
auto form = model | tf::tag(tree);

// queries, face_ids, closest_pts: std::vectors of equal size
tf::parallel_for_each(tf::zip(queries, face_ids, closest_pts), [&](auto row) {
  auto &&[q, id, pt] = row;
  auto [fid, mp] = tf::neighbor_search(form, q);
  id = fid;
  pt = mp.point;
});

import numpy as np
import trueform as tf

model = tf.Mesh(*tf.read_stl("model.stl"))
model.build_tree()

scan = tf.Point(np.load("scan.npy").astype(np.float32))   # (N, 3)
face_ids, dist2, closest = tf.neighbor_search(model, scan)
deviation = tf.signed_distance(model, scan)               # negative inside
out_of_tol = np.abs(deviation) > 0.1

import * as tf from "@polydera/trueform";
import { readFileSync } from "node:fs";

const model = tf.readStl(readFileSync("model.stl"));
await tf.async.buildTree(model);

const queries = tf.point(scanXYZ, 3);   // Float32Array, 3 numbers per point
const { elementIds, points, distances } = tf.neighborSearch(model, queries);
// distances are squared

The tutorials go through single points, the radius, k nearest and posed meshes one step at a time, with pictures.

Where to go next

Tutorials. C++, Python, JavaScript.

Two meshes instead of points. When the query is a whole second mesh, the questions change: do they touch, how far apart are they, which faces meet. That is mesh collision detection.

Distance along the surface. A snapped point makes a good seed for geodesic distances.

Documentation. Neighbor search, distance, signed distance and the rest of the spatial module, in C++, Python and TypeScript.

Spatial queries are one module of trueform. The same engine does mesh booleans, curvature, topology and remeshing, in C++, Python and the browser.

@article{polydera:closest-point-on-a-mesh,
  title={Closest point on a mesh},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/algorithms/closest-point-on-a-mesh},
  organization={Polydera}
}