dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / 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.
## The weight a cone row's held slope gets against the fit's other rows.
let cone_slope_weight: f64 = 1e-2
## The fairness term's weight per unit of the two spans' product.
let fairness_weight: f64 = 1e-5
## 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) * relative_zero:
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 < singular_floor: 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), cone_slope_weight)
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 = fairness_weight * 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]