Repository navigation
overlay: Fast morphology fills no needle notches, whose depth exceeds the budget but which the disc cannot enter #340
Description
#330's Fast mode (overlay 0.3.18, ADR 0087) speeds up erosion of toothed rooms and holes by filling notches with proven chords. axioval/engine adopted it: a 0.4 m erosion of 10k-corner rooms takes 0.04–0.05 s. One shape gets no help: needle teeth, much deeper than they are apart.
Measured by axioval/engine: a 3 × 3 m room (and a column) with teeth 5 cm deep and 0.2 mm apart, a 0.4 m disc, a 1 mm Fast budget.
| corners | Exact | Fast |
|---|---|---|
| 2,000 | about 7 s, 1.7 GB | about 7 s, 1.7 GB |
| 10,000 | did not finish in 600 s | did not finish in 600 s |
Fast fills nothing here. Its proved excess for a chord is e = min(H, max d + g²/(8t)), with H the notch depth and d the corners' distance from the chord (overlay/src/fill.rs). For a 5 cm-deep notch, e ≈ 5 cm, far above the 1 mm budget, so every chord is refused.
That bound is loose for narrow notches. A disc of radius t cannot enter a notch narrower than its diameter by more than the sagitta t − √(t² − g²/4) ≈ g²/(8t), where g is the notch's width at its mouth. Here that is about 1.25e-8 m. Filling the notch therefore changes the eroded or dilated set by at most about that, whatever the notch's depth.
Needed
- Tighten Fast's excess bound with the reach of the disc into the notch. That is the sagitta of a chord of the notch's mouth width, for a notch whose walls stay at least that close to its mouth. Prove it as rigorously as the current bound (ADR 0087,
fill.rsmodule docs), and keepmin(H, …)as a ceiling. - Check that the side and the reported
excess()stay certified. - Look at Exact too: 7 s and 1.7 GB at 2,000 corners is far worse than overlay: erosion of toothed holes and dilation of toothed rooms still grow superlinearly #330's toothed rooms. The needle slivers presumably overlap far more, similar to overlay: union of a soup of grown triangles needs gigabytes for a single-polygon result #338. Profile it, but whether Exact gets faster is a separate decision.
Done when
- The needle room and column at 2,000 and 10,000 corners complete in Fast within the 1 mm budget, in about linear time.
excess()stays within the budget, and the result sits on its certified side, checked pointwise against Exact at 2,000 corners.- The cases are added to
disc_erosion. - A mutation probe covers the new bound.
Follow-up to #330. Reported by axioval/engine (engine#435).
Activity
GeneralPawz commentedon Oct 19, 2026
Triage: accepted, medium. axioval/engine already runs 20,000-corner budgets on Fast, so this only bites the needle shape.
Decision: tighten Fast's proved excess with the disc's reach into a notch. A disc of radius
tcan enter a notch whose mouth has widthg < 2tby at most the sagittat − √(t² − g²/4), provided the notch stays inside the slab its mouth chord spans. So filling such a notch changes the morphology by at most that much, whatever its depth. Prove it infill.rs's module docs as rigorously as the current bound, keepmin(H, …)as a ceiling, and keep side certification andexcess()exact.Profiling Exact on the needle shape is part of the task, but changing Exact is a separate decision.