Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / src / modeling / patch_fit.lucb

## The surface where N G1, G2 or G3 fillets meet at a corner of N flat
## faces (setback.lucb). The fillets stop short of the corner (the
## setback). Between their end sections (A curves, each on a fillet swept
## straight) and curves on the faces (B curves) is a 2N-sided hole. 2N
## quads fill it, one at each of its corners: degree 5 B-spline nets (one
## span for G2; two for G3, whose curves have three). Their outer sides
## are halves of its curves; their inner sides (seams) run from the
## curves' middles to a center.
## The outer sides are exact. Next to an A curve, a quad's first rows are
## the curve's control points moved along the sweep; next to a B curve
## they lie in its plane. So the patch meets the fillets and faces with
## their own continuity: two rows beyond the side for G2, three for G3.
## Across the seams the quads meet in G1 exactly, with the fixed
## coefficients of a vertex where 2N meet: one quad's cross derivative is
## the next one's turned back, plus c t times the seam's, c = 2 cos(2π/2N)
## (1 where six meet, at three fillets). They meet in G2 by
## least squares. Their remaining freedom goes to the smoothest surface
## (least thin-plate energy). It is one linear solve, with no iteration.
## G1 corners (circular fillets) take rational A curves: the circle's arc
## raised to degree 5. The quads are then fitted in homogeneous space, the
## weights first, alone, under the same rows (fixed on the sides and along
## the sweeps), then the weighted points with each plane's rule at its
## point's weight. The seams' rows hold in every homogeneous coordinate, so
## they hold for the rational quads too.
## The literature fits one trimmed surface into the hole instead. Its
## sides are then only near the curves (1e-5 of the corner at best),
## which the booleans cannot use.

## A side of the hole: how the surface beyond its curve goes on. Either
## swept straight along `direction` (`swept`: a fillet's end section), or
## flat, in the plane of normal `direction` (a face). A swept side `coned`
## goes on along the lines from `apex` instead (a variable fillet's cone:
## a straight radius law's strip, its rulings meeting where the radius
## would be 0).
struct HoleSide:
    var swept: bool
    var direction: Vector3
    var apex: Vector3 = Vector3()
    var coned: bool = false

## A control point of the quads: `base`, plus unknowns `first..<first + count`
## times `axes`.
pub struct Slot:
    pub var base: Vector3
    pub var first: usize
    pub var count: usize
    pub var axes: Vector3[3]

## The normal equations of the fit, built a row at a time. A row is a
## combination of control points dotted with one direction.
pub struct Rows:
    pub var size: usize
    pub var matrix: Growing[f64]
    pub var rhs: Growing[f64]
    pub var row: Growing[f64]
    pub var marked: Growing[bool]
    pub var touched: Growing[usize]
    pub var constant: f64

    pub func close():
        self.matrix.close()
        self.rhs.close()
        self.row.close()
        self.marked.close()
        self.touched.close()

    ## Control point `slot`, times `weight`, dotted with `axis`, in this row.
    pub func add(slot: const Slot*, weight: f64, axis: Vector3) -> !:
        if weight == 0.0: return
        self.constant += weight * slot.base.dot(axis)
        for j in 0..<slot.count:
            let at = slot.first + j
            if not self.marked.items[at]:
                self.marked.items[at] = true
                try self.touched.push(at)
            self.row.items[at] += weight * slot.axes[j].dot(axis)

    ## The row, which should equal `target`, weighted `weight`.
    pub func commit(target: f64, weight: f64):
        let n = self.size
        let goal = target - self.constant
        for i in self.touched.view():
            let wi = weight * self.row.items[i]
            for j in self.touched.view(): self.matrix.items[i * n + j] += wi * self.row.items[j]
            self.rhs.items[i] += wi * goal
        for i in self.touched.view():
            self.row.items[i] = 0.0
            self.marked.items[i] = false
        self.touched.clear()
        self.constant = 0.0

## The Bernstein basis of `degree` (at most 11) at `t`, and its
## derivatives to the third (order k at out[k * 12 + i]).
func bernstein(degree: i64, t: f64, out: f64[]):
    let n = (usize)degree
    # The basis of each degree from n - 3 up to n (level d - n + 3).
    var levels: f64[48]
    var b: f64[12]
    for i in 0..<(usize)12: b[i] = 0.0
    for i in 0..<(usize)48: levels[i] = 0.0
    b[0] = 1.0
    for d in 0..<n + 1:
        if d > 0:
            var i = d
            while i > 0:
                b[i] = (1.0 - t) * b[i] + t * b[i - 1]
                i -= 1
            b[0] = (1.0 - t) * b[0]
        if d + 3 >= n:
            for i in 0..<d + 1: levels[(d + 3 - n) * 12 + i] = b[i]
    let binomial: f64[4] = [1.0, 3.0, 3.0, 1.0]
    for k in 0..<(usize)4:
        # Beyond the degree, derivatives vanish.
        if k > n:
            for i in 0..<n + 1: out[k * 12 + i] = 0.0
            continue
        var factor = 1.0
        for f in 0..<k: factor *= (f64)(n - f)
        for i in 0..<n + 1:
            var sum = 0.0
            for j in 0..<k + 1:
                if j > i or i - j > n - k: continue
                # (-1)^(k - j) C(k, j), C(k, j) from the row of k.
                let c = binomial[j] if k == 3 else (1.0 if j == 0 or j == k else 2.0)
                sum += (c if (k - j) % 2 == 0 else -c) * levels[(3 - k) * 12 + i - j]
            out[k * 12 + i] = factor * sum

