Overlay Reconstruction

o17.5.3 fixes the constructive assembly shape before full overlay kernels land.

For debugging workflow, pinned-pair isolation, and regression strategy, see docs/testing/overlay-debugging-playbook.md.

Request Signals

  • union reconstruction

  • difference reconstruction

  • symmetric difference

  • overlay assembly

  • face labeling

  • cccl

Open First

  • docs/architecture/overlay-reconstruction.md

  • docs/architecture/segment-primitives.md

  • src/vibespatial/overlay/reconstruction.py

  • tests/test_overlay_reconstruction.py

Verify

  • uv run pytest tests/test_overlay_reconstruction.py tests/test_segment_primitives.py

  • uv run python scripts/check_docs.py --check

Risks

  • Monolithic overlay kernels would hide the exact stage boundaries needed for CCCL.

  • If stable ordering is not explicit, later dissolve and overlay assembly will drift from pandas-facing semantics.

  • Union, difference, and symmetric difference should not each invent separate topology assembly logic.

Intent

Define one staged reconstruction plan from classified segments to geometry output buffers so later constructive kernels share the same graph.

Options Considered

  1. One bespoke kernel per overlay operation. Fast to sketch, but it duplicates topology assembly and destroys reuse.

  2. Keep using host-side Shapely for all reconstruction. Correct on CPU, but it provides no owned assembly seam for GPU work.

  3. Shared staged reconstruction. Classify segments once, emit nodes once, build directed edges once, label faces once, then apply operation-specific selection at the end.

Decision

Use option 3.

The shared plan is:

  • classify candidate segment pairs

  • emit nodes and split segments at intersections

  • stable-sort directed half-edges

  • walk rings and open chains

  • label faces and chains by source coverage

  • select union/difference/symmetric-difference outputs

  • emit geometry buffers in deterministic order

CCCL Mapping

The intended GPU execution is:

  • compaction of ambiguous segment rows

  • device-side split-event emission for endpoints, touches, proper crosses, and overlaps

  • stable sort for half-edge grouping

  • prefix sums for segment splitting and output sizing

  • reduce-by-key for face labeling and chain aggregation

  • scatter/gather for output restoration

That keeps the expensive topology decisions localized and reusable across overlay operations.

Consequences

  • public overlay() now chooses an execution family before heavy work starts (broadcast_right_intersection, broadcast_right_difference, coverage_union, grouped_union, or generic_reconstruction) and records that family in dispatch telemetry

  • every constructive family still lowers through one canonical NativeTabularResult boundary, so planner selection changes execution shape without reintroducing host-side composition trees

  • Phase 5 now has one reconstruction graph instead of operation-specific glue

  • o17.9.6.2 lands the device split-event and directed-edge primitive that feeds the later half-edge graph work

  • o17.9.6.3 adds canonical node ids, deterministic next_edge traversal, and bounded-face labeling on top of that directed-edge table

  • o17.9.6.4 is allowed to route simple axis-aligned rectangle batches into a dedicated fast path when the generic shared graph would have the wrong performance shape for pairwise box intersections

  • o17.5.5 can build dissolve on top of the same union reconstruction

  • o17.9.6.6 reuses the same bounded-face labels for union, difference, symmetric_difference, and geometry-only identity selectors instead of forking new topology assembly code

  • current GPU overlay output support remains polygon-only at the input seam; mixed-family constructive overlay stays explicitly unsupported until a later change widens the kernel contract

  • later GPU overlay work has an explicit CCCL-friendly assembly seam

  • half-edge node construction sorts source endpoints once and derives target node ids from adjacent twins; node and radial orders use exact stable radix passes instead of duplicated endpoint relations or stacked fp64 key matrices; coordinate keys stream one pass at a time, endpoint grouping reads the sorted permutation directly, and an edge-parallel segmented merge derives radial successors from sparse node offsets without quadratic per-node insertion sorting; source tangents participate only when endpoint subtraction collapses a nonzero component on an atom with exactly one representable fp64 step

  • successor ids are an int32 graph contract through face walk and assembly; face tables retain unordered membership from the first face-id sort and use successors for traversal, production graphs omit diagnostic node/radial arrays, and boundary cycles require neither list ranking nor a rank-key sort

  • assembly scatters selected-face state directly to edge bits instead of rebuilding an edge-to-face inverse; hole classification is block-per-face, while boundary successors and coordinate traversal are sized from the compact boundary relation

  • aligned, grouped, and single-row known-coverage unions share one exact undirected-segment reducer whose radix keys and run comparisons stream one column at a time

  • an oversized row with strictly separated combined polygon-part x intervals lowers to independent synthetic topology rows; grouped right-side parts keep same-side splitting, and interval-disjoint results pack back without a union

  • device geometry concat compacts active coordinate and nested-offset prefixes into retained capacity, so topology pages do not read terminal offsets on host

  • a connected aligned interval component that exceeds the final graph target lowers through MicrocellOverlayExecutionPlan: complete x intervals page at a fixed membership budget, vertical seams atomize by exact endpoint scans, surviving boundary atoms feed the canonical half-edge graph, and contour nesting restores holes and islands without host union-find or grouped cell union; grouped-right indirection remains on its existing exact topology path

  • grouped topology carries signed left/right winding deltas through atomic segment deduplication and partial-overlap renoding; exact source-ring signs ignore duplicate, zero-length, and collinear extreme runs

  • exact cycle orientation labels bounded faces without a shoelace-area epsilon; multi-block incidence propagation removes the former single-block face limit

  • component nesting uses fixed-capacity interval-tree traversal with one block per root, exact orient2d containment, and no quadratic face-pair relation

  • boundary extraction peels leaves and the two-core with one O(E) CAS graph pass, then reuses component nesting hints during ring assembly

  • split-event execution has no host synchronization in its admitted path; structural allocation and named physicalization own all sizing boundaries

  • many-vs-one (N-vs-1) overlay uses a three-tier strategy that bypasses the full reconstruction graph for the common broadcast_right workload shape: (1) containment bypass identifies polygons fully inside the clip polygon and returns them unchanged, (2) batched Sutherland-Hodgman clip handles boundary-crossing simple polygons on GPU, (3) only complex remainder polygons fall through to the full per-group overlay pipeline