Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / surfacing / fill_solve.lucb

## Fill's solve (surfacing Stage 7; fill.lucb has the plan): each
## station's rows and the guides', the energy and rows factored once and
## solved again with the multipliers' shifts, and G2's Gauss-Newton rounds.

## The rows' holds: positions to `close_share` of their tolerance (the
## trim lays the boundaries on the fill to a billionth); a steep slope is
## held only off the side's ends (between `steep_from` and `steep_to`),
## with `steep_weight` of the row weight; curvature rows within
## `curvature_hold` of the curvature tolerance; the flow's rows at
## `flow_weight` of the row weight.
let close_share: f64 = 1e-3
let steep_from: f64 = 0.05
let steep_to: f64 = 0.95
let steep_weight: f64 = 1e-4
let curvature_hold: f64 = 1e-3
let flow_weight: f64 = 1e-2
## The rounds stop when the net moves less than this share of the position
## tolerance; the merit's angle tolerance is at least this (radians); with
## a G2 side or a turn, bending weighs this (the rate of bending carries
## the plate).
let settled_share: f64 = 0.01
let least_angle_tolerance: f64 = 1e-12
let bend_with_rate: f64 = 0.01

# -- The solve.

## The rows of station `st`: G0 (N-sided: Quad's boundary rows are
## fixed), G1, and with `cross` (the last answer's cross derivative there)
## G2 linearized about it; the flow. Into `system` and kept in `held`.
func station_rows(w: const FillWork*, fn: const FillNet*, system: BandSystem*, held: HeldRows*, row: FillRow*, st: const FillStation*, cross: Vector3?, weight: f64) -> !:
    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)]
    let ease = st.weight
    let exact = ease >= 1.0
    # How closely the multipliers drive each row: positions to a thousandth
    # of their tolerance (the trim lays the boundaries on the fill to a
    # billionth); slopes and curvatures to a tenth of theirs (the angle's
    # sine on a cross derivative of about unit length; the curvature's
    # share below).
    let close = w.position * close_share
    let square = w.angle * 0.1
    if not w.opts.quad:
        # G0 (Free too: the boundary's position holds the trim).
        for c in 0..<(usize)3:
            try put_derivative(fn, row, st.uv, st.d, 0, axes[c])
            try held.hold(system, row, weight, st.p.dot(axes[c]), close)
    # Where a lid's turned corners are held (fill_strips.lucb: `cross` set),
    # the strip along the boundary is fixed, its slope with it: no G1 row.
    if st.cross.length() == 0.0 and st.order >= 1 and st.has_face and (ease > 0.0 or st.turned):
        # G1, driven to its tolerance; turned toward a conflicting corner
        # (corner_turn), held whole to the turned normal by the weight
        # alone (the first answer, before the strips are held).
        try put_derivative(fn, row, st.uv, st.d, 1, st.held)
        if st.turned: try held.hold(system, row, weight, 0.0, 0.0)
        else: try held.hold(system, row, weight * ease, 0.0, square if exact else 0.0)
        # Quad: G1 alone is met by a cross derivative shrunk to nothing
        # (the normal then undefined: a lid on vertical walls stays flat),
        # so it leaves the neighbor its way at the base's speed across, a
        # preference ten thousand times weaker (N-sided, the chart holds it).
        if w.opts.quad and st.leave.length() > 0.0:
            var bu: f64[48]
            var bv: f64[48]
            let (fu, fv) = bases_of(fn, st.uv, &bu, &bv)
            var speed = Vector3()
            for a in 0..<(usize)fn.net.du + 1:
                for b in 0..<(usize)fn.net.dv + 1:
                    speed = speed.add(fn.base_point(fu + a, fv + b).multiply_scalar(st.d.x * bu[12 + a] * bv[b] + st.d.y * bu[a] * bv[12 + b]))
            # Its part across the boundary turned onto the neighbor's way
            # with its length (Square's G1 field does the same).
            # Only where the base's slope stands square off the neighbor's
            # plane (a wall under a lid): elsewhere G1 turns it a little and
            # the energy keeps its length; off the corners, whose slopes the
            # sides fix.
            let across = speed.subtract(st.tangent.multiply_scalar(speed.dot(st.tangent)))
            let steep = math.abs((across.normalized() catch failure: recover Vector3()).dot(st.form.n)) > 0.99
            if steep and (st.turned or (st.s > steep_from and st.s < steep_to)):
                let way = st.way.normalized() catch failure: recover Vector3()
                try put_derivative(fn, row, st.uv, st.d, 1, way)
                try held.hold(system, row, weight * steep_weight, across.length(), 0.0)
    # A turn held (its cross derivative leaves the neighbor's plane) has no
    # curvature of the neighbor's to meet.
    if st.order >= 2 and st.has_face and ease > 0.0 and not (st.turned and st.cross.length() > 0.0):
        if let l = cross:
            # n . S_dd = II(S_d, S_d), linearized about the last answer's
            # S_d = l (Gauss-Newton): II(S_d, S_d) ~ 2 II(l, S_d) - II(l, l).
            try put_derivative(fn, row, st.uv, st.d, 2, st.form.n)
            try put_derivative(fn, row, st.uv, st.d, 1, st.form.times(l).multiply_scalar(-2.0))
            # Within a tenth of the curvature tolerance of the larger
            # curvature (the Check tools' floor below).
            let bent = math.max(math.abs(st.form.curvature_of(l)), fill_curvature_floor * l.dot(l))
            try held.hold(system, row, weight * ease, -st.form.curvature_of(l), bent * w.curvature * curvature_hold if exact else 0.0)
    if w.opts.quad and w.opts.flow != fill_flow_natural:
        # The cross derivative's part square to the wanted way vanishes:
        # Normal along the tangent; Next and Adjacent across the way. A
        # preference, not a constraint: a hundredth of the weight, no
        # multipliers.
        var e = Vector3()
        if w.opts.flow == fill_flow_normal: e = st.tangent
        elif st.flow.length() > 0.0:
            let n = st.form.n if st.has_face else st.tangent.cross(st.flow)
            e = n.cross(st.flow).normalized() catch failure: recover Vector3()
        if e.length() > 0.0:
            try put_derivative(fn, row, st.uv, st.d, 1, e)
            try held.hold(system, row, weight * flow_weight, 0.0, 0.0)