## Clamped degree 5 B-spline `points` of `weights` (knots `knots`), as
## weighted points, split at the middle of its domain by knot insertion: the
## halves' weighted points onto `first` and `second` (their weights onto
## `first_weights` and `second_weights`), each from its start, and their
## knots (0 to 1) onto `first_knots` and `second_knots`.
pub func split_middle(points: const Vector3[], weights: const f64[], knots: const f64[], first: Growing[Vector3]*, second: Growing[Vector3]*, first_weights: Growing[f64]*, second_weights: Growing[f64]*, first_knots: Growing[f64]*, second_knots: Growing[f64]*) -> !:
    let p: usize = 5
    var rows = Growing[f64]()
    defer rows.close()
    for at in 0..<points.length:
        let q = points[at].multiply_scalar(weights[at])
        try rows.push(q.x)
        try rows.push(q.y)
        try rows.push(q.z)
        try rows.push(weights[at])
    var u = Growing[f64]()
    defer u.close()
    try u.assign(knots)
    var scratch = Growing[f64]()
    defer scratch.close()
    let low = knots[p]
    let high = knots[knots.length - p - 1]
    let middle = (low + high) * 0.5
    # Knots a rounding off the middle (a joined curve's, 0.49999999999999856)
    # are the middle: inserted again beside them, they made spans of no
    # length and the quads' solve singular.
    var already: usize = 0
    for at in 0..<u.count:
        if math.abs(u.items[at] - middle) <= (high - low) * 1e-9:
            u.items[at] = middle
            already += 1
    for _ in already..<p: try insert_knot(&rows, &u, &scratch, p, 4, middle)
    # The middle's run of knots starts at s; control point s - 1 is the
    # curve's point there.
    var s: usize = 0
    while u.items[s] != middle: s += 1
    let count = rows.count // 4
    for at in 0..<count:
        let q = Vector3(rows.items[at * 4], rows.items[at * 4 + 1], rows.items[at * 4 + 2])
        let weight = rows.items[at * 4 + 3]
        if at < s:
            try first.push(q)
            try first_weights.push(weight)
        if at >= s - 1:
            try second.push(q)
            try second_weights.push(weight)
    for at in 0..<s: try first_knots.push((u.items[at] - low) / (middle - low))
    for _ in 0..<p + 1: try first_knots.push(1.0)
    for _ in 0..<p + 1: try second_knots.push(0.0)
    for at in s + p..<u.count: try second_knots.push((u.items[at] - middle) / (high - middle))

## The clamped degree 5 B-spline basis of `knots` at `t` and its first and
## second derivatives (order k at out[k * 9 + i], for every control point).
pub func spline_basis(knots: const f64[], t: f64, out: f64[]):
    spline_basis_by(knots, t, 9, out)

## spline_basis at stride `stride` (order k at out[k * stride + i]): the
## quads' own rows (fairness_rows, seam_rows) take up to basis_stride
## control points a side, Fill's quads (surfacing/fill_quads.lucb) that many.
pub func spline_basis_by(knots: const f64[], t: f64, stride: usize, out: f64[]):
    var ders: f64[36]
    let count = knots.length - 6
    let first = basis_derivatives(knots, (i64)count, 5, t, &ders)
    for i in 0..<3 * stride: out[i] = 0.0
    for k in 0..<(usize)3:
        for j in 0..<(usize)6: out[k * stride + first + j] = ders[k * 12 + j]

## The most control points a side of a quad has in fairness_rows and
## seam_rows.
pub let basis_stride: usize = 17

