dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / 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 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 * 1e-3
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 > 0.05 and st.s < 0.95)):
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 * 1e-4, 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)), 5e-4 * l.dot(l))
try held.hold(system, row, weight * ease, -st.form.curvature_of(l), bent * w.curvature * 1e-3 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 * 1e-2, 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 * 0.01: 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, 1e-12))
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), 5e-4 * speed) * w.curvature * 0.01)
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 * (0.01 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