FCP collision queries

fcp_2910_collision, v2 · package v5.4 (parts="tracked-fit", branch caps-cutfix) · GTX 1650 (4 GB), 12 CPU threads · 1024 layers, N 128, M 64, 2048 samples per ring, min island area 0, cut at 1e-08 energy left or 5 MB · query: 512 ring vertices, rule nearest · generated 2026-10-30 04:32 · v1 (1024 layers, N 64, 12288 atoms; with the dog and elephant)

Summary

query	set	FCP	best mesh method	FCP speed-up	error bound (% diag)	correct	size
Inside-outside, GPU	11 objects, 1024 layers	9.6 ns/pt	Embree 50.1 ns/pt	5.2×	0.32 %		≤ 2.2 MB
Collision, GPU	11 pairs, 1024 layers	7.0 µs/pose	FCL 18.2 µs/pose	2.6×	miss 0.44 % (0.03 % w/o gear), false 0.00 %	99.93 %
Collision, GPU, every other sample		3.2 µs/pose	FCL 18.2 µs/pose	5.7×		99.84 %
Inside-outside, CPU (v5.5)	12 objects (household, figurines, spring, knot), 256 layers	24.6 ns/pt (12 thr)	Embree 52.4 ns/pt	2.1×	0.34 %		≤ 1.0 MB
Collision, CPU (v5.5)	11 pairs, 256 layers	24.0 µs/pose (12 thr)	FCL 18.4 µs/pose (1 thr)	0.8×	miss 0.00 %, false 0.05 %	99.94 %
Collision, CPU, every other sample		6.3 µs/pose (12 thr)	FCL 18.4 µs/pose (1 thr)	2.9×	miss 0.36 %	99.92 %

CPU, 12 objects: household, two figurines, the spring and the knot (v5.5): error bound (left axis) and time (right axis, log) against the layers; (a) points against Embree, (b) collision against FCL. The GPU results are in sections 2–4.

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

1. Settings: one encoder setting for every object

How the setting was chosen. Every object encoded at 512 and 1024 layers × N 64 and 128 (2048 samples per ring, every island kept), plus two controls at 1024 layers: the package's minimum island area (0.002) and N 255. Each descriptor is cut to all but 1e-8 of the energy (at most 5 MB) and queried at 256, 512 and 1024 ring vertices. The measure is the near-surface points wrong farther than 0.1 % of the diagonal from the surface: a band any approximation of the surface needs, about the size of the meshes' own facets. 2048 layers were left out (encode cost).

1024 layers, N 128 is the only setting that is good on every object: at most 21 points beyond 0.1 % but on the gear (28 with the nearest rule), for 0.08–2.2 MB. 512 layers leave 74–146 on the dino and dress; N 64 leaves 25–34 on the pan and shoe and 4750 on the gear.
Islands: dropping small tracks (the package rule) costs the shoe 4 → 198 and the dino 12 → 22; keeping them costs no measurable size.
N 255 helps the gear (554 → 210) and the shoe (4 → 2) for up to 45 % more bytes; the gear's corners need N far beyond the format's 255 and more query vertices.
Query vertices: NT 512 against 256 removes most of the gear's and dress's errors for up to 60 % more time; 1024 helps only the gear.
The z rule (the sweep itself used the two-centre rule): the nearest layer centre is 1.4–2× faster than testing both neighbouring centres (with a blend where they differ), and as accurate beyond 0.1 % (±3 points per object); it is the rule of every query below.

Every setting at NT 512 (the cut descriptor: all but 1e-08 of the energy, at most 5 MB)

Wrong = of 1M points near the surface (±2 % diag) or 1M uniform in the box + 10 %, against the mesh. Filter boxes under each header take text or >x, <=x, !0; click a header to sort.

