dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / surfacing / builders.lucb
## Surfacing Stage 5 (luced-3d's docs/research/SURFACING-ALIAS-PLASTICITY.md
## §4.6, §6.6): surfaces built from curves. Square (four boundaries, each
## Free, G0, G1, G2, Implied or at a Tangent Angle), Skin (a loft through
## sections), Rail and Profile (sections swept along rails), Set Planar
## (a planar fill of closed curves), the sheet Extrude and Revolve of a
## free curve, and Extend (a surface's edge carried on Linear, Natural,
## Soft or Reflective). Each makes a new body of one sheet (Extend changes
## its face) and is what CadSurfaceBuild calls (build_api.lucb).
##
## This file: what the builders share. Their curves are named as Align's
## masters are ("curve <name>", "edge <face> x y z", "isoparm <face> <0 or
## 1> <fraction>"; align_master.lucb), so a builder can ask the face a
## boundary lies on for its cross derivatives; curves made compatible (one
## degree, one knot vector, on 0..1); Bezier rows from end derivatives (a
## Hermite interpolation of curves, exact); nets made alike and added.
## The builders' fit tolerance is at least this (the curves' size may be
## zero); match_side's G1 limit in degrees for the Align it runs.
let least_build: f64 = 1e-12
let match_angle: f64 = 0.01
## The curves `text` names (words apart by `;`) as masters, onto `out`.
func builder_masters(set: interop.Reference[GeometrySet], text: str, out: Growing[Master]*) -> !:
let bytes = text.bytes
var start: usize = 0
for at in 0..<bytes.length + 1:
if at < bytes.length and bytes[at] != 59: continue
let words = (str)bytes[start..<at]
start = at + 1
if words.length == 0: continue
try out.push(try master_of(set, words, -1, Vector3()))
func close_masters(list: Growing[Master]*):
for m in list.view():
var owned = m
owned.close()
list.close()
func close_splines_of(list: Growing[Spline]*):
for s in list.view():
var owned = s
owned.close()
list.close()
## Whether `c`'s weights all agree (a polynomial curve).
func plain_weights(c: const Spline*) -> bool:
let w0 = c.points.items[0].w
for q in c.points.view():
if math.abs(q.w - w0) > weight_same * math.abs(w0): return false
return true
## The domain's distinct spans of `c`.
func span_count(c: const Spline*) -> usize:
var spans: usize = 0
for k in (usize)c.degree..<c.points.count:
if c.knots.items[k + 1] > c.knots.items[k]: spans += 1
return spans
## `c` as a polynomial curve (weights 1): its own points when its weights
## agree, else refitted at degree 5 (or its own, if higher) on equal
## spans, doubled until within `tolerance` (a circle's arc takes a few
## quintic spans to a ten-millionth). Its ends keep their curvature.
func plain_curve(c: const Spline*, tolerance: f64) -> Spline!:
if plain_weights(c):
var made = try c.copy()
for at in 0..<made.points.count: made.points.items[at] = weighted(made.points.items[at].point(), 1.0)
return made
let degree = (i64)math.max(5.0, (f64)c.degree)
var spans = (usize)math.max(1.0, (f64)span_count(c))
while true:
var knots = Growing[f64]()
defer knots.close()
try uniform_knots(degree, spans, c.low(), c.high(), &knots)
let count = spans + (usize)degree
let keep: usize = 2 if count >= 6 else 0
var made = try refit_curve(c, degree, knots.view(), keep, false)
let off = curve_deviation(c, &made, 64 * spans)
if off <= tolerance or spans >= 256: return made
made.close()
spans *= 2
error(invalid, "unreachable")
## Alias's Rebuild of a builder's curve ("to reduce data and improve
## parameterization"): `c` (a polynomial curve on 0..1) taken by its arc
## length and refitted at its degree (5 at least) on uniform spans, the
## fewest (doubling from one) within `tolerance`, its ends and their
## tangents kept. Its points lie on `c`'s to the tolerance; its speed is
## near constant.
func rebuilt_curve(c: const Spline*, tolerance: f64) -> Spline!:
# Arc length by chords at fine steps: the fraction of length at each
# step (an approximation of the parameter only, the points stay on c).
let steps: usize = 4096
var lengths = Growing[f64]()
defer lengths.close()
try lengths.push(0.0)
var last = c.point_at(c.low())
for k in 1..<steps + 1:
let p = c.point_at(c.low() + (c.high() - c.low()) * (f64)k / (f64)steps)
try lengths.push(lengths.items[k - 1] + p.subtract(last).length())
last = p
let total = lengths.items[steps]
if not (total > 0.0): error(invalid, "Rebuild: the curve has no length")
let degree = (i64)math.max(5.0, (f64)c.degree)
var spans: usize = 1
while true:
var knots = Growing[f64]()
defer knots.close()
try uniform_knots(degree, spans, 0.0, 1.0, &knots)
var params = Growing[f64]()
defer params.close()
try fit_parameters(knots.view(), degree, 2 * ((usize)degree + 1), ¶ms)
var fitter = try make_fitter(degree, knots.view(), params.view(), 1)
defer fitter.close()
var values = Growing[Weighted]()
defer values.close()
for s in params.view(): try values.push(weighted(c.point_at(length_parameter(c, lengths.view(), s)), 1.0))
let j0 = try field_jet(c, c.low(), 1, false)
let j1 = try field_jet(c, c.high(), 1, true)
let d0 = j0.d[1].multiply_scalar(total / math.max(nonzero, j0.d[1].length()))
let d1 = j1.d[1].multiply_scalar(total / math.max(nonzero, j1.d[1].length()))
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)]
starts[0] = weighted(j0.d[0], 1.0)
starts[1] = Weighted(d0.x, d0.y, d0.z, 0.0)
ends[0] = weighted(j1.d[0], 1.0)
ends[1] = Weighted(d1.x, d1.y, d1.z, 0.0)
var made = empty_spline(degree)
errdefer made.close()
try made.knots.assign(knots.view())
try fitter.fit(values.view(), &starts, &ends, &made.points)
# How far it lies from c: each sample's distance to c near where it
# was taken from.
var off = 0.0
let samples = 16 * spans
for k in 0..<samples + 1:
let s = (f64)k / (f64)samples
let p = made.point_at(s)
let near = spline_nearest(c, p)
off = math.max(off, c.point_at(near).subtract(p).length())
if off <= tolerance or spans >= 256: return made
made.close()
spans *= 2
error(invalid, "unreachable")
## The parameter of `c` at fraction `s` of its length, by its chord
## `lengths` (cumulative, at equal steps of the parameter).
func length_parameter(c: const Spline*, lengths: const f64[], s: f64) -> f64:
let steps = lengths.length - 1
let goal = s * lengths[steps]
var low: usize = 0
var high = steps
while high - low > 1:
let mid = (low + high) // 2
if lengths[mid] < goal: low = mid
else: high = mid
let span = lengths[high] - lengths[low]
let f = (goal - lengths[low]) / span if span > 0.0 else 0.0
return c.low() + (c.high() - c.low()) * ((f64)low + math.clamp(f, 0.0, 1.0)) / (f64)steps
## The size of `curves` together: their hulls' box diagonal.
func curves_size(curves: const Spline[]) -> f64:
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for c in curves:
for q in c.points.view():
let p = q.point()
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
return high.subtract(low).length()
## The tolerance builders fit to: a ten-millionth of what they span.
func build_tolerance(curves: const Spline[]) -> f64:
return math.max(least_build, curves_size(curves) * fit_share)
## `curves` made compatible: on 0..1, one degree (the highest of theirs,
## at least `least`) and one knot vector (each one's inner knots inserted
## into the others to the most any has). The same curves.
func make_compatible(curves: Growing[Spline]*, least: i64) -> !:
var degree = least
for c in curves.view(): degree = (i64)math.max((f64)degree, (f64)c.degree)
for at in 0..<curves.count:
unit_domain(&curves.items[at])
let c = &curves.items[at]
if c.degree < degree: try elevate(c, (usize)(degree - c.degree))
# Every distinct inner knot with the most multiplicity any curve gives
# it (knots a billionth apart are one).
var values = Growing[f64]()
defer values.close()
var counts = Growing[usize]()
defer counts.close()
for c in curves.view():
var inner = Growing[f64]()
defer inner.close()
try distinct_inner(&c, knot_near, &inner)
for u in inner.view():
let m = multiplicity(c.knots.view(), u, knot_near)
var found = false
for k in 0..<values.count:
if math.abs(values.items[k] - u) <= knot_near:
counts.items[k] = fewer(counts.items[k] if counts.items[k] > m else m, (usize)degree)
found = true
if not found:
try values.push(u)
try counts.push(fewer(m, (usize)degree))
for at in 0..<curves.count:
let c = &curves.items[at]
for k in 0..<values.count:
var u = values.items[k]
for q in c.knots.view():
if math.abs(q - u) <= knot_near: u = q
let have = multiplicity(c.knots.view(), u, 0.0)
if counts.items[k] > have: _ = try insert_knot(c, u, counts.items[k] - have)
# One knot vector: the first's (the others' differ by rounding).
for at in 1..<curves.count:
if curves.items[at].knots.count != curves.items[0].knots.count: error(invalid, "the curves could not be made compatible")
try curves.items[at].knots.assign(curves.items[0].knots.view())
## The falling factorial n (n - 1) ... (n - k + 1).
func falling(n: usize, k: usize) -> f64:
var f = 1.0
for i in 0..<k: f *= (f64)(n - i)
return f
## Bezier rows of degree n = `first` + `last` - 1 (u from 0 to 1), each
## `size` homogeneous points, from derivatives: `starts` holds the k-th
## derivative at u = 0 for k < `first` (row k at [k size ..< (k + 1)
## size]), `ends` at u = 1 for k < `last`. The rows onto `out`. A Bezier's
## k-th derivative at its start comes from its first k + 1 points,
## n!/(n - k)! Σ (-1)^(k-i) C(k, i) P_i, so each row is solved in turn;
## at its end likewise from its last ones.
func hermite_rows(starts: const Weighted[], first: usize, ends: const Weighted[], last: usize, size: usize, out: Growing[Weighted]*) -> !:
let n = first + last - 1
out.clear()
try out.fill((n + 1) * size, Weighted(0.0, 0.0, 0.0, 0.0))
for j in 0..<first:
for at in 0..<size:
var sum = starts[j * size + at].times(1.0 / falling(n, j))
for i in 0..<j:
let sign = -1.0 if (j - i) % 2 == 1 else 1.0
sum = sum.minus(out.items[i * size + at].times(sign * choose(j, i)))
out.items[j * size + at] = sum
for j in 0..<last:
for at in 0..<size:
var sum = ends[j * size + at].times(1.0 / falling(n, j))
for i in 1..<j + 1:
let sign = -1.0 if (j - i) % 2 == 1 else 1.0
sum = sum.minus(out.items[(n - j + i) * size + at].times(sign * choose(j, i)))
out.items[(n - j) * size + at] = sum.times(-1.0 if j % 2 == 1 else 1.0)
## Bezier knots of degree `n` on 0..1.
func bezier_knots(n: usize, out: Growing[f64]*) -> !:
out.clear()
for _ in 0..<n + 1: try out.push(0.0)
for _ in 0..<n + 1: try out.push(1.0)
## A net from rows: `rows` holds `count` rows of `size` points (row i at
## [i size ..< (i + 1) size]); with `across_u` the rows run along v at
## successive u (u-major as the net), else along u at successive v.
## `row_knots` (degree `row_degree`) are the knots along each row, and the
## other direction is a Bezier of degree count - 1.
func rows_net(rows: const Weighted[], count: usize, size: usize, row_knots: const f64[], row_degree: i64, across_u: bool) -> Net!:
var made = empty_net()
errdefer made.close()
var bezier = Growing[f64]()
defer bezier.close()
try bezier_knots(count - 1, &bezier)
if across_u:
made.du = (i64)count - 1
made.dv = row_degree
made.nu = count
made.nv = size
try made.ku.assign(bezier.view())
try made.kv.assign(row_knots)
try made.points.assign(rows)
return made
made.du = row_degree
made.dv = (i64)count - 1
made.nu = size
made.nv = count
try made.ku.assign(row_knots)
try made.kv.assign(bezier.view())
try made.points.fill(size * count, Weighted(0.0, 0.0, 0.0, 0.0))
for j in 0..<count:
for i in 0..<size: made.points.items[i * count + j] = rows[j * size + i]
return made
## `a` and `b` made alike along `direction` (0 u, 1 v; both on 0..1): one
## degree and one knot vector. The same surfaces.
func match_direction(a: Net*, b: Net*, direction: i64) -> !:
let da = a.du if direction == 0 else a.dv
let db = b.du if direction == 0 else b.dv
if da < db: try net_elevate(a, direction, (usize)(db - da))
if db < da: try net_elevate(b, direction, (usize)(da - db))
for pass in 0..<2:
let from_net = b if pass == 0 else a
let into = a if pass == 0 else b
var inner = Growing[f64]()
defer inner.close()
var counts = Growing[usize]()
defer counts.close()
let knots = from_net.ku.view() if direction == 0 else from_net.kv.view()
let low = knots[(usize)(from_net.du if direction == 0 else from_net.dv)]
let high = knots[from_net.nu if direction == 0 else from_net.nv]
for k in knots:
if k <= low + knot_near or k >= high - knot_near: continue
if inner.count > 0 and math.abs(inner.items[inner.count - 1] - k) <= knot_near: continue
try inner.push(k)
try counts.push(multiplicity(knots, k, knot_near))
for at in 0..<inner.count:
let target = into.ku.view() if direction == 0 else into.kv.view()
let have = multiplicity(target, inner.items[at], knot_near)
if counts.items[at] > have: _ = try net_insert(into, direction, inner.items[at], counts.items[at] - have)
# One knot vector (they differ by rounding at most).
let ka = a.ku.view() if direction == 0 else a.kv.view()
let kb = b.ku.view() if direction == 0 else b.kv.view()
if ka.length != kb.length: error(invalid, "two nets could not be made alike")
if direction == 0: try b.ku.assign(a.ku.view())
else: try b.kv.assign(a.kv.view())
## `a` + `scale` `b`, point by point (alike nets), into `a`.
func add_net(a: Net*, b: const Net*, scale: f64) -> !:
if a.points.count != b.points.count: error(invalid, "nets to add are not alike")
for at in 0..<a.points.count: a.points.items[at] = a.points.items[at].plus(b.points.items[at].times(scale))
## A body of one face on `net`, named `name`, facing along Su x Sv with
## `sense` (the builders' sheets).
func net_body(tolerances: CadTolerances, net: const Net*, name: str, sense: bool) -> interop.Reference[CadModel]!:
return try net_body_within(tolerances, net, name, sense, 0.0)
## net_body with the body's tolerance at least `tolerance` (a billionth of
## the net's size otherwise).
func net_body_within(tolerances: CadTolerances, net: const Net*, name: str, sense: bool, tolerance: f64) -> interop.Reference[CadModel]!:
var points = Growing[Vector3]()
defer points.close()
var weights = Growing[f64]()
defer weights.close()
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for q in net.points.view():
let p = q.point()
if not p.is_finite(): error(invalid, "the surface came out with points at infinity")
try points.push(p)
try weights.push(q.w)
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
return try spline_face(tolerances, points.view(), weights.view(), (i64)net.nu, (i64)net.nv, net.du, net.dv, net.ku.view(), net.kv.view(), sense, name)
## `set` with `model` added as a body after its others.
func with_body_added(set: interop.Reference[GeometrySet], model: interop.Reference[CadModel]) -> interop.Reference[GeometrySet]!:
let one: interop.Reference[CadModel][1] = [model]
return try with_bodies_added(set, one[..<1])
## `set` with `models` added as bodies after its others.
func with_bodies_added(set: interop.Reference[GeometrySet], models: const interop.Reference[CadModel][]) -> interop.Reference[GeometrySet]!:
let source = try set.get()
var list = Growing[interop.Reference[CadModel]]()
defer list.close()
for m in set_models(source): try list.push(m)
for m in models: try list.push(m)
return try with_models(source, list.view())
## The homogeneous derivatives of `c` at `t` to `order` (from below with
## `left`): for a polynomial curve (weights 1, or 0 for a field of
## vectors) these are its own.
func field_jet(c: const Spline*, t: f64, order: usize, left: bool) -> Jet!:
var a: Weighted[6]
try homogeneous_jet(c, t, order, left, &a)
var j = empty_jet()
for k in 0..<order + 1: j.d[k] = Vector3(a[k].x, a[k].y, a[k].z)
return j
## The cubic Hermite at `t` of values `a`, `b` and slopes `da`, `db`.
func cubic_hermite(a: Vector3, da: Vector3, b: Vector3, db: Vector3, t: f64) -> Vector3:
let t2 = t * t
let t3 = t2 * t
return a.multiply_scalar(2.0 * t3 - 3.0 * t2 + 1.0).add(da.multiply_scalar(t3 - 2.0 * t2 + t)).add(b.multiply_scalar(-2.0 * t3 + 3.0 * t2)).add(db.multiply_scalar(t3 - t2))
## The normal of the plane a curve lies in (Implied continuity): from the
## chord and the control point furthest off it; zero when it is straight
## or not planar within `tolerance`.
func curve_plane(c: const Spline*, tolerance: f64) -> Vector3:
let a = c.points.items[0].point()
let b = c.points.items[c.points.count - 1].point()
var chord = b.subtract(a)
if chord.length() <= tolerance:
chord = c.points.items[c.points.count // 2].point().subtract(a)
var far = Vector3()
var most = 0.0
for q in c.points.view():
let d = q.point().subtract(a)
let off = d.cross(chord).length() / math.max(nonzero, chord.length())
if off > most:
most = off
far = d
if most <= tolerance: return Vector3()
let n = chord.cross(far).normalized() catch failure: return Vector3()
for q in c.points.view():
if math.abs(q.point().subtract(a).dot(n)) > tolerance * 10.0: return Vector3()
return n
## `net` as a polynomial net (weights 1): its own points when its weights
## agree, else refitted at degree 5 at least within `tolerance` (Align
## moves rows of plain control points).
func polynomial_net(net: const Net*, tolerance: f64) -> Net!:
if not net.rational():
var made = try net.copy()
for at in 0..<made.points.count: made.points.items[at] = weighted(made.points.items[at].point(), 1.0)
return made
var deviation = 0.0
let su = (usize)math.max(1.0, (f64)(net.nu - (usize)net.du))
let sv = (usize)math.max(1.0, (f64)(net.nv - (usize)net.dv))
return try refit_within(net, (i64)math.max(5.0, (f64)net.du), (i64)math.max(5.0, (f64)net.dv), su, sv, 64, 2, 2, false, tolerance, &deviation)
## Side `side` of `net` (0 u = 0, 1 u = 1, 2 v = 0, 3 v = 1) matched
## G`order` (1 to 3) to `master` (the face its boundary lies on) by Align's
## rows (align.lucb): the input's own hull, Explicit Control off (quintic
## across, spans added for the rows), Refine to Alias's limits. A builder's
## continuity at a boundary picked as an edge or a curve on a face.
func match_side(net: Net*, side: i64, master: Master*, order: i64, tolerance: f64) -> !:
if not master.has_face: error(invalid, "G1 and above need the boundary on a surface: pick an edge, or a curve on a face")
var plain = try polynomial_net(net, tolerance)
errdefer plain.close()
let opts = AlignOptions(order, align_edge, Vector3(), 0.0, false, [1.0, 1.0, 1.0, 1.0, 1.0, 1.0], false, false, 0, 0.0, false, 0.0, 1.0, false, false, 0, 0, 0, 0,
true, 16, [tolerance * 10.0, match_angle, 0.1, 0.1], [0.0, 0.0], -1.0, false, false)
var report = empty_report()
try align_side(&plain, side, master, &opts, &report)
net.close()
*net = plain
## The interpolation across `count` sections at `params` (increasing, 0 to
## 1) by a B-spline of `degree` (at most count - 1) on averaged knots onto
## `knots`; the collocation matrix (count by count, row major) onto
## `matrix` (The NURBS Book A9.1).
func collocation(params: const f64[], degree: usize, knots: Growing[f64]*, matrix: Growing[f64]*) -> !:
let n = params.length
knots.clear()
for _ in 0..<degree + 1: try knots.push(0.0)
for j in 1..<n - degree:
var sum = 0.0
for i in j..<j + degree: sum += params[i]
try knots.push(sum / (f64)degree)
for _ in 0..<degree + 1: try knots.push(1.0)
matrix.clear()
try matrix.fill(n * n, 0.0)
for r in 0..<n:
var values: f64[12]
let first = bases_at(knots.view(), n, degree, params[r], false, &values)
for j in 0..<degree + 1: matrix.items[r * n + first + j] = values[j]
## The homogeneous points `values` (one per parameter) interpolated by the
## collocation `matrix` (n by n): the control points onto `out`.
func interpolate_points(matrix: const f64[], values: const Weighted[], out: Growing[Weighted]*) -> !:
let n = values.length
var a = Growing[f64]()
defer a.close()
var xyz = Growing[Vector3]()
defer xyz.close()
var w = Growing[Vector3]()
defer w.close()
for q in values:
try xyz.push(Vector3(q.x, q.y, q.z))
try w.push(Vector3(q.w, 0.0, 0.0))
try a.assign(matrix)
try solve_dense(&a, n, &xyz)
try a.assign(matrix)
try solve_dense(&a, n, &w)
out.clear()
for k in 0..<n: try out.push(Weighted(xyz.items[k].x, xyz.items[k].y, xyz.items[k].z, w.items[k].x))