Skip to content

overlay: fast disc erosion of floors with 100k+ sub-budget teeth in bounded time and memory #345

Open

Description

@GeneralPawz

Reported by axioval/engine (engine#445), against axiolid-overlay 0.3.19. After #341, ring validation is under 1 % of the profile. What remains is the disc erosion itself on toothed floors.

Case (synthetic, fully reproducible)

  • Call: Region::erode_outer_with(r, Tolerance::new(1e-9, 1e-9), MorphologyMode::fast(1e-3)). erode_inner_with builds the same way.
  • Input: a single Region::new polygon, a 3 × 3 m CCW square at the origin.
    • Bottom side: corners (k·3/n, 5e-4 if k odd else 0) for k = 0..n.
    • Top side: corners (3 − k·3/n, 3 − tooth(k)).
    • So the bottom and top sides carry teeth 0.5 mm deep into the room, and the polygon has 2(n+1) corners. The other two sides are straight.
  • Where the time goes: about 87 % is in ArcArrangement::new, then exact_arc::arrangement::build_charged and exact_arc::point::sign, inside Region::disc (minkowski.rs).
  • The fill: the fast fill keeps nearly every tooth, although every tooth is shallower than the 1 mm budget. The reported excess is about one tooth step, 6e-5 m at 100k corners.
r (m) corners time peak memory
1.4 100k 5.2 s 0.65 GB
1.4 150k 12.7 s 1.8 GB
1.49 200k 7.0 s 4.2 GB

At 50k corners the same room stays at or under 0.27 s and 31 MB for every radius. Times also jump with the tooth spacing: 99k corners at r = 1.6 m took 1.8 s. The consumer's pair-based cost model counts only about 1,000 pairs here, so this memory goes uncharged.

Needed (any one, in order of preference, to be decided in triage)

  • (a) MorphologyMode::Fast fills runs of teeth shallower than its budget, the excess reported as now and staying within the budget, so the arrangement sees the filled outline and not 100k corners.
  • (b) A budgeted disc morphology, like overlay_within (overlay: union of a soup of grown triangles needs gigabytes for a single-polygon result #338), that refuses by name before it allocates beyond a memory budget.
  • (c) A cost estimate the caller can charge before calling, stated as a bound.

Exact mode is unchanged. Fast mode stays an over- or under-approximation of stated side, with its excess reported (ADR 0087).

Done when

  • A committed benchmark (disc_erosion or a new one) covers this toothed room at 50k, 100k, 150k and 200k corners, at r = 1.4 m, 1.49 m and 1.6 m, with time and peak memory.
  • With (a): close to linear growth, with the excess checked against the budget. With (b): refusal before peak memory exceeds the budget.
  • A mutation probe shows that the new rule is load-bearing.

Related: #330 (Exact/Fast morphology), #338 (overlay_within budgets), #341 (ring validation), #323 (short and collinear edges).

Activity

  1. added
    needs-triageFiled but not yet accepted, sized, or scheduled
    optimizationDiscussion-sourced optimization; retype to Optimization once the org type exists
    on Oct 20, 2026
  2. GeneralPawz commented on Oct 20, 2026

    @GeneralPawz
    ContributorAuthor

    Consumer tracking moved: axioval/engine#445 closed with the 100k raise; the remaining need is axioval/engine#455, blocked by this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

needs-triageFiled but not yet accepted, sized, or scheduledoptimizationDiscussion-sourced optimization; retype to Optimization once the org type exists

Type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions