Convex hull straight from the descriptor

Updated 2026-10-30 04:58; study: ~/code/data/meshes/fcp_3010_hull (sections/hull/README.txt).

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.