dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / surfacing / fill.lucb
## Fill (surfacing Stage 7: xNURBS, Plasticity's xNURBS and Patch, Alias's
## N-sided, Rhino 9's Patch; §5.2 and §6.8 of luced-3d's
## docs/research/SURFACING-ALIAS-PLASTICITY.md): the smoothest surface that
## meets a closed loop of boundaries, each Free, G0, G1 or G2 to the
## surface beside it, through interior guide curves and points.
##
## The unknowns are the control points of a polynomial B-spline net,
## quintic both ways on uniform spans by default (Explicit Control sets the
## degrees and spans). The surface minimizes
## E = w_b ∫|∇²(S - R)|² + w_t ∫|∇³(S - R)|² + w_s ∫|∇S|² + w_f ∫(n0 . S)²
## (∇² the second derivatives |S_uu|² + 2|S_uv|² + |S_vv|², ∇³ the third
## |S_uuu|² + 3|S_uuv|² + 3|S_uvv|² + |S_vvv|²): bending, and with any G2
## boundary its rate (Moreton and Séquin's minimum variation, the order a
## curvature boundary condition is well posed in), both of S less a
## reference R, the neighbors carried on into the hole (fill_reference.lucb:
## a ball's cap fills with the ball, not a paraboloid); the membrane
## (Tension, tightening) and the pull toward the boundary's best plane
## (Flatness). The constraints are sampled at stations along the
## boundaries, rows of a least-squares system weighted a million times the
## energy's diagonal and driven to hold by the method of multipliers
## (fill_net.lucb's HeldRows):
## G0: S(uv_k) = B_k;
## G1: n_k . S_d(uv_k) = 0, n_k the neighbor's normal and d the chart
## direction across the boundary: linear, as n_k is fixed;
## G2: n_k . S_dd(uv_k) = II_k(S_d, S_d), the neighbor's second
## fundamental form on the fill's own cross derivative (Pegna and
## Wolter: with G1, equal normal curvature in one transversal direction
## is G2): quadratic, solved by Gauss-Newton, each solve's rows
## linearized about the last answer;
## guides: S(uv) = G at points along each guide curve and at each
## interior point, and with Guide G1 n . S_u = n . S_v = 0 where a
## guide lies on a face;
## flow (Quad): the cross derivative square to the boundary (Normal),
## along the next boundaries' blend (Next), or along the neighbor's own
## cross direction (Adjacent), a preference a hundredth as strong.
## The equations are banded (fill_bands.lucb): the energy's Gram matrices
## are exact per span, and each station touches one block of the net. The
## unknowns are the change from the reference (or a base plane), so the
## band's rounding is relative to that change.
##
## Two domains (§6.8):
## N-sided: the boundary projected onto its best plane (Newell's normal)
## gives each station's chart point; the net covers the projection's box
## with a margin and is trimmed by the boundaries laid on it (their
## feet on the fill, fitted to a billionth of the loop; the trim keeps
## the region holding a point just inside): one trimmed face, as
## xNURBS's N-sided result is, its edges within the fill's worst gap of
## the neighbors' (Stitch's tolerant edges join them);
## Quad: four boundaries on the four sides of an untrimmed patch (its
## domain the sides' mean lengths, so the energy is near isotropic), the
## boundary rows fixed to the curves (fitted on the net's knots within
## the tolerance, by the curves' own parameters), the inner control
## points free.
##
## Refinement (Rhino's Refine, xNURBS's Quality): after a solve the
## stations between the solve's are measured as Stage 0 measures an edge
## (the gap, the angle between normals, the normal curvatures across
## relative to the larger, in percent); while one fails, the spans are
## halved the way it fails, until all pass or they reach the limit. Where
## the neighbors' demands disagree (two G1 neighbors' normals apart at a
## corner, a boundary leaving the other's tangent plane, the two twists
## apart, G2 neighbors' curvatures apart) no surface meets both: the corner
## is reported as a conflict (xNURBS 7 draws them on the model), its
## stations' G1 and G2 rows eased to nothing at the corner within a zone,
## and what fails at the end is reported as runs along the boundaries.
## N-sided domains (Alias's N-sided Projected and Molded, and its N
## quads round a center): Auto fills with quads where their rows can match
## every neighbor exactly (fill_quads.lucb), else projects onto the loop's
## best plane unless a neighbor stands square to it, then molds.
pub let fill_domain_auto: i64 = 0
pub let fill_domain_projected: i64 = 1
pub let fill_domain_molded: i64 = 2
## N quads round a center (fill_quads.lucb): Auto takes it where every
## boundary's neighbor is a plane or a straight sweep across it.
pub let fill_domain_quads: i64 = 3
## Boundary flows (Quad; Plasticity's xNURBS Boundary).
pub let fill_flow_natural: i64 = 0
pub let fill_flow_normal: i64 = 1
pub let fill_flow_next: i64 = 2
pub let fill_flow_adjacent: i64 = 3
## Fill's options: Quad (else N-sided), Tension (0 to 1: bending to
## membrane), Flatness (0 to 1: the pull toward the boundary's plane),
## the Quad flow, the guides' continuity (0 G0, 1 G1), Explicit Control's
## degrees and spans, Refine and its span limit, and the tolerances
## (position in model units, 0: a millionth of the boundary's size; the
## angle in degrees; the curvature in percent).
pub struct FillOptions:
pub var quad: bool
pub var tension: f64
pub var flatness: f64
pub var flow: i64
pub var guide_order: i64
pub var explicit: bool
pub var degree_u: i64
pub var spans_u: i64
pub var degree_v: i64
pub var spans_v: i64
pub var refine: bool
pub var most_spans: i64
pub var position: f64
pub var angle: f64
pub var curvature: f64
pub var domain: i64
## A conflict: the boundary (picked index; -1 a guide), the order that
## fails (0 G0, 1 G1, 2 G2), where it runs from and to (a corner: twice
## the corner), the worst amount (model units, degrees, percent),
## whether it is a corner whose neighbors disagree, and how far from a
## corner the fill gives way to it (model units; zero for a run).
pub struct FillConflict:
pub var boundary: i64
pub var order: i64
pub var start: Vector3
pub var finish: Vector3
pub var amount: f64
pub var corner: bool
pub var reach: f64
## A station: its side and fraction along it, the point (normalized
## units) and the unit tangent along the loop, its chart point and the
## chart direction across into the patch, the order it holds (-1 Free),
## the neighbor (none off a surface), the flow wanted across (zero none),
## and the weight of its G1 and G2 rows (eased near a conflicting corner).
struct FillStation:
var side: usize
var s: f64
var p: Vector3
var tangent: Vector3
var uv: Vector3
var d: Vector3
var order: i64
var has_face: bool
var form: NeighborForm
var flow: Vector3
var weight: f64
## The neighbor's own way across the boundary, out of it (G1 and G2):
## the way the fill leaves it.
var leave: Vector3
## The normal its G1 rows hold the fill to, and the way the fill leaves
## (the neighbor's, but turned toward a conflicting corner's: see
## corner_turn), and whether it is turned.
var held: Vector3
var way: Vector3
var turned: bool
## Turned (Quad): how far the turn has gone (0 to 1, eased), whether
## toward the side's end (else its start), and the cross derivative held
## there (turn_crosses; zero: none yet, the rows let go).
var turn: f64
var toward_end: bool
var cross: Vector3
## A corner whose neighbors' tangent planes disagree (a lid's corner on two
## walls) and whose boundaries meet at an angle: the fill cannot be G1 to
## both, but its own tangent plane there is fixed, the plane of the two
## boundaries' tangents. Within `zone` of each side (a fraction of it)
## the way the fill leaves the boundary turns from the neighbor's to the
## way into the patch at the corner (`into_a` square to side a's tangent
## toward side b, `into_b` the other way), so its normal turns smoothly
## onto the corner's instead of being let go (letting go left the cross
## derivative to collapse there: zebra stripes pinched to the corner).
struct CornerTurn:
var turned: bool
var zone: f64
var into_a: Vector3
var into_b: Vector3
## What a fill works with: its sides (loop order), options, guides, the
## normalized frame (the loop's middle and size; the chart frame ex, ey
## and the plane's normal ez), the tolerances in normalized units, and the
## conflicts at corners.
struct FillWork:
var sides: Growing[FillSide]
var opts: FillOptions
var guides: Growing[Master]
var points: Growing[Vector3]
var center: Vector3
var scale: f64
var ex: Vector3
var ey: Vector3
var ez: Vector3
var position: f64
var angle: f64
var curvature: f64
var corners: Growing[FillConflict]
## Each corner's zone is eased (corner k: side k's end, side k + 1's start).
var eased: Growing[bool]
## Each corner's turn (corner_turn), when its tangent planes disagree.
var turns: Growing[CornerTurn]
## Molded (N-sided): the loop laid round the unit circle by its length,
## side k from angles[k] to angles[k + 1] (the last 2π).
var molded: bool
var angles: Growing[f64]
## Where the sides' ribbons disagree but their points and normals lie on
## one sphere (a ball corner's three fillets), the reference is that
## sphere (fill_reference.lucb's ball_fit).
var ball: FillBall
func close():
close_fill_sides(&self.sides)
close_masters(&self.guides)
self.points.close()
self.corners.close()
self.eased.close()
self.turns.close()
self.angles.close()
## A world point in normalized units, and back.
func local(p: Vector3) -> Vector3:
return p.subtract(self.center).multiply_scalar(1.0 / self.scale)
func world(p: Vector3) -> Vector3:
return self.center.add(p.multiply_scalar(self.scale))
## The N-sided chart point of a normalized point.
func chart(p: Vector3) -> Vector3:
return Vector3(p.dot(self.ex), p.dot(self.ey), 0.0)
## Molded: side `k`'s chart point at fraction `s` along its length:
## on the polygon inscribed in the unit circle with a corner where each
## side starts (the loop's corners stay corners: a smooth circle would
## have the net turn them), on the circle itself for one or two sides.
func disk(k: usize, s: f64) -> Vector3:
let a0 = self.angles.items[k]
let a1 = self.angles.items[k + 1]
if self.sides.count < 3:
let a = a0 + (a1 - a0) * s
return Vector3(math.cos(a), math.sin(a), 0.0)
let p0 = Vector3(math.cos(a0), math.sin(a0), 0.0)
let p1 = Vector3(math.cos(a1), math.sin(a1), 0.0)
return p0.add(p1.subtract(p0).multiply_scalar(s))
## Molded: the way across side `k` into the domain.
func disk_inward(k: usize, s: f64) -> Vector3:
if self.sides.count < 3: return self.disk(k, s).multiply_scalar(-1.0)
let t = self.disk(k, 1.0).subtract(self.disk(k, 0.0)).normalized() catch failure: return self.disk(k, s).multiply_scalar(-1.0)
return Vector3(-t.y, t.x, 0.0)
## Where to start looking for side `k`'s point at its parameter `t`
## (normalized point `p`) on the N-sided net: its projection, or Molded
## its place on the circle.
func seed_of(k: usize, t: f64, p: Vector3) -> Vector3!:
if not self.molded: return self.chart(p)
let side = &self.sides.items[k]
return self.disk(k, try arc_fraction(&side.curve, &side.arc, t))
## What Fill made: the net (world units), whether it is trimmed to the
## loop, its sense, the conflicts, each side's worst gap, angle and
## curvature difference (picked order), the guides' worst miss, the spans
## and the passes.
struct FillMade:
var net: Net
var sense: bool
var conflicts: Growing[FillConflict]
var gaps: Growing[f64]
var angles: Growing[f64]
var curvatures: Growing[f64]
var guide_miss: f64
var passes: i64
## N-sided: each side laid on the fill (world units), the trim's curves,
## and a point of the fill just inside them (the trim keeps the region
## holding it).
var cuts: Growing[Spline]
var inside: Vector3
## N-sided by quads (fill_quads.lucb): the quads' nets (world units),
## one face each, `net` the first's.
var quads: Growing[Net]
func close():
self.net.close()
close_nets(&self.quads)
self.conflicts.close()
self.gaps.close()
self.angles.close()
self.curvatures.close()
close_splines_of(&self.cuts)
# -- The frame and the stations.
## The loop's frame: its middle, size, and best plane (Newell's normal of
## its samples) with a chart frame in it.
func set_frame(w: FillWork*) -> !:
var points = Growing[Vector3]()
defer points.close()
for s in w.sides.view():
for k in 0..<(usize)64: try points.push(s.curve.point_at((f64)k / 64.0))
var center = Vector3()
for p in points.view(): center = center.add(p)
center = center.multiply_scalar(1.0 / (f64)points.count)
var normal = Vector3()
for k in 0..<points.count:
let a = points.items[k].subtract(center)
let b = points.items[(k + 1) % points.count].subtract(center)
normal = normal.add(a.cross(b))
var size = 0.0
for p in points.view(): size = math.max(size, p.subtract(center).length())
if not (size > 0.0): error(invalid, "Fill: the boundaries are a point")
w.center = center
w.scale = size
w.ez = normal.normalized() catch failure: error(invalid, "Fill: the boundaries enclose no area (they double back on themselves)")
w.ex = try square_to(w.ez)
w.ey = w.ez.cross(w.ex)
w.position = (w.opts.position if w.opts.position > 0.0 else size * 1e-6) / size
w.angle = w.opts.angle * math.pi / 180.0
w.curvature = w.opts.curvature
## Side `k`'s parameter at fraction `s` along it: N-sided by its length
## (stations evenly spread), Quad its own parameter (the patch's rows then
## run as the boundary curves do, as Square's: the joined edges' middles
## meet where Stitch looks for them).
func side_param(w: const FillWork*, k: usize, s: f64) -> f64!:
let side = &w.sides.items[k]
if w.opts.quad: return math.clamp(s, 0.0, 1.0)
return try arc_param(&side.curve, &side.arc, s)
## A station on side `k` at fraction `s` with chart point `uv` and chart
## direction across `d` (Quad: fixed by the side; N-sided: set from the
## chart tangent by the caller).
func make_station(w: FillWork*, k: usize, s: f64, uv: Vector3, d: Vector3) -> FillStation!:
let side = &w.sides.items[k]
let t = try side_param(w, k, s)
let j = try curve_jet(&side.curve, t, 1, t >= 1.0)
let p = j.d[0]
let tangent = j.d[1].normalized() catch failure: error(invalid, "Fill: a boundary stops (its tangent vanishes)")
var form = NeighborForm(Vector3(), [0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
let order = side.order()
var has_face = false
var flow = Vector3()
var leave = Vector3()
if side.master.has_face:
form = try neighbor_at(&side.master, p, w.scale)
has_face = true
if order >= 1:
# The neighbor's own way across its edge, out of it.
let probe = Probe(p, tangent, w.world(Vector3()).subtract(p), empty_jet())
let m = &side.master
let goal = try m.target(spline_nearest(&m.curve, p), &probe, 0.0)
leave = goal.t.multiply_scalar(-1.0) if m.kind == master_edge else goal.t
if w.opts.quad and w.opts.flow == fill_flow_adjacent: flow = leave
return FillStation(k, s, w.local(p), tangent, uv, d, order, has_face, form, flow, 1.0, leave, form.n, leave, false, 0.0, false, Vector3())
## The stations of the N-sided chart: `per` along each side by the side's
## share of the loop's chart length, at the middles of equal steps (never
## on a corner), each one's direction across into the loop's inside.
func nsided_stations(w: FillWork*, per_length: f64, out: Growing[FillStation]*) -> !:
out.clear()
for k in 0..<w.sides.count:
# The side's chart length, by 64 chords.
let side = &w.sides.items[k]
var length = 0.0
var before = w.chart(w.local(side.curve.point_at(0.0)))
for q in 1..<(usize)65:
let now = w.chart(w.local(side.curve.point_at((f64)q / 64.0)))
length += now.subtract(before).length()
before = now
if w.molded: length = w.disk(k, 1.0).subtract(w.disk(k, 0.0)).length() if w.sides.count >= 3 else w.angles.items[k + 1] - w.angles.items[k]
let count = (usize)math.clamp(math.ceil(length * per_length), 12.0, 600.0)
for q in 0..<count + 1:
# The side's start (a corner of the loop, G0 alone: its two
# neighbors' other demands are find_corners'), then the middles
# of equal steps.
let s = 0.0 if q == 0 else ((f64)q - 0.5) / (f64)count
var station = try make_station(w, k, s, Vector3(), Vector3())
if q == 0 and station.order > 0: station.order = 0
if w.molded:
# On the circle, across toward its middle.
station.uv = w.disk(k, s)
station.d = w.disk_inward(k, s)
try out.push(station)
continue
station.uv = w.chart(station.p)
let t = Vector3(station.tangent.dot(w.ex), station.tangent.dot(w.ey), 0.0).normalized() catch failure: error(invalid, "Fill: a boundary runs square to the hole's plane; use Molded or Quad, or pick a flatter loop")
# Inside lies to the left of a counterclockwise loop (the
# plane's normal is Newell's: the loop runs counterclockwise).
station.d = Vector3(-t.y, t.x, 0.0)
try out.push(station)
## Quad's chart: side k's chart point at fraction s, and its direction
## across (loop sides 0 to 3 are v = low, u = high, v = high run back,
## u = low run back).
func quad_place(net: const Net*, k: usize, s: f64) -> (Vector3, Vector3):
let u0 = net.u_low()
let u1 = net.u_high()
let v0 = net.v_low()
let v1 = net.v_high()
if k == 0: return (Vector3(u0 + (u1 - u0) * s, v0, 0.0), Vector3(0.0, 1.0, 0.0))
if k == 1: return (Vector3(u1, v0 + (v1 - v0) * s, 0.0), Vector3(-1.0, 0.0, 0.0))
if k == 2: return (Vector3(u1 - (u1 - u0) * s, v1, 0.0), Vector3(0.0, -1.0, 0.0))
return (Vector3(u0, v1 - (v1 - v0) * s, 0.0), Vector3(1.0, 0.0, 0.0))
## Quad's stations: six in each span along each side.
func quad_stations(w: FillWork*, net: const Net*, out: Growing[FillStation]*) -> !:
out.clear()
for k in 0..<(usize)4:
let knots = net.ku.view() if k % 2 == 0 else net.kv.view()
let degree = net.du if k % 2 == 0 else net.dv
var params = Growing[f64]()
defer params.close()
try fit_parameters(knots, degree, 6, ¶ms)
let low = knots[(usize)degree]
let high = knots[knots.length - (usize)degree - 1]
for at in 1..<params.count - 1:
var s = (params.items[at] - low) / (high - low)
if k >= 2: s = 1.0 - s
let (uv, d) = quad_place(net, k, s)
try out.push(try make_station(w, k, s, uv, d))
if w.opts.flow == fill_flow_next or w.opts.flow == fill_flow_normal:
# Next: across each side, the blend of the two boundaries leaving
# its ends into the patch; Normal: square to the boundary.
for at in 0..<out.count:
let st = &out.items[at]
if w.opts.flow == fill_flow_normal:
st.flow = Vector3()
continue
let before = &w.sides.items[(st.side + 3) % 4]
let after = &w.sides.items[(st.side + 1) % 4]
let leaving_start = (try curve_jet(&before.curve, 1.0, 1, true)).d[1].multiply_scalar(-1.0).normalized() catch failure: recover Vector3()
let leaving_end = (try curve_jet(&after.curve, 0.0, 1, false)).d[1].normalized() catch failure: recover Vector3()
st.flow = leaving_start.multiply_scalar(1.0 - st.s).add(leaving_end.multiply_scalar(st.s))
# -- Corners.
## Each corner's disagreement (corner k between side k's end and side
## k + 1's start) onto `w.corners`, the corner marked to ease: two G1
## neighbors' normals apart (the amount in degrees), a boundary leaving the
## other's tangent plane (degrees), two G1 neighbors' twists apart, two G2
## neighbors' normal curvatures apart along the boundaries, or their
## curvatures' rates apart (percent).
func find_corners(w: FillWork*) -> !:
w.corners.clear()
w.eased.clear()
w.turns.clear()
let n = w.sides.count
for k in 0..<n:
try w.eased.push(false)
try w.turns.push(CornerTurn(false, 0.0, Vector3(), Vector3()))
if n < 2: continue
let a = &w.sides.items[k]
let b = &w.sides.items[(k + 1) % n]
let p = a.curve.point_at(1.0)
let ta = (try curve_jet(&a.curve, 1.0, 1, true)).d[1].normalized() catch failure: recover Vector3()
let tb = (try curve_jet(&b.curve, 0.0, 1, false)).d[1].normalized() catch failure: recover Vector3()
var worst = 0.0
var order: i64 = -1
var fa = NeighborForm(Vector3(), [0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
var fb = fa
if a.order() >= 1: fa = try neighbor_at(&a.master, p, w.scale)
if b.order() >= 1: fb = try neighbor_at(&b.master, p, w.scale)
if a.order() >= 1 and b.order() >= 1:
let angle = math.acos(math.clamp(math.abs(fa.n.dot(fb.n)), -1.0, 1.0))
if angle > w.angle:
worst = angle * 180.0 / math.pi
order = 1
if a.order() >= 1 and order < 1:
let off = math.asin(math.clamp(math.abs(fa.n.dot(tb)), 0.0, 1.0))
if off > w.angle:
worst = off * 180.0 / math.pi
order = 1
if b.order() >= 1 and order < 1:
let off = math.asin(math.clamp(math.abs(fb.n.dot(ta)), 0.0, 1.0))
if off > w.angle:
worst = off * 180.0 / math.pi
order = 1
# Tangent planes apart: the fill's own there is the boundaries'.
let planes_apart = order == 1
if a.order() >= 1 and b.order() >= 1 and order < 1:
# The vertex's twist (Gregory's compatibility): G1 along both
# boundaries fixes the fill's shape operator on each one's
# tangent, S(ta) = S_a(ta) and S(tb) = S_b(tb), and a smooth
# surface's is symmetric, so II_a(ta, tb) = II_b(ta, tb) (along a
# boundary running straight through, its normal curvature
# II(t, t) the same from both). Else no smooth fill is G1 to both
# there.
let flat = ta.cross(tb).length() < 1e-3
let ka = ta.dot(fa.times(ta)) if flat else ta.dot(fa.times(tb))
let kb = ta.dot(fb.times(ta)) if flat else ta.dot(fb.times(tb))
let rel = fill_relative(ka, kb)
if rel > w.curvature:
worst = rel
order = 1
if a.order() >= 2 and b.order() >= 2 and order < 1:
# Normal curvatures along both boundaries and between them.
let mid = ta.add(tb).normalized() catch failure: recover ta
for e in [ta, tb, mid]:
let x = e.subtract(fa.n.multiply_scalar(e.dot(fa.n)))
let ka = fa.curvature_of(x) / math.max(1e-300, x.dot(x))
let kb = fb.curvature_of(x) / math.max(1e-300, x.dot(x))
let rel = fill_relative(ka, kb)
if rel > w.curvature and rel > worst:
worst = rel
order = 2
if a.order() >= 2 and b.order() >= 2 and order < 1:
# The curvatures' rates (the third derivatives' symmetry, as the
# twist is the second's): G2 along side a fixes how the fill's
# II(tb, X) changes along ta, G2 along side b how II(ta, X)
# changes along tb, and a smooth surface's are the same. A G2
# fillet's end (its curvature rising from nothing at a wall)
# meeting a wall at an angle disagrees; a G3 fillet's (rising
# with no rate) does not.
# One-sided differences at two steps, extrapolated (Richardson):
# the rate at the corner itself, not a step in (a G3 end's
# curvature grows as the square of the distance).
var rates: f64[4] = [0.0, 0.0, 0.0, 0.0]
var measured = true
for (step, slot) in [(1e-4, 0), (2e-4, 2)]:
let pa = a.curve.point_at(1.0 - step)
let pb = b.curve.point_at(step)
let ha = pa.subtract(p).length() / w.scale
let hb = pb.subtract(p).length() / w.scale
if not (ha > 0.0 and hb > 0.0):
measured = false
continue
let ga = try neighbor_at(&a.master, pa, w.scale)
let gb = try neighbor_at(&b.master, pb, w.scale)
# II(tb, X) along side a, and II(ta, X) along side b, X
# their mean way.
let x = ta.add(tb).normalized() catch failure: recover ta
rates[slot] = (tb.dot(fa.times(x)) - tb.dot(ga.times(x))) / ha
rates[slot + 1] = (ta.dot(gb.times(x)) - ta.dot(fb.times(x))) / hb
if measured:
let ra = 2.0 * rates[0] - rates[2]
let rb = 2.0 * rates[1] - rates[3]
let rel = fill_rate_relative(ra, rb)
if rel > w.curvature * 10.0 and rel > worst:
worst = rel
order = 2
if order < 0: continue
w.eased.items[k] = true
let into_a = tb.subtract(ta.multiply_scalar(tb.dot(ta))).normalized() catch failure: recover Vector3()
let into_b = ta.multiply_scalar(-1.0).subtract(tb.multiply_scalar(-ta.dot(tb))).normalized() catch failure: recover Vector3()
var zone = 0.03
if planes_apart and ta.cross(tb).length() > 0.1 and into_a.length() > 0.0 and into_b.length() > 0.0:
# The zone grows with the turn: a quarter of each side for a
# right angle (a lid's corner on two walls), narrower for less.
let most = quad_turn_zone if w.opts.quad else 0.25
zone = math.clamp(most * worst / 90.0, 0.03, most)
w.turns.items[k] = CornerTurn(true, zone, into_a, into_b)
let corner = p
let eased_zone = zone * turn_margin(w) if w.turns.items[k].turned else zone
try w.corners.push(FillConflict((i64)a.picked, order, corner, corner, worst, true, eased_zone * math.max(a.length, b.length)))
## A Quad lid's turn reaches 35% of each side at a right angle (its strips,
## fill_strips.lucb, spread the turn: a quarter bent them sharply), N-sided
## ones a quarter; a Quad's G1 and G2 ease over its turn and a quarter more
## (where the strip settles onto the neighbor).
let quad_turn_zone: f64 = 0.35
func turn_margin(w: const FillWork*) -> f64:
return 1.25 if w.opts.quad else 1.0
## |a - b| relative to the larger magnitude, in percent, below a floor of
## 5e-4 in normalized units (the Check tools' floor, a thousandth over the
## model's size, the loop's diameter being about twice its normalized one)
## curvatures being flat alike.
func fill_relative(a: f64, b: f64) -> f64:
let larger = math.max(math.max(math.abs(a), math.abs(b)), 5e-4)
return math.abs(a - b) / larger * 100.0
## Station `st` turned toward the conflicting corners its side runs into
## (CornerTurn): the way it leaves the boundary turned from the neighbor's
## toward the way into the patch at the corner by a quintic smoothstep of
## the distance (so the turn starts with no change of slope or curvature),
## its G1 normal the tangent across that way. Its G2 rows are eased there
## (station.weight, corner_ease) as at any conflicting corner.
func corner_turn(w: const FillWork*, st: FillStation*) -> !:
st.held = st.form.n
st.way = st.leave
st.turned = false
st.turn = 0.0
st.cross = Vector3()
if st.order < 1 or not st.has_face or st.leave.length() == 0.0: return
let n = w.sides.count
let end = &w.turns.items[st.side]
let start = &w.turns.items[(st.side + n - 1) % n]
var into = Vector3()
var f = 0.0
var toward_end = false
if end.turned and st.s > 1.0 - end.zone:
into = end.into_a
f = 1.0 - (1.0 - st.s) / end.zone
toward_end = true
if start.turned and st.s < start.zone:
let g = 1.0 - st.s / start.zone
if g > f:
into = start.into_b
f = g
toward_end = false
if not (f > 0.0): return
let t = st.tangent
let leave = st.leave.subtract(t.multiply_scalar(st.leave.dot(t))).normalized() catch failure: return
let inward = into.subtract(t.multiply_scalar(into.dot(t))).normalized() catch failure: return
let e = f * f * f * (10.0 - 15.0 * f + 6.0 * f * f)
# Turned on the great circle from leave to inward (a quarter turn for a
# lid's walls: never through the other side).
let angle = math.acos(math.clamp(leave.dot(inward), -1.0, 1.0))
var way = inward
if angle > 1e-9 and angle < math.pi - 1e-6:
let a = math.sin((1.0 - e) * angle) / math.sin(angle)
let b = math.sin(e * angle) / math.sin(angle)
way = leave.multiply_scalar(a).add(inward.multiply_scalar(b))
let normal = t.cross(way).normalized() catch failure: return
st.held = normal
st.way = way
st.turned = true
st.turn = e
st.toward_end = toward_end
## |a - b| relative to the larger rate of curvature, in percent, below a
## floor of 1e-3 in normalized units (the Check tools' rate floor, a
## thousandth over the model's size squared).
func fill_rate_relative(a: f64, b: f64) -> f64:
let larger = math.max(math.max(math.abs(a), math.abs(b)), 1e-3)
return math.abs(a - b) / larger * 100.0
## The ease of station `st` near an eased corner: 1 off the zones, falling
## as the square of the distance to the corner within a zone of 3% of the
## side (a turned corner's: its turn's zone).
func corner_ease(w: const FillWork*, st: const FillStation*) -> f64:
let n = w.sides.count
let before = (st.side + n - 1) % n
# A turned corner's zone is its turn's.
let zone_end = w.turns.items[st.side].zone * turn_margin(w) if w.turns.items[st.side].turned else 0.03
let zone_start = w.turns.items[before].zone * turn_margin(w) if w.turns.items[before].turned else 0.03
var ease = 1.0
if w.eased.items[st.side] and st.s > 1.0 - zone_end: ease = math.min(ease, math.pow((1.0 - st.s) / zone_end, 2.0))
if w.eased.items[before] and st.s < zone_start: ease = math.min(ease, math.pow(st.s / zone_start, 2.0))
return ease
# -- The nets.
## The Quad net on knots `ku`, `kv`: its boundary rows the sides fitted on
## them (ends at the corners, the mean of the two sides meeting there),
## the inner control points free; the worst miss of a row onto `missed`
## and the spans it misses in onto `split_u`, `split_v`.
func quad_net(w: FillWork*, du: i64, dv: i64, ku: const f64[], kv: const f64[], split_u: Growing[bool]*, split_v: Growing[bool]*) -> FillNet!:
let nu = ku.length - (usize)du - 1
let nv = kv.length - (usize)dv - 1
var fixed = Growing[bool]()
defer fixed.close()
try fixed.fill(nu * nv, false)
var corners: Vector3[4] = [Vector3(), Vector3(), Vector3(), Vector3()]
for k in 0..<(usize)4:
let before = &w.sides.items[(k + 3) % 4]
corners[k] = w.local(w.sides.items[k].curve.point_at(0.0).add(before.curve.point_at(1.0)).multiply_scalar(0.5))
# The base: the corners' bilinear patch (corner k at loop side k's
# start: (0, 0), (1, 0), (1, 1), (0, 1)), exact at the Greville points.
var start = Growing[Weighted]()
defer start.close()
for i in 0..<nu:
let a = (fill_greville(ku, du, i) - ku[(usize)du]) / (ku[nu] - ku[(usize)du])
for j in 0..<nv:
let b = (fill_greville(kv, dv, j) - kv[(usize)dv]) / (kv[nv] - kv[(usize)dv])
let p = corners[0].multiply_scalar((1.0 - a) * (1.0 - b)).add(corners[1].multiply_scalar(a * (1.0 - b))).add(corners[2].multiply_scalar(a * b)).add(corners[3].multiply_scalar((1.0 - a) * b))
try start.push(weighted(p, 1.0))
for k in 0..<(usize)4:
let along_u = k % 2 == 0
let knots = ku if along_u else kv
let degree = du if along_u else dv
let side = &w.sides.items[k]
var params = Growing[f64]()
defer params.close()
try fit_parameters(knots, degree, 12, ¶ms)
var fitter = try make_fitter(degree, knots, params.view(), 0)
defer fitter.close()
let low = knots[(usize)degree]
let high = knots[knots.length - (usize)degree - 1]
let back = k >= 2
var values = Growing[Weighted]()
defer values.close()
for t in params.view():
var s = (t - low) / (high - low)
if back: s = 1.0 - s
try values.push(weighted(w.local(side.curve.point_at(try side_param(w, k, s))), 1.0))
# The row's ends: its corners (net order: low end first).
let first_corner = corners[(k + 1) % 4] if back else corners[k]
let last_corner = corners[k] if back else corners[(k + 1) % 4]
var starts: Weighted[4] = [weighted(first_corner, 1.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(last_corner, 1.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 row = Growing[Weighted]()
defer row.close()
try fitter.fit(values.view(), &starts, &ends, &row)
let count = row.count
for at in 0..<count:
var key: usize = 0
if k == 0: key = at * nv
elif k == 1: key = (nu - 1) * nv + at
elif k == 2: key = at * nv + nv - 1
else: key = at
start.items[key] = row.items[at]
fixed.items[key] = true
# How far the row misses its side, span by span.
var row_curve = empty_spline(degree)
defer row_curve.close()
try row_curve.knots.assign(knots)
try row_curve.points.assign(row.view())
let marks = split_u if along_u else split_v
for span in (usize)degree..<knots.length - (usize)degree - 1:
let a = knots[span]
let b = knots[span + 1]
if not (b > a): continue
for q in 0..<(usize)8:
let t = a + (b - a) * ((f64)q + 0.5) / 8.0
var s = (t - low) / (high - low)
if back: s = 1.0 - s
let want = w.local(side.curve.point_at(try side_param(w, k, s)))
if row_curve.point_at(t).subtract(want).length() > w.position * 0.5: marks.items[span - (usize)degree] = true
return try fill_net(du, dv, ku, kv, fixed.view(), start.view())
## The Greville abscissa of control point `i` of `knots` (degree `degree`).
func fill_greville(knots: const f64[], degree: i64, i: usize) -> f64:
var sum = 0.0
for k in 1..<(usize)degree + 1: sum += knots[i + k]
return sum / (f64)degree