Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / layout / edge_sampling.lucb

## Geometric edge counts and guarded physical-spacing selection.

## An edge's interval count: as few intervals as keep each one's turn
## within the step angle (a quarter turn over the steps) and its chord
## within the chord limit. A line needs one; a circle its sweep over the
## step. A B-spline is probed in every knot span (so a sample never skips
## a polynomial piece) and its count raised to what its worst interval
## needs, not doubled. Sharp knots cannot meet the angle under even
## spacing: past the cap the parameter spacing is tried as well.
## A piece shorter than this share of the tolerance has no direction to
## turn (its ends are one point to the model).
let direction_share: f64 = 0.001

pub func curve_intervals(edge: Curve, divisions: Density, tolerance: f64, metric: ArcMetric*) -> usize!:
    if edge.kind == curve_line: return 1
    if edge.kind == curve_circle:
        var steps = math.max(2.0, math.ceil((f64)(divisions.steps * 4) * math.abs(edge.sweep) / (2.0 * math.pi) - count_slack))
        # Within the chord limit too.
        if divisions.chord > 0.0 and divisions.chord < edge.radius: steps = math.max(steps, math.ceil(math.abs(edge.sweep) / (2.0 * math.acos(1.0 - divisions.chord / edge.radius))))
        return (usize)steps
    let most = (usize)(divisions.steps * 4)
    let spans = knot_spans(edge.knots, edge.degree) if edge.kind == curve_spline else (usize)1
    var count: usize = 1
    while true:
        let worst = try refinement(edge, metric, count, spans, divisions, tolerance)
        if worst <= 1.0: return count
        if count >= most:
            # Sharp knots cannot meet the angle under even spacing; never
            # turn that into an import failure or a runaway budget.
            if metric.uniform:
                metric.uniform = false
                let parameter_count = try curve_intervals(edge, divisions, tolerance, metric)
                # Keep even spacing when its error and turn are no worse
                # than the parameter spacing's at the same count.
                if parameter_count == count:
                    let original = try measure_error(edge, metric, count, tolerance)
                    metric.uniform = true
                    let even = try measure_error(edge, metric, count, tolerance)
                    metric.uniform = even.x <= original.x + 1e-12 and even.y <= original.y + 1e-8
                return parameter_count
            return count
        count = (usize)math.min((f64)most, math.max((f64)(count + 1), math.ceil((f64)count * worst)))

## How many times finer `edge`'s worst interval of `count` must be: each
## interval probed at 4 pieces per knot span it covers (at least 4), its
## turn (between any two pieces) against the step angle's share the pieces
## can show, and its sag against an arc's turning the step (turn_sag; it
## falls as the interval does) or the chord limit (as its square).
func refinement(edge: Curve, metric: ArcMetric*, count: usize, spans: usize, divisions: Density, tolerance: f64) -> f64!:
    let pieces = (usize)math.min(64.0, 4.0 * math.max(1.0, math.ceil((f64)spans / (f64)count)))
    let step = math.pi * 0.5 / (f64)divisions.steps
    let turn_limit = step * (f64)(pieces - 1) / (f64)pieces
    let chord = math.max(tolerance, divisions.within(flat_sag))
    let sag = turn_sag(divisions)
    let p = try new Vector3[pieces + 1] --- in memory.heap
    defer free(p) in memory.heap
    var worst = 0.0
    for interval in 0..<count:
        let ta = metric.station((f64)interval / (f64)count)
        let tb = metric.station((f64)(interval + 1) / (f64)count)
        for at in 0..<pieces + 1: p[at] = try edge.at(ta + (tb - ta) * (f64)at / (f64)pieces)
        let span = p[pieces].subtract(p[0])
        var along = 0.0
        for at in 0..<pieces: along += p[at + 1].subtract(p[at]).length()
        var deflection = 0.0
        for at in 1..<pieces:
            let t = math.clamp(p[at].subtract(p[0]).dot(span) / span.dot(span), 0.0, 1.0) if span.dot(span) > degenerate else 0.0
            deflection = math.max(deflection, p[at].subtract(p[0].add(span.multiply_scalar(t))).length())
        let turning = along * sag
        if deflection > math.max(chord, turning): worst = math.max(worst, math.min(deflection / turning, math.sqrt(deflection / chord)))
        for a in 0..<pieces:
            let da = p[a + 1].subtract(p[a])
            if not (da.length() > tolerance * direction_share): continue
            for b in a + 1..<pieces:
                let db = p[b + 1].subtract(p[b])
                if not (db.length() > tolerance * direction_share): continue
                let turn = math.acos(math.clamp(da.dot(db) / (da.length() * db.length()), -1.0, 1.0))
                if turn > turn_limit: worst = math.max(worst, turn / turn_limit)
    return worst

## How many knot spans of nonzero length a B-spline's domain has.
func knot_spans(knots: const f64[], degree: i64) -> usize:
    var spans: usize = 0
    let last = knots.length - (usize)degree - 1
    for at in (usize)degree..<last:
        if knots[at + 1] > knots[at]: spans += 1
    return spans

func measure_error(edge: Curve, metric: ArcMetric*, count: usize, tolerance: f64) -> Vector3!:
    var result = Vector3()
    for interval in 0..<count:
        var p = [Vector3(), Vector3(), Vector3(), Vector3(), Vector3()]
        let a = metric.station((f64)interval / (f64)count)
        let b = metric.station((f64)(interval + 1) / (f64)count)
        for at in 0..<(usize)5: p[at] = try edge.at(a + (b - a) * (f64)at / 4.0)
        let span = p[4].subtract(p[0])
        for at in 1..<(usize)4:
            let t = math.clamp(p[at].subtract(p[0]).dot(span) / span.dot(span), 0.0, 1.0) if span.dot(span) > degenerate else 0.0
            result.x = math.max(result.x, p[at].subtract(p[0].add(span.multiply_scalar(t))).length())
        for first in 0..<(usize)4:
            for second in first + 1..<(usize)4:
                let da = p[first + 1].subtract(p[first])
                let db = p[second + 1].subtract(p[second])
                if da.length() > tolerance * direction_share and db.length() > tolerance * direction_share:
                    result.y = math.max(result.y, 1.0 - da.dot(db) / (da.length() * db.length()))
    return result