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