object	layers	N	min area	MB	parts	near wrong > 0.1 %	> 0.2 %	> 0.3 %	uniform > 0.1 %	near wrong all, %	max err % diag	near ns/pt	uniform ns/pt	encode s	encode peak GB
gear	512	64	0	0.00	2	4666	527	0	893	1.678	0.281	13.3	9.3	nan	0.5
mug	512	64	0	0.28	12	4	0	0	3	0.154	0.158	20.5	7.1	9	1.0
bowl	512	64	0	0.20	7	1	0	0	1	0.313	0.114	25.2	11.0	9	1.1
dino	512	64	0	0.62	45	82	6	0	3	0.393	0.266	14.3	2.7	7	1.0
horse	512	64	0	0.54	21	0	0	0	0	0.250	0.095	10.7	3.0	6	1.0
shoe	512	64	0	0.84	109	40	0	0	6	0.376	0.194	14.7	7.2	8	1.1
dress	512	64	0	0.62	31	182	5	0	3	0.993	0.237	13.8	3.4	9	1.1
pan_holes	512	64	0	0.49	59	48	18	7	4	0.427	0.362	24.9	8.4	11	1.1
knot	512	64	0	0.25	12	0	0	0	0	0.050	0.018	9.5	2.6	11	1.1
spring	512	64	0	0.18	5	0	0	0	0	0.435	0.083	23.2	12.2	9	1.0
sponge	512	64	0	0.05	96	14	0	0	7	0.398	0.182	14.7	10.9	2	1.3
mug	512	128	0	0.41	12	11	0	0	3	0.111	0.199	20.5	7.1	10	1.0
bowl	512	128	0	0.32	7	1	0	0	1	0.233	0.122	25.2	11.1	9	1.1
dino	512	128	0	0.81	45	74	1	0	3	0.375	0.206	14.4	2.7	7	1.0
horse	512	128	0	0.74	21	2	0	0	0	0.189	0.144	10.8	3.0	6	1.0
shoe	512	128	0	1.38	109	6	1	0	2	0.246	0.239	14.8	7.2	9	1.2
dress	512	128	0	0.98	31	146	2	0	3	0.887	0.216	14.6	3.7	9	1.1
pan_holes	512	128	0	0.79	59	31	14	5	3	0.332	0.335	24.9	8.4	nan	0.5
knot	512	128	0	0.31	12	0	0	0	0	0.039	0.026	9.5	2.6	10	1.1
spring	512	128	0	0.30	5	0	0	0	0	0.436	0.093	23.2	12.2	9	1.0
sponge	512	128	0	0.08	96	0	0	0	0	0.346	0.081	14.8	10.9	3	1.3
gear	512	128	0	0.00	2	548	0	0	104	0.649	0.171	12.7	9.0	0	1.0
mug	1024	64	0	0.36	13	0	0	0	0	0.115	0.088	23.9	8.2	33	1.3
bowl	1024	64	0	0.28	12	0	0	0	0	0.257	0.078	27.7	12.5	33	1.3
dino	1024	64	0	0.97	67	13	1	0	0	0.212	0.272	12.5	3.2	25	1.2
horse	1024	64	0	0.74	23	0	0	0	0	0.200	0.097	10.4	2.9	23	1.3
shoe	1024	64	0	1.33	164	34	0	0	3	0.324	0.193	15.1	7.9	31	1.4
dress	1024	64	0	0.95	43	19	0	0	0	0.691	0.195	11.1	3.0	32	1.4
pan_holes	1024	64	0	0.79	115	25	9	2	3	0.366	0.322	25.1	8.7	33	1.5
knot	1024	64	0	0.31	12	0	0	0	0	0.043	0.014	9.3	2.5	34	1.4
spring	1024	64	0	0.23	4	5	0	0	0	0.178	0.163	21.4	10.6	31	1.2
sponge	1024	64	0	0.05	96	23	0	0	7	0.298	0.154	15.6	11.3	12	1.7
gear	1024	64	0	0.00	2	4750	553	0	891	1.687	0.277	18.3	12.3	1	1.0
mug	1024	128	0	0.53	13	1	0	0	0	0.074	0.106	24.1	8.2	36	1.3
bowl	1024	128	0	0.46	12	0	0	0	0	0.148	0.039	27.6	12.5	34	1.3
dino	1024	128	0	1.28	67	12	2	0	0	0.178	0.237	11.0	2.6	27	1.3
horse	1024	128	0	1.05	23	2	0	0	0	0.136	0.184	10.5	2.9	25	1.3
shoe	1024	128	0	2.18	164	4	0	0	0	0.180	0.144	15.1	7.9	34	1.6
dress	1024	128	0	1.52	43	1	0	0	0	0.535	0.118	11.2	3.0	34	1.4
pan_holes	1024	128	0	1.28	115	21	10	0	1	0.259	0.297	25.2	8.7	37	1.7
knot	1024	128	0	0.40	12	0	0	0	0	0.033	0.009	9.3	2.5	40	1.5
spring	1024	128	0	0.42	5	0	0	0	0	0.150	0.066	21.1	10.5	33	1.2
sponge	1024	128	0	0.08	96	0	0	0	0	0.249	0.096	15.6	11.3	13	1.9
gear	1024	128	0	0.00	2	554	0	0	105	0.656	0.171	17.5	11.9	1	1.0
mug	1024	128	0.002	0.53	13	0	0	0	0	0.077	0.082	24.0	8.2	40	1.3
mug	1024	255	0	0.59	13	2	0	0	0	0.072	0.121	24.0	8.2	46	1.4
bowl	1024	128	0.002	0.46	12	0	0	0	0	0.146	0.035	27.7	12.5	35	1.3
bowl	1024	255	0	0.62	12	0	0	0	0	0.128	0.042	27.7	12.5	42	1.4
dino	1024	128	0.002	1.27	59	22	3	0	1	0.184	0.289	12.3	2.7	27	1.3
dino	1024	255	0	1.35	67	14	0	0	0	0.181	0.190	11.0	2.6	31	1.4
horse	1024	128	0.002	1.05	21	4	0	0	0	0.136	0.138	10.1	2.7	25	1.3
horse	1024	255	0	1.25	23	2	0	0	0	0.118	0.141	10.2	2.7	28	1.4
shoe	1024	128	0.002	2.00	57	198	78	14	13	0.222	0.368	14.5	6.2	33	1.3
shoe	1024	255	0	3.15	164	2	0	0	0	0.145	0.107	15.2	7.9	40	2.0
dress	1024	128	0.002	1.52	41	7	0	0	0	0.546	0.158	12.5	3.5	34	1.4
dress	1024	255	0	2.04	43	1	0	0	0	0.475	0.121	12.5	3.6	38	1.5
pan_holes	1024	128	0.002	1.18	56	31	11	1	1	0.268	0.301	24.9	8.1	35	1.5
pan_holes	1024	255	0	1.78	115	23	11	1	1	0.226	0.307	25.2	8.7	42	2.3
knot	1024	128	0.002	0.40	12	0	0	0	0	0.032	0.012	9.3	2.5	38	1.5
knot	1024	255	0	0.41	12	0	0	0	0	0.033	0.014	9.3	2.5	49	1.6
spring	1024	128	0.002	0.42	5	0	0	0	0	0.151	0.028	21.0	10.5	33	1.2
spring	1024	255	0	0.48	5	0	0	0	0	0.149	0.022	21.0	10.5	36	1.2
sponge	1024	128	0.002	0.08	96	0	0	0	0	0.245	0.077	15.6	11.3	14	1.9
sponge	1024	255	0	0.10	96	0	0	0	0	0.245	0.051	15.5	11.3	17	2.1
gear	1024	128	0.002	0.00	2	566	0	0	105	0.663	0.173	17.5	11.9	1	1.0
gear	1024	255	0	0.00	2	210	0	0	32	0.441	0.150	17.9	12.1	1	1.1

