dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / sketch / offset.lucb
## Offset: copies of a chain of curves a distance to one side, neighbors
## meeting again where their copies cross; and what it would make (its
## preview).
## Copies of the chain `curves` (end to end, in order; each curve may run
## either way) `distance` to the side of plane point (`qx`, `qy`), the side
## taken from the curve nearest it and kept along the chain's way, the
## neighbors' copies meeting again where they cross; the new curves onto
## `out`. Line copies stay parallel to theirs, `distance` away by a
## dimension (so the offset is a value to change); arc copies keep their
## center; a lone circle's copy is concentric, toward the point; a spline's,
## ellipse's or conic's copy is a fit point spline through its offset
## samples. With `relation`, the line, arc and circle copies are held by
## one Offset relation instead (ConstraintKind.offset): one distance for
## the chain, so changing it moves every copy, the corners following as
## the copies share their meeting points. Free-form copies stay as made.
pub func offset_chain(sketch: Sketch*, curves: const i64[], distance: f64, qx: f64, qy: f64, out: Growing[i64]*, relation: bool = false) -> !:
if curves.length == 0: error(invalid, "offset needs curves")
if not (distance > 0.0): error(invalid, "an offset needs a positive distance")
for c in curves:
if c < 0 or c >= (i64)sketch.entities.count or sketch.entity(c).kind == EntityKind.point or sketch.entity(c).kind == EntityKind.text:
error(invalid, "Offset copies curves (not points or text)")
let n = curves.length
# A lone circle: concentric, grown toward the point or shrunk.
if n == 1 and sketch.entity(curves[0]).kind == EntityKind.circle:
let e = sketch.entity(curves[0])
let r = sketch.radius_of(curves[0])
let nr = r + distance if math.hypot(qx - sketch.x(e.first), qy - sketch.y(e.first)) > r else r - distance
if nr <= 0.0: error(invalid, "the offset is larger than the circle's radius")
let made = try sketch.add_circle(e.first, nr, e.construction)
try out.push(made)
if relation: _ = try sketch.constrain(ConstraintKind.offset, curves[0], made, value = distance, side = 1.0 if nr > r else -1.0)
return
# Which way each curve runs along the chain, and the chain's side: +1
# its left as it goes.
var reversed = Growing[bool]()
defer reversed.close()
try orient(sketch, curves, &reversed)
let side = chain_side(sketch, curves, reversed.view(), qx, qy)
_ = try offset_side(sketch, curves, reversed.view(), distance, side, out, relation)
## Copies of the chain `curves` (each running as `reversed` says)
## `distance` to its `side` (+1 its left as it goes, -1 its right), as
## offset_chain makes them, onto `out`; the copy's first and last points
## (the same point when it closes).
func offset_side(sketch: Sketch*, curves: const i64[], reversed: const bool[], distance: f64, side: f64, out: Growing[i64]*, relation: bool) -> (i64, i64)!:
let n = curves.length
var carriers = Growing[Carrier]()
defer carriers.close()
var runs = Growing[f64]()
defer runs.close()
for at in 0..<n: try carriers.push(try offset_carrier(sketch, curves[at], distance, side * (-1.0 if reversed[at] else 1.0), reversed[at], &runs))
let single_loop = n == 1 and math.hypot(carriers.items[0].sx - carriers.items[0].ex, carriers.items[0].sy - carriers.items[0].ey) <= 1e-9 * math.max(1.0, size_of(sketch))
let closed = single_loop or (n > 1 and try chain_closed(sketch, curves, reversed))
# Where each copy starts and ends (in the chain's order): at its
# neighbors' meeting points.
var start_xy = Growing[f64]()
defer start_xy.close()
var end_xy = Growing[f64]()
defer end_xy.close()
for at in 0..<n:
let k = carriers.items[at]
try start_xy.push(k.sx)
try start_xy.push(k.sy)
try end_xy.push(k.ex)
try end_xy.push(k.ey)
for at in 0..<n:
if (at + 1 == n and not closed) or single_loop: break
let next = (at + 1) % n
let (x, y) = joint(&carriers.items[at], &carriers.items[next])
end_xy.items[at * 2] = x
end_xy.items[at * 2 + 1] = y
start_xy.items[next * 2] = x
start_xy.items[next * 2 + 1] = y
# Points, each joint once: a copy starts where the one before ends.
var start_points = Growing[i64]()
defer start_points.close()
var end_points = Growing[i64]()
defer end_points.close()
try start_points.push(try sketch.add_point(start_xy.items[0], start_xy.items[1]))
for at in 0..<n:
let last = at + 1 == n
let p = start_points.items[0] if last and closed else try sketch.add_point(end_xy.items[at * 2], end_xy.items[at * 2 + 1])
try end_points.push(p)
if not last: try start_points.push(p)
# The relation's first copy (its group), once made.
var group: i64 = -1
for at in 0..<n:
let c = curves[at]
let e = sketch.entity(c)
let k = carriers.items[at]
let first = start_points.items[at]
let last = end_points.items[at]
# The copy's side of its source: a line's as the source runs; an
# arc's radius grows by it.
let copy_side = side * (-1.0 if reversed[at] else 1.0)
if k.freeform:
# Through every fourth offset sample, from the copy's start to
# its end (in the chain's order).
var points = Growing[i64]()
defer points.close()
try points.push(first)
var sample: usize = 4
while sample + 1 < k.count:
let i = k.count - 1 - sample if reversed[at] else sample
try points.push(try sketch.add_point(runs.items[k.run + 2 * i], runs.items[k.run + 2 * i + 1]))
sample += 4
try points.push(last)
try out.push(try sketch.add_spline(points.view(), true, construction = e.construction))
elif k.line:
let made = try sketch.add_line(first, last, e.construction)
try out.push(made)
if relation:
group = try offset_held(sketch, group, c, made, copy_side, distance)
else:
_ = try sketch.constrain(ConstraintKind.parallel, c, made)
_ = try sketch.constrain(ConstraintKind.line_distance, first, c, value = distance, side = copy_side)
else:
# Counterclockwise from its own start: against the chain, from
# the copy's last point.
let made = try sketch.add_arc(e.first, last if reversed[at] else first, first if reversed[at] else last, e.construction)
sketch.params.items[(usize)sketch.entity(made).second] = k.r
try out.push(made)
if relation: group = try offset_held(sketch, group, c, made, -copy_side, distance)
return (start_points.items[0], end_points.items[n - 1])
## Copy `copy` of `source` held by the chain's Offset relation on side
## `side`: the relation itself when `group` is -1 (none yet), else a pair
## of it. The relation's group.
func offset_held(sketch: Sketch*, group: i64, source: i64, copy: i64, side: f64, distance: f64) -> i64!:
if group < 0:
_ = try sketch.constrain(ConstraintKind.offset, source, copy, value = distance, side = side)
return copy
try sketch.offset_pair(group, source, copy, side)
return group
## Whether each curve of the chain `curves` runs against it (its end
## where the chain comes in), onto `out`.
func orient(sketch: const Sketch*, curves: const i64[], out: Growing[bool]*) -> !:
out.clear()
let n = curves.length
for at in 0..<n:
let e = sketch.entity(curves[at])
let start = end_point(sketch, e, true)
let end = end_point(sketch, e, false)
var against = false
if start >= 0 and n > 1:
if at + 1 < n:
# Its start meets the next curve (and its end does not).
let next = sketch.entity(curves[at + 1])
against = meets(sketch, start, next) and not meets(sketch, end, next)
else:
# Its end meets the curve before (and its start does not).
let before = sketch.entity(curves[at - 1])
against = meets(sketch, end, before) and not meets(sketch, start, before)
try out.push(against)
## Whether point `point` is an end of curve `e` (the same point, or one at
## its place).
func meets(sketch: const Sketch*, point: i64, e: SketchEntity) -> bool:
let tolerance = 1e-9 * math.max(1.0, size_of(sketch))
for start in [true, false]:
let p = end_point(sketch, e, start)
if p < 0: continue
if p == point or math.hypot(sketch.x(p) - sketch.x(point), sketch.y(p) - sketch.y(point)) <= tolerance: return true
return false
## The chain's side (+1 its left as it goes, -1 its right) that plane
## point (`qx`, `qy`) is on, by the curve nearest it.
func chain_side(sketch: const Sketch*, curves: const i64[], reversed: const bool[], qx: f64, qy: f64) -> f64:
var closest: usize = 0
var best = math.infinity
for at in 0..<curves.length:
let d = distance_to(sketch, sketch.entity(curves[at]), curves[at], qx, qy)
if d < best:
best = d
closest = at
let e = sketch.entity(curves[closest])
let local = signed_side(sketch, curves[closest], qx, qy)
# An arc's signed side is outward, the right of its counterclockwise
# way; a line's and a free-form curve's is the left of its way.
let left = -local if e.kind == EntityKind.arc else local
let along = -left if reversed[closest] else left
return 1.0 if along >= 0.0 else -1.0
## What Offset would make: `curves` offset as offset_chain does, on a copy
## of `sketch`, as points along each new curve onto `out` (x, y pairs, a
## NaN pair after each curve).
pub func offset_preview(sketch: const Sketch*, curves: const i64[], distance: f64, qx: f64, qy: f64, out: Growing[f64]*) -> !:
out.clear()
var copy = try sketch.copy()
defer copy.close()
var made = Growing[i64]()
defer made.close()
try offset_chain(©, curves, distance, qx, qy, &made)
var points = Growing[f64]()
defer points.close()
for c in made.view():
try sample_curve(©, copy.entity(c), 48, &points)
for v in points.view(): try out.push(v)
try out.push(math.nan)
try out.push(math.nan)
## A curve's offset copy as a line or a circle (or, free-form, its offset
## samples in `runs`), with its ends.
struct Carrier:
var line: bool
var x: f64
var y: f64
var dx: f64
var dy: f64
var r: f64
var sx: f64
var sy: f64
var ex: f64
var ey: f64
var freeform: bool
var run: usize
var count: usize
## Curve `c` moved `distance` to its own left (`left` +1; -1 its right:
## a line's and a free-form curve's left as it runs, an arc's center side,
## its counterclockwise way's left), with its ends in the chain's order
## (swapped when it runs `reversed`).
func offset_carrier(sketch: const Sketch*, c: i64, distance: f64, left: f64, reversed: bool, runs: Growing[f64]*) -> Carrier!:
let e = sketch.entity(c)
var k = Carrier(false, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, false, 0, 0)
if e.kind == EntityKind.line:
let (ax, ay, dx, dy) = line_of(sketch, e)
let (ux, uy) = unit_vector(dx, dy)
let d = distance * left
k = Carrier(true, ax - uy * d, ay + ux * d, dx, dy, 0.0, ax - uy * d, ay + ux * d, ax + dx - uy * d, ay + dy + ux * d, false, 0, 0)
elif is_free_form(e.kind):
# Each sample moved along the curve's left normal.
var net = new_net()
defer net.close()
try net_of(sketch, e, &net)
var samples = Growing[f64]()
defer samples.close()
try net.sample(32, &samples)
let count = samples.count // 2
let run = runs.count
for i in 0..<count:
let a = i - 1 if i > 0 else i
let b = i + 1 if i + 1 < count else i
let (tx, ty) = unit_vector(samples.items[2 * b] - samples.items[2 * a], samples.items[2 * b + 1] - samples.items[2 * a + 1])
try runs.push(samples.items[2 * i] - ty * distance * left)
try runs.push(samples.items[2 * i + 1] + tx * distance * left)
k = Carrier(false, 0.0, 0.0, 0.0, 0.0, 0.0, runs.items[run], runs.items[run + 1], runs.items[run + 2 * count - 2], runs.items[run + 2 * count - 1], true, run, count)
else:
# An arc: its left, as it turns counterclockwise, is its center.
let cx = sketch.x(e.first)
let cy = sketch.y(e.first)
let r = sketch.radius_of(c)
let nr = r - distance * left
if nr <= 0.0: error(invalid, "the offset is larger than an arc's radius")
let (sx, sy) = scaled_from(sketch, e.first, e.third, nr / r)
let (tx, ty) = scaled_from(sketch, e.first, e.fourth, nr / r)
k = Carrier(false, cx, cy, 0.0, 0.0, nr, sx, sy, tx, ty, false, 0, 0)
if reversed:
let (sx, sy) = (k.sx, k.sy)
k.sx = k.ex
k.sy = k.ey
k.ex = sx
k.ey = sy
return k
## Where copies `a` (its end) and `b` (its start) meet: their carriers'
## crossing nearest the gap between them, or the gap's middle.
func joint(a: const Carrier*, b: const Carrier*) -> (f64, f64):
let gx = (a.ex + b.sx) * 0.5
let gy = (a.ey + b.sy) * 0.5
# A free-form copy meets its neighbor halfway between their ends.
if a.freeform or b.freeform: return (gx, gy)
var best_x = gx
var best_y = gy
var best = math.infinity
var hits: f64[4] = [0.0, 0.0, 0.0, 0.0]
var count: usize = 0
if a.line and b.line:
let d = a.dx * b.dy - a.dy * b.dx
if math.abs(d) > 1e-12 * math.hypot(a.dx, a.dy) * math.hypot(b.dx, b.dy):
let t = ((b.x - a.x) * b.dy - (b.y - a.y) * b.dx) / d
hits[0] = a.x + t * a.dx
hits[1] = a.y + t * a.dy
count = 1
elif a.line or b.line:
let line = a if a.line else b
let round = b if a.line else a
let l2 = line.dx * line.dx + line.dy * line.dy
let fx = line.x - round.x
let fy = line.y - round.y
let half_b = fx * line.dx + fy * line.dy
let disc = half_b * half_b - l2 * (fx * fx + fy * fy - round.r * round.r)
if disc >= 0.0:
let root = math.sqrt(disc)
for at in 0..<(usize)2:
let t = (-half_b + (root if at == 1 else -root)) / l2
hits[at * 2] = line.x + t * line.dx
hits[at * 2 + 1] = line.y + t * line.dy
count = 2
else:
let d = math.hypot(b.x - a.x, b.y - a.y)
if d > 0.0 and d <= a.r + b.r and d >= math.abs(a.r - b.r):
let along = (a.r * a.r - b.r * b.r + d * d) / (2.0 * d)
let h = math.sqrt(math.max(0.0, a.r * a.r - along * along))
let ux = (b.x - a.x) / d
let uy = (b.y - a.y) / d
for at in 0..<(usize)2:
let s = -1.0 if at == 0 else 1.0
hits[at * 2] = a.x + along * ux - s * h * uy
hits[at * 2 + 1] = a.y + along * uy + s * h * ux
count = 2
for at in 0..<count:
let dist = math.hypot(hits[at * 2] - gx, hits[at * 2 + 1] - gy)
if dist < best:
best = dist
best_x = hits[at * 2]
best_y = hits[at * 2 + 1]
return (best_x, best_y)
## Whether the chain `curves` (each running as `reversed` says) closes:
## its last curve ends where its first starts.
func chain_closed(sketch: const Sketch*, curves: const i64[], reversed: const bool[]) -> bool!:
let start = end_point(sketch, sketch.entity(curves[0]), not reversed[0])
let end = end_point(sketch, sketch.entity(curves[curves.length - 1]), reversed[curves.length - 1])
if start < 0 or end < 0: return false
return start == end or math.hypot(sketch.x(start) - sketch.x(end), sketch.y(start) - sketch.y(end)) <= 1e-9 * size_of(sketch)