FCP collision queries

fcp_2910_collision · branch v5.31 · GTX 1650 (4 GB), 12 CPU threads · 2048 atoms, 128 layers · generated 2026-10-29 11:23

Question. Can the descriptor answer "is this point inside?" and "do these two placed objects collide?" directly, without decoding to a mesh, and faster than the standard and state-of-the-art mesh methods? Seven watertight objects (8k–444k faces), each a 2048-atom descriptor at 128 layers, encoded once and cached. The encode time is not counted, because the descriptor is the stored form. The baselines run on the original meshes.

How FCP answers (scripts/fcpq.py). A point is inside when the signed sum over the parts spanning its height of "inside the part's ring at that height" is positive (hole parts count −1). The ring at height s comes from one of two modes: table evaluates the rings once at the layer centres (128 vertices each, from the stored polynomial: about 5 ms per object, no mesh, no grid). A query blends the two neighbouring rings vertex by vertex and runs an even-odd crossing test. Edges are pre-binned in y (32 bins per layer interval), so a query reads only the few edges that its ray can cross. poly evaluates the stored Chebyshev × Fourier polynomial at the exact height for every query (2K coefficients, then the NT ring vertices), followed by the same crossing test. Collision: the table ring vertices of each object, optionally strided in layers × vertices, are mapped into the other's canonical frame and tested. A pose collides when any vertex is inside. All poses run in one CUDA launch (or a numba prange). CPU and GPU give the same answers.

Findings.

Points: FCP table on CUDA takes 1.6 ns/pt uniform and 3.9 ns/pt near the surface (1M points). That is 15–20× faster than Open3D/Embree (the fastest baseline, 32 / 57 ns), 64–140× faster than Warp's GPU BVH winding number, and 150–170× faster than libigl's fast winding number. On the CPU (12 threads), FCP is 3× faster than Open3D.
"Just evaluate polynomials" alone is not the win. The poly mode costs 0.2–1.1 µs/pt, which is slower than Embree. Rebuilding a ring of 33 harmonics with degree-24 height polynomials for every query outweighs one BVH ray. The speed comes from evaluating the polynomials once per layer, a few ms per object, and then reading the rings. That precompute is still not a decode: it builds no grid and no mesh. The y-bins alone gave 7–10× (table, no bins).
Point accuracy: 0.4 % of uniform points and 3.2 % of near-surface points (within ±2 % of the diagonal) differ from the original mesh, all within a thin band at the surface (slices below). This is the descriptor's shape error at 2048 atoms: against the descriptor's own decoded mesh, the disagreement is 0.1 % / 1.0 %. The elephant and the dress (fine detail) are worst.
Collision: FCP 1×1 on CUDA takes 3.7 µs/pose (about 4.5× faster than FCL and Coal, 10× faster than Warp). The 4×4 stride takes 0.95 µs/pose (17–19× faster than FCL and Coal) and stays at 99.4 % accuracy. Accuracy against the exact mesh test: 99.6 % (1×1). The misses are shallow (penetration ≤ 0.43 % of the diagonal), and the false hits are poses within 0.2–5 % of the diagonal of touching, at the mug handle the 2048 atoms round off. PyBullet with V-HACD is 98.7 % accurate (its convex hulls only add false hits) and needs 11–27 s of decomposition per pair. On the CPU, FCP 1×1 (27 µs) is slower than FCL (16 µs); only the strided samples win there (2.4 µs at 4×4).

Caveats. FCL, Coal and Warp test surface intersection only. Containment (one object fully inside the other) is added to the ground truth, but it never occurred in these poses. FCL, Coal and PyBullet are timed through their Python bindings, one pose per call, which adds 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 (the 444k-face dress: 225 µs/pose). The PyBullet "build" of mug-bowl and mug-mug reads as 0 because the V-HACD output was cached from a smoke run (the uncached mug + bowl took 27 s). The first FCP build of each run includes CuPy's first transfer (mug-bowl 105 ms; the others take 6–10 ms). FCP's collision samples are the side-surface ring vertices: a penetration shallower than the sample spacing, or one only through a flat cap, can be missed. GPU: a GTX 1650, which is small. Larger GPUs would favour both GPU methods.

1. Inside-outside point queries

Near the surface (±2 % of the diagonal), 1M points

method	device	mug ns/pt	bowl ns/pt	dino ns/pt	elephant ns/pt	shoe ns/pt	horse ns/pt	dress ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %
FCP table (CUDA)	gpu	3.58	3.82	4.02	3.99	3.96	3.27	4.78	3.89	14.5	4.98	3.23
FCP table (CPU)	cpu	19.4	17.5	19.4	19.2	19.1	16.1	17.5	18.3	3.1	4.98	3.23
FCP table, no bins (CUDA)	gpu	51.1	53.3	29.6	32.1	40.9	28.1	35.6	37.6	1.5	4.98	3.23
Open3D occupancy (Embree)	cpu	55.6	66	59.2	59.7	54.7	39.1	66.3	56.5	1.0	0.79	0.00
Warp BVH winding number (CUDA)	gpu	117	161	218	421	259	154	829	248	0.2	3.88	0.00
libigl fast winding number	cpu	851	693	591	609	827	531	570	658	0.1	29.8	0.00
FCP poly (CPU)	cpu	982	994	597	571	700	533	571	685	0.1	4.98	3.79
FCP poly (CUDA)	gpu	862	559	1.34e+03	1.41e+03	1.43e+03	1.18e+03	1.25e+03	1.1e+03	0.1	4.98	3.79

Uniform in the box padded by 10 %, 1M points