The query: ring vertices NT and the z rule, at 1024 layers, N 128

table: inside at the two neighbouring layer centres decides where they agree, else each part's two rings blended at the query height; nearest: the ring set of the nearest layer centre, one parity per part (height error at most half a layer).

object	NT	rule	near wrong > 0.1 %	> 0.2 %	uniform > 0.1 %	near wrong all, %	near ns/pt	uniform ns/pt
mug	256	table	1	0	0	0.090	17.8	6.3
mug	256	nearest	1	0	0	0.147	8.9	3.5
mug	512	table	0	0	0	0.080	23.9	8.1
mug	512	nearest	0	0	0	0.139	12.1	4.6
mug	1024	table	0	0	0	0.079	26.4	8.8
mug	1024	nearest	0	0	0	0.137	13.4	5.1
bowl	256	table	0	0	0	0.182	20.1	8.8
bowl	256	nearest	0	0	0	0.256	10.2	4.5
bowl	512	table	0	0	0	0.144	27.7	12.5
bowl	512	nearest	0	0	0	0.220	13.9	6.3
bowl	1024	table	0	0	0	0.141	30.6	13.8
bowl	1024	nearest	0	0	0	0.215	15.4	7.0
dino	256	table	10	1	0	0.196	10.8	3.0
dino	256	nearest	13	2	0	0.331	6.3	1.6
dino	512	table	10	1	0	0.189	10.9	2.6
dino	512	nearest	13	2	0	0.325	7.4	1.7
dino	1024	table	10	1	0	0.188	13.8	2.8
dino	1024	nearest	13	2	0	0.323	9.2	1.8
horse	256	table	3	0	0	0.154	7.8	2.3
horse	256	nearest	4	1	0	0.244	5.0	1.5
horse	512	table	2	0	0	0.132	9.7	2.5
horse	512	nearest	4	1	0	0.224	6.5	1.6
horse	1024	table	2	0	0	0.129	12.2	2.7
horse	1024	nearest	4	1	0	0.222	7.9	1.8
shoe	256	table	7	0	2	0.221	13.6	7.5
shoe	256	nearest	7	0	2	0.289	8.7	4.8
shoe	512	table	3	0	0	0.182	15.2	7.9
shoe	512	nearest	3	0	0	0.258	10.4	5.2
shoe	1024	table	3	0	0	0.181	17.4	8.6
shoe	1024	nearest	3	0	0	0.256	12.0	5.7
dress	256	table	13	0	0	0.583	10.5	3.3
dress	256	nearest	8	0	0	0.613	5.7	1.8
dress	512	table	3	0	0	0.533	11.1	3.0
dress	512	nearest	2	0	0	0.570	7.4	2.0
dress	1024	table	3	0	0	0.529	14.5	3.5
dress	1024	nearest	2	0	0	0.570	9.6	2.2
pan_holes	256	table	33	13	1	0.291	20.3	7.6
pan_holes	256	nearest	30	11	1	0.428	11.1	4.8
pan_holes	512	table	31	13	1	0.255	25.2	8.7
pan_holes	512	nearest	28	11	1	0.395	14.1	5.8
pan_holes	1024	table	31	13	1	0.257	30.9	9.9
pan_holes	1024	nearest	29	11	1	0.393	17.3	6.6
knot	256	table	0	0	0	0.033	8.3	2.5
knot	256	nearest	0	0	0	0.122	5.3	1.5
knot	512	table	0	0	0	0.033	9.3	2.5
knot	512	nearest	0	0	0	0.122	6.2	1.4
knot	1024	table	0	0	0	0.033	9.8	2.3
knot	1024	nearest	0	0	0	0.122	6.8	1.5
spring	256	table	0	0	0	0.163	13.0	6.7
spring	256	nearest	0	0	0	0.292	6.4	3.6
spring	512	table	0	0	0	0.146	21.1	10.5
spring	512	nearest	0	0	0	0.292	10.6	5.5
spring	1024	table	0	0	0	0.143	34.6	17.2
spring	1024	nearest	0	0	0	0.291	17.3	8.9
sponge	256	table	0	0	0	0.250	15.1	11.1
sponge	256	nearest	0	0	0	0.250	10.2	7.4
sponge	512	table	0	0	0	0.251	15.6	11.3
sponge	512	nearest	0	0	0	0.251	11.3	7.9
sponge	1024	table	0	0	0	0.252	15.8	11.4
sponge	1024	nearest	0	0	0	0.252	11.6	8.1
gear	256	table	3744	734	630	1.166	12.5	8.3
gear	256	nearest	3744	734	630	1.166	6.3	4.2
gear	512	table	547	0	105	0.657	17.5	11.9
gear	512	nearest	547	0	105	0.657	8.8	6.0
gear	1024	table	170	0	41	0.626	20.6	13.7
gear	1024	nearest	170	0	41	0.626	10.3	6.9

