Mesh collision detection

Two meshes can be asked three things. Do they touch? How far apart are they? Which faces meet? The questions sound alike, but they cost different amounts, because each one lets the search stop at a different point. Ask the cheapest one that settles your case. This page shows which is which, and what happens to each when the meshes move. Drag two dragons into each other in the live example.

Pick the question

The first question is the cheapest. intersects stops at the first pair of faces that touch, so the colliding case is the fast case: in the JavaScript benchmark below, 0.107 ms at 58,298 faces per mesh and 0.043 ms at 1,025,766. Touching counts: surfaces that meet at a point or along a face return true. A motion planner that only needs to reject a pose should ask it and nothing else. A clearance check needs the second or third. An interference report needs the fourth, and pays for it by visiting the whole contact.

Broad phase and narrow phase in one call

Collision engines split the work in two. The broad phase finds the pairs of parts that might touch, usually by bounding boxes. The narrow phase tests the triangles of those pairs.

In trueform both happen inside one call. Each mesh has its own tree. The query walks the two trees as pairs of nodes and drops every pair whose boxes cannot meet, or cannot beat the best distance found so far. That is the broad phase. When two leaves survive, their triangles are tested in world coordinates. That is the narrow phase. You write neither.

The diagram is in 2D, so every box can be seen. Each curve stands in for a mesh, its segments for faces; the boxes are a schematic tree, the crossings are trueform's. Each curve has 32 leaf boxes, so there are 1,024 leaf pairs. The walk starts from the two root boxes. When two boxes overlap, the larger one is split and its children are paired with the other. When they do not overlap, the pair is dropped with every pair below it. Only four leaf pairs reach the test of their segments, all at the two places where the curves cross. A test that only needs a yes stops at the first of them.

The box shape matters for distance queries. The default tree, in every language, uses axis-aligned boxes. In C++ you can also build an obb_tree, with oriented boxes, or an obbrss_tree, which adds rectangle-swept spheres. They fit the surface tighter and prune more pairs on closest-pair queries. The query calls stay the same.

Closest pair between the Stanford dragon and a randomly transformed copy of itself, 1,025,766 polygons each, in C++.

Apple M4 Max, 16 threads. On the same tree type, trueform is about 2.4× faster than FCL and Coal with OBBRSS, and about 470× faster than FCL with AABB.

Moving meshes in real time

Things that collide move. If moving a mesh meant rewriting its points and rebuilding its tree, every frame would pay the full build.

In trueform a mesh carries a 4×4 transformation. Every query applies it on the fly, to the boxes as they are visited and to the triangles as they are tested. The points are not rewritten and the tree stays valid. A frame costs a matrix assignment and the query.

• Many copies. Shared views of one mesh share its points, faces and tree. Each view carries its own pose. A hundred placements of one part cost one tree.
• three.js. A world matrix goes in transposed, because three.js stores matrices column-major.
• The browser frame loop. The async variants, tf.async.intersects and tf.async.distance, run off the main thread.
• Local edits. When the shape itself changes in a small region, the C++ mod_tree updates the changed faces instead of rebuilding the whole tree. Every query works on it unchanged.

What a frame costs, in Node.js with WebAssembly, on the dragon against a transformed copy. The closest pair is taken across a gap; the test, on a pose where the surfaces cross:

Apple M4 Max, 16 threads, trueform 0.10.8. The last row is the price of the first frame. Every frame after it is one of the rows above.

The tree build itself, and how it compares across languages, is on the closest point page.

Language

C++PythonTypeScript

C++up to 22× faster

Python4.1× faster than MeshLib

TypeScript23× faster

Clearance and near misses

When the meshes do not touch, the useful number is the gap.

The dragon above is the public Stanford mesh; the plate is a synthetic box. One neighbor search returns the closest pair: a face on each mesh, a point on each face in world coordinates, and the squared distance between them. That is the pink segment. distance returns the same gap as one number, and zero when the meshes touch.

Is anything within d? Pass a radius. The search prunes every pair of boxes farther apart than the radius and returns nothing when the gap is larger. A minimum-clearance rule needs no more than that.

Where are they close? Gather the pairs of faces within a distance. The orange faces above are that set, on both meshes, for a band just past the gap. It marks the region to inspect before anything collides.

Proxies. A capsule, a segment with a radius, often stands in for a tool or a robot link. Its clearance is the distance from the segment to the mesh, minus the radius: one query and a subtraction. Segments, triangles, polygons, rays, lines, planes and boxes all work against a mesh. In Python a batch of segments is one call, with one answer per segment, computed in parallel.

