dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / surfacing / blend_surface.lucb
## Blend Surface (surfacing Stage 6: Alias's Freeform Blend and Profile
## Blend, Plasticity's Bridge Surface, Rhino's BlendSrf; §4.1 and §6.7 of
## luced-3d's docs/research/SURFACING-ALIAS-PLASTICITY.md): a surface
## between two sides, each a chain of edges, isoparms, curves on faces or
## free curves (Align's master words; a chain's apart by `+`), meeting
## each G0 to G3, optionally through profile curves.
##
## The sides are matched by the fraction of their length (Flow Control
## Connect ends: start to start, end to end; Free: each station on side 2
## where the plane square to side 1 there cuts it; Edge align: by each
## side's own parameter, so the isoparms leave the sides as their surfaces'
## do), within each side's range (Modify Range); with Interior Edge Align
## side 2 is matched through the profiles' far ends, so the blend's
## isoparms run along the profiles. At a station the section runs from side 1's point
## to side 2's: a B-spline across of degree 5 on uniform spans, as many
## control points as the two sides' continuity holds (six at least; eight,
## three spans, for G3 both sides), whose first rows are the curve that
## continues side 1's surface across it (§6.1's rows by arc length: A' =
## vT, A'' = v²K, A''' = v³K', T the unit tangent, K the curvature vector
## and K' its rate of the surface's curve leaving the side, v the speed)
## and whose last rows are side 2's likewise. The speed v is the side's
## Shape times the chord between the two points (above 1 tighter toward
## the corner, below rounder); the loose middle control points, and the
## orders a side does not ask, follow the cubic Hermite of the ends (a
## straight line between G0 sides), bowed by Proportional Crown (a
## fraction of the chord along the normal of the chord and side 1's run).
## A profile curve (Profile Blend) is passed at its station: the section
## there fitted to it with the same end rows, and the difference from the
## free section carried along the blend by a cubic between profiles
## (constant past the first and last), so the end rows stay exact. The
## sections' rows are fitted along the blend (along.lucb).
pub let flow_connect: i64 = 0
pub let flow_free: i64 = 1
## Edge align: the sides matched by their own parameters, so the blend's
## isoparms leave each side where its surface's own do (a face's edge's
## parameter is its isoparms').
pub let flow_edge: i64 = 2
## Blend Surface's options: each side's continuity (0 G0 to 3 G3) and
## Shape, Proportional Crown, Flow Control, and each side's range (side
## 1 from and to, side 2 from and to, fractions of its length).
pub struct BlendOptions:
pub var continuity: i64[2]
pub var shape: f64[2]
pub var crown: f64
pub var flow: i64
pub var range: f64[4]
## Profile Blend's Interior Edge Align: the blend's isoparms run along
## each profile from side to side (side 2 matched through the profiles'
## far ends); off, as Flow Control matches it. Explicit Control.
pub var interior: bool = false
pub var explicit: Explicit = Explicit(false, 0, 0, 0, 0)
## One side: its masters (the chain), the chain joined into one curve on
## 0..1 within its range, that curve's arc table, its continuity and Shape.
struct BlendSide:
var masters: Growing[Master]
var curve: Spline
var arc: ArcTable
var order: i64
var shape: f64
func close():
close_masters(&self.masters)
self.curve.close()
self.arc.close()
## A profile's correction: its station (a fraction of side 1) and the
## difference of each control point from the free section there.
struct ProfileFix:
var place: f64
var delta: Growing[Weighted]
## What the sections need.
struct BlendWork:
var one: BlendSide
var two: BlendSide
var flow: i64
var crown: f64
## The knots across, the control points a section has, the rows each
## side holds (the fitter's keep), and the fitter across.
var knots: Growing[f64]
var size: usize
var keep: usize
var params: Growing[f64]
var fitter: Fitter
var fixes: Growing[ProfileFix]
## Interior Edge Align: (side 1, side 2) fractions each profile joins,
## in order along side 1.
var pairs: Growing[f64]
func close():
self.one.close()
self.two.close()
self.knots.close()
self.params.close()
self.fitter.close()
self.pairs.close()
for f in self.fixes.view():
var owned = f
owned.delta.close()
self.fixes.close()
## The point of `side` at fraction `s` of its length and its tangent there.
func run_point(side: BlendSide*, s: f64) -> (Vector3, Vector3)!:
let t = try arc_param(&side.curve, &side.arc, s)
let j = try curve_jet(&side.curve, t, 1, t >= side.curve.high())
return (j.d[0], j.d[1])
## The curve leaving `side` into the blend at `p` (its run `along` there),
## toward `toward`: the unit tangent, curvature vector and its rate by arc
## length of the surface's curve across the side (an edge's face
## continued past the edge; a curve on a face or an isoparm, the face on
## toward the other side).
func side_leaving(side: BlendSide*, p: Vector3, along: Vector3, toward: Vector3) -> (Vector3, Vector3, Vector3)!:
var best: usize = 0
var best_distance = 1.0e300
for k in 0..<side.masters.count:
let c = &side.masters.items[k].curve
let d = c.point_at(spline_nearest(c, p)).subtract(p).length()
if d < best_distance:
best_distance = d
best = k
let m = &side.masters.items[best]
if not m.has_face: error(invalid, "Blend Surface: G1 and above need the side on a surface (an edge, an isoparm or a curve on a face); a free curve's side is G0")
let c = &m.curve
let fraction = (spline_nearest(c, p) - c.low()) / math.max(nonzero, c.high() - c.low())
let probe = Probe(p, along, toward.subtract(p), empty_jet())
let goal = try m.target(fraction, &probe, 0.0)
if m.kind == master_edge: return (goal.t.multiply_scalar(-1.0), goal.k, goal.dk.multiply_scalar(-1.0))
return (goal.t, goal.k, goal.dk)
## Side 2's fraction for side 1's point `p` with run `along` (Flow Control
## Free): where the plane through `p` square to `along` cuts side 2,
## nearest `near`; `near` when it does not.
func free_match(w: BlendWork*, p: Vector3, along: Vector3, near: f64) -> f64!:
let d = along.normalized() catch failure: return near
var best = near
var best_gap = 1.0e300
var before = 0.0
var before_value = 0.0
for k in 0..<(usize)129:
let s = (f64)k / 128.0
let (q, _) = try run_point(&w.two, s)
let value = q.subtract(p).dot(d)
if k > 0 and (value == 0.0 or (value > 0.0) != (before_value > 0.0)):
# Bisect the crossing.
var a = before
var b = s
var fa = before_value
for _ in 0..<60:
let m = (a + b) * 0.5
let (qm, _) = try run_point(&w.two, m)
let fm = qm.subtract(p).dot(d)
if (fm > 0.0) == (fa > 0.0):
a = m
fa = fm
else: b = m
let at = (a + b) * 0.5
if math.abs(at - near) < best_gap:
best_gap = math.abs(at - near)
best = at
before = s
before_value = value
return best
## The free section at fraction `s` of side 1 (no profile's correction)
## onto `out`.
func free_section(w: BlendWork*, s: f64, out: Growing[Weighted]*) -> !:
let (p0, a0) = try run_point(&w.one, s)
var s2 = try free_match(w, p0, a0, s) if w.flow == flow_free else s
if w.pairs.count >= 2:
# Through the profiles' ends (linear between, the sides' ends at
# 0 and 1).
var a1 = 0.0
var a2 = 0.0
var b1 = 1.0
var b2 = 1.0
for k in 0..<w.pairs.count // 2 + 1:
let n1 = w.pairs.items[2 * k] if k < w.pairs.count // 2 else 1.0
let n2 = w.pairs.items[2 * k + 1] if k < w.pairs.count // 2 else 1.0
if n1 >= s:
b1 = n1
b2 = n2
break
a1 = n1
a2 = n2
s2 = a2 + (b2 - a2) * (s - a1) / math.max(nonzero, b1 - a1)
let (p1, a1) = try run_point(&w.two, s2)
let chord = p1.subtract(p0)
let c = chord.length()
if not (c > 0.0): error(invalid, "Blend Surface: the two sides meet; a blend needs a gap between them")
# The surfaces' curves leaving each side (none for G0).
var t0 = Vector3()
var k0 = Vector3()
var r0 = Vector3()
var t1 = Vector3()
var k1 = Vector3()
var r1 = Vector3()
if w.one.order > 0:
let (a, b, d) = try side_leaving(&w.one, p0, a0, p1)
t0 = a
k0 = b
r0 = d
if w.two.order > 0:
let (a, b, d) = try side_leaving(&w.two, p1, a1, p0)
t1 = a
k1 = b
r1 = d
let v0 = w.one.shape * c
let v1 = w.two.shape * c
# The reference: the cubic Hermite of the ends (the chord's slope at a
# G0 side), bowed by the crown along the normal of the chord and side
# 1's run.
let m0 = t0.multiply_scalar(v0) if w.one.order > 0 else chord
let m1 = t1.multiply_scalar(-v1) if w.two.order > 0 else chord
var bow = Vector3()
if w.crown != 0.0:
let n = chord.cross(a0).normalized() catch failure: recover Vector3()
bow = n.multiply_scalar(4.0 * w.crown * c)
let third = p0.multiply_scalar(12.0).add(m0.multiply_scalar(6.0)).subtract(p1.multiply_scalar(12.0)).add(m1.multiply_scalar(6.0))
let reference_start: Vector3[4] = [p0, m0.add(bow), p0.multiply_scalar(-6.0).subtract(m0.multiply_scalar(4.0)).add(p1.multiply_scalar(6.0)).subtract(m1.multiply_scalar(2.0)).subtract(bow.multiply_scalar(2.0)), third]
let reference_end: Vector3[4] = [p1, m1.subtract(bow), p0.multiply_scalar(6.0).add(m0.multiply_scalar(2.0)).subtract(p1.multiply_scalar(6.0)).add(m1.multiply_scalar(4.0)).subtract(bow.multiply_scalar(2.0)), third]
# The rows each side asks, the reference's past its order.
let own_start: Vector3[4] = [p0, t0.multiply_scalar(v0), k0.multiply_scalar(v0 * v0), r0.multiply_scalar(v0 * v0 * v0)]
let own_end: Vector3[4] = [p1, t1.multiply_scalar(-v1), k1.multiply_scalar(v1 * v1), r1.multiply_scalar(-v1 * v1 * v1)]
var starts: Weighted[4] = [Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0)]
var ends: Weighted[4] = [Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0)]
for j in 0..<w.keep + 1:
let a = own_start[j] if (i64)j <= w.one.order else reference_start[j]
let b = own_end[j] if (i64)j <= w.two.order else reference_end[j]
starts[j] = Weighted(a.x, a.y, a.z, 1.0 if j == 0 else 0.0)
ends[j] = Weighted(b.x, b.y, b.z, 1.0 if j == 0 else 0.0)
var values = Growing[Weighted]()
defer values.close()
for t in w.params.view():
let h = cubic_hermite(p0, m0, p1, m1, t).add(bow.multiply_scalar(t * (1.0 - t)))
try values.push(weighted(h, 1.0))
try w.fitter.fit(values.view(), &starts, &ends, out)
## The section at fraction `s` of side 1: the free one, corrected by the
## profiles (a cubic between their stations, constant past the ends).
func blend_section(context: void*, s: f64, out: Growing[Weighted]*) -> !:
let w = (BlendWork*)context
try free_section(w, s, out)
let n = w.fixes.count
if n == 0: return
var j: usize = 0
while j + 1 < n and w.fixes.items[j + 1].place <= s: j += 1
for i in 0..<w.size:
var fix = w.fixes.items[0].delta.items[i]
if n > 1 and s > w.fixes.items[0].place and s < w.fixes.items[n - 1].place:
# Catmull-Rom slopes (flat at the first and last profile).
let a = w.fixes.items[j].place
let b = w.fixes.items[j + 1].place
let f = (s - a) / (b - a)
let da = fix_slope(w, j, i).times(b - a)
let db = fix_slope(w, j + 1, i).times(b - a)
let pa = w.fixes.items[j].delta.items[i]
let pb = w.fixes.items[j + 1].delta.items[i]
let f2 = f * f
let f3 = f2 * f
fix = pa.times(2.0 * f3 - 3.0 * f2 + 1.0).plus(da.times(f3 - 2.0 * f2 + f)).plus(pb.times(-2.0 * f3 + 3.0 * f2)).plus(db.times(f3 - f2))
elif n > 1 and s >= w.fixes.items[n - 1].place:
fix = w.fixes.items[n - 1].delta.items[i]
out.items[i] = out.items[i].plus(fix)
## Profile `k`'s correction's slope along the blend at control point `i`.
func fix_slope(w: const BlendWork*, k: usize, i: usize) -> Weighted:
let n = w.fixes.count
if k == 0 or k + 1 >= n: return Weighted(0.0, 0.0, 0.0, 0.0)
let a = &w.fixes.items[k - 1]
let b = &w.fixes.items[k + 1]
return b.delta.items[i].minus(a.delta.items[i]).times(1.0 / (b.place - a.place))
## A side from the chain `words` (a chain's masters apart by `+`), its
## range `from` to `to`.
func blend_side(set: interop.Reference[GeometrySet], words: str, order: i64, shape: f64, from_at: f64, to_at: f64, own: bool) -> BlendSide!:
var masters = Growing[Master]()
errdefer close_masters(&masters)
let bytes = words.bytes
var start: usize = 0
for at in 0..<bytes.length + 1:
if at < bytes.length and bytes[at] != 43: continue
if at > start: try masters.push(try master_of(set, (str)bytes[start..<at], -1, Vector3()))
start = at + 1
if masters.count == 0: error(invalid, "Blend Surface: pick both sides (edges, isoparms or curves)")
var whole = try joined_set(masters.view())
defer whole.close()
if not (from_at >= 0.0 and to_at <= 1.0 and to_at - from_at > least_range): error(invalid, "Blend Surface: a side's range runs from 0 to 1 of it, start before end")
var curve = try segment_of(&whole, from_at, to_at)
errdefer curve.close()
let arc = try placing_table(&curve, own)
return BlendSide(masters, curve, arc, order, shape)
## Blend Surface's net between sides `first` and `second` by `opts`,
## through the profile curves `profiles` (Align's master words apart by
## `;`; none for a Freeform Blend).
func blend_net(set: interop.Reference[GeometrySet], first: str, second: str, opts: const BlendOptions*, profiles: str) -> Net!:
for k in 0..<(usize)2:
if opts.continuity[k] < 0 or opts.continuity[k] > 3: error(invalid, "Blend Surface: each side is G0 to G3")
if not (opts.shape[k] > 0.0): error(invalid, "Blend Surface: a side's Shape is more than 0")
let own = opts.flow == flow_edge
var one = try blend_side(set, first, opts.continuity[0], opts.shape[0], opts.range[0], opts.range[1], own)
var two = blend_side(set, second, opts.continuity[1], opts.shape[1], opts.range[2], opts.range[3], own) catch failure:
one.close()
error(failure.code, failure.message)
# Side 2 runs the way side 1 does (their starts nearer than crossed).
let a0 = one.curve.point_at(0.0)
let a1 = one.curve.point_at(1.0)
if a0.subtract(two.curve.point_at(1.0)).length() + a1.subtract(two.curve.point_at(0.0)).length() < a0.subtract(two.curve.point_at(0.0)).length() + a1.subtract(two.curve.point_at(1.0)).length():
let turned_round = reversed_spline(&two.curve) catch failure:
one.close()
two.close()
error(failure.code, failure.message)
two.curve.close()
two.curve = turned_round
two.arc.close()
two.arc = placing_table(&two.curve, own) catch failure:
one.close()
two.close()
error(failure.code, failure.message)
var profile_masters = Growing[Master]()
defer close_masters(&profile_masters)
if profiles.length > 0:
builder_masters(set, profiles, &profile_masters) catch failure:
one.close()
two.close()
error(failure.code, failure.message)
# The section's structure: the rows each side holds (both the higher
# order), six control points at least, more for a profile to shape.
let keep = (usize)math.max((f64)opts.continuity[0], (f64)opts.continuity[1])
var size = 2 * (keep + 1)
if size < 6: size = 6
if profile_masters.count > 0: size += 2
var knots = Growing[f64]()
var params = Growing[f64]()
var made_fitter = section_fitter(size, keep, &knots, ¶ms) catch failure:
knots.close()
params.close()
one.close()
two.close()
error(failure.code, failure.message)
var w = BlendWork(one, two, opts.flow, opts.crown, knots, size, keep, params, made_fitter, Growing[ProfileFix](), Growing[f64]())
defer w.close()
# The sides' size sets the tolerance (shallow copies, only read).
let sides: Spline[2] = [w.one.curve, w.two.curve]
let tolerance = build_tolerance(sides[..<2])
# Interior Edge Align: where each profile's ends join the sides.
if opts.interior and profile_masters.count > 0:
for m in profile_masters.view():
let a = m.curve.point_at(m.curve.low())
let b = m.curve.point_at(m.curve.high())
let near_a = w.one.curve.point_at(spline_nearest(&w.one.curve, a)).subtract(a).length()
let near_b = w.one.curve.point_at(spline_nearest(&w.one.curve, b)).subtract(b).length()
let on_one = a if near_a <= near_b else b
let on_two = b if near_a <= near_b else a
let f1 = try arc_fraction(&w.one.curve, &w.one.arc, spline_nearest(&w.one.curve, on_one))
let f2 = try arc_fraction(&w.two.curve, &w.two.arc, spline_nearest(&w.two.curve, on_two))
var slot: usize = 0
while slot < w.pairs.count // 2 and w.pairs.items[2 * slot] < f1: slot += 1
try w.pairs.insert(2 * slot, f2)
try w.pairs.insert(2 * slot, f1)
# Each profile's station and its difference from the free section.
for m in profile_masters.view():
try add_profile(&w, &m.curve)
var source = SectionSource((void*)&w, blend_section, tolerance)
let spans = fewer(64, (usize)math.max(2.0, (f64)math.max((f64)span_count(&w.one.curve), (f64)span_count(&w.two.curve))))
var net = try along_net(&source, w.knots.view(), 5, size, spans)
if not opts.explicit.on: return net
defer net.close()
return try explicit_net(&net, &opts.explicit, keep, 0)
## The fitter across a section of `size` control points holding `keep` + 1
## at each end: its knots (degree 5, uniform) onto `knots`, its parameters
## onto `params`.
func section_fitter(size: usize, keep: usize, knots: Growing[f64]*, params: Growing[f64]*) -> Fitter!:
try uniform_knots(5, size - 5, 0.0, 1.0, knots)
try fit_parameters(knots.view(), 5, 12, params)
return try make_fitter(5, knots.view(), params.view(), keep)
## Profile curve `c` added to `w`'s corrections: its station is where its
## end nearer side 1 lies on it; there the section is fitted to it with the
## same end rows.
func add_profile(w: BlendWork*, c: const Spline*) -> !:
var profile = try c.copy()
defer profile.close()
unit_domain(&profile)
let start = profile.point_at(0.0)
let finish = profile.point_at(1.0)
let near_start = w.one.curve.point_at(spline_nearest(&w.one.curve, start)).subtract(start).length()
let near_finish = w.one.curve.point_at(spline_nearest(&w.one.curve, finish)).subtract(finish).length()
if near_finish < near_start:
let turned_round = try reversed_spline(&profile)
profile.close()
profile = turned_round
let foot = spline_nearest(&w.one.curve, profile.point_at(0.0))
let place = try arc_fraction(&w.one.curve, &w.one.arc, foot)
for f in w.fixes.view():
if math.abs(f.place - place) < same_place: error(invalid, "Blend Surface: two profiles sit at one place")
var loose = Growing[Weighted]()
defer loose.close()
try free_section(w, place, &loose)
# The section through the profile: the free one's end rows, its
# middle fitted to the profile's points (by their fraction of it).
var values = Growing[Weighted]()
defer values.close()
var table = try arc_table(&profile)
defer table.close()
for t in w.params.view(): try values.push(weighted(profile.point_at(try arc_param(&profile, &table, t)), 1.0))
var starts: Weighted[4] = [Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0)]
var ends: Weighted[4] = [Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0), Weighted(0.0, 0.0, 0.0, 0.0)]
# The end rows as the free section has them: its derivatives at both
# ends to the order held.
var section = empty_spline(5)
defer section.close()
try section.knots.assign(w.knots.view())
try section.points.assign(loose.view())
var jet: Weighted[6]
try homogeneous_jet(§ion, 0.0, w.keep, false, &jet)
for j in 0..<w.keep + 1: starts[j] = jet[j]
try homogeneous_jet(§ion, 1.0, w.keep, true, &jet)
for j in 0..<w.keep + 1: ends[j] = jet[j]
var through = Growing[Weighted]()
defer through.close()
try w.fitter.fit(values.view(), &starts, &ends, &through)
var delta = Growing[Weighted]()
errdefer delta.close()
for i in 0..<w.size: try delta.push(through.items[i].minus(loose.items[i]))
var slot = w.fixes.count
while slot > 0 and w.fixes.items[slot - 1].place > place: slot -= 1
try w.fixes.insert(slot, ProfileFix(place, delta))