2. Everyday objects

2a. Inside-outside point queries

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

method	device	mug ns/pt	bowl ns/pt	dino 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	12.1	14	7.49	10.4	6.52	7.79	9.36	5.7	189	0.29
FCP table (CPU)	cpu	28.2	26.2	28.4	35.7	21.4	22.8	26.7	2.0	189	0.29
Open3D occupancy (Embree)	cpu	56.1	55.5	48.4	55	40.5	67.5	53.2	1.0	0.702	0.00
Warp BVH winding number (CUDA)	gpu	113	160	218	262	154	827	226	0.2	8.25	0.00
libigl fast winding number	cpu	863	714	609	942	547	597	698	0.1	31.9	0.00

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

method	device	mug ns/pt	bowl ns/pt	dino 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	4.7	6.39	2	5.89	1.84	2	3.3	8.7	189	0.04
FCP table (CPU)	cpu	23.1	15.9	21.2	24.3	23.3	19.7	21.1	1.4	189	0.04
Open3D occupancy (Embree)	cpu	32.8	32.8	20.9	32.4	22.4	35.6	28.9	1.0	0.702	0.00
libigl fast winding number	cpu	377	268	115	385	171	267	243	0.1	31.9	0.00
Warp BVH winding number (CUDA)	gpu	120	242	221	247	161	1.03e+03	253	0.1	8.25	0.00

Small batches: near the surface, 10k points

method	device	mug ns/pt	bowl ns/pt	dino 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	13.8	17.2	14.2	15.7	10.9	13.6	14.1	5.8	189	0.28	0.38
FCP table (CPU)	cpu	25.2	24.8	24.4	34.9	18.2	600	42.4	1.9	189	0.28	0.38
Open3D occupancy (Embree)	cpu	85.3	91.1	78.4	87.2	63.9	90.2	82.1	1.0	0.702	0.00	0.43
Warp BVH winding number (CUDA)	gpu	125	154	211	250	162	867	229	0.4	8.25	0.00	0.43
trimesh contains (Embree)	cpu	2.08e+03	1.92e+03	1.71e+03	2.22e+03	1.52e+03	2.9e+03	2.01e+03	0.0	80.7	0.00	0.43
libigl fast winding number	cpu	1.41e+03	1.57e+03	1.83e+03	2.3e+03	1.39e+03	1.49e+04	2.4e+03	0.0	31.9	0.00	0.43

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

2b. Mesh-mesh collision