## The quads filling the hole bounded by `curves` (three to sixteen of
## them; a setback corner's are 2N), onto `out` (their
## weights onto `out_weights`), their knots (the same both ways) onto
## `quad_knots`. `curves` are degree 5 B-splines of knots `knots` and
## weights `weights` in a loop: curve k's control points are curves[k * n..]
## (n per curve), each curve starting where the one before ends. The
## surface beyond curve k goes on as `sides[k]` says, with `continuity` (1,
## 2 or 3: that many rows beyond each side follow it).
## Quad k sits at the hole's corner where curve k starts. Its side v = 0
## is the first half of curve k; its side u = 0 is the second half of
## curve k - 1, from that corner back. Its corner (1, 1) is the center.
## Its m^2 control points are u-major (point (a, b) at a * m + b).
func corner_patch(curves: const Vector3[], weights: const f64[], knots: const f64[], sides: const HoleSide[], continuity: i64, out: Growing[Vector3]*, out_weights: Growing[f64]*, quad_knots: Growing[f64]*, fullness: f64 = 1.0, extra_knots: usize = 0, held_flat: bool = false) -> !:
    let n = knots.length - 6
    let h = (usize)continuity + 1
    let count = sides.length
    if count < 3 or count > 16 or curves.length != count * n or weights.length != curves.length or continuity < 1 or continuity > 3: error(invalid, "a corner patch needs three to sixteen degree 5 curves, G1, G2 or G3")
    var rational = false
    for weight in weights: rational = rational or weight != 1.0
    # Unit size about the curves' middle, so the weights mean the same at
    # any scale.
    var origin = Vector3()
    for p in curves: origin = origin.add(p)
    origin = origin.multiply_scalar(1.0 / (f64)curves.length)
    var scale = 0.0
    for p in curves: scale = math.max(scale, p.subtract(origin).length())
    if scale <= 0.0: error(invalid, "a corner patch's curves are a point")
    var first = Growing[Vector3]()
    defer first.close()
    var second = Growing[Vector3]()
    defer second.close()
    var first_weights = Growing[f64]()
    defer first_weights.close()
    var second_weights = Growing[f64]()
    defer second_weights.close()
    var local = Growing[Vector3]()
    defer local.close()
    var second_knots = Growing[f64]()
    defer second_knots.close()
    for k in 0..<count:
        local.clear()
        for i in 0..<n: try local.push(curves[k * n + i].subtract(origin).multiply_scalar(1.0 / scale))
        quad_knots.clear()
        second_knots.clear()
        try split_middle(local.view(), weights[k * n..<(k + 1) * n], knots, &first, &second, &first_weights, &second_weights, quad_knots, &second_knots)
    # Each half refined by `extra_knots` knots spread evenly over its interior
    # (the same in every half, and symmetric, so a half run backwards
    # keeps them): more rows for the quads to take a hole's shape with.
    for r in 0..<extra_knots:
        let value = (f64)(r + 1) / (f64)(extra_knots + 1)
        try refine_halves(&first, &first_weights, quad_knots, count, value)
        try refine_halves(&second, &second_weights, &second_knots, count, value)
    # Halves are m points; the second half run backwards has the first's
    # knots (the curves are symmetric in their knots).
    let m = first.count // count
    if m > 9 or second.count != count * m or m < h * 2 - 1: error(invalid, "a corner patch's curves are not split evenly")
    let qk = quad_knots.view()
    # What each control point is: kind 1 fixed (on a side), 2 a side's
    # point moved along its sweep, 3 in a side's plane, 0 free. Keys are
    # quad points (k * m + a) * m + b, a seam's points under the quad whose
    # side u = 1 it is, the center last.
    let center = count * m * m
    var kinds = Growing[i64]()
    defer kinds.close()
    try kinds.fill(center + 1, 0)
    var bases = Growing[Vector3]()
    defer bases.close()
    try bases.fill(center + 1, Vector3())
    var ways = Growing[Vector3]()
    defer ways.close()
    try ways.fill(center + 1, Vector3())
    # Each point's weight where a side or a sweep fixes it.
    var known = Growing[f64]()
    defer known.close()
    try known.fill(center + 1, 1.0)
    for k in 0..<count:
        let before = (k + count - 1) % count
        for a in 0..<m:
            let key = patch_key(k, a, 0, m, count)
            kinds.items[key] = 1
            bases.items[key] = first.items[k * m + a]
            known.items[key] = first_weights.items[k * m + a]
        for b in 0..<m:
            let key = patch_key(k, 0, b, m, count)
            kinds.items[key] = 1
            bases.items[key] = second.items[before * m + m - 1 - b]
            known.items[key] = second_weights.items[before * m + m - 1 - b]
    # A coned side's rows run along the lines to its apex, each point a
    # step of its own (in the unit frame). (One share of the line for the
    # whole row is the cone's own net, exact, but only with the face curves'
    # legs at its ends taking it too, and the fit then collapsed the rows
    # onto the side.)
    var apexes = Growing[Vector3]()
    defer apexes.close()
    for side in sides: try apexes.push(side.apex.subtract(origin).multiply_scalar(1.0 / scale))
    # Beside a face (a B side) a G1 patch of four or more fillets still
    # takes two rows in its plane: flat across it to second order, it cannot
    # bulge out through the face past the first row (an irregular apex's
    # patch did). Three keep Fusion's Setback shape, unless `held_flat`.
    for k in 0..<count:
        let before = (k + count - 1) % count
        let flat = h if h > 3 or (count == 6 and not held_flat) else 3
        let rows_k = h if sides[k].swept else flat
        let rows_before = h if sides[before].swept else flat
        for a in 1..<m:
            for b in 1..<rows_k: set_rule(&kinds, &bases, &ways, &known, patch_key(k, a, b, m, count), first.items[k * m + a], first_weights.items[k * m + a], &sides[k], apexes.items[k], b)
        for a in 1..<rows_before:
            for b in 1..<m: set_rule(&kinds, &bases, &ways, &known, patch_key(k, a, b, m, count), second.items[before * m + m - 1 - b], second_weights.items[before * m + m - 1 - b], &sides[before], apexes.items[before], a)
    # Where two fillets' sides meet at a hole corner (a three-sided corner),
    # the quad's points (a, b) beside both (a and b below h) lie on both
    # sweeps: where the line from side k's point a along its sweep crosses
    # the line from the other side's point b along its own. A section's
    # first h points lie along its leg in the face the corner touches, so
    # these lines cross, and the patch meets both strips with their
    # continuity right to the corner.
    for k in 0..<count:
        let before = (k + count - 1) % count
        if rational or not sides[k].swept or not sides[before].swept: continue
        let da = sides[k].direction
        let db = sides[before].direction
        let along = da.dot(db)
        let det = 1.0 - along * along
        if det < 1e-12: error(invalid, "a corner's fillets meet along one line")
        for a in 1..<h:
            for b in 1..<h:
                let pa = first.items[k * m + a]
                let pb = second.items[before * m + m - 1 - b]
                let gap = pb.subtract(pa)
                let ta = (gap.dot(da) - along * gap.dot(db)) / det
                let tb = (along * gap.dot(da) - gap.dot(db)) / det
                let key = patch_key(k, a, b, m, count)
                kinds.items[key] = 1
                bases.items[key] = pa.add(da.multiply_scalar(ta)).add(pb.add(db.multiply_scalar(tb))).multiply_scalar(0.5)
    # The unknowns behind each control point (keys no quad uses get none).
    var used = Growing[bool]()
    defer used.close()
    try used.fill(center + 1, false)
    for k in 0..<count:
        for a in 0..<m:
            for b in 0..<m: used.items[patch_key(k, a, b, m, count)] = true
    # Rational: the weights first, a field of their own (in x), fixed on
    # the sides and along the sweeps, free elsewhere.
    var point_weights = Growing[f64]()
    defer point_weights.close()
    try point_weights.assign(known.view())
    if rational: try fit_weights(&kinds, &known, &used, m, quad_knots.view(), &point_weights, count)
    # A sweep moves a point's weighted position along its way times its
    # weight; a plane holds n . X = h w at the point's weight.
    for key in 0..<center + 1:
        if kinds.items[key] == 2: ways.items[key] = ways.items[key].multiply_scalar(point_weights.items[key])
        if kinds.items[key] == 3: bases.items[key] = bases.items[key].multiply_scalar(point_weights.items[key] / known.items[key])
    # Fullness other than 1: the fit made once, then again with its center
    # held where its bulge from the curves' middle (the origin) is scaled by
    # it (Alias's Pivot Curve Length Ratio, a Ball Corner's fullness).
    for pass in 0..<(2 if fullness != 1.0 else 1):
        if pass == 1:
            let bulge = out.items[out.count - 1].subtract(origin).multiply_scalar(1.0 / scale)
            out.clear()
            out_weights.clear()
            kinds.items[center] = 1
            bases.items[center] = bulge.multiply_scalar(fullness * point_weights.items[center])
        try fit_points(&kinds, &bases, &ways, &used, &point_weights, m, qk, count, origin, scale, out, out_weights)
    # G2 or G3 beside a cone: its curvature across, at stations along the
    # side, held to the cone's in that fit's slopes, a second solve
    # (fill_quads' rule: G2 linear once the slope is held).
    var stations = Growing[ConeStation]()
    defer stations.close()
    if continuity >= 2 and not rational:
        try cone_stations(sides, out.view(), m, qk, count, origin, scale, &stations)
        if stations.count > 0:
            out.clear()
            out_weights.clear()
            try fit_points(&kinds, &bases, &ways, &used, &point_weights, m, qk, count, origin, scale, out, out_weights, stations.view())
    # (fit_points ends with the center: not a quad's point.)
    out.count -= 1

