FCP: what the experiments show
FCP stores a shape as signed parts of rings stacked along one axis: each ring by its Fourier coefficients, the heights by Chebyshev polynomials, all of it as atoms sorted by energy, so any prefix of the atoms is a coarser copy of the same shape. This page collects what the studies found about using that descriptor directly, without decoding it to a mesh. Each row links to the page with the method, the per-object tables and the figures.
Queries straight from the descriptor, at a glance
12 objects (8 household from Google Scanned Objects, the dino and horse figurines, a spring and a knot), 128 layers unless noted, one Intel i5-10400F CPU; ray casting: four objects, also a GTX 1650. Times are medians over the objects; distances in % of the object's diagonal. Thread counts differ between rows, and the standard methods run as their libraries do; the table below puts the solid queries on one thread each.
| query | FCP | standard method on the mesh | accuracy | verdict | details |
|---|---|---|---|---|---|
| inside-outside point test | 25–28 ns per point (12 threads) | Embree occupancy: 52 ns | wrong answers only within 0.29–0.55 % of the surface (128–512 layers) | 1.9× faster | collision |
| collision of two placed objects | 23–24 µs per pose (12 threads) | FCL: 18 µs (1 thread) | 99.86–99.95 % of poses right; no missed contact deeper than 0.15 % | slower on the CPU; the speed-up is a GPU result (poses in one batch) | collision |
| ray casting (provisional) | staircase, GPU: 5–19 ns per ray in a view; exact, GPU: 0.33–0.86 µs | Embree: 7–13 ns (needs a decoded mesh); Warp GPU BVH: 3–7 ns | exact: 0 missed or late hits, CPU and GPU; staircase: up to half a layer off on sloped walls | staircase on par per ray; exact 26–108× slower than Embree; both save the 120–340 ms decode | ray casting |
| volume | 0.03–0.05 ms (1 thread; one contraction of the atoms) | exact tetrahedron sum: 0.04–0.05 ms | median error 0.13–0.47 %, worst 0.88 % (0.17 % and 0.74 % at 6144 atoms); from 20k points without normals: median 0.24–0.28 %, worst 1.9 % | as fast as the exact mesh volume; from points as close as Poisson with true normals | volume |
| convex hull | 4.0 ms (1 thread; 64 directions, earlier method) | qhull: 4.0 ms; decode, then qhull: 107 ms | hull volume −1.0 % median (worst −3.8 %); mean surface gap 0.13 % | even with qhull on the mesh; 27× faster than through a decode | hull |
| oriented bounding box | 1.4 ms (12 threads; all three bounds) | minimal box (trimesh): 80 ms; Open3D principal-axes box: 3.5 ms, up to +50 % volume | volume −2.3 to +3.6 %; up to 0.50 % of the diagonal outside | 18–86× faster (median 52×): a near-minimal box, faster than a principal-axes box | bounds |
| smallest enclosing sphere | 1.0 ms (12 threads) | exact smallest ball (qhull + min ball): 3.9 ms | radius −0.06 to +0.7 %; up to 0.15 % of the diagonal outside | 2.2–6.7× faster (median 3.8×), if a radius within 1 % will do | bounds |
| axis-aligned bounding box | 1.0 ms (12 threads) | Open3D on the mesh vertices: 0.015 ms, exact | volume −2.2 to +1.9 %; up to 0.52 % of the diagonal outside | 29–201× slower: use the exact box when the mesh or the points are at hand | bounds |
The solid queries on one thread
A fair comparison: one thread for every method, 12 objects, encoding not counted. Each query uses its own balanced setting (the fastest within 1 % median error and a bounded worst case), so these are not all one descriptor. Encoding once takes 55 ms at 1k vertices and 2.5 s at 1M (128 layers, 2048 atoms).
| query | against the exact standard route | size error, median (worst object) | worst case, % of the diagonal | details |
|---|---|---|---|---|
| convex hull | 2.0× faster than qhull | 0.91 % (3.7 %) | 1.25 largest gap to the true hull | tradeoffs |
| volume | 2.0× faster than the tetrahedron sum | 0.32 % (0.8 %) | – | tradeoffs |
| oriented bounding box | 22× faster than the faster minimal box | 1.00 % (3.5 %) | 0.50 farthest vertex outside | tradeoffs |
| smallest enclosing sphere | 3.2× faster than the exact ball | 0.40 % (1.0 %) | 0.20 farthest vertex outside | tradeoffs |
| axis-aligned bounding box | 81× slower than Open3D | 0.75 % (2.4 %) | 0.74 farthest vertex outside | tradeoffs |
What holds across the studies
- No query needs a decode. Every answer above comes from the atoms or the rings; the routes through a decoded mesh take 70–2000 ms per object, one to four orders of magnitude more.
- The error is the encoding's, not the query's. The descriptor's hull is within a mean 0.02–0.07 % of the decoded mesh's own hull; the volume from the atoms equals the layer sum of the ring areas; what remains is how well the rings fit the surface.
- Errors sit at the slicing. Wrong inside-outside answers cluster where a piece starts or ends between two slices (claws, toes, a mug's cavity floor and handle joint) or where the slices cut a tube obliquely (the spring's coils, all within 0.2 %; the knot has none beyond 0.1 %); more layers shrink that band (wrong answers near the surface 1.25 → 0.37 % from 128 to 512 layers) but cost encode time and, for the hull and the bounds, query time.
- Query time does not grow with the mesh. FCP's cost is set by its layers and atoms, while the standard routes grow with the vertices. On one thread at the default setting, FCP overtakes the tetrahedron sum from 4.8k vertices, the exact sphere from 5.2k and qhull from 6.9k, and it beats the minimal box at every size (tradeoffs).
- Bounds are close, not guaranteed. At the bounds page's settings no mesh vertex lies more than 0.53 % of the diagonal outside the boxes or the sphere; lighter settings give up more (0.74 % at the balanced axis-aligned box, up to 3.9 % at the fastest oriented box). A conservative use needs that margin added.
- Error falls with the atoms above about 64 atoms. On all 12 objects, from 64 atoms up every step lowers the error, in both versions tested. Below that it can rise (up to +30 %), and the new centre order moves those rises rather than removing them: better on some objects, worse on others. With every atom the new version is better on 10 objects and equal on 2 (monotonicity).
- Atoms barely matter for solid properties. Volume, hull and bounds change little from 2048 to 6144 atoms at 128 layers (the volume's worst case stays at 0.74 % from the mesh).
Caveats
- CPU timings only, except ray casting; the other GPU numbers are still to come.
- Ray casting is work in progress on four objects: a bench prototype whose numbers will change.
- The convex hull and the bounds are a prototype outside the package; the volume from the atoms is a study script.
- Package versions differ: collision and inside-outside on v5.5 (7ccd2a39), solid properties on v5.31 (db3e6ceb).
- Point clouds are clean, complete and uniformly sampled (20k points); scan noise and holes are not tested here.
Pages
Point tests against Embree and pose tests against FCL at 128–512 layers; where the wrong answers sit.
The slab tracer's exact and staircase modes on CPU and GPU, against Embree and a GPU BVH.
One table: volume, convex hull, oriented and axis-aligned boxes, smallest sphere, each against the standard method on the mesh.
How the hull is built from the rings, per-object accuracy and timing, and its defects.
Volume from the atoms, from meshes and from point clouds, against the exact volume and Poisson reconstruction.
Speed against accuracy for 549 settings across five queries, one thread for every method, and how each scales with mesh size.
Error at each prefix on the 12 objects, v5.5 against the new version, log-log.
Axis-aligned box, oriented box and smallest sphere from the descriptor's hull, against the mesh's, with renders of both.