method	device	mug ns/pt	bowl ns/pt	dino ns/pt	elephant ns/pt	shoe ns/pt	horse ns/pt	dress ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %
FCP table (CUDA)	gpu	2.18	1.98	1.02	1.72	2.03	1.14	1.3	1.57	20.2	4.98	0.38
FCP table (CPU)	cpu	10.4	9.9	8.1	10.4	11.4	7.58	7.9	9.28	3.4	4.98	0.38
FCP table, no bins (CUDA)	gpu	28.7	29.5	2.9	10.1	18	5.66	6.24	10.7	3.0	4.98	0.38
Open3D occupancy (Embree)	cpu	32.4	41.3	31.5	31.3	31.9	21.8	34.6	31.6	1.0	0.79	0.00
FCP poly (CPU)	cpu	454	547	83.6	174	297	146	128	213	0.1	4.98	0.46
libigl fast winding number	cpu	372	286	115	207	383	165	261	237	0.1	29.8	0.00
Warp BVH winding number (CUDA)	gpu	123	244	222	541	244	161	1.04e+03	283	0.1	3.88	0.00
FCP poly (CUDA)	gpu	578	366	277	623	840	499	450	491	0.1	4.98	0.46

Small batches: near the surface, 10k points

method	device	mug ns/pt	bowl ns/pt	dino ns/pt	elephant ns/pt	shoe ns/pt	horse ns/pt	dress ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %	wrong vs decoded %
FCP table (CUDA)	gpu	6.7	7.01	7.61	7.75	7.58	6.61	8.45	7.36	11.5	4.98	3.33	1.04
FCP table (CPU)	cpu	20.5	18.5	20.8	20.5	20.4	17.2	18.2	19.4	4.4	4.98	3.33	1.04
FCP table, no bins (CUDA)	gpu	59.4	61.4	37	40.4	48.7	34.6	37.3	44.4	1.9	4.98	3.33	1.04
Open3D occupancy (Embree)	cpu	87.1	92.3	76.2	92.6	84.9	67.4	97.1	84.8	1.0	0.79	0.00	2.93
Warp BVH winding number (CUDA)	gpu	128	156	207	397	241	163	854	246	0.3	3.88	0.00	2.93
FCP poly (CPU)	cpu	986	1.01e+03	610	580	726	539	580	697	0.1	4.98	3.90	1.90
FCP poly (CUDA)	gpu	1.05e+03	747	1.51e+03	1.59e+03	1.59e+03	1.34e+03	1.43e+03	1.28e+03	0.1	4.98	3.90	1.90
trimesh contains (Embree)	cpu	1.98e+03	1.86e+03	1.65e+03	2.33e+03	2.05e+03	1.45e+03	2.7e+03	1.97e+03	0.0	68.4	0.00	2.93
libigl fast winding number	cpu	1.42e+03	1.52e+03	1.82e+03	2.46e+03	2.27e+03	1.38e+03	1.45e+04	2.38e+03	0.0	29.8	0.00	2.93

Where FCP is wrong (near-surface points in a thin slab; red = FCP disagrees with the mesh)

2. Mesh-mesh collision

method	device	mug-bowl µs/pose	dino-elephant µs/pose	shoe-horse µs/pose	mug-mug µs/pose	dress-horse µs/pose	geo-mean µs/pose	× vs Coal	build ms (mean)	accuracy vs mesh %	missed	false	accuracy vs decoded %
FCP stride 4x4 (CUDA)	gpu	1.48	0.868	0.733	1.26	0.646	0.948	19.1	27.71	99.41	49	10	99.63
FCP stride 2x2 (CUDA)	gpu	2.11	1.5	1.33	1.69	1.33	1.57	11.5	27.71	99.58	28	14	99.80
FCP stride 4x4 (CPU)	cpu	1.86	4.8	2.15	1.43	2.82	2.39	7.6	27.71	99.41	49	10	99.63
FCP stride 1x1 (CUDA)	gpu	4.29	3.04	3.74	3.54	3.86	3.67	4.9	27.71	99.61	20	19	99.79
FCP stride 2x2 (CPU)	cpu	6.24	16.2	6.68	4.68	8.98	7.77	2.3	27.71	99.58	28	14	99.80
FCL (BVH, tri-tri)	cpu	21.5	15.1	13.1	19.8	12.7	16	1.1	372.9	100.00	0	0	99.72
Coal (BVH, tri-tri)	cpu	24.6	16.3	14.5	22.8	14.4	18.1	1.0	272.5	100.00	0	0	99.72
FCP stride 1x1 (CPU)	cpu	21.7	49.8	23.4	16.9	31.5	26.7	0.7	27.71	99.61	20	19	99.79
Warp (GPU BVH, tri-tri)	gpu	22.7	22.4	23.7	19.8	225	35.1	0.5	9.847	100.00	0	0	99.72
PyBullet (V-HACD + GJK)	cpu	327	228	176	347	155	234	0.1	9,492	98.67	0	133	98.47

mug-bowl: 8454 / 14030 faces, 66 % of 2000 poses collide; dino-elephant: 19690 / 52216 faces, 40 % of 2000 poses collide; shoe-horse: 24314 / 13840 faces, 39 % of 2000 poses collide; mug-mug: 8454 / 8454 faces, 62 % of 2000 poses collide; dress-horse: 444020 / 13840 faces, 31 % of 2000 poses collide

How wrong are the misses

Example poses (decoded meshes for display; blue = A fixed, orange = B placed)

Files

Scripts in ../scripts (fcpq.py = the descriptor queries, points_bench.py, collide_bench.py, renders.py, report.py); raw numbers in points.csv, collide.csv, logs alongside.

FCP: collision and inside-outside queries straight from the descriptor