method	device	mug-bowl µs/pose	dino-horse µ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	3.96	1.2	1.32	3	1.08	1.82	9.7	401.5	99.71	29	0	99.74
FCP stride 2x2 (CUDA)	gpu	5.34	2.25	2.5	3.55	1.91	2.89	6.1	401.5	99.89	11	0	99.92
FCP stride 4x4 (CPU)	cpu	2.68	5.31	5.22	2.98	3.78	3.84	4.6	401.5	99.71	29	0	99.74
FCP stride 1x1 (CUDA)	gpu	8.74	8.03	7.26	5.43	5.76	6.93	2.5	401.5	99.96	4	0	99.97
FCP stride 2x2 (CPU)	cpu	8.27	16.1	13	5.44	10.9	10	1.8	401.5	99.89	11	0	99.92
FCL (BVH, tri-tri)	cpu	23.5	11.5	13.1	20.1	12.8	15.6	1.1	358.2	100.00	0	0	99.93
Coal (BVH, tri-tri)	cpu	25.4	12.8	14.7	23.5	15.1	17.6	1.0	260.4	100.00	0	0	99.93
Warp (GPU BVH, tri-tri)	gpu	21	15.4	27.3	19.8	224	33	0.5	4.236	100.00	0	0	99.93
FCP stride 1x1 (CPU)	cpu	28	53.5	37.2	20.1	35.4	33.1	0.5	401.5	99.96	4	0	99.97
PyBullet (V-HACD + GJK)	cpu	337	157	184	357	159	223	0.1	0.06119	98.70	0	130	98.65

mug-bowl: 8454 / 14030 faces, 66 % of 2000 poses collide; dino-horse: 19690 / 13840 faces, 32 % 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)

3. Concave, interleaved and perforated shapes

3a. Inside-outside point queries

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

method	device	pan_holes ns/pt	knot ns/pt	spring ns/pt	sponge ns/pt	gear ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %
FCP table (CUDA)	gpu	14.2	6.12	10.6	11.3	8.82	9.84	4.7	305	0.35
FCP table (CPU)	cpu	32.4	27.5	22.4	48.7	15.6	27.3	1.7	305	0.35
Open3D occupancy (Embree)	cpu	48.8	50.4	57.9	49.8	31.3	46.7	1.0	0.29	0.00
Warp BVH winding number (CUDA)	gpu	169	293	683	133	42.2	180	0.3	2.34	0.00
libigl fast winding number	cpu	1.55e+03	458	563	1.5e+03	1.76e+03	1.01e+03	0.0	10.7	0.00

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

method	device	pan_holes ns/pt	knot ns/pt	spring ns/pt	sponge ns/pt	gear ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %
FCP table (CUDA)	gpu	6.08	1.59	5.64	8.64	6.02	4.91	6.6	305	0.08
FCP table (CPU)	cpu	21.4	22.4	21.7	34.2	12.6	21.4	1.5	305	0.08
Open3D occupancy (Embree)	cpu	31.4	25.7	39.2	45.3	24.9	32.4	1.0	0.29	0.00
Warp BVH winding number (CUDA)	gpu	146	378	599	105	39.4	169	0.2	2.34	0.00
libigl fast winding number	cpu	1.07e+03	157	237	1.37e+03	1.5e+03	606	0.1	10.7	0.00

Small batches: near the surface, 10k points

method	device	pan_holes ns/pt	knot ns/pt	spring ns/pt	sponge ns/pt	gear ns/pt	geo-mean ns/pt	× vs Open3D	build ms (mean)	wrong vs mesh %	wrong vs decoded %
FCP table (CUDA)	gpu	20	9.35	12	15.9	11.5	13.3	5.6	305	0.34	0.46
FCP table (CPU)	cpu	36	18.4	20.1	37.7	15.6	23.9	3.1	305	0.34	0.46
Open3D occupancy (Embree)	cpu	77.8	81.8	93.2	80.3	49.5	74.9	1.0	0.29	0.00	0.50
Warp BVH winding number (CUDA)	gpu	195	276	632	184	43.4	193	0.4	2.34	0.00	0.50
trimesh contains (Embree)	cpu	2.16e+03	1.66e+03	2.57e+03	2.31e+03	1.08e+03	1.87e+03	0.0	22	0.00	0.50
libigl fast winding number	cpu	2.66e+03	1.91e+03	3.37e+03	1.6e+03	1.85e+03	2.19e+03	0.0	10.7	0.00	0.50

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

3b. Mesh-mesh collision

