Fast and Robust Mesh Collision Detection in C++

Collision detection asks three questions about two meshes. Do they touch? If not, how far apart are they? If they do, which faces touch? trueform answers all three on triangle meshes, with each mesh in its own pose. It is header-only C++17. This tutorial covers the test, the clearance, the contact faces, and moving a mesh without rebuilding anything.

Install

Header-only. It needs C++17 and oneTBB. Add it to your project via CMake FetchContent:

FetchContent_Declare(
  trueform
  GIT_REPOSITORY https://github.com/polydera/trueform
)
FetchContent_MakeAvailable(trueform)
target_link_libraries(my_app PRIVATE tf::trueform)

Also available via conan, nuget, and pip. See the installation guide for all options.

Loading the meshes

#include <trueform/trueform.hpp>

auto fixture_buffer = tf::read_stl("fixture.stl");
auto part_buffer = tf::read_obj<3>("part.obj");

tf::read_stl and tf::read_obj<3> return a tf::polygons_buffer that owns the data. .polygons() is a view on it. If your faces and points already live in your own arrays, wrap them with tf::make_polygons(tf::make_faces<3>(faces), tf::make_points<3>(points)). No copy is made.

To follow along without files, use a subdivided box as the static mesh and a small sphere as the moving one:

auto static_buffer = tf::make_box_mesh(2.f, 2.f, 2.f, 10, 10, 10);
auto moving_buffer = tf::make_sphere_mesh(0.5f, 30, 30);
auto fixture = static_buffer.polygons();
auto part = moving_buffer.polygons();

The box spans −1 to 1 on each axis. The sphere has radius 0.5.

Building the spatial trees

Every query runs on a spatial tree per mesh. Build each one once and tag it onto its mesh:

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 part_form = part | tf::tag(part_tree);

(4, 4) is four children per node and up to four faces per leaf. The docs recommend it for all workloads. For distance queries between two meshes, an obb_tree or obbrss_tree gives tighter culling. The calls below stay the same.

Moving a mesh

Tag a transformation onto a form. Every query applies it on the fly. The points are not rewritten and the tree stays valid.

auto at = [](float x, float y, float z) {
  return tf::make_transformation_from_translation(tf::make_vector(x, y, z));
};

auto moved = part_form | tf::tag(at(3.f, 0.f, 0.f));

For a rotation, compose it with the translation. tf::transformed(R, T) applies R first, then T:

auto R = tf::make_rotation(tf::deg(30.f), tf::axis<2>);
auto posed = part_form | tf::tag(tf::transformed(R, at(3.f, 0.f, 0.f)));

Do the meshes collide?

tf::intersects returns a bool:

tf::intersects(fixture_form, part_form | tf::tag(at(3.f, 0.f, 0.f)));   // false
tf::intersects(fixture_form, part_form | tf::tag(at(1.3f, 0.f, 0.f)));  // true

Touching counts. With the sphere at x = 1.5, its surface just meets the box face at x = 1, and the answer is true.

The test is on surfaces. A sphere entirely inside the box does not cross any box face, so tf::intersects(fixture_form, part_form) returns false. To catch containment, test one vertex of the moving mesh against the closed mesh with tf::winding_number (see the Spatial docs).

How far apart are they?

For clearance, use tf::distance. It returns 0 when the meshes touch.

auto near = part_form | tf::tag(at(1.55f, 0.f, 0.f));

float gap = tf::distance(fixture_form, near);     // 0.05
float gap2 = tf::distance2(fixture_form, near);   // 0.0025, squared

To get the closest pair itself, call tf::neighbor_search with two forms:

auto [ids, metric_point_pair] = tf::neighbor_search(fixture_form, near);
auto [face0, face1] = ids;                    // closest face on each mesh
auto [dist2, pt0, pt1] = metric_point_pair;   // squared distance, world points

Pass a radius to only look that far. The result converts to bool and is false when nothing is in range. A tight radius also prunes the search:

if (auto within = tf::neighbor_search(fixture_form, near, 0.1f)) {
  auto [ids, mpp] = within;
}

A mesh against a primitive works the same way. A common case is a capsule: a segment with a radius, as a stand-in for a tool or a robot link.

auto axis = tf::make_segment_between_points(tf::make_point(1.3f, -0.5f, 0.f),
                                            tf::make_point(1.3f, 0.5f, 0.f));
float radius = 0.2f;

auto [face_id, metric_point] = tf::neighbor_search(fixture_form, axis);
float clearance = std::sqrt(metric_point.metric) - radius;   // 0.1

// closest points between the axis and that face
auto [d2, on_axis, on_face] =
    tf::closest_metric_point_pair(axis, fixture[face_id]);

Which faces touch?

tf::gather_ids with two forms collects every pair of intersecting faces:

auto touching = part_form | tf::tag(at(1.3f, 0.f, 0.f));

std::vector<std::pair<int, int>> pairs;
tf::gather_ids(fixture_form, touching, tf::intersects_f,
               std::back_inserter(pairs));
// pairs.size() == 120

The first id indexes a face of the first mesh, the second a face of the second. Use them to color the contact, to transfer attributes, or to restrict a finer check.

For near misses, give tf::gather_ids your own test. The first one prunes tree nodes, the second checks faces:

float d = 0.1f;
auto within_d = [d2 = d * d](const auto &a, const auto &b) {
  return tf::distance2(a, b) <= d2;
};

std::vector<std::pair<int, int>> close;
tf::gather_ids(fixture_form, near, within_d, within_d,
               std::back_inserter(close));
// close.size() == 430

Working with results

In a motion loop, the trees are built once and only the transformation changes:

for (int i = 0; i <= 6; ++i) {
  auto step = part_form | tf::tag(at(3.f - 0.5f * i, 0.f, 0.f));
  bool hit = tf::intersects(fixture_form, step);
  float gap = tf::distance(fixture_form, step);
}

To test many copies of one part in different poses, tag one transformation per copy onto the same form. They share the data and the tree.

When you need the contact as geometry, not just face pairs, compute the intersection curves:

auto curves = tf::make_intersection_curves(
    fixture, part | tf::tag(at(1.3f, 0.f, 0.f)));

Related tutorials

• Fast and Robust Closest Point on a Mesh in C++ — nearest surface point for a batch of queries.
• Fast and Exact Mesh Intersection Curves in C++ — exact curves where two or more meshes cross.
• Fast Mesh Booleans in C++ — exact union, intersection and difference of two meshes.
• Fast Variadic Mesh Booleans in C++ — one arrangement, many boolean expressions over N meshes.

Performance

Apple M4 Max 16 threads

The closest pair between two meshes of 1,025,766 polygons takes under 1 ms, against 370 ms for FCL. Building the spatial tree is the up-front cost of every query on this page:

A tagged transformation does not rebuild the tree, so a moving mesh pays this cost once.

Full benchmarks · Documentation

@article{polydera:fast-mesh-collision-detection-in-cpp,
  title={Fast and Robust Mesh Collision Detection in C++},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/tutorials/fast-mesh-collision-detection-in-cpp},
  organization={Polydera}
}