Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / modeling / boolean.lucb

## Booleans of two closed solids, OpenCASCADE's General Fuse structure in
## a lean form (docs/research/CAD-MODELING-STUDY.md ยง3.1):
##
## 1. Both solids in one shape; vertices closer than the tolerance merged.
## 2. For each pair of faces whose boxes meet, where their surfaces meet
##    (intersect.lucb), each curve clipped to both faces: its crossings with
##    either face's boundary split it and the boundary edges (clip.lucb);
##    the stretches inside both faces become new edges across both. Faces on
##    one surface (coplanar ones above all: a sketch on a face extruded onto
##    it) imprint each other's boundaries instead.
## 3. Every edge cut at its split points; pieces with the same ends and the
##    same middle are one edge, so faces meeting along new edges share them.
## 4. Every face split along its new edges (split.lucb).
## 5. Each piece classified at a point well inside it: on the other solid's
##    coincident face (facing the same way or not), else inside or outside
##    the other solid by counting crossings of rays through its mesh.
## 6. The pieces the operation keeps: union, the outside ones; subtract,
##    the first's outside and the second's inside, turned; intersect, the
##    inside ones. Of coincident pieces one is kept or none.
## 7. Written as a new B-rep; an edge not used exactly twice, once each
##    way, means the result is not closed: an error, never a broken solid.

## Boolean operations (combine's `op`).
pub let op_union: i64 = 0
pub let op_subtract: i64 = 1
pub let op_intersect: i64 = 2

## Piece classes.
let class_out: i64 = 0
let class_in: i64 = 1
let class_same: i64 = 2
let class_opposite: i64 = 3

## Where an original edge is cut, by parameter.
struct Cut:
    var edge: usize
    var t: f64

## A new edge: an interval of a carrier between merged vertices, lying
## across faces fa and fb (fb -1 for one face).
struct Section:
    var edge: ShapeEdge
    var fa: i64
    var fb: i64

## Original edge `edge`'s pieces lie across face `face` where inside it.
struct Imprint:
    var face: usize
    var edge: usize

## Two faces on one surface; `same` when their normals agree.
struct Coincident:
    var fa: usize
    var fb: usize
    var same: bool

## The working state of one boolean.
struct Work:
    var w: Shape
    var faces_a: usize
    var size: f64
    var tol: f64
    ## Merged vertices, and each shape point's merged vertex.
    var vertices: Growing[Vector3]
    var point_vertex: Growing[i64]
    var cuts: Growing[Cut]
    var sections: Growing[Section]
    var imprints: Growing[Imprint]
    var coincident: Growing[Coincident]
    ## Final edges (vertices merged), and each original edge's pieces:
    ## piece_ids[piece_starts[e]..<piece_starts[e + 1]], from its start.
    var finals: Growing[ShapeEdge]
    var piece_ids: Growing[i64]
    var piece_starts: Growing[usize]
    var section_ids: Growing[i64]

    func close():
        self.w.close()
        self.vertices.close()
        self.point_vertex.close()
        self.cuts.close()
        self.sections.close()
        self.imprints.close()
        self.coincident.close()
        self.finals.close()
        self.piece_ids.close()
        self.piece_starts.close()
        self.section_ids.close()

    ## The merged vertex at `p`.
    func vertex(p: Vector3) -> i64!:
        for at in 0..<self.vertices.count:
            if self.vertices.items[at].subtract(p).length() <= self.tol * 10.0: return (i64)at
        try self.vertices.push(p)
        return (i64)self.vertices.count - 1

    ## The final edge for `edge` (vertices merged): an existing one with the
    ## same ends and middle, or a new one; and whether `edge` runs its way.
    func final_edge(edge: ShapeEdge) -> (i64, bool)!:
        let middle = try self.w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
        for at in 0..<self.finals.count:
            let other = self.finals.items[at]
            let same_ends = (other.start == edge.start and other.end == edge.end) or (other.start == edge.end and other.end == edge.start)
            if not same_ends: continue
            if (try self.w.at(other.carrier, (other.t0 + other.t1) * 0.5)).subtract(middle).length() > self.tol * 100.0: continue
            var forward = other.start == edge.start
            if edge.start == edge.end:
                # A closed edge: its way by the tangent in its middle.
                let mine = (try self.w.tangent(edge.carrier, (edge.t0 + edge.t1) * 0.5)).multiply_scalar(1.0 if edge.t1 > edge.t0 else -1.0)
                let theirs = (try self.w.tangent(other.carrier, (other.t0 + other.t1) * 0.5)).multiply_scalar(1.0 if other.t1 > other.t0 else -1.0)
                forward = mine.dot(theirs) > 0.0
            return ((i64)at, forward)
        try self.finals.push(edge)
        return ((i64)self.finals.count - 1, true)

    func is_a(f: usize) -> bool:
        return f < self.faces_a

