Approximate collision and inside-outside on the CPU, straight from the descriptor

Updated 2026-10-30 16:24; study: ~/code/data/meshes/fcp_2910_collision (sections/collision/README.txt).

Package v5.5 (commit 7ccd2a39, parts="tracked-fit", interp="poly"). 12 objects (household: mug, mug ace, bowl, bowl serving, bowl dog, flower pot, shoe, jogger; figurines: dino, horse; synthetic: spring, knot; 4.6k–77k faces; the household objects and figurines from Google Scanned Objects), encoded at 128, 256 and 512 layers (N 128, M 64, 2048 samples per ring, small islands and one-layer pieces kept where the package drops them, every atom, cut at 1e-8 of the energy) and queried without decoding: a point is inside when the rings at its nearest layer centre contain it (512 vertices per ring); two placed objects collide when a ring vertex of one lies inside the other. CPU: Intel(R) Core(TM) i5-10400F CPU @ 2.90GHz, FCP in numba with 12 threads and with 1. References on the same CPU: Embree (Open3D RaycastingScene occupancy, its own threads) for points, FCL (BVH, triangle-triangle, one call per pose through python-fcl, 1 thread) for collision. The error bound is the largest distance from the true surface at which an answer was still wrong: over 1M points within ±2 % of the diagonal of the surface plus 1M uniform points per object, and over 2000 poses near contact per pair (11 pairs; the true depth or gap of every pose from the meshes). Beyond it, every answer was right.

layers	size, MB median (max)	points: error bound, % diag	points: wrong, % (±2 % band)	points: FCP, ns/point (12 threads)	points: FCP, ns/point (1 thread)	points: Embree, ns/point	collision: deepest miss, % diag	collision: widest false hit, % diag	collision: correct, % of poses	collision: FCP, µs/pose (12 threads)	collision: FCP, µs/pose (1 thread)	collision: FCL, µs/pose
128	0.20 (0.55)	0.55	1.25	27.9	212	52.4	0.15	0.17	99.86	22.7	127	18.4
256	0.27 (0.99)	0.34	0.64	24.6	200	52.4	0.00	0.05	99.94	24.0	132	18.4
512	0.37 (1.76)	0.29	0.37	25.9	204	52.4	0.00	0.03	99.95	24.5	142	18.4

Points: FCP answers in 24.6–27.9 ns per point with 12 threads, 1.9× faster than Embree on the same CPU, at every layer count. The error bound is 0.29–0.55 % of the diagonal; its worst case comes from a handful of points at sharp details and pieces that start or end between two slices (below), and it falls with the layers; the share of wrong answers near the surface falls 1.25 → 0.37 %. Collision: no missed contact deeper than 0.15 % of the diagonal and no false one wider than 0.17 % at 128 layers (0.05 % from 256 layers); 99.86–99.95 % of poses correct. On the CPU, FCP is not faster than FCL at this sampling: 22.7–24.5 µs per pose with 12 threads and 127–142 µs with 1, against 18.4 µs for FCL on one thread; with every other sample FCP takes 6.2–7.0 µs (99.86–99.92 % correct, misses up to 0.62 %). FCP's collision speed-up is a GPU result (the poses in one batch).

Error bound (left axis, % of the diagonal) and CPU time (right axis, log) against
the number of layers, for inside-outside points (a) and collision (b), FCP against Embree and FCL. — Error bound (left axis) and CPU time (right axis, log) against the layers; times are geometric means over the 12 objects or 11 pairs, bounds the worst case.

Wrong inside-outside answers on the mug, the dino, the spring and the knot at 256 layers — Inside-outside (256 layers): every point answered wrongly farther than 0.1 % of the diagonal from the surface (of 2M per object), coloured by that distance. On the mug and the dino they sit where a piece starts or ends between two slices (the mug's cavity floor and handle joint, the dino's claws, toes and tail); on the spring they are spread along the coils, all within 0.2 % of the diagonal, where the slices cut the tube obliquely; the knot has none.

Three wrong collision answers at 256 layers, zoomed on the contact — Inside-outside (256 layers): every point answered wrongly farther than 0.1 % of the diagonal from the surface (of 2M per object), coloured by that distance. On the mug and the dino they sit where a piece starts or ends between two slices (the mug's cavity floor and handle joint, the dino's claws, toes and tail); on the spring they are spread along the coils, all within 0.2 % of the diagonal, where the slices cut the tube obliquely; the knot has none.