method	device	spring-spring µs/pose	knot-knot µs/pose	sponge-sponge µs/pose	gear-gear µs/pose	pan_holes-mug µs/pose	knot-spring µs/pose	geo-mean µs/pose	× vs Coal	build ms (mean)	accuracy vs mesh %	missed	false	accuracy vs decoded %
FCP stride 4x4 (CUDA)	gpu	3.04	1.3	4.64	1.44	1.92	2.99	2.31	10.0	560.2	99.54	55	0	99.62
FCP stride 4x4 (CPU)	cpu	0.644	3.77	7.63	0.802	5.46	1.94	2.32	9.9	560.2	99.54	55	0	99.62
FCP stride 2x2 (CUDA)	gpu	3.68	2.49	6.81	1.99	3.47	4.3	3.51	6.6	560.2	99.80	24	0	99.87
FCP stride 1x1 (CUDA)	gpu	4.47	8.2	17.5	2.88	10.2	7.06	7.14	3.2	560.2	99.91	11	0	99.95
FCP stride 2x2 (CPU)	cpu	1.79	13.7	22.8	2.62	15.4	7	7.35	3.1	560.2	99.80	24	0	99.87
FCL (BVH, tri-tri)	cpu	24.5	15.8	33.6	15.3	20.9	18.8	20.7	1.1	175.6	100.00	0	0	99.89
Coal (BVH, tri-tri)	cpu	26	16.5	42.3	16.2	26.2	19.8	23.1	1.0	130.6	100.00	0	0	99.89
Warp (GPU BVH, tri-tri)	gpu	46.7	23.2	13.8	11.4	44.9	29.8	24.7	0.9	3.414	100.00	0	0	99.89
FCP stride 1x1 (CPU)	cpu	6.3	50.1	74.1	9.52	46.5	24.6	25.2	0.9	560.2	99.91	11	0	99.95
PyBullet (V-HACD + GJK)	cpu	491	183	715	296	294	283	342	0.1	0.05518	98.73	0	152	98.62

spring-spring: 76796 / 76796 faces, 77 % of 2000 poses collide; knot-knot: 28800 / 28800 faces, 52 % of 2000 poses collide; sponge-sponge: 1300 / 1300 faces, 75 % of 2000 poses collide; gear-gear: 992 / 992 faces, 76 % of 2000 poses collide; pan_holes-mug: 16092 / 8454 faces, 54 % of 2000 poses collide; knot-spring: 28800 / 76796 faces, 59 % of 2000 poses collide

How wrong are the misses

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

4. How far from the surface can an answer be wrong?

A threshold you can rely on. For every setting, ε is the largest distance from the true surface at which an answer was still wrong: over 11 objects × 2M points (±2 % of the diagonal of the surface, and uniform in the box) for points, and over 11 pairs × 2000 poses near contact for collisions (the true depth of every colliding pose and the gap of every free one, from the meshes). Beyond ε every answer was right. Empirical, not a proof: it holds on these objects.

