Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / modeling / stitch.lucb

## Stitch and Unstitch (surfacing Stage 3: Alias's Shell Stitch and
## Unstitch, Parasolid's sewing; ยง6.5 of luced-3d's
## docs/research/SURFACING-ALIAS-PLASTICITY.md).
##
## Stitch joins bodies (open surface bodies above all) into one where their
## boundary edges meet within a gap: vertices closer than the gap merge,
## the closest pairs first (SMLib's passes of a doubling tolerance, in
## their limit), never two of one face (a face thinner than the gap keeps
## its width: it is not glued to itself),
## an edge passing a merged vertex within the gap is cut there, and two
## edges between the same vertices whose middles lie within the gap become
## one edge the two faces share (the booleans' vertex and edge steps,
## boolean.lucb steps 1 and 3, at the gap). Faces are turned so neighbors
## agree, and a body whose every edge is shared becomes a closed solid.
##
## The joined edges keep the first face's curve; the other face lies off it
## by up to the gap. Each edge so made keeps that distance as its precision
## and each merged vertex its own (Parasolid's tolerant edges and
## vertices: BrepModel.edge_precision), so the model's tolerance is not
## widened for all of it; meshing reads the largest. The result's
## tolerant edges are then rebuilt where their faces' surfaces meet, and
## its vertices where theirs do (SMLib's edge refinement after sewing):
## their precision falls back under the tolerance; an open result's
## boundary edges keep their curves, their ends the rebuilt vertices. Where
## that changes the body's shape too much (a face's surface not reaching),
## the tolerant result stays.
##
## Unstitch is the other way: every face of a body its own open body, its
## edges its own.

## What a stitch did: the body, how many edges it joined, the widest gap
## it closed, and whether the result is closed.
pub struct Stitched:
    pub var model: interop.Reference[CadModel]
    pub var joined: i64
    pub var widest: f64
    pub var closed: bool

