Question. Can the descriptor answer "is this point inside?" and "do these two placed objects
collide?" directly, without decoding to a mesh, faster than the standard and state-of-the-art mesh methods (BVH ray
casting, BVH winding numbers, BVH triangle-triangle tests), and how accurately? Eleven watertight objects: six everyday
ones (mug, bowl, dino, horse, shoe, dress: 8k–444k faces) and five concave, interleaved or perforated ones (a pan with
334 holes, a trefoil knot, a coil spring, a Menger sponge, a 24-tooth gear). v2 of the study: one encoder setting for
every object, chosen by a sweep (section 1); the dog and the elephant of
v1 are left out.
The setting. 1024 layers, N 128 harmonics, height degree up to 64, 2048 arc-length samples per
ring, every island kept (the package drops tracks below 0.2 % of the largest slice's area), encoded with every atom and
cut to all but 1e-8 of the energy (at most 5 MB): 0.08–2.2 MB per object, 25–40 s and at most 1.9 GB to encode.
Package v5.4, parts="tracked-fit" (with decision 29's cut fix); the study patches three encoder constants
in-process and replaces the selection's padded array (lowmem.py); nothing in the package is changed.
How FCP answers (scripts/fcpq.py). The rings at the layer centres are evaluated once
from the stored polynomials (512 vertices each; the ring tables take 0.1–0.3 s per object). A point is inside when the
signed count of the parts whose ring at the nearest layer centre contains it is positive (hole parts count −1):
one even-odd crossing test per part present at that height, on the edges of the point's y-bin only. The height is read
to half a layer (0.05 % of the diagonal or less). Collision: the ring vertices of each object (strided) are mapped into
the other's canonical frame and tested; a pose collides when any is inside. All poses in one CUDA launch (or a numba
prange). CPU and GPU give the same answers.
Findings.
- Points: FCP on CUDA takes 3.3 ns/pt uniform and 9.4 ns/pt near the surface (1M points, everyday
objects, geometric means): 8.7× and 5.7× faster than Open3D/Embree, the fastest mesh method (29 / 53 ns), 24–77×
faster than Warp's GPU BVH winding number and 74× faster than libigl. Complex shapes: 4.9 / 9.8 ns, 6.6× and 4.7× faster
than Embree. On the CPU, FCP is 1.4–2× faster than Embree.
- Point accuracy: of 1M points within ±2 % of the diagonal of the surface, at most 28 (the pan) are
wrong farther than 0.1 % of the diagonal from it, on every object but the gear (547: its sharp teeth); one point (the
pan) farther than 0.3 %, none farther than 0.4 %. Mug, bowl, knot, spring and sponge: 0. All wrong answers together are
0.14–0.66 % of the near-surface points, nearly all within 0.1 % of the diagonal of the surface; 0.01–0.18 % of uniform
points (section 1, NT 512, the nearest rule).
- Collision: FCP on CUDA takes 6.9 µs/pose at 99.96 % agreement with the exact mesh test (FCL, Coal):
2.2× faster than FCL, 2.5× faster than Coal, 4.8× faster than Warp's GPU triangle test. Sparser samplings: 2.9 µs
at 99.89 % (5.4× FCL), 1.8 µs at 99.71 % (8.5×). Complex pairs: 7.1 µs at 99.91 % (2.9× FCL). No false hit in any run;
the 15 missed collisions of the finest sampling (of 22 000 poses) are grazing contacts: 11 less than 0.005 % of the
diagonal deep, two below 0.025 %, and two between gear teeth at 0.10 and 0.34 %. PyBullet with V-HACD is 98.7 % (its convex hulls only add false hits).
Caveats. FCL, Coal and PyBullet are timed through their Python bindings, one pose per call
(a few µs of overhead per pose); the GPU methods batch all 2000 poses. The Warp collision kernel tests every triangle of A
against B's BVH, so it scales with A's faces. FCP's collision samples are the side-surface ring vertices: a penetration
shallower than their spacing can be missed. The ring tables cost 0.1–0.3 s per object to build (Embree's BVH: about 1 ms),
paid once per object, not per query. GPU: a GTX 1650, which is small.