## A guide point: where (normalized), its chart point, and the guide
## face's normal for G1 (zero none).
struct GuidePoint:
    var p: Vector3
    var uv: Vector3
    var n: Vector3

## The guides' points onto `out` (normalized; chart points N-sided by the
## projection, Quad later by the nearest point of a first answer).
func guide_points(w: FillWork*, per_length: f64, out: Growing[GuidePoint]*) -> !:
    out.clear()
    for m in w.guides.items[..<w.guides.count]:
        if m.curve.points.count == 0: error(invalid, "Fill: a guide is a face; pick curves, edges, isoparms or points")
        let length = size_of(&m.curve) / w.scale
        let count = (usize)math.clamp(math.ceil(length * per_length), 8.0, 400.0)
        for q in 0..<count + 1:
            let t = m.curve.low() + (m.curve.high() - m.curve.low()) * (f64)q / (f64)count
            let p = m.curve.point_at(t)
            var n = Vector3()
            if m.has_face and w.opts.guide_order >= 1:
                var held = m
                n = (try neighbor_at(&held, p, w.scale)).n
            let local = w.local(p)
            try out.push(GuidePoint(local, w.chart(local), n))
    for p in w.points.view():
        let local = w.local(p)
        try out.push(GuidePoint(local, w.chart(local), Vector3()))

## The answer for `stations` and `guides` on `fn` (its free control points
## set). G0 and G1 are linear: one factored system, solved again with the
## multipliers' shifts (HeldRows) until they settle. G2 asks the normal
## part of S_dd to be II(S_d, S_d), quadratic in the answer: Gauss-Newton,
## each solve's G2 rows linearized about the last answer's cross
## derivatives (iterating the right side alone diverges: a larger S_d asks
## a larger S_dd, which stretches S_d further; the linearized row weighs
## that), until the cross derivatives settle. Returns the passes.
## `warm`: the net holds an answer already (a lid's turns, held now), so
## G2's rounds start from it rather than from a solve without G2's rows.
func solve_fill(w: const FillWork*, fn: FillNet*, stations: const FillStation[], guides: const GuidePoint[], warm: bool = false) -> i64!:
    var any_g2 = false
    for st in stations: any_g2 = any_g2 or (st.order >= 2 and st.has_face)
    var crosses = Growing[Vector3?]()
    defer crosses.close()
    var passes: i64 = 0
    if not (warm and any_g2): passes = try solve_once(w, fn, stations, guides, crosses.view())
    if not any_g2: return passes
    var merit = fill_merit(w, fn, stations)
    var before = Growing[Weighted]()
    defer before.close()
    var after = Growing[Weighted]()
    defer after.close()
    for round in 0..<8:
        crosses.clear()
        for st in stations:
            if st.order < 2 or not st.has_face:
                try crosses.push(none)
                continue
            let j = net_jet(fn, st.uv)
            try crosses.push(j[1].multiply_scalar(st.d.x).add(j[2].multiply_scalar(st.d.y)))
        try before.assign(fn.net.points.view())
        passes += try solve_once(w, fn, stations, guides, crosses.view())
        try after.assign(fn.net.points.view())
        # Damped: the step's share that lowers the stations' misfit (a
        # Gauss-Newton step is quadratic's guess, and on a tight neighbor,
        # a small fillet's curvature asking a long cross derivative, the
        # full step can overshoot and the rounds run away).
        var share = 1.0
        var taken = false
        for _ in 0..<6:
            for k in 0..<after.count:
                let a = before.items[k].point()
                fn.net.points.items[k] = weighted(a.add(after.items[k].point().subtract(a).multiply_scalar(share)), 1.0)
            let now = fill_merit(w, fn, stations)
            if now < merit:
                merit = now
                taken = true
                break
            share *= 0.5
        if not taken:
            # No share helps: the last answer stands.
            try fn.net.points.assign(before.view())
            break
        var change = 0.0
        for k in 0..<before.count: change = math.max(change, fn.net.points.items[k].point().subtract(before.items[k].point()).length())
        # Settled within a hundredth of the position tolerance.
        if change < w.position * settled_share: break
    return passes