## `models` stitched within `gap` (see the file's header); with `tolerant`
## a closed result keeps its tolerant joins as they are (not rebuilt).
pub func stitch_models(models: const interop.Reference[CadModel][], gap: f64, tolerant: bool = false) -> Stitched!:
    if not (gap > 0.0) or not math.is_finite(gap) or gap > 1.0: error(invalid, "Stitch's gap is between 0 and 1 model units, as Alias's")
    if models.length == 0: error(invalid, "Stitch: pick the surfaces to join")
    var w = try shape_of(models[0].value())
    for at in 1..<models.length:
        var other = shape_of(models[at].value()) catch failure:
            w.close()
            error(failure.code, failure.message)
        defer other.close()
        append_shape(&w, &other) catch failure:
            w.close()
            error(failure.code, failure.message)
    # Slivers out and short edges collapsing (stitch_heal.lucb), before
    # the vertices merge.
    var collapse = Growing[i64]()
    defer collapse.close()
    heal_slivers(&w, gap, &collapse) catch failure:
        w.close()
        error(failure.code, failure.message)
    let faces = w.faces.count
    var work = Work(w, faces, 1.0, gap * 0.1, Growing[Vector3](), Growing[i64](), Growing[Cut](), Growing[Section](), Growing[Imprint](),
                    Growing[Coincident](), Growing[ShapeEdge](), Growing[i64](), Growing[usize](), Growing[i64](), Growing[bool]())
    defer work.close()
    var low = Vector3(1.0e300, 1.0e300, 1.0e300)
    var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
    for p in work.w.points.view():
        low = lower(low, p)
        high = upper(high, p)
    work.size = math.max(1e-6, high.subtract(low).length())
    # Edges used once (each face's boundary), before: what may join.
    var before = try stitch_open_edges(&work.w)
    # Vertices within the gap merge, the closest first (closest_merges).
    try closest_merges(&work, gap, collapse.view())
    try vertex_cuts(&work)
    try cut_edges(&work)
    # Each face's loops in final edges: each use replaced by its pieces.
    var pieces = try new_pieces()
    defer pieces.close()
    var piece_face = Growing[usize]()
    defer piece_face.close()
    var piece_name = Growing[i64]()
    defer piece_name.close()
    for f in 0..<faces:
        var at: usize = 0
        let uses = work.w.face_uses(f)
        for size in work.w.face_sizes(f):
            for use in uses[at..<at + (usize)size]:
                let e = edge_index(use)
                let first = work.piece_starts.items[e]
                let last = work.piece_starts.items[e + 1]
                for k in 0..<last - first:
                    let id = work.piece_ids.items[first + k if use > 0 else last - 1 - k]
                    # A short edge collapsed to one vertex is gone.
                    if try collapsed_piece(&work, id, gap): continue
                    try pieces.uses.push(id if use > 0 else -id)
            at += (usize)size
            try pieces.cycle_starts.push(pieces.uses.count)
            try pieces.pieces.push(pieces.cycle_starts.count - 2)
        try pieces.piece_starts.push(pieces.pieces.count)
        try piece_face.push(f)
        try piece_name.push(work.w.faces.items[f].name)
    # How far apart the edges each final edge joins lie (sampled); joined
    # edges farther apart than the gap (their middles matched, their
    # bulges did not) refuse.
    var gaps = Growing[f64]()
    defer gaps.close()
    try gaps.fill(work.finals.count, 0.0)
    for e in 0..<work.w.edges.count:
        let original = work.w.edges.items[e]
        for k in work.piece_starts.items[e]..<work.piece_starts.items[e + 1]:
            let id = edge_index(work.piece_ids.items[k])
            let final = work.finals.items[id]
            for step in 0..<9:
                let p = try work.w.at(final.carrier, final.t0 + (final.t1 - final.t0) * (f64)step / 8.0)
                let t = try nearest_on(&work.w, original.carrier, p, original.t0, original.t1)
                gaps.items[id] = math.max(gaps.items[id], (try work.w.at(original.carrier, t)).subtract(p).length())
    for g in gaps.view():
        if g > gap * 1.5: error(invalid, "Stitch: two edges joined at their ends lie farther apart than the gap between them")
    var turn = Growing[bool]()
    defer turn.close()
    try orient_shell(&work, &pieces, &turn)
    var keep = Growing[bool]()
    defer keep.close()
    try keep.fill(faces, true)
    let after = try stitch_open_pieces(&work, &pieces)
    if after >= before: error(invalid, "Stitch: no boundary edges lie within the gap of each other (widen Gap to close larger gaps)")
    # The models' own tolerance stays the body's; joins widen only theirs.
    var base = 0.0
    for model in models:
        let b = model.value().brep() else error(invalid, "Stitch needs B-rep bodies")
        base = math.max(base, b.base_tolerance())
    var made = try write_pieces(&work, &pieces, piece_face.view(), piece_name.view(), keep.view(), turn.view(), false, 0.0, base, gaps.view())
    errdefer made.release()
    let widest = try tolerant_joins(made.value(), gap, base)
    # Tolerant edges rebuilt where their faces' surfaces meet
    # (rebuilt_joins): their precision falls back under the tolerance. An
    # open result's boundary keeps its curves.
    if widest > base and not tolerant:
        if let exact = try rebuilt_joins(made.value(), base, after > 0):
            made.release()
            made = exact
            _ = try tolerant_joins(made.value(), gap, base)
    return Stitched(made, (i64)(before - after) // 2, widest, after == 0)

## How many edges of `w` one face uses once and no other face uses.
func stitch_open_edges(w: const Shape*) -> usize!:
    var counts = Growing[i64]()
    defer counts.close()
    try counts.fill(w.edges.count, 0)
    for f in 0..<w.faces.count:
        for use in w.face_uses(f): counts.items[edge_index(use)] += 1
    var open: usize = 0
    for c in counts.view():
        if c == 1: open += 1
    return open

## How many final edges the stitched faces use once.
func stitch_open_pieces(work: const Work*, pieces: const Pieces*) -> usize!:
    var counts = Growing[i64]()
    defer counts.close()
    try counts.fill(work.finals.count, 0)
    for use in pieces.uses.view(): counts.items[edge_index(use)] += 1
    var open: usize = 0
    for at in 0..<counts.count:
        if counts.items[at] == 1: open += 1
        if counts.items[at] > 2: error(invalid, "Stitch: more than two faces would meet at an edge; stitch them in smaller sets")
    return open

## Which faces to turn so every shared edge is used once each way: from
## each face not yet reached, its neighbors across shared edges, turned
## when they use the edge the same way. A shell that cannot agree (a
## Moebius band) refuses.
func orient_shell(work: const Work*, pieces: const Pieces*, turn: Growing[bool]*) -> !:
    let count = pieces.piece_count()
    try turn.fill(count, false)
    var reached = Growing[bool]()
    defer reached.close()
    try reached.fill(count, false)
    # Each final edge's users: piece and way.
    var users = Growing[i64]()
    defer users.close()
    try users.fill(work.finals.count * 2, 0)
    for p in 0..<count:
        for c in pieces.piece_cycles(p):
            for use in pieces.cycle(c):
                let e = edge_index(use)
                let signed = ((i64)p + 1) * (1 if use > 0 else -1)
                if users.items[e * 2] == 0: users.items[e * 2] = signed
                elif users.items[e * 2 + 1] == 0 and edge_index(users.items[e * 2]) != p: users.items[e * 2 + 1] = signed
    var queue = Growing[usize]()
    defer queue.close()
    for start in 0..<count:
        if reached.items[start]: continue
        reached.items[start] = true
        queue.clear()
        try queue.push(start)
        var head: usize = 0
        while head < queue.count:
            let p = queue.items[head]
            head += 1
            for c in pieces.piece_cycles(p):
                for use in pieces.cycle(c):
                    let e = edge_index(use)
                    let a = users.items[e * 2]
                    let b = users.items[e * 2 + 1]
                    if a == 0 or b == 0: continue
                    let mine = a if edge_index(a) == p else b
                    let theirs = b if edge_index(a) == p else a
                    let q = edge_index(theirs)
                    # Same way (after this face's own turn): turn the other.
                    let same = ((mine > 0) != turn.items[p]) == (theirs > 0)
                    if reached.items[q]:
                        if same != turn.items[q]: error(invalid, "Stitch: the faces cannot all face one way (a one-sided shell)")
                        continue
                    turn.items[q] = same
                    reached.items[q] = true
                    try queue.push(q)
    # Faces turned run their loops backwards in write_pieces; their normal
    # turns with them, so the body faces one way.

## Precision for `model`'s edges and vertices after a stitch within `gap`:
## each edge shared by two faces keeps the most of the gap it closed (set
## as it was written) and how far its faces' surfaces lie from it
## (sampled), each vertex the most of its edges'; only when more than
## `base`. Refused when an edge's faces lie farther than the gap. The
## widest found.
func tolerant_joins(model: const CadModel*, gap: f64, base: f64) -> f64!:
    let b = model.brep() else error(invalid, "Stitch made no B-rep")
    var w = try shape_of(model)
    defer w.close()
    let brep = (BrepModel*)b
    var widest = 0.0
    var vertex_most = Growing[f64]()
    defer vertex_most.close()
    try vertex_most.fill(w.points.count, 0.0)
    for e in 0..<w.edges.count:
        let f1 = w.sides.items[e * 2]
        let f2 = w.sides.items[e * 2 + 1]
        if f1 < 0 or f2 < 0: continue
        var most = try b.edge_precision_of((i64)e)
        if most <= base: most = 0.0
        for k in 0..<17:
            let p = try w.edge_at(e, (f64)k / 16.0)
            most = math.max(most, try gap_off_surface(&w.surfaces.items[(usize)w.faces.items[(usize)f1].surface], p))
            most = math.max(most, try gap_off_surface(&w.surfaces.items[(usize)w.faces.items[(usize)f2].surface], p))
        if most > gap * 1.5: error(invalid, "Stitch: a joined edge lies farther from its faces than the gap")
        widest = math.max(widest, most)
        if most > base:
            try brep.set_edge_precision((i64)e, most)
            let edge = w.edges.items[e]
            vertex_most.items[(usize)edge.start] = math.max(vertex_most.items[(usize)edge.start], most)
            vertex_most.items[(usize)edge.end] = math.max(vertex_most.items[(usize)edge.end], most)
    for v in 0..<vertex_most.count:
        let now = try b.vertex_precision_of((i64)v)
        if vertex_most.items[v] > now: try brep.set_vertex_precision((i64)v, vertex_most.items[v])
    return widest

## How far `p` lies from surface `s`.
func gap_off_surface(s: const Surface*, p: Vector3) -> f64!:
    if s.kind != surface_spline: return surface_distance(s, p)
    # Newton from the four nearest points of a 17 by 17 lattice: from the
    # nearest of 9 by 9 alone a surface turning sharply (a fill rising off
    # walls) led it to a stationary point off the true foot.
    var seeds: Vector3[4] = [Vector3(0.5, 0.5, 0.0), Vector3(0.5, 0.5, 0.0), Vector3(0.5, 0.5, 0.0), Vector3(0.5, 0.5, 0.0)]
    var near: f64[4] = [1.0e300, 1.0e300, 1.0e300, 1.0e300]
    for i in 0..<(usize)17:
        for j in 0..<(usize)17:
            let at = Vector3((f64)i / 16.0, (f64)j / 16.0, 0.0)
            var d = (try evaluate(*s, at)).subtract(p).length()
            var place = at
            for k in 0..<(usize)4:
                if d < near[k]:
                    let (kept_d, kept_at) = (near[k], seeds[k])
                    near[k] = d
                    seeds[k] = place
                    d = kept_d
                    place = kept_at
    var best = near[0]
    for k in 0..<(usize)4:
        if near[k] > 1.0e299: break
        let uv = try nearest_parameters(*s, p, seeds[k], false)
        best = math.min(best, (try evaluate(*s, uv)).subtract(p).length())
    return best

## Every face of `model` an open body of its own, its edges its own
## (Unstitch).
pub func unstitch_model(model: const CadModel*, out: Growing[interop.Reference[CadModel]]*) -> !:
    let count = model.face_count()
    if count == 0: error(invalid, "Unstitch: the body has no faces")
    for f in 0..<count:
        let one: i64[1] = [f]
        let piece = try model.subset(one[..<1])
        out.push(piece) catch failure:
            piece.release()
            error(failure.code, failure.message)

## Alias's Stitch options for CAD export (Detach periodic surfaces, Detach
## single curve boundaries), on a stitched body: what it did.
pub struct Detached:
    pub var model: interop.Reference[CadModel]
    ## Periodic faces split in two, and closed edges split in two.
    pub var periodic: i64
    pub var single: i64

## `model` made ready for systems that refuse faces wrapping round their
## surface and loops of one closed edge:
##   - `wrapping` (periodic): a face going round its surface's axis (it uses a seam
##     edge both ways: a cylinder's, a cone's or a sphere's side, a torus
##     once each way round) is split in two by the plane through the axis
##     and the seam, so each half meets the seam once; a torus is cut
##     again by its equator plane (its other seam);
##   - `single`: an edge closing on itself alone as a loop (a disc's circle,
##     a hemisphere's equator) is split at its middle into two edges.
## A periodic B-spline face (closed rows of its own) is refused: rebuild it
## open first. A body with nothing to detach comes back as it is.
pub func detached(model: interop.Reference[CadModel], wrapping: bool, single: bool) -> Detached!:
    var current = model.clone()
    errdefer current.release()
    var splits: i64 = 0
    if wrapping:
        # Faces need names to be picked by: the unnamed ones get them.
        let named = try CadModeling.tagged(current, "#detach")
        current.release()
        current = named
        # One face at a time, its seams by the shape as it is now.
        for _ in 0..<64:
            var w = try shape_of(current.value())
            defer w.close()
            var found: i64 = -1
            var seam: i64 = -1
            for f in 0..<w.faces.count:
                seam = seam_of(&w, f)
                if seam >= 0:
                    found = (i64)f
                    break
            if found < 0: break
            let s = &w.surfaces.items[(usize)w.faces.items[(usize)found].surface]
            if s.kind == surface_spline: error(invalid, "Detach periodic surfaces: a closed B-spline face is not split; rebuild it open first")
            if s.kind == surface_plane: break
            let edge = w.edges.items[(usize)seam]
            let middle = try w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
            let off = middle.subtract(s.origin)
            let radial = off.subtract(s.z.multiply_scalar(off.dot(s.z)))
            # A torus's seam round its axis (the ring) is cut by the
            # equator plane; one along its tube by the axis plane.
            var normal = s.z
            if s.kind != surface_torus or (try edge_axis_reach(&w, (usize)seam, s)) > 1e-9 * (s.radius + s.angle):
                normal = s.z.cross(radial).normalized() catch failure: error(invalid, "Detach periodic surfaces: the seam lies on the axis")
            let along = (try radial.normalized()) if radial.length() > 0.0 else s.x
            var plane = try plane_surface(s.origin, along, normal)
            defer plane.close()
            var chosen = Growing[bool]()
            defer chosen.close()
            try chosen.fill(w.faces.count, false)
            chosen.items[(usize)found] = true
            let split = try split_faces_by(current.value(), chosen.view(), &plane, "#detach")
            current.release()
            current = split
            splits += 1
    var closed_edges: i64 = 0
    if single:
        var w = try shape_of(current.value())
        defer w.close()
        closed_edges = try split_closed_loops(&w)
        if closed_edges > 0:
            let b = try brep_of(&w)
            defer b.release()
            let made = try CadModel.of_brep(b)
            current.release()
            current = made
    return Detached(current, splits, closed_edges)

## An edge face `f` uses both ways in one loop (its seam), or -1.
func seam_of(w: const Shape*, f: usize) -> i64:
    let uses = w.face_uses(f)
    for a in 0..<uses.length:
        for b in a + 1..<uses.length:
            if uses[a] == -uses[b]: return (i64)edge_index(uses[a])
    return -1

## How far a torus's seam edge `e` strays along its axis from the
## equator plane (0 for the ring, which the equator plane cuts).
func edge_axis_reach(w: const Shape*, e: usize, s: const Surface*) -> f64!:
    var most = 0.0
    for k in 0..<5:
        let p = try w.edge_at(e, (f64)k / 4.0)
        most = math.max(most, math.abs(p.subtract(s.origin).dot(s.z)))
    return most

## Every closed edge that alone makes a loop split at its middle into two
## edges (each loop using it uses both halves); how many were split.
func split_closed_loops(w: Shape*) -> i64!:
    var second = Growing[i64]()
    defer second.close()
    try second.fill(w.edges.count, -1)
    var count: i64 = 0
    for f in 0..<w.faces.count:
        let uses = w.face_uses(f)
        var at: usize = 0
        for size in w.face_sizes(f):
            if size == 1:
                let e = edge_index(uses[at])
                let edge = w.edges.items[e]
                if edge.start == edge.end and second.items[e] < 0:
                    let mid = (edge.t0 + edge.t1) * 0.5
                    let v = try w.add_point(try w.at(edge.carrier, mid))
                    second.items[e] = try w.add_edge(ShapeEdge(edge.carrier, mid, edge.t1, v, edge.end))
                    w.edges.items[e].t1 = mid
                    w.edges.items[e].end = v
                    while w.edge_slack.count < w.edges.count - 1: try w.edge_slack.push(0.0)
                    try w.edge_slack.push(w.edge_slack_of(e))
                    count += 1
            at += (usize)size
    if count == 0: return 0
    # The loops again, each split edge's use followed (or, backwards,
    # preceded) by its second half's.
    var uses = Growing[i64]()
    defer uses.close()
    var sizes = Growing[i64]()
    defer sizes.close()
    for f in 0..<w.faces.count:
        let first = uses.count
        let loop_first = sizes.count
        let old = w.face_uses(f)
        var at: usize = 0
        for size in w.face_sizes(f):
            var made: i64 = 0
            for use in old[at..<at + (usize)size]:
                let other = second.items[edge_index(use)] if edge_index(use) < second.count else -1
                if other < 0:
                    try uses.push(use)
                    made += 1
                elif use > 0:
                    try uses.push(use)
                    try uses.push(other + 1)
                    made += 2
                else:
                    try uses.push(-(other + 1))
                    try uses.push(use)
                    made += 2
            try sizes.push(made)
            at += (usize)size
        w.faces.items[f].first = first
        w.faces.items[f].count = uses.count - first
        w.faces.items[f].loop_first = loop_first
    try w.uses.assign(uses.view())
    try w.sizes.assign(sizes.view())
    try w.index_sides()
    return count

## `model` (closed) with its tolerant edges (precision over `base`) and
## their faces' other edges found again where the faces' surfaces meet,
## and their vertices where theirs do: Offset Face's machinery with each
## face replaced by its own surface (face_moves.lucb). None when that
## refuses.
func rebuilt_joins(model: const CadModel*, base: f64, open: bool = false) -> interop.Reference[CadModel]?!:
    let b = model.brep() else return none
    var w = try shape_of(model)
    defer w.close()
    var chosen = Growing[bool]()
    defer chosen.close()
    try chosen.fill(w.faces.count, false)
    for e in 0..<w.edges.count:
        if (try b.edge_precision_of((i64)e)) <= base: continue
        for side in 0..<(usize)2:
            let f = w.sides.items[e * 2 + side]
            if f >= 0: chosen.items[(usize)f] = true
    var faces = Growing[usize]()
    defer faces.close()
    var targets = Growing[Surface]()
    defer:
        for k in 0..<targets.count: targets.items[k].close()
        targets.close()
    var senses = Growing[bool]()
    defer senses.close()
    for f in 0..<w.faces.count:
        if not chosen.items[f]: continue
        try faces.push(f)
        try targets.push(try surface_copy(&w.surfaces.items[(usize)w.faces.items[f].surface]))
        try senses.push(w.faces.items[f].sense)
    if faces.count == 0: return none
    # The precision the stitch gave is found again from the new geometry;
    # the body's tolerance is its faces' own again (shape_of reads the
    # largest).
    w.tolerance = base
    for e in 0..<w.edge_slack.count: w.edge_slack.items[e] = 0.0
    for p in 0..<w.point_slack.count: w.point_slack.items[p] = 0.0
    let m = FaceMove(move_replace, Vector3(), Vector3(), Vector3(), 0.0, 0.0)
    var no_distances = Growing[f64]()
    defer no_distances.close()
    let made = substitute(&w, faces.view(), &m, targets.view(), senses.view(), no_distances.view(), open) catch failure:
        if failure.code != invalid: error(failure.code, failure.message)
        return none
    return made

## Whether final edge piece `id` (signed) runs from a vertex back to it
## within `gap` (a short edge whose ends merged): no edge at all.
func collapsed_piece(work: const Work*, id: i64, gap: f64) -> bool!:
    let final = work.finals.items[edge_index(id)]
    if final.start != final.end: return false
    let middle = try work.w.at(final.carrier, (final.t0 + final.t1) * 0.5)
    return middle.subtract(work.vertices.items[(usize)final.start]).length() <= gap

## Each point of `work`'s shape its merged vertex (`work.point_vertex`):
## pairs within `gap` merged closest first, unless the two groups hold a
## point of one face between them (that face would lose an edge). The
## point pairs `collapse` (short edges' ends, stitch_heal.lucb) merge
## before any, though one face holds both. Each vertex sits at its
## group's first point, its zone reaching its farthest.
func closest_merges(work: Work*, gap: f64, collapse: const i64[]) -> !:
    let w = &work.w
    let n = w.points.count
    # The faces at each point (by its edges), as pairs (point, face).
    var at_point = Growing[i64]()
    defer at_point.close()
    for f in 0..<w.faces.count:
        for use in w.face_uses(f):
            let edge = w.edges.items[edge_index(use)]
            for v in [edge.start, edge.end]:
                try at_point.push(v)
                try at_point.push((i64)f)
    # Candidate pairs within the gap, by distance.
    var pairs = Growing[f64]()
    defer pairs.close()
    var order = Growing[usize]()
    defer order.close()
    var keys = Growing[f64]()
    defer keys.close()
    for i in 0..<n:
        for j in i + 1..<n:
            let d = w.points.items[i].subtract(w.points.items[j]).length()
            if d > gap: continue
            try keys.push(d)
            try pairs.push((f64)i)
            try pairs.push((f64)j)
    try order.fill(keys.count, 0)
    for k in 0..<order.count: order.items[k] = k
    # Insertion by distance (the pairs are few: boundary points near each
    # other).
    for k in 1..<order.count:
        var at = k
        while at > 0 and keys.items[order.items[at - 1]] > keys.items[order.items[at]]:
            let swap = order.items[at]
            order.items[at] = order.items[at - 1]
            order.items[at - 1] = swap
            at -= 1
    var group = Growing[usize]()
    defer group.close()
    for i in 0..<n: try group.push(i)
    var at_pair: usize = 0
    while at_pair + 1 < collapse.length:
        let a = union_root(group.items, (usize)collapse[at_pair])
        let b = union_root(group.items, (usize)collapse[at_pair + 1])
        if a != b: group.items[b if a < b else a] = a if a < b else b
        at_pair += 2
    for k in order.view():
        let a = union_root(group.items, (usize)pairs.items[k * 2])
        let b = union_root(group.items, (usize)pairs.items[k * 2 + 1])
        if a == b: continue
        # A face holding a point of each group refuses the merge.
        var shared = false
        var x: usize = 0
        while x < at_point.count and not shared:
            if union_root(group.items, (usize)at_point.items[x]) == a:
                let face = at_point.items[x + 1]
                var y: usize = 0
                while y < at_point.count:
                    if at_point.items[y + 1] == face and union_root(group.items, (usize)at_point.items[y]) == b:
                        shared = true
                        break
                    y += 2
            x += 2
        if shared: continue
        group.items[b if a < b else a] = a if a < b else b
    # One vertex per group, at its first point.
    var merged_at = Growing[i64]()
    defer merged_at.close()
    try merged_at.fill(n, -1)
    for i in 0..<n:
        let root = union_root(group.items, i)
        if merged_at.items[root] < 0:
            merged_at.items[root] = (i64)work.vertices.count
            try work.vertices.push(w.points.items[root])
            try work.zones.push(math.max(work.tol * 5.0, w.point_slack_of(root)))
        let v = (usize)merged_at.items[root]
        work.zones.items[v] = math.max(work.zones.items[v], w.points.items[i].subtract(work.vertices.items[v]).length())
        try work.point_vertex.push((i64)v)