Each geometric query from the descriptor against the standard route from the mesh, on the CPU with one thread for
every method (numba, OpenMP and BLAS pinned to one thread; Intel(R) Core(TM) i5-10400F CPU @ 2.90GHz). Twelve objects (the collision section's), encoded
from their meshes at 64, 128 and 256 layers and 512, 2048 and 6144 atoms (package v5.31, commit db3e6ceb); for the hull and
the bounds also 16, 32, 64 and 128 directions M and 64, 128 and 256 samples per ring, and for the OBB the descriptor's own
frame or its own and the world's: 549 configurations over the five tasks, every one on every object. Exact references from the mesh:
the convex hull's volume (qhull), the mesh's volume, its AABB, the smaller of trimesh's and Open3D's minimal boxes, the exact
smallest ball. Encoding is not in these times (its own table below). Times are medians after a warm-up, taken while
the load average was logged; objects first timed under another job's load (above 3) were timed again
on a quiet machine (load average at most 2.6 for the times shown).
Every FCP configuration (colour: layers; marker: atoms) at its time relative to the baseline (x, geometric mean
over the 12 objects, log scale) and its size relative to exact (y, median over the objects: volume for the hull, the volume
and the boxes, radius for the sphere). The exact baseline is the star at (1, 1); crosses are standard routes that are not
exact (NumPy's AABB, Open3D's principal-axes box, trimesh's sphere, Poisson reconstruction from 20k points with true
normals; with estimated normals Poisson's volume is off the scale, median 1.72). The dotted line is the Pareto front in
time and error; the circled configurations are in the tables: accurate (the least median error), balanced
(the fastest within 1 % median error whose worst case stays within 1 % of the diagonal: the farthest vertex outside a
bound; for the hull its largest gap to the true hull, within 2 %, since no setting reaches 1 %; for the volume the
worst object's error, within 1 %), fast (the fastest
within 5 % median error, with no limit on the worst case).
convex hull
configuration
time, ms (median)
time / baseline (geometric mean)
hull volume / exact, median (range)
error, median / worst
largest gap to the true hull, worst, % diagonal
baseline: qhull (scipy) on the mesh vertices
–
3.571
1
exact
–
0
FCP fast
64 layers, 512 atoms, M = 16, 64 samples
0.692
0.220 (4.5× faster)
0.9521 (0.854–0.988)
4.79 % / 14.63 %
5.17 %
FCP balanced
128 layers, 2048 atoms, M = 128, 64 samples
1.561
0.490 (2.0× faster)
0.9909 (0.963–1.001)
0.91 % / 3.68 %
1.25 %
FCP accurate
256 layers, 512 atoms, M = 128, 256 samples
8.149
2.703 (2.7× slower)
0.9977 (0.967–1.005)
0.36 % / 3.32 %
1.40 %
volume
configuration
time, ms (median)
time / baseline (geometric mean)
volume / exact, median (range)
error, median / worst
baseline: tetrahedron sum over the mesh (numba)
–
0.043
1
exact
–
FCP fast
64 layers, 512 atoms
0.019
0.438 (2.3× faster)
0.9955 (0.962–1.001)
0.45 % / 3.82 %
FCP balanced
64 layers, 2048 atoms
0.021
0.508 (2.0× faster)
0.9973 (0.992–1.003)
0.32 % / 0.78 %
FCP accurate
256 layers, 6144 atoms
0.037
0.822 (1.2× faster)
0.9987 (0.993–1.000)
0.13 % / 0.71 %
AABB
configuration
time, ms (median)
time / baseline (geometric mean)
box volume / exact, median (range)
error, median / worst
farthest vertex outside, worst, % diagonal
baseline: Open3D on the mesh vertices
–
0.015
1
exact
–
0
FCP fast
64 layers, 512 atoms, M = 16, 64 samples
0.557
43.411 (43.4× slower)
0.9918 (0.920–1.063)
2.04 % / 8.05 %
2.96 %
FCP balanced
128 layers, 2048 atoms, M = 16, 64 samples
1.016
81.283 (81.3× slower)
0.9985 (0.976–1.013)
0.75 % / 2.36 %
0.74 %
FCP accurate
128 layers, 2048 atoms, M = 64, 256 samples
3.600
285.777 (285.8× slower)
1.0011 (0.979–1.020)
0.50 % / 2.13 %
0.51 %
OBB
configuration
time, ms (median)
time / baseline (geometric mean)
box volume / exact, median (range)
error, median / worst
farthest vertex outside, worst, % diagonal
baseline: the faster of trimesh's oriented_bounds and Open3D's minimal box
–
76.281
1
exact
–
0
FCP fast
64 layers, 512 atoms, M = 16, 64 samples, frames: own
0.667
0.012 (81.5× faster)
1.0196 (0.918–1.093)
3.78 % / 9.35 %
3.90 %
FCP balanced
128 layers, 2048 atoms, M = 32, 128 samples, frames: both
2.372
0.045 (22.2× faster)
1.0059 (0.977–1.035)
1.00 % / 3.51 %
0.50 %
FCP accurate
256 layers, 6144 atoms, M = 32, 128 samples, frames: both
4.491
0.086 (11.6× faster)
1.0037 (0.977–1.037)
0.95 % / 3.73 %
0.47 %
OBB cases. Much faster, losing accuracy: fast is 81× faster than the minimal box at 3.8 % median volume and up to 3.9 % of the diagonal outside (64 layers are too coarse for bounds). Nearly as accurate and still faster: accurate is 12× faster at 0.95 % median volume, 0.47 % outside. Against the quick standard route: Open3D's principal-axes box is 16× faster than the minimal box but 18 % too large at the median; balanced is faster still (22×) and within 1.0 %.
smallest sphere
configuration
time, ms (median)
time / baseline (geometric mean)
radius / exact, median (range)
error, median / worst
farthest vertex outside, worst, % diagonal
baseline: qhull, then the exact smallest ball of its vertices
–
3.890
1
exact
–
0
FCP fast
64 layers, 512 atoms, M = 16, 64 samples
0.620
0.168 (6.0× faster)
1.0037 (0.996–1.016)
0.43 % / 1.61 %
2.54 %
FCP balanced
128 layers, 512 atoms, M = 16, 64 samples
1.111
0.314 (3.2× faster)
1.0040 (0.999–1.010)
0.40 % / 1.04 %
0.20 %
FCP accurate
256 layers, 2048 atoms, M = 32, 64 samples
2.042
0.611 (1.6× faster)
1.0005 (0.994–1.003)
0.09 % / 0.61 %
0.40 %
Mesh size. The standard routes' cost grows with the mesh; the descriptor's does not (its size is set by the
layers and atoms). Four objects (mug, dino, horse, knot) resampled to 1k–1M vertices (quadric decimation, Loop
subdivision); per size the exact references are recomputed. FCP at three settings: fast (64 layers, 512 atoms, M = 16,
64 samples), default (128, 2048, 64, 128) and accurate (256, 6144, 128, 256).
Top: time against the mesh's vertices (median over the four objects, log-log), the standard route in black and
FCP's three settings flat (encoding excluded). Bottom: FCP's size relative to exact at each mesh size. The OBB's baseline
here is trimesh's minimum-volume box alone (Open3D's minimal box took 29 ms to 3.8 s on the 12 objects, 3.8 s on the
14k-vertex knot, too slow for the sweep); trimesh's is not always minimal, so FCP's box can come out slightly smaller.
FCP faster from
fast
default
accurate
convex hull
1.7k
6.9k
26.7k
volume
3.6k
4.8k
6.8k
OBB
always faster
always faster
always faster
smallest sphere
1.1k
5.2k
21.4k
Encoding (one thread, from the mesh; median over the four objects; once per object, then every query above):
layers
atoms
1k vertices
3k vertices
10k vertices
30k vertices
100k vertices
300k vertices
1M vertices
64
512
29 ms
34 ms
55 ms
102 ms
272 ms
736 ms
2.40 s
128
2048
55 ms
63 ms
83 ms
138 ms
323 ms
819 ms
2.50 s
256
6144
115 ms
128 ms
153 ms
221 ms
440 ms
996 ms
2.80 s
Verdict at the balanced setting of each task (12 objects, one thread):
