Bounding volumes straight from the descriptor
Updated 2026-10-30 17:25; study: ~/code/data/meshes/fcp_3010_hull (sections/hull/README.txt).
Package v5.31 (commit db3e6ceb), mesh encodes, the 12 objects of the collision section. The axis-aligned box (AABB), an oriented box (OBB) and the smallest enclosing sphere come from points that can be vertices of the descriptor's convex hull, found without a grid, a mesh or a hull surface: each ring's Fourier coefficients straight from its part's atoms (the part's height basis times its atoms; each part's end rings held to its edges), then one numba kernel, the rings in parallel: a ring's 128 samples, its 2D hull and its support point in 64 directions; per direction the rings on the upper envelope of (height, support) are kept (0.4k–4.8k points at 128 layers). The AABB is their minimum and maximum; the OBB is the smallest of six boxes that keep one axis of the world frame or of the descriptor's own frame and turn the other two to the minimum-area rectangle of the projected hull (rotating calipers, the six in parallel); the sphere is the exact smallest ball of the points (randomized incremental). References from the source mesh: its vertex AABB; for the OBB the smaller of trimesh's minimum-volume box and Open3D's minimal box (each is smaller than the other on some objects: Open3D's by up to 2.9 % on the shoe); the exact smallest ball (qhull, then the same ball algorithm). "Outside" is the farthest source-mesh vertex outside FCP's bound, in % of the diagonal. Times: CPU i5-10400F (numba on 12 threads for FCP; the references as the libraries run), medians over the objects; FCP's times are from an idle machine (load average 0.3), the accuracy columns from a later run of the same code.
| layers | atoms | AABB volume / mesh's | AABB: outside, max % | OBB volume / smallest reference OBB | OBB: outside, max % | sphere radius / exact | sphere: outside, max % | AABB + sphere, ms | all three, ms (range) |
|---|---|---|---|---|---|---|---|---|---|
| 128 | 2048 | 0.978–1.019 | 0.52 | 0.977–1.036 | 0.50 | 0.999–1.007 | 0.15 | 0.98 | 1.41 (0.91–4.10) |
| 128 | 6144 | 0.979–1.018 | 0.52 | 0.977–1.035 | 0.50 | 0.999–1.007 | 0.12 | 1.00 | 1.48 (0.92–3.90) |
| 256 | 6144 | 0.977–1.015 | 0.53 | 0.977–1.039 | 0.47 | 0.994–1.003 | 0.34 | 1.78 | 2.44 (1.40–7.30) |
Against the standard routes (128 layers, 2048 atoms; the standard routes work on the source mesh's vertices, 2.3k–38k; ms, median and range over the 12 objects):
| bound | method | time, ms | size |
|---|---|---|---|
| AABB | FCP (with the sphere; the pass is shared) | 0.98 (0.66–3.33) | 0.978–1.019 of the mesh's, approximate |
Open3D AxisAlignedBoundingBox, mesh vertices | 0.01 (0.01–0.08) | exact | |
| NumPy min / max, mesh vertices | 0.34 (0.11–1.84) | exact | |
| OBB | FCP (all three bounds) | 1.41 (0.91–4.10) | 0.977–1.036 of the smallest reference |
trimesh oriented_bounds (minimum volume) | 79.71 (20.41–150.91) | 1.000–1.030 | |
Open3D create_from_points_minimal | 339.02 (29.05–3844.13) | 1.000–1.001 | |
Open3D create_from_points (principal axes) | 3.53 (1.69–16.99) | 1.000–1.498 (median 1.183) | |
| sphere | FCP (with the AABB) | 0.98 (0.66–3.33) | radius 0.999–1.007 of the exact |
| exact: qhull, then the smallest ball of its vertices | 3.94 (2.13–18.17) | 1 (the reference) | |
trimesh minimum_nsphere | 19.34 (3.38–959.53) | 1.0000–1.0040 (larger than exact by over 1e-5 on 4 objects) |
Verdict (128 layers, 2048 atoms; speed against the fastest standard route giving the same kind of bound, per object; accuracy given up against the reference):
| bound | FCP speed vs the best standard route | size vs the reference | farthest source vertex outside FCP's bound | use FCP? |
|---|---|---|---|---|
| AABB | 29–201× slower (Open3D, 0.015 ms) | -2.2 to +1.9 % volume | up to 0.52 % of the diagonal (median 0.11 %) | no, when the mesh or the points are at hand: theirs is exact and faster |
| OBB | 18–86× faster (median 52×) than the faster minimal box; 1.5–4.3× than Open3D's principal-axes box | -2.3 to +3.6 % volume (principal-axes box: up to +50 %) | up to 0.50 % (median 0.14 %) | yes: a near-minimal box, faster than a principal-axes box |
| sphere | 2.2–6.7× faster (median 3.8×) than the exact route | -0.06 to +0.7 % radius | up to 0.15 % (median 0.02 %) | yes, if a radius within 1 % will do |
| all three | 20–89× faster (median 55×): 1.4 ms against 83 ms | as above | up to 0.52 % | yes |
The accuracy given up: 2.2 % in the AABB's volume, 3.6 % in the OBB's, 0.7 % in the sphere's radius (worst objects). Most of it is the encoding's own error (on the source mesh the same ball algorithm gives the exact ball); the OBB adds its search over six frames: on the shoe its box is 3.6 % larger than Open3D's minimal box, which there is 2.9 % smaller than trimesh's. None of the descriptor's bounds encloses the object for certain; inflate them by about 0.5 % of the diagonal where enclosure must hold. The standard routes run as well on a point cloud's points: the descriptor's advantage is where the descriptor is what one holds (stored, sent, or encoded for its other queries), and where a near-minimal OBB is wanted quickly.