## How far `fn` misses what `stations` ask, each measure over its
## tolerance, squared and summed (the damped rounds' merit): G0's gap, G1's
## normal part of the cross derivative, G2's normal curvature across.
func fill_merit(w: const FillWork*, fn: const FillNet*, stations: const FillStation[]) -> f64:
    var sum = 0.0
    for st in stations:
        let j = net_jet(fn, st.uv)
        if not w.opts.quad:
            let gap = j[0].subtract(st.p).length() / w.position
            sum += gap * gap
        if st.order < 1 or not st.has_face or st.weight < 1.0: continue
        let sd = j[1].multiply_scalar(st.d.x).add(j[2].multiply_scalar(st.d.y))
        let speed = math.max(sd.dot(sd), nonzero)
        let slope = st.held.dot(sd) / (math.sqrt(speed) * math.max(w.angle, least_angle_tolerance))
        sum += slope * slope
        if st.order < 2: continue
        let sdd = j[3].multiply_scalar(st.d.x * st.d.x).add(j[4].multiply_scalar(2.0 * st.d.x * st.d.y)).add(j[5].multiply_scalar(st.d.y * st.d.y))
        let want = st.form.curvature_of(sd)
        let bent = (st.form.n.dot(sdd) - want) / (math.max(math.abs(want), fill_curvature_floor * speed) * w.curvature * percent_share)
        sum += bent * bent
    return sum

## One factored solve of `stations` and `guides` on `fn`, G2 rows where
## `crosses` gives a station's cross derivative (empty: none), repeated
## with the multipliers' shifts until they settle. Returns the passes.
func solve_once(w: const FillWork*, fn: FillNet*, stations: const FillStation[], guides: const GuidePoint[], crosses: const (Vector3?)[]) -> i64!:
    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 system = try band_system(fn.count, fn.half)
    defer system.close()
    let tension = math.clamp(w.opts.tension, 0.0, 1.0)
    let flat = math.clamp(w.opts.flatness, 0.0, 1.0)
    # G2 asks a third-order energy (the rate of bending, Moreton and
    # Séquin's minimum variation): with position, slope and curvature held
    # it is the well-posed one, as bending is for position and slope.
    var higher = false
    for st in stations: higher = higher or (st.order >= 2 and st.has_face) or st.turned
    let bend = 1.0 - 0.99 * tension
    try add_energy(&system, fn, bend * (bend_with_rate if higher else 1.0), bend if higher else 0.0, tension * 10.0, flat * 100.0, w.ez)
    var base = Growing[f64]()
    defer base.close()
    try base.assign(system.rhs.view())
    let weight = 1e6 * system.diagonal_mean()
    var row = try fill_row(fn.count)
    defer row.close()
    var held = held_rows()
    defer held.close()
    for at in 0..<stations.length:
        let cross: Vector3? = crosses[at] if at < crosses.length else none
        try station_rows(w, fn, &system, &held, &row, &stations[at], cross, weight)
    for g in guides:
        for c in 0..<(usize)3:
            try put_derivative(fn, &row, g.uv, Vector3(), 0, axes[c])
            try held.hold(&system, &row, weight, g.p.dot(axes[c]), w.position * 0.1)
        if g.n.length() > 0.0:
            try put_derivative(fn, &row, g.uv, Vector3(1.0, 0.0, 0.0), 1, g.n)
            try held.hold(&system, &row, weight, 0.0, w.angle * 0.1)
            try put_derivative(fn, &row, g.uv, Vector3(0.0, 1.0, 0.0), 1, g.n)
            try held.hold(&system, &row, weight, 0.0, w.angle * 0.1)
    try system.factor()
    var x = Growing[f64]()
    defer x.close()
    let passes = try solve_held(&system, &held, base.view(), &x)
    take_answer(fn, x.view())
    return passes