dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / surfacing / square_fields.lucb
## Square's fields (square.lucb has the plan): the derivatives across each
## side its continuity asks (field_targets), the corners' mixed
## derivatives every field holds (corner_set), and each field fitted on its
## pair's knots, a corner whose neighbors disagree confined to its zone.
## A side's target counts as square to the boundary when its part along
## it is over `square_least`; Implied continuity's symmetry plane holds
## the side within `plane_share` of its size; the targets' end differences
## step `target_step` (fractions of the side) apart.
let square_least: f64 = 1e-6
let plane_share: f64 = 1e-6
let target_step: f64 = 1e-3
# -- The fields.
## Whether `code` asks a neighbor's tangent plane, its curvature, a plane.
func wants_tangent(code: i64) -> bool:
return code == square_g1 or code == square_g2 or code == square_angle
func order_of_code(code: i64, cubic: bool) -> usize:
if code == square_g2 or code == square_implied_curvature: return 2
if code == square_g1 or code == square_implied_tangent or code == square_angle: return 1
return 1 if cubic else 0
## 0 at a side's ends rising to 1 a quarter of the way in (a quintic
## smoothstep, flat to the second order at the ends): where Boundary
## Blend, Influence and Colinear act, leaving the corners as they are.
func plateau(t: f64) -> f64:
let x = math.min(1.0, math.min(t, 1.0 - t) * 4.0)
if x <= 0.0: return 0.0
return x * x * x * (10.0 - 15.0 * x + 6.0 * x * x)
## Picked boundary `k`'s reach: its pair's Influence, and the Boundary
## Blend's share (the first of the pair 2 b, the second 2 (1 - b), so b
## above a half moves where they meet toward the second).
func side_reach(opts: const SquareOptions*, k: usize) -> f64:
let pair = k % 2
let share = 2.0 * opts.blend[pair] if k < 2 else 2.0 * (1.0 - opts.blend[pair])
return opts.influence[pair] * share
## The cross derivatives side `s` asks at fraction `t` along it (1 and,
## for G2, 2), onto `out` (out[1], out[2]); `sides` all four, `lin` the
## G0 patch (its slope gives the probe's way out and the corners' twists).
func field_targets(sides: SquareSide[4]*, masters: Growing[Master]*, s: usize, lin: const Net*, plane: Vector3, t: f64, out: Vector3[3]*) -> !:
let side = &(*sides)[s]
let code = side.code
let curve = &side.curve
let point = try field_jet(curve, t, 1, t >= 1.0)
# The corners: the neighbors' derivatives across this side (the
# tangents, second derivatives) and the G0 patch's twists.
let (first, at0) = adjacent(s, false)
let (last, at1) = adjacent(s, true)
let j0 = try field_jet(&(*sides)[first].curve, at0, 2, at0 >= 1.0)
let j1 = try field_jet(&(*sides)[last].curve, at1, 2, at1 >= 1.0)
var parts: Weighted[16]
var shown: Weighted[16]
let c0 = side_uv(s, 0.0)
let c1 = side_uv(s, 1.0)
lin.partials(c0.x, c0.y, &parts)
euclidean_partials(&parts, &shown)
let twist0 = Vector3(shown[5].x, shown[5].y, shown[5].z)
lin.partials(c1.x, c1.y, &parts)
euclidean_partials(&parts, &shown)
let twist1 = Vector3(shown[5].x, shown[5].y, shown[5].z)
let l = cubic_hermite(j0.d[1], twist0, j1.d[1], twist1, t)
let m = j0.d[2].multiply_scalar(1.0 - t).add(j1.d[2].multiply_scalar(t))
# Boundary Blend and Influence: the slope across scaled off the
# corners (the corners' own data untouched).
let reach = 1.0 + (side.reach - 1.0) * plateau(t)
if code == square_implied_tangent or code == square_implied_curvature:
(*out)[1] = plane.multiply_scalar(l.dot(plane) * reach)
(*out)[2] = m.subtract(plane.multiply_scalar(m.dot(plane)))
return
# The G0 patch's slope across (Blend Cubic's field for G0 and Free).
let uv = side_uv(s, t)
lin.partials(uv.x, uv.y, &parts)
euclidean_partials(&parts, &shown)
let slope = Vector3(shown[4].x, shown[4].y, shown[4].z) if s < 2 else Vector3(shown[1].x, shown[1].y, shown[1].z)
if not wants_tangent(code):
(*out)[1] = slope.multiply_scalar(reach)
return
# The neighbor's answer at the boundary's point there.
let outward = slope.multiply_scalar(-1.0) if s == 0 or s == 2 else slope
let probe = Probe(point.d[0], point.d[1], outward, empty_jet())
var m_master = &masters.items[side.picked]
let goal = try m_master.target(m_master.nearest(point.d[0]), &probe, 0.0)
var n = goal.n
if not (n.length() > 0.0): error(invalid, "Square: G1 and G2 need the boundary on a surface (an edge, or a curve on a face)")
# The way on from the neighbor across the boundary, in its tangent
# plane square to the boundary (the neighbor continued).
var on = goal.t.multiply_scalar(-1.0)
if code == square_angle:
# The neighbor's tangent plane turned about the edge: positive
# angles lift the surface toward the neighbor's normal side (its
# way across turns toward n).
let a = side.angle * math.pi / 180.0
let tilted = n.multiply_scalar(math.cos(a)).subtract(on.multiply_scalar(math.sin(a)))
on = on.multiply_scalar(math.cos(a)).add(n.multiply_scalar(math.sin(a)))
n = tilted
# The slope across: L's part along the boundary kept (the skew the
# corners give), its part across turned onto the way on with its
# length. Where the neighbors' tangents lie in the neighbor's plane (a
# hole in one smooth surface) that is L in the plane, as a projection
# gives; where they leave it (a cap on a box's walls) a projection would
# shrink the slope to nothing, and this keeps its size (Alias's Square
# rises square off such walls).
let tangent = point.d[1].normalized() catch failure: error(invalid, "Square: a boundary stops (its tangent vanishes)")
# The neighbor's way across follows its isoparm; square it to the
# boundary, still in its tangent plane.
on = on.subtract(tangent.multiply_scalar(on.dot(tangent))).normalized() catch failure: error(invalid, "Square: the neighbor runs along the boundary there")
let along = tangent.multiply_scalar(l.dot(tangent))
# ∂S/∂u at u = 1 (and ∂S/∂v at v = 1) leaves the patch, into the
# neighbor: the way on reversed there.
let inward = 1.0 if s == 0 or s == 2 else -1.0
let across = l.subtract(along).length()
var d1 = along.add(on.multiply_scalar(inward * across))
if side.colinear and code != square_angle:
# Colinear: off the corners the slope runs along the neighbor's
# own isoparm across (as Align without skew), its part square to
# the boundary the same; at the corners the corners' lines.
let iso = goal.t.multiply_scalar(-1.0)
let square_part = iso.dot(on)
if square_part > square_least:
let lined = iso.multiply_scalar(inward * across / square_part)
let c = plateau(t)
d1 = d1.multiply_scalar(1.0 - c).add(lined.multiply_scalar(c))
d1 = d1.multiply_scalar(reach)
(*out)[1] = d1
if code == square_g2:
let ab = chart_direction(goal.su, goal.sv, d1)
let second = goal.l * ab.x * ab.x + 2.0 * goal.m * ab.x * ab.y + goal.nn * ab.y * ab.y
(*out)[2] = m.subtract(n.multiply_scalar(m.dot(n))).add(n.multiply_scalar(second))
## The plane a side's Implied continuity mirrors in (zero for others).
func side_plane(side: const SquareSide*) -> Vector3!:
if side.code != square_implied_tangent and side.code != square_implied_curvature: return Vector3()
let plane = curve_plane(&side.curve, size_of(&side.curve) * plane_share)
if not (plane.length() > 0.0): error(invalid, "Square: Implied continuity needs a boundary lying in a plane (the symmetry plane)")
return plane
## Derivative `k` across side `s` that its continuity asks at `t` along it.
func target_at(sides: SquareSide[4]*, masters: Growing[Master]*, s: usize, lin: const Net*, plane: Vector3, k: usize, t: f64) -> Vector3!:
var target: Vector3[3] = [Vector3(), Vector3(), Vector3()]
try field_targets(sides, masters, s, lin, plane, math.clamp(t, 0.0, 1.0), &target)
return target[k]
## The derivatives along side `s` (orders 0 to 2) of its field `k`'s
## target at its start (`end` false) or end: one-sided differences of
## fourth order a thousandth apart (the targets are smooth along a side).
func target_ends(sides: SquareSide[4]*, masters: Growing[Master]*, s: usize, lin: const Net*, plane: Vector3, k: usize, end: bool, out: Vector3[3]*) -> !:
let h = target_step
var f: Vector3[5] = [Vector3(), Vector3(), Vector3(), Vector3(), Vector3()]
for i in 0..<(usize)5:
let t = 1.0 - h * (f64)i if end else h * (f64)i
f[i] = try target_at(sides, masters, s, lin, plane, k, t)
let way = -1.0 if end else 1.0
(*out)[0] = f[0]
(*out)[1] = f[0].multiply_scalar(-25.0).add(f[1].multiply_scalar(48.0)).add(f[2].multiply_scalar(-36.0)).add(f[3].multiply_scalar(16.0)).add(f[4].multiply_scalar(-3.0)).multiply_scalar(way / (12.0 * h))
(*out)[2] = f[0].multiply_scalar(35.0).add(f[1].multiply_scalar(-104.0)).add(f[2].multiply_scalar(114.0)).add(f[3].multiply_scalar(-56.0)).add(f[4].multiply_scalar(11.0)).multiply_scalar(1.0 / (12.0 * h * h))
## The corners' mixed derivatives ∂^(a+b) S/∂u^a ∂v^b, a and b 0 to 2,
## one set the four sides' fields all hold (so the Gordon patch meets every
## field exactly): along the boundaries (a or b 0) the boundary curves'
## own derivatives; where both sides have a field, the mean of what each
## asks (they agree when the neighbors do, as on one smooth surface); else
## the one side's. Corner (ab, cd) of sides ab (0 A, 1 B) and cd (2 C, 3
## D) at [(ab 2 + cd - 2) 9 + a 3 + b].
func corner_set(sides: SquareSide[4]*, masters: Growing[Master]*, lin: const Net*, cubic: bool, out: Growing[Vector3]*) -> !:
try out.fill(36, Vector3())
for ab in 0..<(usize)2:
for cd in 2..<(usize)4:
let along_ab = cd == 3
let along_cd = ab == 1
let corner = (ab * 2 + cd - 2) * 9
let o_ab = order_of_code((*sides)[ab].code, cubic)
let o_cd = order_of_code((*sides)[cd].code, cubic)
let plane_ab = try side_plane(&(*sides)[ab])
let plane_cd = try side_plane(&(*sides)[cd])
let jab = try field_jet(&(*sides)[ab].curve, 1.0 if along_ab else 0.0, 2, along_ab)
let jcd = try field_jet(&(*sides)[cd].curve, 1.0 if along_cd else 0.0, 2, along_cd)
for b in 0..<(usize)3: out.items[corner + b] = jab.d[b]
for a in 0..<(usize)3: out.items[corner + a * 3] = jcd.d[a]
out.items[corner] = jab.d[0].add(jcd.d[0]).multiply_scalar(0.5)
for a in 1..<(usize)3:
var from_ab: Vector3[3] = [Vector3(), Vector3(), Vector3()]
if a <= o_ab: try target_ends(sides, masters, ab, lin, plane_ab, a, along_ab, &from_ab)
for b in 1..<(usize)3:
var from_cd: Vector3[3] = [Vector3(), Vector3(), Vector3()]
if b <= o_cd: try target_ends(sides, masters, cd, lin, plane_cd, b, along_cd, &from_cd)
var value = Vector3()
if a <= o_ab and b <= o_cd: value = from_ab[b].add(from_cd[a]).multiply_scalar(0.5)
elif a <= o_ab: value = from_ab[b]
elif b <= o_cd: value = from_cd[a]
out.items[corner + a * 3 + b] = value
# -- Corners whose neighbors disagree.
#
# Where the two neighbors at a corner ask different things there (a cap on
# a box's walls: each wall wants the patch rising square off it, while the
# other boundary leaves the corner flat along the top), no surface meets
# both fields at the corner itself: such a corner is singular. Gregory's
# patch (1974) keeps each side's own field everywhere but the corner and
# lets the twist there depend on the way in; ours does the same locally: a
# side's field is its own target, plus the corner set's mismatch (its
# value and first two derivatives) carried down to nothing by a quintic
# Hermite within the corner zone, a span of its own. Off the zone each field is
# exactly what its continuity asks, so the boundary measures G1 or G2 all
# along it but for the zone's sliver at the corner, which Alias's Square
# leaves as a break at the corner too.
## The corner zone: the fraction of a side the mismatch fades over.
let corner_zone: f64 = 1.0 / 256.0
## The quintic Hermite on the zone (s from 0 to 1 across it) taking the
## values `d` (the mismatch and its first two derivatives, by the side's
## parameter, `h` the zone's length signed the way in) at s = 0 down to
## nothing, flat to the second order, at s = 1: one quintic span, so a
## field's fit holds it exactly.
func zone_hermite(d: const Vector3[3]*, s: f64, h: f64) -> Vector3:
if s >= 1.0: return Vector3()
let s2 = s * s
let s3 = s2 * s
let h0 = 1.0 - s3 * (10.0 - 15.0 * s + 6.0 * s2)
let h1 = s - s3 * (6.0 - 8.0 * s + 3.0 * s2)
let h2 = 0.5 * (s2 - s3 * (3.0 - 3.0 * s + s2))
return (*d)[0].multiply_scalar(h0).add((*d)[1].multiply_scalar(h * h1)).add((*d)[2].multiply_scalar(h * h * h2))
## A field's corner mismatches at its start and end (derivatives 0 to 2
## along the side) and whether each end has one.
struct ZoneFix:
var start: Vector3[3]
var end: Vector3[3]
var at_start: bool
var at_end: bool
## The correction at `t` along the side.
func at(t: f64) -> Vector3:
var fix = Vector3()
if self.at_start and t < corner_zone: fix = fix.add(zone_hermite(&self.start, t / corner_zone, corner_zone))
if self.at_end and t > 1.0 - corner_zone: fix = fix.add(zone_hermite(&self.end, (1.0 - t) / corner_zone, -corner_zone))
return fix
## Side `s`'s fields (see the file's header) onto it, each holding the
## corner set's derivatives along the side (to the second) at both ends;
## the worst fit of a field returned, and the middles of the spans that
## missed `tolerance` (against the largest value it holds) onto `missed`.
## A corner whose mismatch would move the field beyond the tolerance gets
## its zone (see above): the zone's knot, when the side lacks it, onto
## `zones` (the patch is then built again with it).
func make_fields(sides: SquareSide[4]*, masters: Growing[Master]*, s: usize, lin: const Net*, cubic: bool, corners: const Vector3[], tolerance: f64, missed: Growing[f64]*, zones: Growing[f64]*) -> f64!:
let order = order_of_code((*sides)[s].code, cubic)
try (*sides)[s].fields.push(try (*sides)[s].curve.copy())
if order == 0: return 0.0
let plane = try side_plane(&(*sides)[s])
let q = (*sides)[s].curve.degree
var knots = Growing[f64]()
defer knots.close()
try knots.assign((*sides)[s].curve.knots.view())
let count = (*sides)[s].curve.points.count
let keep = fewer(2, count // 2 - 1)
var params = Growing[f64]()
defer params.close()
try fit_parameters(knots.view(), q, 2 * ((usize)q + 1), ¶ms)
var fitter = try make_fitter(q, knots.view(), params.view(), keep)
defer fitter.close()
var worst = 0.0
for k in 1..<order + 1:
# The corners: A and B (s 0, 1) meet C at their start, D at their
# end; C and D meet A and B. Derivative k across, b along.
var starts: Weighted[4]
var ends: Weighted[4]
for b in 0..<(usize)4:
starts[b] = Weighted(0.0, 0.0, 0.0, 0.0)
ends[b] = Weighted(0.0, 0.0, 0.0, 0.0)
var own_start: Vector3[3] = [Vector3(), Vector3(), Vector3()]
var own_end: Vector3[3] = [Vector3(), Vector3(), Vector3()]
try target_ends(sides, masters, s, lin, plane, k, false, &own_start)
try target_ends(sides, masters, s, lin, plane, k, true, &own_end)
var fix = ZoneFix([Vector3(), Vector3(), Vector3()], [Vector3(), Vector3(), Vector3()], false, false)
for b in 0..<keep + 1:
let first = (s * 2 + 0) * 9 + k * 3 + b if s < 2 else ((s - 2) * 9 + b * 3 + k)
let last = (s * 2 + 1) * 9 + k * 3 + b if s < 2 else ((2 + s - 2) * 9 + b * 3 + k)
let a0 = corners[first]
let a1 = corners[last]
starts[b] = Weighted(a0.x, a0.y, a0.z, 0.0)
ends[b] = Weighted(a1.x, a1.y, a1.z, 0.0)
fix.start[b] = a0.subtract(own_start[b])
fix.end[b] = a1.subtract(own_end[b])
var largest = 0.0
for t in params.view(): largest = math.max(largest, (try target_at(sides, masters, s, lin, plane, k, t)).length())
# A corner zone where the field itself must break off (its value
# disagrees with the corner's), its knot first. A disagreement in
# the twists alone is a gentle one, spread along the side by the
# fit as Coons patches do.
fix.at_start = fix.start[0].length() > tolerance * 0.1 * math.max(largest, nonzero)
fix.at_end = fix.end[0].length() > tolerance * 0.1 * math.max(largest, nonzero)
let joint = (usize)math.max(1.0, (f64)(q - 2))
if fix.at_start and multiplicity(knots.view(), corner_zone, knot_same) < joint: try zones.push(corner_zone)
if fix.at_end and multiplicity(knots.view(), 1.0 - corner_zone, knot_same) < joint: try zones.push(1.0 - corner_zone)
var values = Growing[Weighted]()
defer values.close()
for t in params.view():
let target = (try target_at(sides, masters, s, lin, plane, k, t)).add(fix.at(t))
try values.push(Weighted(target.x, target.y, target.z, 0.0))
var made = empty_spline(q)
errdefer made.close()
try made.knots.assign(knots.view())
try fitter.fit(values.view(), &starts, &ends, &made.points)
# How far it misses between the fit's parameters.
for span in (usize)q..<count:
let a = knots.items[span]
let b = knots.items[span + 1]
if not (b > a): continue
var off = 0.0
for i in 1..<(usize)8:
let t = a + (b - a) * (f64)i / 8.0
let target = (try target_at(sides, masters, s, lin, plane, k, t)).add(fix.at(t))
let got = try field_jet(&made, t, 0, false)
off = math.max(off, got.d[0].subtract(target).length())
worst = math.max(worst, off)
if off / math.max(largest, nonzero) > tolerance: try missed.push((a + b) * 0.5)
try (*sides)[s].fields.push(made)
return worst