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

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.

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).

Solid properties straight from the descriptor

The 12 objects of the collision section; CPU: Intel(R) Core(TM) i5-10400F CPU @ 2.90GHz, one thread. Volume from the stored atoms in one contraction (no rings, no grid); convex hull from the rings (prototype, not in the package). Volume error against the source mesh's volume (volume rows), its convex hull's volume (hull rows), or the reference bound's volume (box and sphere rows; the sphere's from its radius; trimesh's minimum sphere is up to 0.4 % too large and slower, so the exact ball is the reference); the boxes and the sphere are taken from the vertices of the descriptor's hull (M = 64), and their FCP time includes that hull; the hull gap from 20k points on the true hull to the descriptor's hull. The 6144-atom runs from points ran at a load average of about 7: their times are upper bounds.

Convex hull straight from the descriptor

Package v5.31 (commit db3e6ceb; the working tree only raises MAX_ATOMS to 12288; defaults: parts="tracked-fit", interp="poly"), the 12 objects of the collision section, encoded at 128 layers (1024 or 6144 atoms) and at 256 layers (6144 atoms). The hull is built from the descriptor without a decode grid, a mesh or qhull: the solid rings are evaluated from the Fourier and Chebyshev coefficients (holes are inside the solid and never touch the hull), each part's end rings are held to the part's outer edges, and per level (a layer centre or a part edge) one numba kernel takes the 2D hull of the ring samples and its support point in M directions. In each direction a hull vertex must lie on the upper concave envelope of (height, support) over the levels; neighbouring directions' envelopes are joined by height and the end levels capped, which gives a closed triangle surface in O(levels × M). Reference: scipy's qhull on the source mesh's vertices, and the route through the decoded mesh (fcp.decode, then qhull). CPU: Intel(R) Core(TM) i5-10400F CPU @ 2.90GHz, one thread for both (median of 21 runs; the decode route of 7). Distances in % of the source mesh's diagonal, from 20k points on the source mesh's hull to the descriptor's hull; volume relative to the source mesh's hull.

Time: at 128 layers and M = 64 the descriptor's hull takes 2.3–13.9 ms, against 2.1–16.3 ms for qhull on these meshes (2.3k–38k vertices): about even, faster on 7 of 12 (mug, bowl, bowl serving, shoe, jogger, spring, knot), at most 2.36×. The gain is in not having the mesh: the decode route is 69–195 ms, 13–66× slower. qhull's cost grows with the hull it outputs, and the descriptor's hull has more vertices than the mesh's (the rings are dense where the mesh is coarse), so a large source mesh is where the descriptor wins outright (a 222k-vertex dress outside this set: 3.5 ms against 39 ms); the knot and spring, with many parts per level, are the slowest descriptor hulls. M = 128 and 256 layers cost 1.5× and 2.0× the time (medians). Accuracy: the volume is 0.962–0.998 of the true hull at 128 layers, the mean gap 0.05–0.29 % of the diagonal, the largest 1.21 % (mug). Nearly all of it is the encoding, not the hull: the decoded mesh's hull (qhull) is as far from the true hull (mean 0.02–0.25 %, max up to 1.15 %), and the descriptor's hull is within a mean 0.02–0.07 % of it (max 0.18–0.72 %, the spring and knot at the top: 64 directions are too few there; M = 128 lowers their max gap, knot 0.58 → 0.15 %, spring 0.74 → 0.33 % (decoded mesh's hull: 0.09, 0.24 %)). A flat top or bottom also moves: a part ends at a layer edge, so a cap sits up to half a layer from the true one (the mug's top: 0.19 % of the diagonal). 256 layers lower the gap only where the layers were the limit (horse, mug ace, spring); elsewhere it is the rings' own error. Defects: the surface is convex only up to the M directions (dents up to 0.71 % of the diagonal at M = 64, on the spring); and where one pair of support points lies on the envelopes of two non-neighbouring directions, the bands on both sides use that edge: no open edge on any of the 48 hulls, but 0–11 edges shared by four triangles (a fold, not a hole; the volume is unaffected). A final qhull over the descriptor hull's own vertices would remove both (1–6 ms on 500–2400 such vertices in the first trials), giving up most of the gain. Prototype, not in the package.

Volume straight from the descriptor

Package v5.31 (commit db3e6ceb; the working tree only raises MAX_ATOMS), defaults (parts="tracked-fit", interp="poly", the gwn point slicer), 128 layers, 2048 atoms; the 12 objects of the collision section. The exact volume is the source mesh's (tetrahedra over its faces). From each mesh, 20k area-uniform surface points (seed 3) with the true normals; every point method gets the same points. FCP's volume is one contraction of the stored atoms: a ring's area is π Σ_k k (a_x,kb_y,k − b_x,ka_y,k) in its Fourier coefficients, and the height atoms are orthonormal on a part's layer centres, so the sum of the ring areas over the layers is the same expression in the atom vectors: V = dz · ∏scale · π Σ_parts sign · |Σ_k k (⟨a_x,k, b_y,k⟩ − ⟨b_x,k, a_y,k⟩)| (the midpoint rule over the layers; no ring is evaluated, no grid, no mesh; one numba loop). Standard route from points: screened Poisson reconstruction (Open3D 0.20, depth 8), then its mesh's volume, with the true normals (the best case) and with normals estimated from the points (what a scan gives). CPU: Intel i5-10400F; FCP's encode on numba's 12 threads and on a GTX 1650; Poisson on one thread (its threaded run was slower here). Times are medians over the objects.

Accuracy: FCP is within 0.74 % of the exact volume from the mesh (median 0.31 %) and within 1.76 % from the points (median 0.25 %), without normals; Poisson with the true normals is as close (median 0.22 %, max 0.90 %). With estimated normals Poisson is off by more than 5 % on 10 of 12 objects (bowl +152 %, bowl serving +145 %, mug +141 %, bowl dog +125 %, flower pot +109 %, mug ace +85 %, shoe +58 %, jogger +19 %, dino +6 %, spring -20 %): on the thin-walled ones the orientation flips across a wall and the surface closes over the opening (renders). More atoms, more layers: 6144 atoms at 128 layers and at 256 layers move the error little: from the mesh the median falls 0.31 → 0.17 → 0.13 % but the worst stays 0.71 %; from the points it is 0.25 / 0.28 / 0.24 %. The per-object errors keep their sign and size across the settings (mugs and bowls 0.2–0.7 % low, the spring from points 1.8 % high): a bias of the encoding and of the point slicer, not a shortage of atoms. The 6144-atom runs had other jobs on the machine (load average about 7, against about 0 for the 2048 run): their times in the first table are upper bounds. Time: once encoded, FCP's volume takes 20–57 µs, about the cost of the tetrahedron sum over the source mesh itself (27–235 µs, numba): faster on 9 of 12 objects, the gain growing with the mesh (spring, 77k faces: 5.1×); the volume of a Poisson mesh takes 3.3–12.7 ms (NumPy). The cost from points is the encode: 2.8 s on the CPU and 1.0 s on CUDA (median), against 1.5 s for Poisson on one thread; the descriptor, once made, also answers the other queries of this report. Caveats: clean, complete, uniformly sampled points; Poisson's meshes are not watertight by Open3D's strict test (the volume is taken as is, its sign ignored); learned reconstruction is not compared.