## The quads' points for corner_patch (its kinds of control points, their
## bases and ways, the weights fitted), onto `out` and `out_weights` keyed as
## corner_patch's, the center last; `origin` and `scale` its unit frame.
func fit_points(kinds: const Growing[i64]*, bases: const Growing[Vector3]*, ways: const Growing[Vector3]*, used: const Growing[bool]*, point_weights: const Growing[f64]*, m: usize, qk: const f64[], count: usize, origin: Vector3, scale: f64, out: Growing[Vector3]*, out_weights: Growing[f64]*, stations: (const ConeStation[])? = none) -> !:
    let center = count * m * m
    var slots = Growing[Slot]()
    defer slots.close()
    var size: usize = 0
    for key in 0..<center + 1:
        let kind = kinds.items[key]
        var slot = Slot(bases.items[key], size, 0, [Vector3(), Vector3(), Vector3()])
        if not used.items[key]: slot.count = 0
        elif kind == 2:
            slot.count = 1
            slot.axes[0] = ways.items[key]
        elif kind == 3:
            slot.count = 2
            slot.axes[0] = try across(ways.items[key])
            slot.axes[1] = ways.items[key].cross(slot.axes[0])
        elif kind == 0:
            slot.count = 3
            slot.axes = [Vector3(1.0, 0.0, 0.0), Vector3(0.0, 1.0, 0.0), Vector3(0.0, 0.0, 1.0)]
        size += slot.count
        try slots.push(slot)
    var rows = Rows(size, Growing[f64](), Growing[f64](), Growing[f64](), Growing[bool](), Growing[usize](), 0.0)
    defer rows.close()
    try rows.matrix.fill(size * size, 0.0)
    try rows.rhs.fill(size, 0.0)
    try rows.row.fill(size, 0.0)
    try rows.marked.fill(size, false)
    try fairness_rows(&rows, slots.view(), m, qk, count)
    try seam_rows(&rows, slots.view(), m, qk, count)
    if let held = stations: try cone_rows(&rows, slots.view(), m, qk, count, held)
    try cholesky_solve(rows.matrix.items[..<size * size], rows.rhs.items[..<size], size)
    for k in 0..<count:
        for a in 0..<m:
            for b in 0..<m:
                let key = patch_key(k, a, b, m, count)
                let slot = slots.items[key]
                var p = slot.base
                for j in 0..<slot.count: p = p.add(slot.axes[j].multiply_scalar(rows.rhs.items[slot.first + j]))
                let weight = point_weights.items[key]
                try out.push(origin.add(p.multiply_scalar(scale / weight)))
                try out_weights.push(weight)
    # The center (the quads' shared corner), last, for a second pass.
    let slot = slots.items[center]
    var p = slot.base
    for j in 0..<slot.count: p = p.add(slot.axes[j].multiply_scalar(rows.rhs.items[slot.first + j]))
    try out.push(origin.add(p.multiply_scalar(scale / point_weights.items[center])))