Contact

When the meshes do touch, the face pairs say where. Each row of the result holds one face of the first mesh and one face of the second. The unique ids in each column are the faces in contact on each side. Colour them, count them, carry their attributes, or restrict a finer check to them.

When the contact is needed as geometry, the intersection curves give the exact curves where the surfaces cross. When the overlap is needed as a solid, mesh booleans give it.

One mesh against itself

A cloth, a hose or a scanned surface can fold through itself. has_self_intersections asks that of one mesh. It stops at the first contact, like the test between two meshes, and decides each pair in exact arithmetic. Faces that share a vertex or an edge are neighbours, not a contact, so a fan or a bowtie does not count on its own.

When the answer is yes, the self-intersection curves say where the surface crosses itself.

In a larger pipeline

Each query answers a question about surfaces at one pose. Some collision questions need one more step, and each step is a trueform call.

• One mesh inside another. A mesh wholly inside another crosses none of its faces, so intersects returns false and distance returns the gap between the surfaces. Test one vertex of the inner mesh as well: a negative signed_distance, or a winding_number near 1, means inside.
• How much they overlap. When two meshes intersect, boolean_intersection returns the overlap as a closed solid, and volume measures it. The intersection curves give the rim of the overlap.
• Motion between poses. A thin part that moves fast can pass through a wall between two poses with both clear. Sample the motion so that no step moves the part farther than its thickness. Each sample costs a matrix assignment and a query, against trees built once.
• Many bodies. In a scene of many bodies, ask only the pairs whose bounding boxes overlap. Every body keeps its tree as it moves.

The first two, in Python:

# wholly inside: no faces cross, and one vertex of the part is inside the fixture
inside = not tf.intersects(fixture, part) and tf.signed_distance(fixture, vertex) < 0

# how much they overlap: the overlap as a closed solid, then its volume
if tf.intersects(fixture, part):
    (faces, points), _, _ = tf.boolean_intersection(fixture, part)
    overlap = tf.volume((faces, points))

Collision in code

Each example poses one mesh against another and asks the three questions.

#include <trueform/trueform.hpp>

tf::aabb_tree<int, float, 3> fixture_tree(fixture, tf::config_tree(4, 4));
tf::aabb_tree<int, float, 3> part_tree(part, tf::config_tree(4, 4));
auto fixture_form = fixture | tf::tag(fixture_tree);
auto posed = part | tf::tag(part_tree) | tf::tag(
    tf::make_transformation_from_translation(tf::make_vector(1.3f, 0.f, 0.f)));

bool hit = tf::intersects(fixture_form, posed);
float gap = tf::distance(fixture_form, posed);

std::vector<std::pair<int, int>> pairs;
tf::gather_ids(fixture_form, posed, tf::intersects_f, std::back_inserter(pairs));

import numpy as np
import trueform as tf

fixture = tf.Mesh(*tf.read_stl("fixture.stl"))
part = tf.Mesh(*tf.read_obj("part.obj"))

T = np.eye(4, dtype=np.float32)
T[:3, 3] = [1.3, 0.0, 0.0]
part.transformation = T                       # no rebuild

hit = tf.intersects(fixture, part)            # stops at the first hit
gap = tf.distance(fixture, part)
pairs = tf.gather_intersecting_ids(fixture, part)   # (M, 2) face pairs

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

const fixed = tf.readStl(readFileSync("fixture.stl"));
const moving = tf.readStl(readFileSync("part.stl"));
moving.transformation = tf.makeTranslation(1.3, 0, 0);

const hit = tf.intersects(fixed, moving);
const gap = tf.distance(fixed, moving);
const { elementId0, elementId1, point0, point1, distance2 } =
  tf.neighborSearch(fixed, moving);

In a motion loop, build the trees once and change only the transformation. The tutorials walk through each question with a box and a sphere you can check by hand.

Where to go next

Tutorials. C++, Python, JavaScript.

Points instead of a second mesh. When the query is a batch of points, a scan or a probe, the job is closest point on a mesh: deviation maps, registration and snapping.

The contact as geometry. Intersection curves in C++, Python and JavaScript. The overlap as a solid: mesh booleans.

Documentation. Intersection tests, distance, neighbor search and gathering ids, in C++, Python and TypeScript.

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

@article{polydera:mesh-collision-detection,
  title={Mesh collision detection},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/algorithms/mesh-collision-detection},
  organization={Polydera}
}