OBB cases. Much faster, losing accuracy: fast is {f(1 / q.loc['fast'].time_ratio, 0)}× faster than the minimal box "
f"at {f(100 * q.loc['fast'].err_med, 1)} % median volume and up to {f(q.loc['fast'].out_max, 1)} % of the diagonal outside (64 layers are too coarse "
f"for bounds). Nearly as accurate and still faster: accurate is {f(1 / q.loc['accurate'].time_ratio, 0)}× faster at "
f"{f(100 * q.loc['accurate'].err_med, 2)} % median volume, {f(q.loc['accurate'].out_max, 2)} % outside. Against the quick standard route: Open3D's "
f"principal-axes box is {f(1 / pca_t, 0)}× faster than the minimal box but {f(100 * (pca_s - 1), 0)} % too large at the median; "
f"balanced is faster still ({f(1 / q.loc['balanced'].time_ratio, 0)}×) and within {f(100 * q.loc['balanced'].err_med, 1)} %.
")
# crossovers on the sweep
combos = [("fast", 64, 512), ("default", 128, 2048), ("accurate", 256, 6144)]
xr = []
for task in ("hull", "volume", "obb", "sphere"):
cells = []
for name, L, A in combos:
v = crossover(s, task, name, L, A)
cells.append("always faster" if v == 0 else ("not within 1M" if v is None else f"{v / 1e3:.1f}k"))
xr.append(f"
{names[task]}
" + "".join(f"
{x}
" for x in cells) + "
")
# absolute times on the sweep: the figure shows speed-ups
tg = [1000, 30000, 1000000]
thead = "".join(f"
{'1M' if t >= 1e6 else f'{t // 1000}k'} vertices
" for t in tg)
tr = []
dflt = s[(s.layers == 128) & (s.atoms == 2048)].groupby("target")
for task, lab, col in (("hull", "convex hull", "qhull_ms"), ("volume", "volume", "tetra_ms"), ("obb", "OBB", "trimesh_obb_ms"), ("sphere", "smallest sphere", "sphere_exact_ms")):
bm = dflt[col].median()
fm = dflt.volume_ms.median() if task == "volume" else dflt[f"default_{task}_ms"].median()
tr.append(f"
{lab}: baseline
" + "".join(f"
{bm[t]:.3g}
" for t in tg) + "
")
tr.append(f"
{lab}: FCP default
" + "".join(f"
{fm[t]:.3g}
" for t in tg) + "
")
trows = "".join(tr)
# encoding table: median over the four objects, per mesh size
enc = s.groupby(["layers", "atoms", "target"]).encode_ms.median().unstack("target")
ehead = "".join(f"
{'1M' if t >= 1e6 else f'{int(t / 1e3)}k'} vertices
" for t in enc.columns)
erows = "".join(f"
{L}
{A}
" + "".join(f"
{f(v / 1e3 if v >= 1e3 else v, 2 if v >= 1e3 else 0)}{' s' if v >= 1e3 else ' ms'}
" for v in row) + "
"
for (L, A), row in enc.iterrows())
loads = (g.load.max(), s.load.max())
cpu = [l.split(":", 1)[1].strip() for l in open("/proc/cpuinfo") if l.startswith("model name")][0]
verdict = []
for task, label, _ in TASKS:
t = P[P.task == task].set_index("pick")
best = t.loc["balanced"] if "balanced" in t.index else t.iloc[0]
verdict.append((label, best))
wl = {"convex hull": "largest gap to the true hull", "volume": None}
vt = "".join(f"
{'–' if l == 'volume' else f(r.gap_max if l == 'convex hull' else r.out_max, 2) + ' % (' + ('largest gap to the true hull' if l == 'convex hull' else 'farthest vertex outside') + ')'}
"
for l, r in verdict)
html = f"""
Tradeoffs: speed against accuracy, one thread
Each geometric query from the descriptor against the standard route from the mesh, on the CPU with one thread for
every method (numba, OpenMP and BLAS pinned to one thread; {cpu}). Twelve objects (the collision section's), encoded
from their meshes at 64, 128 and 256 layers and 512, 2048 and 6144 atoms (package v5.31, commit db3e6ceb); for the hull and
the bounds also 16, 32, 64 and 128 directions M and 64, 128 and 256 samples per ring, and for the OBB the descriptor's own
frame or its own and the world's: {len(c)} configurations over the five tasks, every one on every object. Exact references from the mesh:
the convex hull's volume (qhull), the mesh's volume, its AABB, the smaller of trimesh's and Open3D's minimal boxes, the exact
smallest ball. Encoding is not in these times (its own table below). Times are medians after a warm-up, taken while
the load average was logged; objects first timed under another job's load (above 3) were timed again
on a quiet machine (load average at most {f(loads[0], 1)} for the times shown).
Baseline first: the exact standard route is the star at 1× and 100 %, and better is always towards the top
right. x: speed-up over the baseline (geometric mean over the 12 objects, log scale; left of 1× is slower). y: accuracy,
100 % minus the size error (each object's error, then the median over the objects; the whisker reaches the worst object). FCP is shown at its three settings
for each task, those of the tables below: accurate (the least median error of the {len(c)} configurations),
balanced (the fastest within 1 % median error whose worst case stays within 1 % of the diagonal: the farthest vertex
outside a bound; for the hull its largest gap to the true hull, within 2 %, since no setting reaches 1 %; for the volume the
worst object's error, within 1 %), fast (the fastest within 5 % median error, with no limit on the worst case). Crosses
are other standard routes; those off the scale are noted in the panel with their numbers.
{''.join(tables)}
Mesh size. The standard routes' cost grows with the mesh; the descriptor's does not (its size is set by the
layers and atoms). Four objects (mug, dino, horse, knot) resampled to 1k–1M vertices (quadric decimation, Loop
subdivision); per size the exact references are recomputed. FCP at three fixed settings: low (64 layers, 512 atoms, M = 16,
64 samples), default (128, 2048, 64, 128) and high (256, 6144, 128, 256).
Baseline first, the black line at 1× and 100 %; better is always up and right. Top: FCP's speed-up over the
baseline against the mesh's vertices (median over the four objects, log-log, encoding excluded): above 1× FCP is faster. Bottom:
FCP's accuracy at each mesh size (each object's error, then the median). The OBB's baseline here is trimesh's minimum-volume box alone (Open3D's minimal box took
29 ms to 3.8 s on the 12 objects, 3.8 s on the 14k-vertex knot, too slow for the sweep); trimesh's is not always minimal.
time, ms
{thead}
{trows}
FCP faster from (vertices)
low
default
high
{''.join(xr)}
Encoding (one thread, from the mesh; median over the four objects; once per object, then every query above):
layers
atoms
{ehead}
{erows}
Verdict at the balanced setting of each task (12 objects, one thread):
task
speed against the exact standard route
size error, median (worst object)
worst case, % of the diagonal
{vt}
"""
(SECTION / "tradeoffs_section.html").write_text(html)
readme = (SECTION / "README.txt").read_text()
note = ("tradeoffs_*: ~/code/data/meshes/fcp_3010_hull/scripts/: tradeoffs.py (base, o3d, grid, retime: out/tr_base.csv, tr_o3d.csv, "
"tr_grid.csv), tradeoffs_sizes.py (make, o3d, run: out/tr_sizes*.csv), then tradeoffs_figs.py (tradeoffs_scatter.png, "
"tradeoffs_sizes.png, tradeoffs_configs.csv, tradeoffs_section.html). One thread everywhere.")
lines = [l for l in readme.splitlines() if not l.startswith("tradeoffs_*")] + [note]
(SECTION / "README.txt").write_text("\n".join(lines).rstrip("\n") + "\n")
if __name__ == "__main__":
g, b = load()
c = configs(g)
P = pick(c)
c.to_csv(SECTION / "tradeoffs_configs.csv", index=False)
scatter(c, b, P)
if (OUT / "tr_sizes.csv").exists():
sizes_fig(pd.read_csv(OUT / "tr_sizes.csv"))
section(c, P, b)
print(P[["task", "pick", "layers", "atoms", "M", "n_t", "frames", "time_ratio", "ms_med", "base_ms_med", "size_med", "err_med", "err_max", "out_max", "load_max"]].round(4).to_string())