## A station beside a coned side for corner_patch's second solve: quad
## `quad` at `uv`, the way `d` across into it (u or v), the slope across
## held (`slope`, the unit frame's) and the cone's normal `n` and normal
## curvature `curvature` in that slope.
struct ConeStation:
    var quad: usize
    var uv: Vector3
    var d: Vector3
    var slope: Vector3
    var n: Vector3
    var curvature: f64

## The stations beside `sides`' coned sides (24 a half) from the first
## solve's quads `quads` (world, keyed as corner_patch's out): the cone
## through each side's curve and its apex, its normal and its normal
## curvature in the quad's slope across there (the rulings straight, only
## the slope's part along the curve bends: S_u·N times its share squared).
func cone_stations(sides: const HoleSide[], quads: const Vector3[], m: usize, qk: const f64[], count: usize, origin: Vector3, scale: f64, out: Growing[ConeStation]*) -> !:
    var b0: f64[64]
    var b1: f64[64]
    let mm = m * m
    for c in 0..<count:
        if not sides[c].coned: continue
        let apex = sides[c].apex.subtract(origin).multiply_scalar(1.0 / scale)
        # The side's first half on quad c (v = 0, across along v), its second
        # on quad c + 1 (u = 0, across along u).
        for half in 0..<(usize)2:
            let quad = c if half == 0 else (c + 1) % count
            for q in 0..<(usize)24:
                let t = ((f64)q + 0.5) / 24.0
                spline_basis_by(qk, t, basis_stride, b0[..<64])
                spline_basis_by(qk, 0.0, basis_stride, b1[..<64])
                var p = Vector3()
                var along = Vector3()
                var bend = Vector3()
                var slope = Vector3()
                for a in 0..<m:
                    for b in 0..<m:
                        let x = quads[quad * mm + a * m + b].subtract(origin).multiply_scalar(1.0 / scale)
                        let fa = b0[a] if half == 0 else b1[a]
                        let fb = b1[b] if half == 0 else b0[b]
                        p = p.add(x.multiply_scalar(fa * fb))
                        along = along.add(x.multiply_scalar((b0[basis_stride + a] * b1[b]) if half == 0 else (b1[a] * b0[basis_stride + b])))
                        bend = bend.add(x.multiply_scalar((b0[2 * basis_stride + a] * b1[b]) if half == 0 else (b1[a] * b0[2 * basis_stride + b])))
                        slope = slope.add(x.multiply_scalar((b0[a] * b1[basis_stride + b]) if half == 0 else (b1[basis_stride + a] * b0[b])))
                let ruling = p.subtract(apex)
                let n = along.cross(ruling).normalized() catch failure: continue
                # The slope as along and ruling parts.
                let aa = along.dot(along)
                let ar = along.dot(ruling)
                let rr = ruling.dot(ruling)
                let det = aa * rr - ar * ar
                if det <= 0.0: continue
                let share = (slope.dot(along) * rr - slope.dot(ruling) * ar) / det
                let d = Vector3(0.0, 1.0, 0.0) if half == 0 else Vector3(1.0, 0.0, 0.0)
                let uv = Vector3(t, 0.0, 0.0) if half == 0 else Vector3(0.0, t, 0.0)
                try out.push(ConeStation(quad, uv, d, slope, n, share * share * bend.dot(n)))

