Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / 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) < 1e-300: 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)