dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / nurbs / nets.lucb
## Surfaces: a rational tensor-product net in homogeneous form, and the
## curve operations applied across it. Along u, every column of the net
## (fixed v index) is a curve over the u knots; they all change alike, so
## the result is a net again. Rebuilding fits rows, then columns, with the
## boundary's cross derivatives held (fitting.lucb's header).
## A net: degrees, counts, knots and the points u-major (index u nv + v).
pub struct Net:
pub var du: i64
pub var dv: i64
pub var nu: usize
pub var nv: usize
pub var ku: Growing[f64]
pub var kv: Growing[f64]
pub var points: Growing[Weighted]
pub func close():
self.ku.close()
self.kv.close()
self.points.close()
pub func copy() -> Net!:
var made = empty_net()
errdefer made.close()
made.du = self.du
made.dv = self.dv
made.nu = self.nu
made.nv = self.nv
try made.ku.assign(self.ku.view())
try made.kv.assign(self.kv.view())
try made.points.assign(self.points.view())
return made
pub func u_low() -> f64:
return self.ku.items[(usize)self.du]
pub func u_high() -> f64:
return self.ku.items[self.nu]
pub func v_low() -> f64:
return self.kv.items[(usize)self.dv]
pub func v_high() -> f64:
return self.kv.items[self.nv]
## Its homogeneous partial derivatives (a, b) for a, b to 3 at knot
## parameters (u, v): out[a * 4 + b]; at the domain's high ends the
## limit from below.
pub func partials(u: f64, v: f64, out: Weighted[16]*):
var bu: f64[48]
var bv: f64[48]
let fu = basis_jet(self.ku.view(), (i64)self.nu, self.du, u, u >= self.u_high(), &bu)
let fv = basis_jet(self.kv.view(), (i64)self.nv, self.dv, v, v >= self.v_high(), &bv)
for k in 0..<(usize)16: (*out)[k] = Weighted(0.0, 0.0, 0.0, 0.0)
for i in 0..<(usize)self.du + 1:
for j in 0..<(usize)self.dv + 1:
let q = self.points.items[(fu + i) * self.nv + fv + j]
for a in 0..<(usize)4:
for b in 0..<(usize)4:
(*out)[a * 4 + b] = (*out)[a * 4 + b].plus(q.times(bu[a * 12 + i] * bv[b * 12 + j]))
## The point at knot parameters (u, v).
pub func point_at(u: f64, v: f64) -> Vector3:
var bu: f64[12]
var bv: f64[12]
let fu = nurbs_basis(self.ku.view(), (i64)self.nu, self.du, math.clamp(u, self.u_low(), self.u_high()), &bu)
let fv = nurbs_basis(self.kv.view(), (i64)self.nv, self.dv, math.clamp(v, self.v_low(), self.v_high()), &bv)
var sum = Weighted(0.0, 0.0, 0.0, 0.0)
for i in 0..<(usize)self.du + 1:
for j in 0..<(usize)self.dv + 1:
sum = sum.plus(self.points.items[(fu + i) * self.nv + fv + j].times(bu[i] * bv[j]))
return sum.point()
## Whether any weight differs from the first.
pub func rational() -> bool:
for q in self.points.view():
if math.abs(q.w - self.points.items[0].w) > same_weight * math.abs(self.points.items[0].w): return true
return false
pub func empty_net() -> Net:
return Net(1, 1, 0, 0, Growing[f64](), Growing[f64](), Growing[Weighted]())
## The net of B-spline surface `s`.
pub func net_of(s: const Surface*) -> Net!:
if s.kind != surface_spline: error(invalid, "this face is not a B-spline: convert it first")
var made = empty_net()
errdefer made.close()
made.du = s.du
made.dv = s.dv
made.nu = (usize)s.nu
made.nv = (usize)s.nv
try made.ku.assign(s.ku)
try made.kv.assign(s.kv)
for at in 0..<s.points.length: try made.points.push(weighted(s.points[at], s.weights[at]))
return made
## A B-spline surface record of `net`.
pub func surface_of(net: const Net*) -> Surface!:
var points = Growing[Vector3]()
defer points.close()
var weights = Growing[f64]()
defer weights.close()
for q in net.points.view():
try points.push(q.point())
try weights.push(q.w)
return try Surface(surface_spline, Vector3(), Vector3(1.0, 0.0, 0.0), Vector3(0.0, 0.0, 1.0), 0.0, 0.0, points.view(), weights.view(),
net.ku.view(), net.kv.view(), (i64)net.nu, (i64)net.nv, net.du, net.dv)
## The net's curves along `direction` (0: u, each column; 1: v, each row).
pub func curves_along(net: const Net*, direction: i64, out: Growing[Spline]*) -> !:
let along_u = direction == 0
let lines = net.nv if along_u else net.nu
let length = net.nu if along_u else net.nv
for line in 0..<lines:
var c = empty_spline(net.du if along_u else net.dv)
errdefer c.close()
try c.knots.assign(net.ku.view() if along_u else net.kv.view())
for k in 0..<length: try c.points.push(net.points.items[k * net.nv + line if along_u else line * net.nv + k])
try out.push(c)
## A net from `curves` along `direction` (all on one knot vector), the
## other direction's degree and knots taken from `like`.
pub func net_from(curves: const Spline[], direction: i64, like: const Net*) -> Net!:
var made = empty_net()
errdefer made.close()
let along_u = direction == 0
let first = &curves[0]
made.du = first.degree if along_u else like.du
made.dv = like.dv if along_u else first.degree
try made.ku.assign(first.knots.view() if along_u else like.ku.view())
try made.kv.assign(like.kv.view() if along_u else first.knots.view())
made.nu = made.ku.count - (usize)made.du - 1
made.nv = made.kv.count - (usize)made.dv - 1
try made.points.fill(made.nu * made.nv, Weighted(0.0, 0.0, 0.0, 0.0))
for line in 0..<curves.length:
let c = &curves[line]
if c.knots.count != first.knots.count: error(invalid, "a net's curves came out on different knots")
for k in 0..<c.points.count:
if along_u: made.points.items[k * made.nv + line] = c.points.items[k]
else: made.points.items[line * made.nv + k] = c.points.items[k]
return made
func close_curves(curves: Growing[Spline]*):
for c in curves.view():
var owned = c
owned.close()
curves.close()
## Knot `t` (a fraction of the domain along `direction`) inserted `times`
## times across the net; returns how many went in.
pub func net_insert(net: Net*, direction: i64, fraction: f64, times: usize) -> usize!:
var curves = Growing[Spline]()
defer close_curves(&curves)
try curves_along(net, direction, &curves)
let low = net.u_low() if direction == 0 else net.v_low()
let high = net.u_high() if direction == 0 else net.v_high()
let t = low + (high - low) * fraction
var done: usize = 0
for at in 0..<curves.count: done = try insert_knot(&curves.items[at], t, times)
if done == 0: return 0
let made = try net_from(curves.view(), direction, net)
net.close()
*net = made
return done
## Knot `t` (the inner knot nearest a fraction of the domain) removed up to
## `times` times across the net, while every curve moves at most
## `tolerance`; returns how many went.
pub func net_remove(net: Net*, direction: i64, fraction: f64, times: usize, tolerance: f64) -> usize!:
let knots = net.ku.view() if direction == 0 else net.kv.view()
let degree = net.du if direction == 0 else net.dv
let count = net.nu if direction == 0 else net.nv
let low = knots[(usize)degree]
let high = knots[count]
let t = low + (high - low) * fraction
var u = math.nan
for k in knots:
if k > low and k < high and (math.is_nan(u) or math.abs(k - t) < math.abs(u - t)): u = k
if math.is_nan(u): error(invalid, "this surface has no inner knots that way to remove")
var k = times
while k > 0:
var curves = Growing[Spline]()
defer close_curves(&curves)
try curves_along(net, direction, &curves)
var all = true
for at in 0..<curves.count:
if (try remove_knot(&curves.items[at], u, k, tolerance)) != k: all = false
if all:
let made = try net_from(curves.view(), direction, net)
net.close()
*net = made
return k
k -= 1
return 0
## The degree along `direction` raised by `by` (the same surface).
pub func net_elevate(net: Net*, direction: i64, by: usize) -> !:
if by == 0: return
var curves = Growing[Spline]()
defer close_curves(&curves)
try curves_along(net, direction, &curves)
for at in 0..<curves.count: try elevate(&curves.items[at], by)
let made = try net_from(curves.view(), direction, net)
net.close()
*net = made
## Every inner knot along `direction` to full multiplicity: Bezier patches.
pub func net_bezier(net: Net*, direction: i64) -> !:
var curves = Growing[Spline]()
defer close_curves(&curves)
try curves_along(net, direction, &curves)
for at in 0..<curves.count: try to_bezier(&curves.items[at])
let made = try net_from(curves.view(), direction, net)
net.close()
*net = made
## The degree along `direction` lowered by one within `tolerance` (its
## deviation onto `deviation`; refused beyond it).
pub func net_reduce(net: Net*, direction: i64, tolerance: f64, deviation: f64*) -> !:
var curves = Growing[Spline]()
defer close_curves(&curves)
try curves_along(net, direction, &curves)
var reduced = Growing[Spline]()
defer close_curves(&reduced)
var worst = 0.0
for at in 0..<curves.count:
var d = 0.0
try reduced.push(try reduce_curve(&curves.items[at], math.infinity, &d))
let made = try net_from(reduced.view(), direction, net)
worst = net_deviation(net, &made, 12)
*deviation = worst
if worst > tolerance:
var owned = made
owned.close()
var buffer: u8[200]
error(invalid, try strings.format(buffer, f"lowering the degree moves the surface {worst:.6f}, more than the tolerance {tolerance}"))
net.close()
*net = made
## The largest distance between `a` and `b` (equal domains) at `per`
## samples a span of `a`, both ways.
pub func net_deviation(a: const Net*, b: const Net*, per: usize) -> f64:
let su = per * (a.nu - (usize)a.du) + 1
let sv = per * (a.nv - (usize)a.dv) + 1
var most = 0.0
for i in 0..<su + 1:
let u = a.u_low() + (a.u_high() - a.u_low()) * (f64)i / (f64)su
for j in 0..<sv + 1:
let v = a.v_low() + (a.v_high() - a.v_low()) * (f64)j / (f64)sv
most = math.max(most, a.point_at(u, v).subtract(b.point_at(u, v)).length())
return most
## Euclidean partials of a surface from its homogeneous ones (The NURBS
## Book, A4.4), as homogeneous points of weight 1 (then 0).
pub func euclidean_partials(a: const Weighted[16]*, out: Weighted[16]*):
var s: Vector3[16] = [Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3()]
let w = (*a)[0].w
for k in 0..<(usize)4:
for l in 0..<(usize)4:
var v = Vector3((*a)[k * 4 + l].x, (*a)[k * 4 + l].y, (*a)[k * 4 + l].z)
for j in 1..<l + 1: v = v.subtract(s[k * 4 + l - j].multiply_scalar(choose(l, j) * (*a)[j].w))
for i in 1..<k + 1:
v = v.subtract(s[(k - i) * 4 + l].multiply_scalar(choose(k, i) * (*a)[i * 4].w))
for j in 1..<l + 1: v = v.subtract(s[(k - i) * 4 + l - j].multiply_scalar(choose(k, i) * choose(l, j) * (*a)[i * 4 + j].w))
s[k * 4 + l] = v.multiply_scalar(1.0 / w)
(*out)[k * 4 + l] = Weighted(v.x / w, v.y / w, v.z / w, 1.0 if k + l == 0 else 0.0)
## `net` rebuilt on knots `ku` (degree `du`) and `kv` (degree `dv`), its
## boundary held to G`keep_u` across its u ends and G`keep_v` across its
## v ends; with `rational` false, weights 1.
pub func refit_net(net: const Net*, du: i64, ku: const f64[], dv: i64, kv: const f64[], keep_u: usize, keep_v: usize, rational: bool) -> Net!:
var pu = Growing[f64]()
defer pu.close()
var pv = Growing[f64]()
defer pv.close()
try fit_parameters(ku, du, 2 * ((usize)du + 1), &pu)
try fit_parameters(kv, dv, 2 * ((usize)dv + 1), &pv)
var fu = try make_fitter(du, ku, pu.view(), keep_u)
defer fu.close()
var fv = try make_fitter(dv, kv, pv.view(), keep_v)
defer fv.close()
let nu = fu.count()
let nv = fv.count()
# Pass 1, along u: one line a v sample, then the v ends' cross
# derivatives 1..keep_v (lines of the partials (0, b)).
var lines = Growing[Weighted]()
defer lines.close()
var values = Growing[Weighted]()
defer values.close()
var fitted = Growing[Weighted]()
defer fitted.close()
var table: Weighted[16]
var shown: Weighted[16]
let v_ends: f64[2] = [net.v_low(), net.v_high()]
let rows = pv.count + 2 * keep_v
for row in 0..<rows:
var v = 0.0
var b: usize = 0
if row < pv.count: v = pv.items[row]
else:
let extra = row - pv.count
v = v_ends[extra // keep_v]
b = extra % keep_v + 1
values.clear()
for u in pu.view():
net.partials(u, v, &table)
if not rational: euclidean_partials(&table, &shown)
try values.push(table[b] if rational else shown[b])
var starts: Weighted[4]
var ends: Weighted[4]
net.partials(net.u_low(), v, &table)
if not rational: euclidean_partials(&table, &shown)
for a in 0..<(usize)4: starts[a] = table[a * 4 + b] if rational else shown[a * 4 + b]
net.partials(net.u_high(), v, &table)
if not rational: euclidean_partials(&table, &shown)
for a in 0..<(usize)4: ends[a] = table[a * 4 + b] if rational else shown[a * 4 + b]
try fu.fit(values.view(), &starts, &ends, &fitted)
for q in fitted.view(): try lines.push(q)
# Pass 2, along v: each control column through the lines.
var made = empty_net()
errdefer made.close()
made.du = du
made.dv = dv
made.nu = nu
made.nv = nv
try made.ku.assign(ku)
try made.kv.assign(kv)
try made.points.fill(nu * nv, Weighted(0.0, 0.0, 0.0, 0.0))
for i in 0..<nu:
values.clear()
for row in 0..<pv.count: try values.push(lines.items[row * nu + i])
var starts: Weighted[4]
var ends: Weighted[4]
for k in 0..<(usize)4:
starts[k] = Weighted(0.0, 0.0, 0.0, 0.0)
ends[k] = Weighted(0.0, 0.0, 0.0, 0.0)
starts[0] = lines.items[0 * nu + i]
ends[0] = lines.items[(pv.count - 1) * nu + i]
for b in 1..<keep_v + 1:
starts[b] = lines.items[(pv.count + b - 1) * nu + i]
ends[b] = lines.items[(pv.count + keep_v + b - 1) * nu + i]
try fv.fit(values.view(), &starts, &ends, &fitted)
for j in 0..<nv: made.points.items[i * nv + j] = fitted.items[j]
return made
## `net` rebuilt within `tolerance`: from `spans_u` by `spans_v` uniform
## spans, a knot added in the middle of every span still further off than
## the tolerance, until it is within it or a direction has `most` spans.
## Its deviation onto `deviation`.
pub func refit_within(net: const Net*, du: i64, dv: i64, spans_u: usize, spans_v: usize, most: usize, keep_u: usize, keep_v: usize, rational: bool, tolerance: f64, deviation: f64*) -> Net!:
var ku = Growing[f64]()
defer ku.close()
var kv = Growing[f64]()
defer kv.close()
try uniform_knots(du, spans_u, net.u_low(), net.u_high(), &ku)
try uniform_knots(dv, spans_v, net.v_low(), net.v_high(), &kv)
while true:
var made = try refit_net(net, du, ku.view(), dv, kv.view(), keep_u, keep_v, rational)
var worst_u = Growing[f64]()
defer worst_u.close()
var worst_v = Growing[f64]()
defer worst_v.close()
let worst = try span_errors(net, &made, &worst_u, &worst_v)
*deviation = worst
let full = made.nu - (usize)du >= most and made.nv - (usize)dv >= most
if worst <= tolerance or full: return made
made.close()
try split_spans(&ku, du, worst_u.view(), tolerance, most)
try split_spans(&kv, dv, worst_v.view(), tolerance, most)
error(invalid, "unreachable")
## The largest distance in each u span and each v span of `made` from
## `net` (8 samples a span both ways), and over all.
func span_errors(net: const Net*, made: const Net*, worst_u: Growing[f64]*, worst_v: Growing[f64]*) -> f64!:
let spans_u = made.nu - (usize)made.du
let spans_v = made.nv - (usize)made.dv
try worst_u.fill(spans_u, 0.0)
try worst_v.fill(spans_v, 0.0)
var most = 0.0
for su in 0..<spans_u:
let a = made.ku.items[(usize)made.du + su]
let b = made.ku.items[(usize)made.du + su + 1]
for sv in 0..<spans_v:
let c = made.kv.items[(usize)made.dv + sv]
let d = made.kv.items[(usize)made.dv + sv + 1]
for i in 0..<(usize)9:
for j in 0..<(usize)9:
let u = a + (b - a) * (f64)i / 8.0
let v = c + (d - c) * (f64)j / 8.0
let e = net.point_at(u, v).subtract(made.point_at(u, v)).length()
worst_u.items[su] = math.max(worst_u.items[su], e)
worst_v.items[sv] = math.max(worst_v.items[sv], e)
most = math.max(most, e)
return most
## A knot in the middle of every span of `knots` whose error passed
## `tolerance`, while there are fewer than `most` spans.
func split_spans(knots: Growing[f64]*, degree: i64, errors: const f64[], tolerance: f64, most: usize) -> !:
var made = Growing[f64]()
defer made.close()
var spans = errors.length
let p = (usize)degree
for i in 0..<p + 1: try made.push(knots.items[i])
for span in 0..<errors.length:
if errors[span] > tolerance and spans < most:
try made.push((knots.items[p + span] + knots.items[p + span + 1]) * 0.5)
spans += 1
if span + 1 < errors.length: try made.push(knots.items[p + span + 1])
for i in knots.count - p - 1..<knots.count: try made.push(knots.items[i])
try knots.assign(made.view())
## Every inner knot of `net` along `direction` removed as far as the
## surface stays within `tolerance` (Alias's Reduce Spans): with `single`,
## only down to one of each (Del Multi Knots). Returns how many went.
pub func net_reduce_spans(net: Net*, direction: i64, tolerance: f64, single: bool) -> usize!:
var removed: usize = 0
var changed = true
while changed:
changed = false
let knots = net.ku.view() if direction == 0 else net.kv.view()
let degree = net.du if direction == 0 else net.dv
let count = net.nu if direction == 0 else net.nv
let low = knots[(usize)degree]
let high = knots[count]
var inner = Growing[f64]()
defer inner.close()
for k in knots:
if k > low and k < high and (inner.count == 0 or inner.items[inner.count - 1] != k): try inner.push(k)
for u in inner.view():
let m = multiplicity(knots, u, 0.0)
let times = m - 1 if single else m
if times == 0: continue
let gone = try net_remove(net, direction, (u - low) / (high - low), times, tolerance)
if gone > 0:
removed += gone
changed = true
break
return removed