## The second solve's rows at `stations`: the slope across held, and the
## normal part of the second derivative across the cone's curvature in it.
func cone_rows(rows: Rows*, slots: const Slot[], m: usize, qk: const f64[], count: usize, stations: const ConeStation[]) -> !:
    var bu: f64[64]
    var bv: f64[64]
    let axes: Vector3[3] = [Vector3(1.0, 0.0, 0.0), Vector3(0.0, 1.0, 0.0), Vector3(0.0, 0.0, 1.0)]
    for st in stations:
        spline_basis_by(qk, st.uv.x, basis_stride, bu[..<64])
        spline_basis_by(qk, st.uv.y, basis_stride, bv[..<64])
        for axis in axes:
            for a in 0..<m:
                for b in 0..<m: try rows.add(&slots[patch_key(st.quad, a, b, m, count)], st.d.x * bu[basis_stride + a] * bv[b] + st.d.y * bu[a] * bv[basis_stride + b], axis)
            rows.commit(st.slope.dot(axis), 1e-2)
        for a in 0..<m:
            for b in 0..<m: try rows.add(&slots[patch_key(st.quad, a, b, m, count)], st.d.x * st.d.x * bu[2 * basis_stride + a] * bv[b] + st.d.y * st.d.y * bu[a] * bv[2 * basis_stride + b], st.n)
        rows.commit(st.curvature, 1e5)

## The quads' weights onto `out` (keyed as corner_patch's points): fixed
## where `kinds` says a side or a sweep fixes them (`known`), else fitted
## by the seams' rows and the fairness, in one coordinate.
func fit_weights(kinds: const Growing[i64]*, known: const Growing[f64]*, used: const Growing[bool]*, m: usize, knots: const f64[], out: Growing[f64]*, count: usize) -> !:
    var slots = Growing[Slot]()
    defer slots.close()
    var size: usize = 0
    for key in 0..<kinds.count:
        var slot = Slot(Vector3(known.items[key], 0.0, 0.0), size, 0, [Vector3(1.0, 0.0, 0.0), Vector3(), Vector3()])
        let kind = kinds.items[key]
        if used.items[key] and (kind == 0 or kind == 3):
            slot.count = 1
            slot.base = Vector3()
        size += slot.count
        try slots.push(slot)
    if size == 0:
        try out.assign(known.view())
        return
    var rows = Rows(size, Growing[f64](), Growing[f64](), Growing[f64](), Growing[bool](), Growing[usize](), 0.0)
    defer rows.close()
    try rows.matrix.fill(size * size, 0.0)
    try rows.rhs.fill(size, 0.0)
    try rows.row.fill(size, 0.0)
    try rows.marked.fill(size, false)
    try fairness_rows(&rows, slots.view(), m, knots, count)
    try seam_rows(&rows, slots.view(), m, knots, count)
    try cholesky_solve(rows.matrix.items[..<size * size], rows.rhs.items[..<size], size)
    out.clear()
    for key in 0..<kinds.count:
        let slot = slots.items[key]
        let weight = slot.base.x + (rows.rhs.items[slot.first] if slot.count == 1 else 0.0)
        if not (weight > 0.0): error(invalid, "a corner patch's weights turned negative: use another corner type there")
        try out.push(weight)