128 layers (N ≥ 64, NT ≥ 256): points farther than 0.7 % of the diagonal are always classified right; a collision deeper than 0.5 % is always found with the densest sampling (0.3 % without the gear; 0.62–1.04 % with every other sample), and no false collision is reported for a gap wider than 0.25 %. at most 0.3–0.5 MB per object, about 6 ns per point and 4.3 µs per pose on the GPU.
256 layers or more (N ≥ 64, NT ≥ 256): points 0.4 %, collision misses 0.5 % (all set by the gear's tooth tips: 0.08 % without the gear), false hits 0.05 % (none at 1024 layers, N 128).
The rule of thumb: ε(points) ≈ max(90 / layers, 0.35) % of the diagonal: half a layer of height resolution down to about 256 layers, then a floor set by the in-plane fit (facets, sharp corners, pieces between slices). Collision misses follow the sampling density, not the layers: every 1/128 of the height and of the ring (sampling 1): 0.5 %; twice as sparse: 0.6–1.0 %; four times: 2.3–2.6 %. False hits follow the point bound.
What breaks it: N 32 (the gear: 0.57 %, false hits 0.44 %), and NT 128 with N 128 (rings with 128 harmonics drawn with 128 vertices: 0.72 %).

layers	N	NT	max MB	points ε % diag	points ε w/o gear	missed contact ε sampling 1	sampling 2	sampling 4	missed ε s1 w/o gear	false hit ε sampling 1	near ns/pt (median)	µs/pose s1 (median)
128	32	128	0.16	0.73	0.68	0.62	0.63	2.55	0.30	0.24	4.7	3.83
128	32	256	0.16	0.68	0.68	0.62	0.62	2.55	0.30	0.44	6.1	4.32
128	32	512	0.16	0.68	0.68	0.62	0.62	2.55	0.30	0.44	8.0	5.25
128	64	128	0.29	0.67	0.67	0.62	1.04	2.31	0.30	0.24	4.7	3.81
128	64	256	0.29	0.67	0.67	0.47	0.62	2.31	0.30	0.24	6.1	4.30
128	64	512	0.29	0.67	0.67	0.47	0.62	2.31	0.30	0.24	8.1	4.77
128	128	128	0.49	0.71	0.64	0.62	1.04	2.31	0.30	0.24	4.7	3.83
128	128	256	0.49	0.64	0.64	0.44	1.04	2.31	0.30	0.24	6.1	4.31
128	128	512	0.49	0.64	0.64	0.44	0.62	2.31	0.30	0.24	8.6	4.78
256	32	128	0.28	0.74	0.51	0.62	0.63	2.55	0.27	0.06	4.5	4.17
256	32	256	0.28	0.60	0.50	0.62	0.63	2.55	0.27	0.44	6.0	4.98
256	32	512	0.28	0.57	0.50	0.62	0.62	2.55	0.27	0.44	9.0	5.20
256	64	128	0.51	0.62	0.36	0.62	0.62	2.31	0.08	0.05	4.5	4.19
256	64	256	0.51	0.36	0.36	0.47	0.62	2.31	0.08	0.05	6.0	4.99
256	64	512	0.51	0.36	0.36	0.47	0.62	2.31	0.08	0.05	9.1	5.22
256	128	128	0.86	0.72	0.40	0.62	1.04	2.31	0.08	0.05	4.5	4.17
256	128	256	0.86	0.37	0.37	0.08	1.04	2.31	0.08	0.05	6.1	4.91
256	128	512	0.86	0.37	0.37	0.44	0.62	2.31	0.08	0.05	9.1	5.21
512	32	128	0.48	0.73	0.46	0.62	1.04	2.55	0.27	0.06	5.0	5.11
512	32	256	0.48	0.60	0.53	0.62	0.63	2.55	0.27	0.44	6.3	5.17
512	32	512	0.48	0.57	0.53	0.62	0.63	2.55	0.27	0.44	9.7	5.90
512	64	128	0.84	0.62	0.37	0.62	0.62	2.31	0.03	0.03	4.7	5.11
512	64	256	0.84	0.37	0.37	0.47	0.62	2.31	0.03	0.03	6.3	5.19
512	64	512	0.84	0.37	0.37	0.47	0.62	2.31	0.03	0.03	10.1	5.93
512	128	128	1.38	0.72	0.38	0.62	1.04	2.31	0.05	0.03	4.7	5.11
512	128	256	1.38	0.38	0.38	0.44	0.62	2.31	0.05	0.03	6.3	5.19
512	128	512	1.38	0.38	0.38	0.44	0.62	2.31	0.05	0.03	10.1	5.95
1024	32	128	0.77	0.73	0.48	0.62	0.63	2.55	0.27	0.06	5.8	6.24
1024	32	256	0.77	0.60	0.48	0.62	0.63	2.55	0.27	0.44	6.6	6.30
1024	32	512	0.77	0.57	0.48	0.62	0.63	2.55	0.27	0.44	10.9	6.54
1024	64	128	1.33	0.62	0.34	0.62	0.62	2.31	0.03	0.02	5.2	6.27
1024	64	256	1.33	0.35	0.34	0.47	0.62	2.31	0.03	0.02	6.6	6.32
1024	64	512	1.33	0.34	0.34	0.47	0.62	2.31	0.03	0.02	10.8	6.58
1024	128	128	2.18	0.72	0.35	0.62	1.04	2.31	0.05	0.00	7.1	6.25
1024	128	256	2.18	0.32	0.32	0.44	0.62	2.31	0.05	0.00	7.9	6.32
1024	128	512	2.18	0.32	0.32	0.44	0.62	2.31	0.03	0.00	10.7	6.62

Sampling s: collision samples every s/128 of the height and every s·NT/128-th ring vertex. Raw: bound_points.csv, bound_collide.csv (per object / pair); scripts/bound.py.

5. 512 layers against 1024 layers

set	FCP query	unit	time 1024 layers	time 512 layers	wrong % / accuracy % 1024 layers	wrong % / accuracy % 512 layers
everyday	points near, (CUDA)	ns/pt	9.36	9.54	0.291	0.497
everyday	points near, (CPU)	ns/pt	26.75	75.88	0.291	0.497
everyday	points uniform, (CUDA)	ns/pt	3.30	3.29	0.039	0.064
everyday	points uniform, (CPU)	ns/pt	21.05	40.26	0.039	0.064
everyday	collision, sampling 1x1 (CPU)	µs/pose	33.07	75.68	99.960	99.950
everyday	collision, sampling 1x1 (CUDA)	µs/pose	6.93	5.97	99.960	99.950
everyday	collision, sampling 2x2 (CPU)	µs/pose	10.05	24.45	99.890	99.900
everyday	collision, sampling 2x2 (CUDA)	µs/pose	2.89	2.92	99.890	99.900
everyday	collision, sampling 4x4 (CPU)	µs/pose	3.84	9.58	99.710	99.730
everyday	collision, sampling 4x4 (CUDA)	µs/pose	1.82	1.64	99.710	99.730
complex	points near, (CUDA)	ns/pt	9.84	9.43	0.348	0.499
complex	points near, (CPU)	ns/pt	27.32	75.12	0.348	0.499
complex	points uniform, (CUDA)	ns/pt	4.91	6.01	0.080	0.116
complex	points uniform, (CPU)	ns/pt	21.40	53.53	0.080	0.116
complex	collision, sampling 1x1 (CPU)	µs/pose	25.18	47.55	99.908	99.892
complex	collision, sampling 1x1 (CUDA)	µs/pose	7.14	6.69	99.908	99.892
complex	collision, sampling 2x2 (CPU)	µs/pose	7.35	17.91	99.800	99.750
complex	collision, sampling 2x2 (CUDA)	µs/pose	3.51	3.54	99.800	99.750
complex	collision, sampling 4x4 (CPU)	µs/pose	2.32	7.75	99.542	99.567
complex	collision, sampling 4x4 (CUDA)	µs/pose	2.31	2.26	99.542	99.567

Points: wrong % of 1M points against the mesh (all distances); collision: agreement with the exact mesh test. Raw: points*_L512.csv, collide*_L512.csv.

6. Where the remaining errors are

What is left, at the chosen setting. Each slice figure: the mesh slice (black), the descriptor's rings at that layer (blue), and the near-surface points answered wrongly from ±2 layers around it, coloured by their distance to the true surface (darker is farther; filled: false inside, open: false outside), with the two densest groups zoomed (the bar is 0.1 % of the diagonal). Three kinds remain:

Sharp corners (gear): the ring is a Fourier series, so a corner is rounded off by up to 0.17 % of the diagonal. N 255 with 2048 samples per ring removes it on the gear at 256 layers (5 kB); here N is 128 for every object.
Pieces that start or end between two layers (the pan's rim lip, the dino's toes): a part's top and bottom sit on a half-layer boundary, and a piece present in the mesh between two slices is not in the descriptor. This is the height question handed over in fcp_devel/docs/HANDOVER_height_fit.md (exact end heights, a fit against the continuous surface).
Facets: the descriptor is smoother than the mesh, so points closer than about one facet's sag to the surface can fall on either side; they are inside the 0.1 % band and not counted above.

The dog of v1 (a scanned plush toy whose whole surface is 0.1–0.3 %-of-the-diagonal bumps) is in v1 and slices/3d_cmp_dog.png.

3d dino

3d pan holes

dino

gear

pan holes

shoe

7. Found on the way

In the package (reported, not changed here):

The cut rule could leave a part whole (_parts.split_by_fit, v5.31): the cut at the largest coefficient step was picked first and then had to pass the 10 % gain test; when it failed, no other cut was tried. The dog at 2048 layers kept a 719-layer part with rings 2.6 % of the diagonal off (17 642 points wrong beyond 0.1 %, 1 699 with the fix). Fixed in v5.4 (decision 29), which this report uses.
Encode memory is padded to the longest part: the selection's basis array has one (longest part × degree) block per Fourier coefficient: 6–13 GB at 2048 layers, out of memory for some objects. One basis per part gives the same atoms (float32 round-off aside) in 1–2 GB (lowmem.py).
Small islands are dropped (MIN_AREA_FRAC = 0.002 of the largest slice): toes, thin strips, small holes; a fixed error no budget can remove. Every island is kept here.
512 samples per ring (N_SAMPLES) caps the in-plane detail whatever N is; 2048 here.

In this study's query (fixed): blending each part's rings between two layer centres morphed unrelated shapes where two tracks merge (the dropped track stopped half way, the continuing one changed shape): slabs one layer thick read empty, up to 1.8 % of the diagonal deep. The nearest-centre rule has no such case. Ground truth and meshes were checked: every mesh watertight with consistent winding; Open3D's 3-ray occupancy and libigl's winding number agree on every point.

Files

Scripts in ../scripts: fcpq.py (the descriptor queries), sweep.py and rule_cmp.py (section 1), bound.py (section 4), points_bench.py and collide_bench.py (FCP_SET=complex for section 3), slice_errors.py and render3d.py (section 5), lowmem.py (the encoder's selection without its padded array), common.py (the setting), make_shapes.py, renders.py, report.py. Raw numbers: sweep.csv, rule_cmp.csv, points*.csv, collide*.csv; logs alongside. Earlier: v1/, a6144/, a2048/.

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

Summary

1. Settings: one encoder setting for every object

Every setting at NT 512 (the cut descriptor: all but 1e-08 of the energy, at most 5 MB)

The query: ring vertices NT and the z rule, at 1024 layers, N 128

2. Everyday objects

2a. Inside-outside point queries

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

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

Small batches: near the surface, 10k points

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

2b. Mesh-mesh collision

How wrong are the misses

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

3. Concave, interleaved and perforated shapes

3a. Inside-outside point queries

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

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

Small batches: near the surface, 10k points

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

3b. Mesh-mesh collision

How wrong are the misses

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

4. How far from the surface can an answer be wrong?

5. 512 layers against 1024 layers

6. Where the remaining errors are

3d dino

3d pan holes

dino

gear

pan holes

shoe

7. Found on the way

Files