dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / modeling / splines.lucb
## B-spline surfaces in modeling: their chart (the surface's own parameters,
## found by inversion), normals, and where a plane or a cylinder along the
## sweep cuts a profile swept straight (a surface of linear extrusion: two
## rows of control points, the second the first moved by one vector), in
## closed form. Blends of G2 and
## G3 continuity are such surfaces (blend.lucb), as are extruded splines.
## Other pairs with B-spline surfaces are not supported yet.
## Surface `s`'s parameters at `p` (on it within `tol`), by inversion
## from `seed`; an error when `p` is not on it.
func spline_uv(s: const Surface*, p: Vector3, tol: f64, seed: Vector3 = Vector3(0.5, 0.5, 0.0)) -> (f64, f64)!:
let uv = try project(*s, p, seed, tol)
return (uv.x, uv.y)
## Whether `s` is a profile swept straight, and the sweep (the second row's
## offset from the first).
func extrusion_of(s: const Surface*) -> (bool, Vector3):
if s.kind != surface_spline or s.nv != 2 or s.dv != 1: return (false, Vector3())
let sweep = s.points[1].subtract(s.points[0])
let reach = sweep.length()
if reach <= 0.0: return (false, Vector3())
for u in 0..<(usize)s.nu:
if s.points[u * 2 + 1].subtract(s.points[u * 2]).subtract(sweep).length() > reach * 1e-9: return (false, Vector3())
if s.weights.length > 0 and s.weights[u * 2] != s.weights[u * 2 + 1]: return (false, Vector3())
return (true, sweep)
## Where plane `p` cuts profile surface `s` (extrusion_of), onto `out`: the
## profile moved along the sweep onto the plane (an affine copy, exact) when
## the plane crosses the sweep; else lines along it through the profile's
## points on the plane (its ends where it touches, found exactly). Spline
## curves are stored in `w`.
func plane_extrusion(w: Shape*, p: const Surface*, s: const Surface*, sweep: Vector3, tol: f64, out: Growing[Carrier]*) -> !:
let n = p.z
let h = n.dot(p.origin)
let along = try sweep.normalized()
let nu = (usize)s.nu
let crossing = n.dot(along)
if math.abs(crossing) > 1e-9:
var moved = Growing[Vector3]()
defer moved.close()
var weights = Growing[f64]()
defer weights.close()
for u in 0..<nu:
let q = s.points[u * 2]
try moved.push(q.add(along.multiply_scalar((h - n.dot(q)) / crossing)))
try weights.push(s.weights[u * 2] if s.weights.length > 0 else 1.0)
# Knots from 0 to 1, as carriers of traced curves run.
var knots = Growing[f64]()
defer knots.close()
let low = s.ku[0]
let span = s.ku[s.ku.length - 1] - low
for k in s.ku: try knots.push((k - low) / span)
let spline = try w.store_spline(moved.view(), weights.view(), knots.view(), s.du, Matrix4())
try out.push(Carrier(2, Vector3(), Vector3(), Vector3(), 0.0, 0.0, spline))
return
try along_sweep(p, s, along, tol, out)
## Where `other`, a plane or a cylinder lying along profile surface `s`'s
## sweep (its axis that way), meets it, onto `out`: lines along the sweep
## through the profile's points on `other`. A blend's section touches its
## faces at its ends, tangentially (a G1 conic, a G2 or G3 section on a
## cylinder: no sign change there), so an end within `tol` of `other` is a
## meeting; inside, a curve hugging it (touching it, G2) stays within reach
## over a stretch, so only crossings count there, each found by bisection.
func along_sweep(other: const Surface*, s: const Surface*, along: Vector3, tol: f64, out: Growing[Carrier]*) -> !:
let samples = 64 * (usize)s.nu
var previous = 0.0
for k in 0..<samples + 1:
let u = (f64)k / (f64)samples
let point = try evaluate(*s, Vector3(u, 0.0, 0.0))
let value = sweep_gap(other, point)
var hit = false
var at = u
if math.abs(value) <= tol:
hit = k == 0 or k == samples
elif k > 0 and math.abs(previous) > tol and (previous < 0.0) != (value < 0.0):
var low = u - 1.0 / (f64)samples
var high = u
for _ in 0..<60:
let middle = (low + high) * 0.5
let m = sweep_gap(other, try evaluate(*s, Vector3(middle, 0.0, 0.0)))
if (m < 0.0) == (previous < 0.0): low = middle
else: high = middle
at = (low + high) * 0.5
hit = true
if hit: try out.push(Carrier(0, try evaluate(*s, Vector3(at, 0.0, 0.0)), along, Vector3(), 0.0, 0.0, -1))
previous = value
## How far `p` is from `other` (along_sweep's plane: along its normal; its
## cylinder: from the axis less the radius), signed.
func sweep_gap(other: const Surface*, p: Vector3) -> f64:
let d = p.subtract(other.origin)
if other.kind == surface_plane: return d.dot(other.z)
return d.subtract(other.z.multiply_scalar(d.dot(other.z))).length() - other.radius
## Where faces `fa` and `fb` of `w` meet when one lies on a B-spline
## surface, onto `out`: a plane and a profile swept straight, in closed
## form (plane_extrusion), and a cylinder along its sweep (along_sweep); a profile turned about an axis and a plane
## across it, or a cylinder or cone about it, in circles (coaxial_spline);
## whether it did (anything else is traced: march.lucb).
func spline_meet(w: Shape*, fa: usize, fb: usize, tol: f64, out: Growing[Carrier]*) -> bool!:
let sa = &w.surfaces.items[(usize)w.faces.items[fa].surface]
let sb = &w.surfaces.items[(usize)w.faces.items[fb].surface]
let spline = sa if sa.kind == surface_spline else sb
let other = sb if sa.kind == surface_spline else sa
if other.kind == surface_plane:
let (swept, sweep) = extrusion_of(spline)
if swept:
try plane_extrusion(w, other, spline, sweep, tol, out)
return true
# A cylinder along a profile's sweep (a D-shaft's, where a plane meets
# it along its length): lines through the profile's points on it.
if other.kind == surface_cylinder:
let (swept, sweep) = extrusion_of(spline)
if swept and math.abs(math.abs(other.z.dot(try sweep.normalized())) - 1.0) <= 1e-9:
try along_sweep(other, spline, try sweep.normalized(), tol, out)
return true
# Two profiles swept straight along different ways (two G2 fillets
# meeting at a corner): their curve lies in a plane bisecting the
# sweeps, as an affine copy of either profile.
if sa.kind == surface_spline and sb.kind == surface_spline:
let (swept_a, sweep_a) = extrusion_of(sa)
let (swept_b, sweep_b) = extrusion_of(sb)
if swept_a and swept_b:
if try extrusion_pair(w, sa, sweep_a, sb, sweep_b, tol, out): return true
let (turned, center, axis) = revolution_of(spline, tol)
if turned and other.kind != surface_spline:
if try coaxial_spline(spline, center, axis, other, tol, out): return true
# Kept apart by a plane, they touch at most, along curves their
# boundaries carry: nothing to add.
if try kept_apart(sa, sb, tol): return true
# Anything else is traced (march.lucb).
return false
## Whether surfaces `sa` and `sb` (one a B-spline) cannot cross, only
## touch, because a plane keeps them apart. A B-spline surface lies in its
## control points' hull. So the planes tried are a flat surface's own,
## with the B-spline's control points all on one side; and, for a profile
## swept straight, the planes square to the sweep at its ends, with the
## other's control points beyond one. A setback corner's patch meets the
## faces and fillets about it this way (setback.lucb).
func kept_apart(sa: const Surface*, sb: const Surface*, tol: f64) -> bool!:
if sa.kind == surface_spline and sb.kind == surface_plane: return one_side(sa.points, sb.z, sb.z.dot(sb.origin), tol)
if sb.kind == surface_spline and sa.kind == surface_plane: return one_side(sb.points, sa.z, sa.z.dot(sa.origin), tol)
if sa.kind != surface_spline or sb.kind != surface_spline: return false
for pass in 0..<2:
let swept = sa if pass == 0 else sb
let other = sb if pass == 0 else sa
let (is_swept, sweep) = extrusion_of(swept)
if not is_swept: continue
let d = try sweep.normalized()
let (low, high) = along_range(swept.points, d)
let (other_low, other_high) = along_range(other.points, d)
if other_high <= low + tol or other_low >= high - tol: return true
return false
## Whether `points` all lie on one side of the plane n . p = h (within
## `tol` of it counts as either).
func one_side(points: const Vector3[], n: Vector3, h: f64, tol: f64) -> bool:
var below = false
var above = false
for p in points:
let s = n.dot(p) - h
if s < -tol: below = true
if s > tol: above = true
return not (below and above)
## The least and greatest of `points` along `d`.
func along_range(points: const Vector3[], d: Vector3) -> (f64, f64):
var low = 1.0e300
var high = -1.0e300
for p in points:
low = math.min(low, d.dot(p))
high = math.max(high, d.dot(p))
return (low, high)
## Whether `s` is a profile turned about an axis (the surfaces Revolve and
## rim blends make of splines: rows of five control points, two rational
## quadratic arcs), and that axis: a point on it and its direction.
func revolution_of(s: const Surface*, tol: f64) -> (bool, Vector3, Vector3):
if s.kind != surface_spline or s.nv != 5 or s.dv != 2: return (false, Vector3(), Vector3())
for u in 0..<(usize)s.nu:
let q0 = s.points[u * 5]
let q2 = s.points[u * 5 + 2]
let q4 = s.points[u * 5 + 4]
let n = q2.subtract(q0).cross(q4.subtract(q0))
let length = n.length()
if length <= tol * tol: continue
let axis = n.multiply_scalar(1.0 / length)
# The circle's center: where the chords' bisectors meet, in its plane.
let m1 = q0.add(q2).multiply_scalar(0.5)
let m2 = q2.add(q4).multiply_scalar(0.5)
let d1 = axis.cross(q2.subtract(q0))
let d2 = axis.cross(q4.subtract(q2))
let det = d1.cross(d2).dot(axis)
if math.abs(det) < nonzero: continue
let t = m2.subtract(m1).cross(d2).dot(axis) / det
return (true, m1.add(d1.multiply_scalar(t)), axis)
return (false, Vector3(), Vector3())
## Where a turned profile (`s`, about `center` along `axis`) meets `other`:
## a plane across the axis, where the profile's height is the plane's; a
## cylinder or cone about the axis, where its radius is theirs. Each place
## along the profile (its ends found exactly) is a circle onto `out`. False
## when `other` is none of these.
func coaxial_spline(s: const Surface*, center: Vector3, axis: Vector3, other: const Surface*, tol: f64, out: Growing[Carrier]*) -> bool!:
let kind = other.kind
if kind == surface_plane:
if math.abs(math.abs(other.z.dot(axis)) - 1.0) > 1e-9: return false
elif kind == surface_cylinder or kind == surface_cone:
if math.abs(math.abs(other.z.dot(axis)) - 1.0) > 1e-9: return false
let offset = other.origin.subtract(center)
if offset.subtract(axis.multiply_scalar(offset.dot(axis))).length() > tol: return false
else: return false
let x = try across(axis)
let samples = 64 * (usize)s.nu
var previous = 0.0
for k in 0..<samples + 1:
let u = (f64)k / (f64)samples
let p = try evaluate(*s, Vector3(u, 0.0, 0.0))
let value = coaxial_gap(p, center, axis, other)
var at = -1.0
if math.abs(value) <= tol:
# On it at an end (a blend's contact); inside, only crossings.
if k == 0 or k == samples: at = u
elif k > 0 and math.abs(previous) > tol and (previous < 0.0) != (value < 0.0):
var low = u - 1.0 / (f64)samples
var high = u
for _ in 0..<60:
let middle = (low + high) * 0.5
if (coaxial_gap(try evaluate(*s, Vector3(middle, 0.0, 0.0)), center, axis, other) < 0.0) == (previous < 0.0): low = middle
else: high = middle
at = (low + high) * 0.5
if at >= 0.0:
let q = try evaluate(*s, Vector3(at, 0.0, 0.0))
let h = q.subtract(center).dot(axis)
let foot = center.add(axis.multiply_scalar(h))
let radius = q.subtract(foot).length()
if radius > tol: try out.push(Carrier(1, foot, x, axis.cross(x), radius, radius, -1))
previous = value
return true
## How far profile point `p` is from `other` (a plane across the axis: in
## height; a cylinder or cone about it: in radius), signed.
func coaxial_gap(p: Vector3, center: Vector3, axis: Vector3, other: const Surface*) -> f64:
if other.kind == surface_plane: return p.subtract(other.origin).dot(other.z)
let d = p.subtract(other.origin)
let h = d.dot(other.z)
let radial = d.subtract(other.z.multiply_scalar(h)).length()
if other.kind == surface_cylinder: return radial - other.radius
return radial - (other.radius + h * math.tan(other.angle))
## Where profiles swept straight `a` (along `sweep_a`) and `b` meet, when
## that is in a plane bisecting their sweeps (equal fillets meeting at a
## symmetric corner): the plane through where their profiles' end lines
## (the contacts) cross, its copy of `a`'s profile checked to lie on `b`.
## False when no such plane holds the curve.
func extrusion_pair(w: Shape*, a: const Surface*, sweep_a: Vector3, b: const Surface*, sweep_b: Vector3, tol: f64, out: Growing[Carrier]*) -> bool!:
let da = try sweep_a.normalized()
let db = try sweep_b.normalized()
if da.cross(db).length() < 1e-9: return false
let ends: f64[2] = [0.0, 1.0]
let signs: f64[2] = [-1.0, 1.0]
for ea in ends:
let pa = try evaluate(*a, Vector3(ea, 0.0, 0.0))
for eb in ends:
let pb = try evaluate(*b, Vector3(eb, 0.0, 0.0))
# Where the end lines pa + s da and pb + t db cross.
let k = da.dot(db)
let r = pa.subtract(pb)
let det = 1.0 - k * k
let s = (k * r.dot(db) - r.dot(da)) / det
let t = (r.dot(db) - k * r.dot(da)) / det
let x = pa.add(da.multiply_scalar(s))
if x.subtract(pb.add(db.multiply_scalar(t))).length() > tol * 10.0: continue
for sign in signs:
let n = try da.add(db.multiply_scalar(sign)).normalized()
let plane = try Surface(0, x, try across(n), n, 0.0, 0.0, a.points[..<0], a.weights[..<0], a.ku[..<0], a.kv[..<0], 0, 0, 0, 0)
defer:
var owned = plane
owned.close()
var curves = Growing[Carrier]()
defer curves.close()
try plane_extrusion(w, &plane, a, sweep_a, tol, &curves)
if curves.count != 1 or curves.items[0].kind != curve_spline: continue
# On `b` too, sampled.
var on = true
for step in 0..<9:
let q = try spline_point(w, curves.items[0].spline, (f64)step / 8.0)
# Off `b` where it cannot be inverted there.
let uv = project(*b, q, Vector3(0.5, 0.5, 0.0), tol * 100.0) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
on = false
break
if (try evaluate(*b, uv)).subtract(q).length() > tol * 100.0:
on = false
break
if on:
try out.push(curves.items[0])
return true
return false
## Stored spline `index` of `w` at parameter `t` (0 to 1).
func spline_point(w: const Shape*, index: i64, t: f64) -> Vector3!:
let (points, weights, knots, degree) = w.spline_net(index)
return try NurbsCurve.at(points, weights, degree, knots, knots[(usize)degree] + (knots[points.length] - knots[(usize)degree]) * t)