## The `count` halves in `points` (weighted points, weights `weights`, each
## half's knots `knots`) given knot `value` once more; `knots` gains it.
func refine_halves(points: Growing[Vector3]*, weights: Growing[f64]*, knots: Growing[f64]*, count: usize, value: f64) -> !:
    let m = points.count // count
    var all = Growing[Vector3]()
    defer all.close()
    var all_weights = Growing[f64]()
    defer all_weights.close()
    var rows = Growing[f64]()
    defer rows.close()
    var u = Growing[f64]()
    defer u.close()
    var scratch = Growing[f64]()
    defer scratch.close()
    for k in 0..<count:
        rows.clear()
        for at in k * m..<(k + 1) * m:
            let q = points.items[at]
            try rows.push(q.x)
            try rows.push(q.y)
            try rows.push(q.z)
            try rows.push(weights.items[at])
        try u.assign(knots.view())
        try insert_knot(&rows, &u, &scratch, 5, 4, value)
        for at in 0..<rows.count // 4:
            try all.push(Vector3(rows.items[at * 4], rows.items[at * 4 + 1], rows.items[at * 4 + 2]))
            try all_weights.push(rows.items[at * 4 + 3])
    try points.assign(all.view())
    try weights.assign(all_weights.view())
    try knots.assign(u.view())

## Quad k's control point (a, b) of `count` quads as a key: a seam's
## points under the quad whose side u = 1 it is (quad k's side v = 1 is
## quad k - 1's side u = 1, run the same way), the center last.
pub func patch_key(k: usize, a: usize, b: usize, m: usize, count: usize) -> usize:
    if a == m - 1 and b == m - 1: return count * m * m
    if b == m - 1: return (((k + count - 1) % count) * m + m - 1) * m + a
    return (k * m + a) * m + b

## The rule of a side for control point `key` in row `row` beside it
## (moved from `base` along its sweep, or in its plane; a coned side's
## first row along its line to `apex`), unless it is fixed. A sweep's rule wins: where a fillet's rows meet a
## face's, the fillet's lie in the face.
func set_rule(kinds: Growing[i64]*, bases: Growing[Vector3]*, ways: Growing[Vector3]*, known: Growing[f64]*, key: usize, base: Vector3, weight: f64, side: const HoleSide*, apex: Vector3, row: usize):
    let kind = kinds.items[key]
    if kind == 1 or kind == 2: return
    # A cone's rows past the first are free: its curvature across is held
    # by stations (cone_stations), not by them.
    if side.coned and row >= 2: return
    if kind == 3 and not side.swept: return
    kinds.items[key] = 2 if side.swept else 3
    bases.items[key] = base
    ways.items[key] = side.direction
    known.items[key] = weight
    if side.coned:
        # Along its line to the apex (a ruling of the cone).
        ways.items[key] = base.multiply_scalar(1.0 / weight).subtract(apex).normalized() catch failure: recover side.direction

