dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / modeling / offset_surface.lucb
## This file: a B-spline surface's offset (base + d · normal), fitted as a
## B-spline to the model's tolerance, for Offset Face, Move and Shell on
## B-spline faces (face_moves.lucb). The offset is as smooth as the base's
## normal, one order less than the base: it keeps the base's degree and
## breakpoints, each interior breakpoint once more (a G2 strip's C2 joins
## become C1). The fit interpolates the exact offset at the Greville points
## of those knots (a collocation, solved per row and per column), and
## halves every span until it stays within a quarter of the tolerance over
## each span, at most seven times: two neighbors' offsets, fitted on knots
## of their own, then meet within the tolerance at their shared edge and
## tangentially (a G2 corner patch's offsets, fitted to the whole
## tolerance, met its strips' 1.4e-6 apart at 0.04 degrees, and their
## meshes did not close). A profile swept straight (an extruded
## blend) stays one: its offset is the offset profile swept the same way,
## and it is swept four offsets further both ways, so a neighbor moved out
## past its old end (a shell's opened top) still meets it.
## The offset of B-spline `s` by `d` along its normal (nurbs_normal's
## side), within `tolerance`.
func offset_spline(s: const Surface*, d: f64, tolerance: f64) -> Surface!:
var ku = Growing[f64]()
defer ku.close()
var kv = Growing[f64]()
defer kv.close()
# A profile swept straight offsets to one swept straight: its sweep
# needs no more spans.
let (swept, _) = extrusion_of(s)
for round in 0..<(usize)8:
try offset_knots(s.ku, s.du, (usize)s.nu, round, &ku)
try offset_knots(s.kv, s.dv, (usize)s.nv, 0 if swept else round, &kv)
let made = try offset_fit(s, d, ku.view(), kv.view())
if (try offset_error(s, d, &made)) <= tolerance * 0.25:
if not swept: return made
defer made.close()
return try swept_further(&made, math.abs(d) * 4.0)
made.close()
error(invalid, "a B-spline face's offset does not fit within the tolerance (its curvature is too near the offset)")
## Knots for the offset along one direction of a base with `knots` (of
## `degree`, `count` control points): the same degree and breakpoints, each
## interior breakpoint's multiplicity one more (up to the degree), every
## span halved `round` times.
func offset_knots(knots: const f64[], degree: i64, count: usize, round: usize, out: Growing[f64]*) -> !:
out.clear()
let p = (usize)degree
let low = knots[p]
let high = knots[count]
for _ in 0..<p + 1: try out.push(low)
var at = p + 1
var previous = low
while at < count:
let value = knots[at]
var times: usize = 0
while at < count and knots[at] == value:
times += 1
at += 1
try span_halves(previous, value, round, out)
for _ in 0..<(p if times + 1 > p else times + 1): try out.push(value)
previous = value
try span_halves(previous, high, round, out)
for _ in 0..<p + 1: try out.push(high)
## The interior knots splitting [a, b] into 2^round equal spans.
func span_halves(a: f64, b: f64, round: usize, out: Growing[f64]*) -> !:
let pieces = (usize)1 << round
for k in 1..<pieces: try out.push(a + (b - a) * (f64)k / (f64)pieces)
## The point of the exact offset at knot values (u, v) of the base (whose
## domain the fit shares).
func offset_point(s: const Surface*, d: f64, u: f64, v: f64) -> Vector3!:
let uv = normalized(s, u, v)
let n = try nurbs_normal(*s, uv)
if n.length() < 0.5: error(invalid, "a B-spline face has a point with no normal (a pole or a fold): its offset is not made")
return (try evaluate(*s, uv)).add(n.multiply_scalar(d))
## The B-spline on knots `ku` and `kv` (of the base's degrees) through the
## exact offset at their Greville points.
func offset_fit(s: const Surface*, d: f64, ku: const f64[], kv: const f64[]) -> Surface!:
let p = (usize)s.du
let q = (usize)s.dv
let nu = ku.length - p - 1
let nv = kv.length - q - 1
if nu * nv > 65536: error(invalid, "a B-spline face's offset needs more than 65,536 control points")
let gu = try new f64[nu] --- in memory.heap
defer free(gu) in memory.heap
let gv = try new f64[nv] --- in memory.heap
defer free(gv) in memory.heap
for i in 0..<nu: gu[i] = greville_of(ku, p, i)
for j in 0..<nv: gv[j] = greville_of(kv, q, j)
# The exact offset at every pair, then each row solved along u, then
# each column along v.
let values = try new Vector3[nu * nv] --- in memory.heap
defer free(values) in memory.heap
for i in 0..<nu:
for j in 0..<nv: values[i * nv + j] = try offset_point(s, d, gu[i], gv[j])
let along_u = try collocation(ku, p, gu)
defer free(along_u) in memory.heap
let along_v = try collocation(kv, q, gv)
defer free(along_v) in memory.heap
let column = try new Vector3[nu if nu > nv else nv] --- in memory.heap
defer free(column) in memory.heap
for j in 0..<nv:
for i in 0..<nu: column[i] = values[i * nv + j]
try solve_dense(along_u, nu, column[..<nu])
for i in 0..<nu: values[i * nv + j] = column[i]
for i in 0..<nu:
for j in 0..<nv: column[j] = values[i * nv + j]
try solve_dense(along_v, nv, column[..<nv])
for j in 0..<nv: values[i * nv + j] = column[j]
let weights = try new f64[nu * nv] --- in memory.heap
defer free(weights) in memory.heap
for at in 0..<weights.length: weights[at] = 1.0
return try Surface(surface_spline, Vector3(), Vector3(1.0, 0.0, 0.0), Vector3(0.0, 0.0, 1.0), 0.0, 0.0, values, weights, ku, kv, (i64)nu, (i64)nv, s.du, s.dv)
## The Greville point of control point `i` on `knots` of `degree`.
func greville_of(knots: const f64[], degree: usize, i: usize) -> f64:
var sum: f64 = 0.0
for k in 1..<degree + 1: sum += knots[i + k]
return sum / (f64)degree
## The n × n collocation matrix of the bases on `knots` (of `degree`) at
## `points`, row by row.
func collocation(knots: const f64[], degree: usize, points: const f64[]) -> f64[]!:
let n = points.length
let matrix = try new f64[n * n] --- in memory.heap
for at in 0..<matrix.length: matrix[at] = 0.0
var values: f64[12]
for i in 0..<n:
let first = nurbs_basis(knots, (i64)n, (i64)degree, points[i], &values)
for k in 0..<degree + 1:
if first + k < n: matrix[i * n + first + k] = values[k]
return matrix
## Solve `matrix` (n × n, row by row; left as it was) x = `rhs` in place,
## by elimination with partial pivoting on a copy.
func solve_dense(matrix: const f64[], n: usize, rhs: Vector3[]) -> !:
let a = try new f64[n * n] --- in memory.heap
defer free(a) in memory.heap
for at in 0..<a.length: a[at] = matrix[at]
for column in 0..<n:
var pivot = column
for row in column + 1..<n:
if math.abs(a[row * n + column]) > math.abs(a[pivot * n + column]): pivot = row
if math.abs(a[pivot * n + column]) < 1e-14: error(invalid, "a B-spline offset's collocation is singular")
if pivot != column:
for k in 0..<n:
let swap = a[column * n + k]
a[column * n + k] = a[pivot * n + k]
a[pivot * n + k] = swap
let swap = rhs[column]
rhs[column] = rhs[pivot]
rhs[pivot] = swap
for row in column + 1..<n:
let factor = a[row * n + column] / a[column * n + column]
if factor == 0.0: continue
for k in column..<n: a[row * n + k] -= factor * a[column * n + k]
rhs[row] = rhs[row].subtract(rhs[column].multiply_scalar(factor))
var row = n
while row > 0:
row -= 1
var sum = rhs[row]
for k in row + 1..<n: sum = sum.subtract(rhs[k].multiply_scalar(a[row * n + k]))
rhs[row] = sum.multiply_scalar(1.0 / a[row * n + row])
## The fit's largest distance from the exact offset over its spans: five
## by five points in each, from next to its sides to its middle (an offset
## a quarter-span grid passed strayed seven tolerances between, and its
## neighbors' offsets then met at an angle).
func offset_error(s: const Surface*, d: f64, made: const Surface*) -> f64!:
var worst: f64 = 0.0
let p = (usize)made.du
let q = (usize)made.dv
for i in p..<(usize)made.nu:
let a = made.ku[i]
let b = made.ku[i + 1]
if not (b > a): continue
for j in q..<(usize)made.nv:
let c = made.kv[j]
let e = made.kv[j + 1]
if not (e > c): continue
for fu in [0.03, 0.25, 0.5, 0.75, 0.97]:
for fv in [0.03, 0.25, 0.5, 0.75, 0.97]:
let u = a + (b - a) * fu
let v = c + (e - c) * fv
let exact = try offset_point(s, d, u, v)
worst = math.max(worst, (try evaluate(*made, normalized(made, u, v))).subtract(exact).length())
return worst
## Knot values (u, v) of `s` as its normalized parameters (evaluate's).
func normalized(s: const Surface*, u: f64, v: f64) -> Vector3:
let u0 = s.ku[(usize)s.du]
let u1 = s.ku[(usize)s.nu]
let v0 = s.kv[(usize)s.dv]
let v1 = s.kv[(usize)s.nv]
return Vector3((u - u0) / (u1 - u0), (v - v0) / (v1 - v0), 0.0)
## Profile surface `s` (two rows, the second the first moved along the
## sweep) swept `reach` further at both ends.
func swept_further(s: const Surface*, reach: f64) -> Surface!:
let points = try new Vector3[s.points.length] --- in memory.heap
defer free(points) in memory.heap
for u in 0..<(usize)s.nu:
let a = s.points[u * 2]
let b = s.points[u * 2 + 1]
let along = b.subtract(a).normalized() catch failure: recover Vector3()
points[u * 2] = a.subtract(along.multiply_scalar(reach))
points[u * 2 + 1] = b.add(along.multiply_scalar(reach))
return try Surface(surface_spline, s.origin, s.x, s.z, s.radius, s.angle, points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv)