Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / src / sketch / shapes.lucb

## The sketch's free-form curves as NURBS on its plane's coordinates
## (sketch x and y): a control point spline its own net with clamped
## uniform knots; a fit point spline the net that passes through its points
## (global interpolation, chord-length parameters and averaged knots: The
## NURBS Book, §9.2.1); an ellipse three rational quadratic arcs of a
## circle mapped onto it (NURBS keep an affine map); a conic one rational
## quadratic span, the apex weighted rho / (1 - rho). curves.lucb puts the
## nets on the plane; the editor's drawing and picking sample them.

## A NURBS curve: control points (`xs`, `ys`), weights, knots and degree.
pub struct Net:
    pub var xs: Growing[f64]
    pub var ys: Growing[f64]
    pub var ws: Growing[f64]
    pub var knots: Growing[f64]
    pub var degree: i64

    pub func close():
        self.xs.close()
        self.ys.close()
        self.ws.close()
        self.knots.close()

    pub func count() -> usize:
        return self.xs.count

    func clear():
        self.xs.clear()
        self.ys.clear()
        self.ws.clear()
        self.knots.clear()

    func push(x: f64, y: f64, w: f64 = 1.0) -> !:
        try self.xs.push(x)
        try self.ys.push(y)
        try self.ws.push(w)

    ## The parameter range: from the first to the last of its spans.
    pub func range() -> (f64, f64):
        return (self.knots.items[(usize)self.degree], self.knots.items[self.xs.count])

    ## The point at parameter `t` (clamped to the range).
    pub func at(t: f64) -> (f64, f64):
        let (low, high) = self.range()
        let u = math.max(low, math.min(high, t))
        let p = (usize)self.degree
        let span = find_span(self.knots.view(), self.xs.count, p, u)
        var basis: f64[6] = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
        basis_at(self.knots.view(), span, u, p, basis[0..])
        var x = 0.0
        var y = 0.0
        var w = 0.0
        for j in 0..<p + 1:
            let i = span - p + j
            let weighted = basis[j] * self.ws.items[i]
            x += weighted * self.xs.items[i]
            y += weighted * self.ys.items[i]
            w += weighted
        return (x / w, y / w)

    ## `count` + 1 points along it, evenly in its parameter, onto `out` as
    ## x, y pairs.
    pub func sample(count: usize, out: Growing[f64]*) -> !:
        out.clear()
        let (low, high) = self.range()
        for at in 0..<count + 1:
            let (x, y) = self.at(low + (high - low) * (f64)at / (f64)count)
            try out.push(x)
            try out.push(y)

## Spline `e`'s degree: its own, or one less than its points when fewer.
pub func spline_degree(e: SketchEntity) -> i64:
    return e.third if e.third < e.second - 1 else e.second - 1

pub func new_net() -> Net:
    return Net(Growing[f64](), Growing[f64](), Growing[f64](), Growing[f64](), 0)

## Spline, ellipse or conic `e` of `sketch` as a NURBS onto `out`.
pub func net_of(sketch: const Sketch*, e: SketchEntity, out: Net*) -> !:
    out.clear()
    if e.kind == EntityKind.spline:
        if e.fourth != 0:
            try fit_net(sketch, e, out)
            return
        let n = e.second
        out.degree = spline_degree(e)
        for at in 0..<n:
            let point = sketch.spline_point(e, at)
            try out.push(sketch.x(point), sketch.y(point))
        try clamped_knots(n, out.degree, &out.knots)
    elif e.kind == EntityKind.ellipse:
        try ellipse_net(sketch, e, out)
    elif e.kind == EntityKind.conic:
        let rho = sketch.params.items[(usize)e.second]
        out.degree = 2
        try out.push(sketch.x(e.first), sketch.y(e.first))
        try out.push(sketch.x(e.fourth), sketch.y(e.fourth), rho / (1.0 - rho))
        try out.push(sketch.x(e.third), sketch.y(e.third))
        for k in [0.0, 0.0, 0.0, 1.0, 1.0, 1.0]: try out.knots.push(k)
    else:
        error(invalid, "only splines, ellipses and conics are nets")

## The curvature factor of a clamped uniform control point spline of `n`
## points and degree `p` at its ends: there its curvature is the factor
## times cross(P1 - P0, P2 - P1) / |P1 - P0|³ (its first span is 1 long,
## its second 2, or 1 when there is only one).
pub func end_curvature_factor(n: i64, p: i64) -> f64:
    if p < 2: return 0.0
    let second = 1.0 if n - p <= 1 else 2.0
    return ((f64)(p - 1) / (f64)p) / second

## Knots for `n` control points of degree `p`, clamped at both ends, the
## spans between them 1 apart.
func clamped_knots(n: i64, p: i64, out: Growing[f64]*) -> !:
    out.clear()
    for at in 0..<p + 1: try out.push(0.0)
    for at in 1..<n - p: try out.push((f64)at)
    for at in 0..<p + 1: try out.push((f64)(n - p))

## A fit point spline's net: degree p = min(degree, n - 1) through its n
## points, at their chord-length parameters, the knots averaged from them.
func fit_net(sketch: const Sketch*, e: SketchEntity, out: Net*) -> !:
    let n = (usize)e.second
    let p = (usize)spline_degree(e)
    out.degree = (i64)p
    var params = Growing[f64]()
    defer params.close()
    var total = 0.0
    try params.push(0.0)
    for at in 1..<n:
        let a = sketch.spline_point(e, (i64)at - 1)
        let b = sketch.spline_point(e, (i64)at)
        total += math.hypot(sketch.x(b) - sketch.x(a), sketch.y(b) - sketch.y(a))
        try params.push(total)
    for at in 0..<n: params.items[at] = params.items[at] / total if total > 0.0 else (f64)at / (f64)(n - 1)
    for at in 0..<p + 1: try out.knots.push(0.0)
    for j in 1..<n - p:
        var sum = 0.0
        for i in j..<j + p: sum += params.items[i]
        try out.knots.push(sum / (f64)p)
    for at in 0..<p + 1: try out.knots.push(1.0)
    # N(params) P = Q, solved for x and y together.
    let a = try new f64[n * n] --- in memory.heap
    defer free(a) in memory.heap
    let bx = try new f64[n] --- in memory.heap
    defer free(bx) in memory.heap
    let by = try new f64[n] --- in memory.heap
    defer free(by) in memory.heap
    for at in 0..<n * n: a[at] = 0.0
    var basis: f64[6] = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    for k in 0..<n:
        let u = params.items[k]
        let span = find_span(out.knots.view(), n, p, u)
        basis_at(out.knots.view(), span, u, p, basis[0..])
        for j in 0..<p + 1: a[k * n + span - p + j] = basis[j]
        let point = sketch.spline_point(e, (i64)k)
        bx[k] = sketch.x(point)
        by[k] = sketch.y(point)
    if not solve_two(a, n, bx, by): error(invalid, "a fit point spline's points cannot be passed through (two at one place?)")
    for at in 0..<n: try out.push(bx[at], by[at])

## An ellipse as three rational quadratic arcs of 120 degrees, a circle's
## (as curves.lucb's arcs) mapped onto it.
func ellipse_net(sketch: const Sketch*, e: SketchEntity, out: Net*) -> !:
    let cx = sketch.x(e.first)
    let cy = sketch.y(e.first)
    let dx = sketch.x(e.third) - cx
    let dy = sketch.y(e.third) - cy
    let a = math.max(math.hypot(dx, dy), 1e-300)
    let b = sketch.params.items[(usize)e.second]
    let ux = dx / a
    let uy = dy / a
    out.degree = 2
    let step = 2.0 * math.pi / 3.0
    let middle = 1.0 / math.cos(step * 0.5)
    for arc in 0..<(usize)3:
        let angle = step * (f64)arc
        for (reach, turn, weight) in [(1.0, 0.0, 1.0), (middle, step * 0.5, math.cos(step * 0.5))]:
            let ex = reach * math.cos(angle + turn) * a
            let ey = reach * math.sin(angle + turn) * b
            try out.push(cx + ex * ux - ey * uy, cy + ex * uy + ey * ux, weight)
    try out.push(cx + a * ux, cy + a * uy)
    for k in [0.0, 0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 3.0]: try out.knots.push(k)

## The knot span holding `u` for `n` control points of degree `p`.
func find_span(knots: const f64[], n: usize, p: usize, u: f64) -> usize:
    if u >= knots[n]: return n - 1
    var low = p
    var high = n
    while high - low > 1:
        let middle = (low + high) // 2
        if u < knots[middle]: high = middle
        else: low = middle
    return low

## The p + 1 basis functions not zero at `u` in span `span`, onto `out`
## (The NURBS Book, A2.2).
func basis_at(knots: const f64[], span: usize, u: f64, p: usize, out: f64[]):
    var left: f64[6] = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    var right: f64[6] = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    out[0] = 1.0
    for j in 1..<p + 1:
        left[j] = u - knots[span + 1 - j]
        right[j] = knots[span + j] - u
        var saved = 0.0
        for r in 0..<j:
            let denominator = right[r + 1] + left[j - r]
            let temporary = out[r] / denominator if denominator != 0.0 else 0.0
            out[r] = saved + right[r + 1] * temporary
            saved = left[j - r] * temporary
        out[j] = saved