## The thin-plate energy of every quad (S_uu^2 + 2 S_uv^2 + S_vv^2 over
## its square), weighted lightly: it only chooses among the surfaces the
## seams allow. Over a quad it is p^T M p (p its control points, each
## axis alike), M the same for every quad: made once by Gauss points in
## each span, then added for each quad's unknowns.
pub func fairness_rows(rows: Rows*, slots: const Slot[], m: usize, knots: const f64[], count: usize) -> !:
    let nodes: f64[8] = [0.019855071751231856, 0.10166676129318664, 0.2372337950418355, 0.4082826787521751, 0.5917173212478249, 0.7627662049581645, 0.8983332387068134, 0.9801449282487681]
    let weights: f64[8] = [0.05061426814518813, 0.11119051722668724, 0.15685332293894364, 0.18134189168918100, 0.18134189168918100, 0.15685332293894364, 0.11119051722668724, 0.05061426814518813]
    let orders: usize[6] = [2, 0, 1, 1, 0, 2]
    let factors: f64[3] = [1.0, 2.0, 1.0]
    var points = Growing[f64]()
    defer points.close()
    var spans = Growing[f64]()
    defer spans.close()
    for at in 5..<knots.length - 6:
        let a = knots[at]
        let b = knots[at + 1]
        if b <= a: continue
        for q in 0..<(usize)8:
            try points.push(a + (b - a) * nodes[q])
            try spans.push((b - a) * weights[q])
    # M over the m^2 control points (u-major).
    let mm = m * m
    var energy = Growing[f64]()
    defer energy.close()
    try energy.fill(mm * mm, 0.0)
    var term = Growing[f64]()
    defer term.close()
    try term.fill(mm, 0.0)
    var bu: f64[64]
    var bv: f64[64]
    for qu in 0..<points.count:
        spline_basis_by(knots, points.items[qu], basis_stride, bu[..<64])
        for qv in 0..<points.count:
            spline_basis_by(knots, points.items[qv], basis_stride, bv[..<64])
            let weight = 1e-5 * spans.items[qu] * spans.items[qv]
            for t in 0..<(usize)3:
                let du = orders[t * 2]
                let dv = orders[t * 2 + 1]
                for a in 0..<m:
                    for b in 0..<m: term.items[a * m + b] = bu[du * basis_stride + a] * bv[dv * basis_stride + b]
                let w = weight * factors[t]
                for i in 0..<mm:
                    let wi = w * term.items[i]
                    if wi == 0.0: continue
                    for j in 0..<mm: energy.items[i * mm + j] += wi * term.items[j]
    # Each quad's share: p_i . p_j times M_ij, through its slots.
    let n = rows.size
    for k in 0..<count:
        for i in 0..<mm:
            let si = slots[patch_key(k, i // m, i % m, m, count)]
            for j in 0..<mm:
                let coefficient = energy.items[i * mm + j]
                if coefficient == 0.0: continue
                let sj = slots[patch_key(k, j // m, j % m, m, count)]
                for x in 0..<si.count:
                    let axis = si.axes[x]
                    rows.rhs.items[si.first + x] -= coefficient * axis.dot(sj.base)
                    for y in 0..<sj.count: rows.matrix.items[(si.first + x) * n + sj.first + y] += coefficient * axis.dot(sj.axes[y])

## The seams' rows. Seam k is quad k's side u = 1 and quad k + 1's side
## v = 1, both from a curve's middle (t = 0) to the center. G1, weighted
## to hold: Q_k,u(1, t) + Q_k+1,v(t, 1) = c t Q_k,v(1, t), c = 2 cos(2π /
## count). That is C1 at the curve (where the halves meet smoothly) and, at
## the center, the quads' corners an affine regular polygon about it (c = 1
## for six). G2, by least squares: Q_k+1,vv = Q_k,uu - 2ct Q_k,uv +
## (ct)^2 Q_k,vv, weighted `g2_weight`. Not where three quads meet (a
## three-sided corner): there G2 at the center asks for no second
## derivatives at all, and the quads collapse onto it; without those rows
## their seams still come out G2 within a few percent.
pub func seam_rows(rows: Rows*, slots: const Slot[], m: usize, knots: const f64[], count: usize, g2_weight: f64 = 1.0) -> !:
    let c = 2.0 * math.cos(2.0 * math.pi / (f64)count)
    let axes: Vector3[3] = [Vector3(1.0, 0.0, 0.0), Vector3(0.0, 1.0, 0.0), Vector3(0.0, 0.0, 1.0)]
    var at_end: f64[64]
    spline_basis_by(knots, 1.0, basis_stride, at_end[..<64])
    var bt: f64[64]
    let samples = 24
    for s in 0..<samples:
        let t = ((f64)s + 0.5) / (f64)samples
        spline_basis_by(knots, t, basis_stride, bt[..<64])
        let ct = c * t
        for k in 0..<count:
            let next = (k + 1) % count
            for axis in axes:
                for a in 0..<m:
                    for b in 0..<m:
                        try rows.add(&slots[patch_key(k, a, b, m, count)], at_end[basis_stride + a] * bt[b] - ct * at_end[a] * bt[basis_stride + b], axis)
                        try rows.add(&slots[patch_key(next, a, b, m, count)], bt[a] * at_end[basis_stride + b], axis)
                rows.commit(0.0, 1e3)
            for axis in axes:
                for a in 0..<m:
                    for b in 0..<m:
                        try rows.add(&slots[patch_key(next, a, b, m, count)], bt[a] * at_end[2 * basis_stride + b], axis)
                        let w = -at_end[2 * basis_stride + a] * bt[b] + 2.0 * ct * at_end[basis_stride + a] * bt[basis_stride + b] - ct * ct * at_end[a] * bt[2 * basis_stride + b]
                        try rows.add(&slots[patch_key(k, a, b, m, count)], w, axis)
                rows.commit(0.0, 0.0 if count == 3 else g2_weight)

## Solves symmetric positive definite `matrix` (n x n) x = `rhs`, in
## place: the solution replaces `rhs`.
pub func cholesky_solve(matrix: f64[], rhs: f64[], n: usize) -> !:
    for j in 0..<n:
        var d = matrix[j * n + j]
        for k in 0..<j: d -= matrix[j * n + k] * matrix[j * n + k]
        if d <= 0.0: error(invalid, "a corner patch's fit is singular")
        let diagonal = math.sqrt(d)
        matrix[j * n + j] = diagonal
        for i in j + 1..<n:
            var s = matrix[i * n + j]
            for k in 0..<j: s -= matrix[i * n + k] * matrix[j * n + k]
            matrix[i * n + j] = s / diagonal
    for i in 0..<n:
        var s = rhs[i]
        for k in 0..<i: s -= matrix[i * n + k] * rhs[k]
        rhs[i] = s / matrix[i * n + i]
    var i = n
    while i > 0:
        i -= 1
        var s = rhs[i]
        for k in i + 1..<n: s -= matrix[k * n + i] * rhs[k]
        rhs[i] = s / matrix[i * n + i]