## A box holding face `f` of `w`, never short of it (a pair of faces whose
## boxes miss is never met). A plane's face lies within its boundary's box;
## a curved face can bulge past its boundary, so it takes its surface's
## extent there: a cylinder's or cone's band between the boundary's
## heights, a sphere's ball, a torus whole, a B-spline's control net.
func face_box(w: const Shape*, f: usize) -> (Vector3, Vector3)!:
    var low = Vector3(1.0e300, 1.0e300, 1.0e300)
    var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
    for use in w.face_uses(f):
        let (l, h) = try edge_box(w, edge_index(use))
        low = lower(low, l)
        high = upper(high, h)
    let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
    if s.kind == surface_plane: return (low, high)
    if s.kind == surface_spline:
        low = Vector3(1.0e300, 1.0e300, 1.0e300)
        high = Vector3(-1.0e300, -1.0e300, -1.0e300)
        for p in s.points:
            low = lower(low, p)
            high = upper(high, p)
        return (low, high)
    if s.kind == surface_sphere:
        let r = Vector3(s.radius, s.radius, s.radius)
        return (s.origin.subtract(r), s.origin.add(r))
    if s.kind == surface_torus:
        # The ring's circle, widened by the tube.
        let (l, h) = circle_box(s.origin, s.z, s.radius)
        let tube = Vector3(s.angle, s.angle, s.angle)
        return (l.subtract(tube), h.add(tube))
    # A cylinder or cone between the boundary's lowest and highest heights
    # (from its box's corners): the circles there hold the band between
    # (a cone's points are blends of theirs).
    var bottom = 1.0e300
    var top = -1.0e300
    for corner in 0..<8:
        let p = Vector3(high.x if corner % 2 == 1 else low.x, high.y if (corner // 2) % 2 == 1 else low.y, high.z if corner >= 4 else low.z)
        let height = p.subtract(s.origin).dot(s.z)
        bottom = math.min(bottom, height)
        top = math.max(top, height)
    let slope = math.tan(s.angle) if s.kind == surface_cone else 0.0
    let r0 = math.abs(s.radius + bottom * slope)
    let r1 = math.abs(s.radius + top * slope)
    let (l0, h0) = circle_box(s.origin.add(s.z.multiply_scalar(bottom)), s.z, r0)
    let (l1, h1) = circle_box(s.origin.add(s.z.multiply_scalar(top)), s.z, r1)
    return (lower(l0, l1), upper(h0, h1))

## A box holding edge `e` of `w`: a line's ends, an arc's whole circle or
## ellipse, a B-spline's control points (it lies in their hull).
func edge_box(w: const Shape*, e: usize) -> (Vector3, Vector3)!:
    let edge = w.edges.items[e]
    let c = w.carriers.items[(usize)edge.carrier]
    if c.kind == curve_line:
        let a = try w.at(edge.carrier, edge.t0)
        let b = try w.at(edge.carrier, edge.t1)
        return (lower(a, b), upper(a, b))
    if c.kind == curve_circle or c.kind == curve_ellipse:
        # Along each axis, origin +- |(a x_i, b y_i)|.
        let reach = Vector3(math.sqrt(c.a * c.x.x * c.a * c.x.x + c.b * c.y.x * c.b * c.y.x),
                            math.sqrt(c.a * c.x.y * c.a * c.x.y + c.b * c.y.y * c.b * c.y.y),
                            math.sqrt(c.a * c.x.z * c.a * c.x.z + c.b * c.y.z * c.b * c.y.z))
        return (c.origin.subtract(reach), c.origin.add(reach))
    let (points, _, _, _) = w.spline_net(c.spline)
    var low = Vector3(1.0e300, 1.0e300, 1.0e300)
    var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
    for p in points:
        low = lower(low, p)
        high = upper(high, p)
    return (low, high)

## The box of the circle of `radius` about unit `axis` through `center`:
## along each axis e, center +- radius sqrt(1 - (axis . e)^2).
func circle_box(center: Vector3, axis: Vector3, radius: f64) -> (Vector3, Vector3):
    let reach = Vector3(radius * math.sqrt(math.max(0.0, 1.0 - axis.x * axis.x)), radius * math.sqrt(math.max(0.0, 1.0 - axis.y * axis.y)),
                        radius * math.sqrt(math.max(0.0, 1.0 - axis.z * axis.z)))
    return (center.subtract(reach), center.add(reach))

func lower(a: Vector3, b: Vector3) -> Vector3:
    return Vector3(math.min(a.x, b.x), math.min(a.y, b.y), math.min(a.z, b.z))

func upper(a: Vector3, b: Vector3) -> Vector3:
    return Vector3(math.max(a.x, b.x), math.max(a.y, b.y), math.max(a.z, b.z))

func boxes_meet(a: (Vector3, Vector3), b: (Vector3, Vector3), pad: f64) -> bool:
    let (al, ah) = a
    let (bl, bh) = b
    return al.x <= bh.x + pad and bl.x <= ah.x + pad and al.y <= bh.y + pad and bl.y <= ah.y + pad and al.z <= bh.z + pad and bl.z <= ah.z + pad

## `source` appended to `into`: indices moved past what `into` has.
func append_shape(into: Shape*, source: const Shape*) -> !:
    let points = (i64)into.points.count
    let carriers = (i64)into.carriers.count
    let edges = (i64)into.edges.count
    let surfaces = (i64)into.surfaces.count
    let splines = (i64)into.splines.count
    let spline_points = into.spline_points.count
    let spline_knots = into.spline_knots.count
    for p in source.points.view(): try into.points.push(p)
    for s in source.splines.view(): try into.splines.push(ShapeSpline(s.first + spline_points, s.count, s.knot_first + spline_knots, s.degree))
    for p in source.spline_points.view(): try into.spline_points.push(p)
    for w in source.spline_weights.view(): try into.spline_weights.push(w)
    for k in source.spline_knots.view(): try into.spline_knots.push(k)
    for c in source.carriers.view():
        var moved = c
        if moved.spline >= 0: moved.spline += splines
        try into.carriers.push(moved)
    for e in source.edges.view(): try into.edges.push(ShapeEdge(e.carrier + carriers, e.t0, e.t1, e.start + points, e.end + points))
    for s in source.surfaces.view():
        try into.surfaces.push(try Surface(s.kind, s.origin, s.x, s.z, s.radius, s.angle, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv))
    var uses = Growing[i64]()
    defer uses.close()
    for f in 0..<source.faces.count:
        uses.clear()
        for use in source.face_uses(f): try uses.push(use + edges if use > 0 else use - edges)
        try into.add_face(source.faces.items[f].surface + surfaces, source.faces.items[f].sense, uses.view(), source.face_sizes(f), try into.add_name(source.face_name(f)))

## `a` combined with `b` by `op` (op_union, op_subtract, op_intersect).
pub func combine(a: const CadModel*, b: const CadModel*, op: i64) -> interop.Reference[CadModel]!:
    var first = try shape_of(a)
    let faces_a = first.faces.count
    var second = try shape_of(b)
    defer second.close()
    try append_shape(&first, &second)
    var work = Work(first, faces_a, 1.0, 1e-9, Growing[Vector3](), Growing[i64](), Growing[Cut](), Growing[Section](), Growing[Imprint](),
                    Growing[Coincident](), Growing[ShapeEdge](), Growing[i64](), Growing[usize](), Growing[i64]())
    defer work.close()
    var low = Vector3(1.0e300, 1.0e300, 1.0e300)
    var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
    for f in 0..<work.w.faces.count:
        let (l, h) = try face_box(&work.w, f)
        low = Vector3(math.min(low.x, l.x), math.min(low.y, l.y), math.min(low.z, l.z))
        high = Vector3(math.max(high.x, h.x), math.max(high.y, h.y), math.max(high.z, h.z))
    work.size = math.max(1e-6, high.subtract(low).length())
    # Relative to the model's size, not the inputs' tolerances: results
    # are inputs again, and their tolerance must not grow from one to the
    # next.
    work.tol = math.max(work.size * 1e-7, 1e-10)
    for p in work.w.points.view(): try work.point_vertex.push(try work.vertex(p))
    try intersect_faces(&work)
    try vertex_cuts(&work)
    try cut_edges(&work)
    var others = try new_others(&work)
    defer others.close()
    return try assemble(&work, op, &others)

## Steps 2: new edges where faces of the two solids meet.
func intersect_faces(work: Work*) -> !:
    let w = &work.w
    var lows = Growing[Vector3]()
    defer lows.close()
    var highs = Growing[Vector3]()
    defer highs.close()
    for f in 0..<w.faces.count:
        let (l, h) = try face_box(w, f)
        try lows.push(l)
        try highs.push(h)
    var curves = Growing[Carrier]()
    defer curves.close()
    var hits = Growing[Hit]()
    defer hits.close()
    var ts = Growing[f64]()
    defer ts.close()
    for fa in 0..<work.faces_a:
        for fb in work.faces_a..<w.faces.count:
            if not boxes_meet((lows.items[fa], highs.items[fa]), (lows.items[fb], highs.items[fb]), work.tol * 10.0): continue
            let sa = w.faces.items[fa]
            let sb = w.faces.items[fb]
            curves.clear()
            var met = meet_curves
            if w.surfaces.items[(usize)sa.surface].kind == surface_spline or w.surfaces.items[(usize)sb.surface].kind == surface_spline:
                try spline_meet(w, fa, fb, work.tol, &curves)
            else:
                met = try meet(&w.surfaces.items[(usize)sa.surface], &w.surfaces.items[(usize)sb.surface], work.tol, &curves)
            if met == meet_march:
                # Where both faces are, a little more.
                let pad = Vector3(work.size * 0.01, work.size * 0.01, work.size * 0.01)
                let la = lows.items[fa]
                let lb = lows.items[fb]
                let ha = highs.items[fa]
                let hb = highs.items[fb]
                let box_low = Vector3(math.max(la.x, lb.x), math.max(la.y, lb.y), math.max(la.z, lb.z)).subtract(pad)
                let box_high = Vector3(math.min(ha.x, hb.x), math.min(ha.y, hb.y), math.min(ha.z, hb.z)).add(pad)
                try marched(w, fa, fb, box_low, box_high, work.size, work.tol, &curves)
                met = meet_curves
            if met != meet_curves:
                let same = (met == meet_same) == (sa.sense == sb.sense)
                try work.coincident.push(Coincident(fa, fb, same))
                try imprint(work, fa, fb)
                try imprint(work, fb, fa)
                continue
            for carrier in curves.view():
                let c = try w.add_carrier(carrier)
                var lowest = 0.0
                var highest = 2.0 * math.pi
                var closed = carrier.kind != curve_line
                if carrier.kind == curve_spline:
                    # A traced curve: its knots' range; closed when it ends
                    # where it starts.
                    highest = 1.0
                    closed = (try w.at(c, 0.0)).subtract(try w.at(c, 1.0)).length() <= work.tol * 10.0
                if carrier.kind == curve_line:
                    # The line across the two faces' boxes, and a margin.
                    lowest = 1.0e300
                    highest = -1.0e300
                    let al = lows.items[fa]
                    let ah = highs.items[fa]
                    for corner in 0..<8:
                        let p = Vector3(ah.x if corner % 2 == 1 else al.x, ah.y if (corner // 2) % 2 == 1 else al.y, ah.z if corner >= 4 else al.z)
                        let t = p.subtract(carrier.origin).dot(carrier.x)
                        lowest = math.min(lowest, t)
                        highest = math.max(highest, t)
                    lowest -= work.size * 0.1
                    highest += work.size * 0.1
                hits.clear()
                ts.clear()
                for side in 0..<2:
                    let f = fa if side == 0 else fb
                    for use in w.face_uses(f):
                        let e = edge_index(use)
                        let before = hits.count
                        try crossings(w, c, lowest, highest, e, work.size, work.tol, &hits)
                        for at in before..<hits.count: try work.cuts.push(Cut(e, hits.items[at].s))
                for hit in hits.view(): try ts.push(hit.t)
                sort.sort(ts.items[..<ts.count])
                try add_sections(work, c, closed, lowest, highest, ts.view(), fa, fb)

## The stretches of carrier `c` between consecutive crossings `ts` that lie
## inside both faces, as sections.
func add_sections(work: Work*, c: i64, closed: bool, low: f64, high: f64, ts: const f64[], fa: usize, fb: usize) -> !:
    let w = &work.w
    var bounds = Growing[f64]()
    defer bounds.close()
    for t in ts:
        if bounds.count > 0 and (try w.at(c, t)).subtract(try w.at(c, bounds.items[bounds.count - 1])).length() <= work.tol * 10.0: continue
        try bounds.push(t)
    if closed:
        if bounds.count > 1 and (try w.at(c, bounds.items[0])).subtract(try w.at(c, bounds.items[bounds.count - 1])).length() <= work.tol * 10.0:
            bounds.count -= 1
        if bounds.count == 0: try bounds.push(low if w.carriers.items[(usize)c].kind == curve_spline else try seam_parameter(work, c, fa, fb))
        try bounds.push(bounds.items[0] + (high - low))
    let count = bounds.count
    if count < 2: return
    for at in 0..<count - 1:
        let t0 = bounds.items[at]
        let t1 = bounds.items[at + 1]
        var halfway = (t0 + t1) * 0.5
        if halfway > high and w.carriers.items[(usize)c].kind == curve_spline: halfway -= high - low
        let middle = try w.at(c, halfway)
        let ia = try face_contains(w, fa, middle, work.tol)
        let ib = try face_contains(w, fb, middle, work.tol)
        if ia == outside or ib == outside or (ia == on_boundary and ib == on_boundary): continue
        # A closed traced curve's stretch may run past its end: wrap it.
        if t1 > high and w.carriers.items[(usize)c].kind == curve_spline:
            try add_wrapped(work, c, t0, t1, low, high, fa, fb)
            continue
        # Along a boundary edge of one face: that edge, cut at the stretch's
        # ends, lies across the other face (no second edge on the same line).
        if ia == on_boundary or ib == on_boundary:
            let owner = fa if ia == on_boundary else fb
            let other = fb if ia == on_boundary else fa
            var found = false
            for use in w.face_uses(owner):
                let e = edge_index(use)
                let edge = w.edges.items[e]
                if not try same_curve(w, c, e, work.tol): continue
                let s_mid = try nearest_on(w, edge.carrier, middle, edge.t0, edge.t1)
                if (try w.at(edge.carrier, s_mid)).subtract(middle).length() > work.tol * 10.0: continue
                try work.cuts.push(Cut(e, try nearest_on(w, edge.carrier, try w.at(c, t0), edge.t0, edge.t1)))
                try work.cuts.push(Cut(e, try nearest_on(w, edge.carrier, try w.at(c, t1), edge.t0, edge.t1)))
                try work.imprints.push(Imprint(other, e))
                found = true
                break
            if found: continue
        let start = try work.vertex(try w.at(c, t0))
        let end = try work.vertex(try w.at(c, t1))
        # Ends merged into one vertex: nothing between them (a closed curve
        # once around is its own loop).
        if start == end and not (closed and count == 2): continue
        try work.sections.push(Section(ShapeEdge(c, t0, t1, start, end), (i64)fa, (i64)fb))

## A stretch of closed traced curve `c` (parameters low..high) from t0
## past its end to t1: two sections meeting at its ends' vertex.
func add_wrapped(work: Work*, c: i64, t0: f64, t1: f64, low: f64, high: f64, fa: usize, fb: usize) -> !:
    let w = &work.w
    let start = try work.vertex(try w.at(c, t0))
    let seam = try work.vertex(try w.at(c, high))
    let end = try work.vertex(try w.at(c, t1 - (high - low)))
    if start != seam: try work.sections.push(Section(ShapeEdge(c, t0, high, start, seam), (i64)fa, (i64)fb))
    if seam != end: try work.sections.push(Section(ShapeEdge(c, low, t1 - (high - low), seam, end), (i64)fa, (i64)fb))

## Face `onto` and coincident face `source`: where `source`'s boundary
## crosses `onto`'s, both cut; `source`'s boundary inside `onto` imprints it.
func imprint(work: Work*, onto: usize, source: usize) -> !:
    let w = &work.w
    var hits = Growing[Hit]()
    defer hits.close()
    for use in w.face_uses(source):
        let e = edge_index(use)
        let edge = w.edges.items[e]
        for other in w.face_uses(onto):
            let o = edge_index(other)
            hits.clear()
            try crossings(w, edge.carrier, edge.t0, edge.t1, o, work.size, work.tol, &hits)
            for hit in hits.view():
                try work.cuts.push(Cut(e, hit.t))
                try work.cuts.push(Cut(o, hit.s))
        try work.imprints.push(Imprint(onto, e))

## A vertex lying inside an edge cuts it there, so faces meeting along it
## share the vertex (OpenCASCADE's vertex/edge interference): a new edge's
## end on an edge it does not cross, one solid's vertex on an edge of the
## other, or where an edge is cut, on edges lying along it.
func vertex_cuts(work: Work*) -> !:
    let w = &work.w
    var lows = Growing[Vector3]()
    defer lows.close()
    var highs = Growing[Vector3]()
    defer highs.close()
    let pad = work.tol * 10.0
    for e in 0..<w.edges.count:
        var low = Vector3(1.0e300, 1.0e300, 1.0e300)
        var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
        for step in 0..<17:
            let p = try w.edge_at(e, (f64)step / 16.0)
            low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
            high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
        # Arcs bulge between samples: a sixteenth of their reach more.
        let bulge = high.subtract(low).length() * 0.02 + pad
        try lows.push(low.subtract(Vector3(bulge, bulge, bulge)))
        try highs.push(high.add(Vector3(bulge, bulge, bulge)))
    # The ends of new edges, and every vertex of both solids (one solid's
    # vertex on the other's edge: edges lying along each other).
    var done = Growing[bool]()
    defer done.close()
    for _ in work.vertices.view(): try done.push(false)
    var candidates = Growing[i64]()
    defer candidates.close()
    for section in work.sections.view():
        try candidates.push(section.edge.start)
        try candidates.push(section.edge.end)
    for v in work.point_vertex.view(): try candidates.push(v)
    # Where edges are cut too: an edge lying along a cut one is cut alike.
    for at in 0..<work.cuts.count:
        let cut = work.cuts.items[at]
        try candidates.push(try work.vertex(try w.at(w.edges.items[cut.edge].carrier, cut.t)))
        try done.push(false)
    for v in candidates.view():
        if done.items[(usize)v]: continue
        done.items[(usize)v] = true
        let p = work.vertices.items[(usize)v]
        for e in 0..<w.edges.count:
            let l = lows.items[e]
            let h = highs.items[e]
            if p.x < l.x or p.y < l.y or p.z < l.z or p.x > h.x or p.y > h.y or p.z > h.z: continue
            let edge = w.edges.items[e]
            let t = try nearest_on(w, edge.carrier, p, edge.t0, edge.t1)
            if (try w.at(edge.carrier, t)).subtract(p).length() > pad: continue
            try work.cuts.push(Cut(e, t))

## Step 3: every original edge cut where it was crossed, into final edges.
func cut_edges(work: Work*) -> !:
    let w = &work.w
    var ts = Growing[f64]()
    defer ts.close()
    try work.piece_starts.push(0)
    for e in 0..<w.edges.count:
        let edge = w.edges.items[e]
        ts.clear()
        let span = edge.t1 - edge.t0
        for cut in work.cuts.view():
            if cut.edge != e: continue
            let f = (cut.t - edge.t0) / span
            if f > 1e-9 and f < 1.0 - 1e-9: try ts.push(f)
        sort.sort(ts.items[..<ts.count])
        var previous_fraction = 0.0
        var previous_vertex = work.point_vertex.items[(usize)edge.start]
        let last_vertex = work.point_vertex.items[(usize)edge.end]
        for at in 0..<ts.count + 1:
            let fraction = ts.items[at] if at < ts.count else 1.0
            let vertex = (try work.vertex(try w.edge_at(e, fraction))) if at < ts.count else last_vertex
            # Cuts that merge into a vertex already there cut nothing.
            if at < ts.count and (vertex == previous_vertex or vertex == last_vertex): continue
            if vertex == previous_vertex and fraction - previous_fraction < 1e-9: continue
            let piece = ShapeEdge(edge.carrier, edge.t0 + span * previous_fraction, edge.t0 + span * fraction, previous_vertex, vertex)
            let (id, forward) = try work.final_edge(piece)
            try work.piece_ids.push((id + 1) * (1 if forward else -1))
            previous_fraction = fraction
            previous_vertex = vertex
        try work.piece_starts.push(work.piece_ids.count)
    for section in work.sections.view():
        let (id, forward) = try work.final_edge(section.edge)
        try work.section_ids.push((id + 1) * (1 if forward else -1))