dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / sketch / projection.lucb
## Fusion's Project: a body's edges cast straight onto the sketch's plane.
## A CadProjection holds every edge of a body as samples on the plane (the
## editor draws them and finds the one clicked); projecting one adds its
## shadow to the sketch as a line, circle or arc when it is one (to the
## sketch's precision), else a fit point spline through its samples, fixed
## and linked to the edge by its reference. relink_sketch casts each linked
## edge again from the body as it is now, so the projection follows changes
## upstream.
## Samples per projected edge (its ends among them).
let per_edge: usize = 33
## A body's edges on a sketch plane: `per_edge` x, y samples each, in the
## body's edge order, each edge's mean height off the plane (along its
## normal, u × v), the body (for the edges' references, faces and
## silhouettes) and the plane (`origin`, `u`, `v`).
pub struct CadProjection:
var samples: Growing[f64]
var heights: Growing[f64]
var model: interop.Reference[CadModel]
var origin: Vector3
var u: Vector3
var v: Vector3
pub func close():
self.samples.close()
self.heights.close()
self.model.release()
func trace(visit: func(ownership.Object*, void*) -> unit, context: void*):
_ = visit
_ = context
## `model`'s edges cast onto the plane through `origin` whose x and y
## run along `u` and `v`.
pub static func of(model: interop.Reference[CadModel], origin: Vector3, u: Vector3, v: Vector3) -> interop.Reference[CadProjection]!:
var samples = Growing[f64]()
errdefer samples.close()
var heights = Growing[f64]()
errdefer heights.close()
var w = try shape_of(model.value())
defer w.close()
let n = u.cross(v)
for e in 0..<w.edges.count:
try cast_edge(&w, e, origin, u, v, &samples)
var height = 0.0
for k in 0..<per_edge:
height += (try w.edge_at(e, (f64)k / (f64)(per_edge - 1))).subtract(origin).dot(n)
try heights.push(height / (f64)per_edge)
return try interop.Reference[CadProjection].adopt(new CadProjection(samples, heights, model.clone(), origin, u, v) in memory.heap, cad_projection_type, memory.heap)
pub func edge_count() -> i64:
return (i64)(self.samples.count // (2 * per_edge))
## The edge whose shadow passes nearest (`x`, `y`), within `reach`, or -1.
pub func nearest(x: f64, y: f64, reach: f64) -> i64:
var best: i64 = -1
var best_distance = reach
for e in 0..<self.samples.count // (2 * per_edge):
let run = self.samples.view()[e * 2 * per_edge..<(e + 1) * 2 * per_edge]
if end_on(run, 1e-9 * math.max(1.0, reach)): continue
for k in 0..<per_edge - 1:
let d = segment_distance(x, y, run[2 * k], run[2 * k + 1], run[2 * k + 2], run[2 * k + 3])
if d <= best_distance:
best_distance = d
best = (i64)e
return best
## Edge `edge`'s reference (modeling's names).
pub func reference(edge: i64) -> interop.Owned[str]!:
var w = try shape_of(self.model.value())
defer w.close()
var text = Growing[u8]()
defer text.close()
try references_of(&w, [edge], &text)
return try interop.copy_text((str)text.view())
pub let cad_projection_type: interop.Type[CadProjection] = interop.Type[CadProjection]("CadProjection", CadProjection.close, CadProjection.trace, closeable = true)
## The samples of a projection (x, y pairs, `per_edge` an edge), for the
## editor's drawing.
pub func projection_samples(p: const CadProjection*) -> const f64[]:
return p.samples.view()
pub func projection_per_edge() -> usize:
return per_edge
## Edge `e` of `w` sampled and cast onto the plane, onto `out` (unfolded).
func cast_edge(w: const Shape*, e: usize, origin: Vector3, u: Vector3, v: Vector3, out: Growing[f64]*) -> !:
let at = out.count
for k in 0..<per_edge:
let p = try w.edge_at(e, (f64)k / (f64)(per_edge - 1))
let d = p.subtract(origin)
try out.push(d.dot(u))
try out.push(d.dot(v))
unfold(out.items[at..<out.count])
## The silhouette `reference` names on `model` (its shape `w`) cast onto
## the plane through `origin` (axes `u`, `v`), onto `out`.
func cast_silhouette(w: const Shape*, model: const CadModel*, reference: str, origin: Vector3, u: Vector3, v: Vector3, out: Growing[f64]*) -> !:
let mesh = try model.tessellate(silhouette_divisions)
defer mesh.release()
var points = Growing[Vector3]()
defer points.close()
try resolve_silhouette(w, mesh.value(), reference, u.cross(v), per_edge, &points)
for q in points.view():
let d = q.subtract(origin)
try out.push(d.dot(u))
try out.push(d.dot(v))
## A run whose samples all lie on one line but turn back along it (a
## circle or an arc past half a turn seen edge-on) made the segment it
## covers: its samples evenly from the extreme nearer its start to the
## other, so it casts a line (Fusion's: a rim seen from the side is a
## line).
func unfold(run: f64[]):
let n = run.length // 2
# The two samples farthest apart.
var a: usize = 0
var b: usize = 0
var most = 0.0
for i in 0..<n:
let d = math.hypot(run[2 * i] - run[0], run[2 * i + 1] - run[1])
if d > most:
most = d
a = i
most = 0.0
for i in 0..<n:
let d = math.hypot(run[2 * i] - run[2 * a], run[2 * i + 1] - run[2 * a + 1])
if d > most:
most = d
b = i
if most <= 0.0: return
let tolerance = most * 1e-9
let dx = (run[2 * b] - run[2 * a]) / most
let dy = (run[2 * b + 1] - run[2 * a + 1]) / most
var previous = -1.0
var monotone = true
var sense = 0.0
for i in 0..<n:
let x = run[2 * i] - run[2 * a]
let y = run[2 * i + 1] - run[2 * a + 1]
if math.abs(x * dy - y * dx) > tolerance: return
let along = x * dx + y * dy
if i > 0:
let step = along - previous
if math.abs(step) > tolerance:
if sense == 0.0: sense = step
elif step * sense < 0.0: monotone = false
previous = along
if monotone: return
# From the extreme nearer the run's start.
let first = a if math.hypot(run[2 * a] - run[0], run[2 * a + 1] - run[1]) <= math.hypot(run[2 * b] - run[0], run[2 * b + 1] - run[1]) else b
let last = b if first == a else a
let (sx, sy, ex, ey) = (run[2 * first], run[2 * first + 1], run[2 * last], run[2 * last + 1])
for i in 0..<n:
let f = (f64)i / (f64)(n - 1)
run[2 * i] = sx + (ex - sx) * f
run[2 * i + 1] = sy + (ey - sy) * f
## Add the shadow of the edge whose samples are `run` to `sketch`, fixed
## and linked to `reference`; the curve made.
pub func add_shadow(sketch: Sketch*, run: const f64[], reference: str) -> i64!:
let tolerance = 1e-6 * math.max(1.0, size_of(sketch))
if end_on(run, tolerance): error(invalid, "this edge runs straight at the sketch's plane: it casts only a point")
let n = run.length // 2
var made: i64 = -1
let kind = shadow_kind(run, tolerance)
if kind == EntityKind.line:
made = try sketch.add_line(try sketch.add_point(run[0], run[1]), try sketch.add_point(run[2 * n - 2], run[2 * n - 1]))
elif kind == EntityKind.circle:
let circle = circle_through(run, tolerance) else error(invalid, "a circular shadow has no circle")
made = try sketch.add_circle(try sketch.add_point(circle[0], circle[1]), circle[2])
elif kind == EntityKind.arc:
# Counterclockwise from whichever end the samples turn away from.
let circle = circle_through(run, tolerance) else error(invalid, "a circular shadow has no circle")
let center = try sketch.add_point(circle[0], circle[1])
let a = try sketch.add_point(run[0], run[1])
let b = try sketch.add_point(run[2 * n - 2], run[2 * n - 1])
let turning = (run[2] - run[0]) * (run[1] - circle[1]) - (run[3] - run[1]) * (run[0] - circle[0])
made = try sketch.add_arc(center, b if turning > 0.0 else a, a if turning > 0.0 else b)
else:
# A fit point spline through every fourth sample (and its end).
var points = Growing[i64]()
defer points.close()
let loop = run_closed(run, tolerance)
var k: usize = 0
while k < n:
if not (loop and k == n - 1): try points.push(try sketch.add_point(run[2 * k], run[2 * k + 1]))
k = k + 4 if k + 4 < n or k == n - 1 else n - 1
if loop: try points.push(points.items[0])
made = try sketch.add_spline(points.view(), true)
_ = try sketch.constrain(ConstraintKind.fix, made)
try sketch.link(made, reference)
return made
## What a shadow of samples `run` is: a line when straight, a circle
## when closed on one, an arc when open on one, else a spline.
func shadow_kind(run: const f64[], tolerance: f64) -> EntityKind:
let loop = run_closed(run, tolerance)
if not loop and straight(run, tolerance): return EntityKind.line
if let circle = circle_through(run, tolerance):
_ = circle
return EntityKind.circle if loop else EntityKind.arc
return EntityKind.spline
## Whether the samples end where they start.
func run_closed(run: const f64[], tolerance: f64) -> bool:
let n = run.length // 2
return math.hypot(run[0] - run[2 * n - 2], run[1] - run[2 * n - 1]) <= tolerance
## Whether every sample is at the first's place (an edge seen end-on).
func end_on(run: const f64[], tolerance: f64) -> bool:
for k in 1..<run.length // 2:
if math.hypot(run[2 * k] - run[0], run[2 * k + 1] - run[1]) > tolerance: return false
return true
## Whether the samples lie on their chord.
func straight(run: const f64[], tolerance: f64) -> bool:
let n = run.length // 2
let dx = run[2 * n - 2] - run[0]
let dy = run[2 * n - 1] - run[1]
let length = math.hypot(dx, dy)
if length <= tolerance: return false
for k in 1..<n - 1:
if math.abs(dx * (run[2 * k + 1] - run[1]) - dy * (run[2 * k] - run[0])) / length > tolerance: return false
return true
## The circle the samples lie on, [x, y, r], or none when they do not.
func circle_through(run: const f64[], tolerance: f64) -> f64[3]?:
let n = run.length // 2
let m = n // 3
let q = (2 * n) // 3
let (ax, ay, bx, by, cx, cy) = (run[0], run[1], run[2 * m], run[2 * m + 1], run[2 * q], run[2 * q + 1])
let d = 2.0 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
if math.abs(d) <= 1e-12: return none
let a2 = ax * ax + ay * ay
let b2 = bx * bx + by * by
let c2 = cx * cx + cy * cy
let ox = (a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)) / d
let oy = (a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)) / d
let r = math.hypot(ax - ox, ay - oy)
for k in 0..<n:
if math.abs(math.hypot(run[2 * k] - ox, run[2 * k + 1] - oy) - r) > tolerance: return none
return [ox, oy, r]
## Cast every linked edge of `sketch` again from `model` onto the plane
## through `origin` (axes `u`, `v`): each shadow's points and radius follow
## its edge (a split edge: its piece nearest where it was), a linked point
## the edge's end nearest it. Edges the projected
## faces' loops gained get shadows of their own. How many links no longer
## find their edge, or find it another kind of curve now (they stay as
## they were; their curves onto `lost_out`), and how many edges were
## gained.
pub func relink_sketch(sketch: Sketch*, model: const CadModel*, origin: Vector3, u: Vector3, v: Vector3, lost_out: Growing[i64]*? = none) -> (i64, i64)!:
if let out = lost_out: out.clear()
if sketch.links.count == 0 and sketch.faces.count == 0: return (0, 0)
var w = try shape_of(model)
defer w.close()
var edges = Growing[usize]()
defer edges.close()
var runs = Growing[f64]()
defer runs.close()
# The curves that follow, each with where its samples start in `runs`.
var plan = Growing[(i64, usize)]()
defer plan.close()
var followed = Growing[bool]()
defer followed.close()
try followed.fill(w.edges.count, false)
let tolerance = 1e-6 * math.max(1.0, size_of(sketch))
var lost: i64 = 0
for l in sketch.links.view():
# A silhouette: its face's again, nearest where it was.
if is_silhouette(sketch.link_reference(l)):
let at = runs.count
cast_silhouette(&w, model, sketch.link_reference(l), origin, u, v, &runs) catch failure:
lost += 1
if let out = lost_out: try out.push(l.entity)
runs.count = at
continue
let run = runs.view()[at..<runs.count]
if end_on(run, tolerance) or shadow_kind(run, tolerance) != sketch.entity(l.entity).kind:
lost += 1
if let out = lost_out: try out.push(l.entity)
runs.count = at
continue
try plan.push((l.entity, at))
continue
resolve_edges(&w, sketch.link_reference(l), &edges) catch failure:
lost += 1
if let out = lost_out: try out.push(l.entity)
continue
# An edge split upstream follows its piece nearest where it was
# (resolve_edges gives that first); the other pieces are gained.
let e = edges.items[0]
let at = runs.count
try cast_edge(&w, e, origin, u, v, &runs)
let run = runs.view()[at..<runs.count]
let kind = sketch.entity(l.entity).kind
if kind != EntityKind.point and (end_on(run, tolerance) or shadow_kind(run, tolerance) != kind):
lost += 1
if let out = lost_out: try out.push(l.entity)
runs.count = at
continue
followed.items[e] = true
try plan.push((l.entity, at))
try follow_all(sketch, plan.view(), runs.view(), tolerance)
let gained = try add_gained_edges(sketch, &w, followed.view(), origin, u, v)
return (lost, gained)
## Every planned curve (entity, where its edge's samples start in `runs`)
## moved onto its edge now. Ends first, from where the curves are now: a
## point several curves share goes where the first puts it, and a curve
## that would put it elsewhere (its edge was split, or the loop changed)
## gets a point of its own there. Then centers, radii and a spline's
## inner points.
func follow_all(sketch: Sketch*, plan: const (i64, usize)[], runs: const f64[], tolerance: f64) -> !:
let per = per_edge * 2
# Each curve's end targets, from the points as they are before any
# moves (the way a curve runs is judged from them).
var targets = Growing[EndTarget]()
defer targets.close()
for (curve, at) in plan:
try end_targets(sketch, curve, runs[at..<at + per], &targets)
# Where each point goes, and the curve that put it there.
var owner = Growing[i64]()
defer owner.close()
try owner.fill(sketch.entities.count, -1)
var place = Growing[f64]()
defer place.close()
try place.fill(sketch.entities.count * 2, 0.0)
for target in targets.view():
let p = (usize)target.point
if p < owner.count and owner.items[p] >= 0 and owner.items[p] != target.curve and math.hypot(place.items[2 * p] - target.x, place.items[2 * p + 1] - target.y) > tolerance:
# Taken elsewhere: this curve's own point.
let own = try sketch.add_point(target.x, target.y)
rewire(sketch, target.curve, target.point, own)
continue
owner.items[p] = target.curve
place.items[2 * p] = target.x
place.items[2 * p + 1] = target.y
for p in 0..<owner.count:
if owner.items[p] >= 0: sketch.place((i64)p, place.items[2 * p], place.items[2 * p + 1])
for (curve, at) in plan:
try follow_inside(sketch, curve, runs[at..<at + per])
## Where one end of a following curve goes: point `point` of curve `curve`.
struct EndTarget:
var curve: i64
var point: i64
var x: f64
var y: f64
## Curve `curve`'s ends onto the ends of its edge's samples `run`, as
## targets onto `out`: a line's and a spline's by the way it runs, an
## arc's counterclockwise; a linked point to the nearer end.
func end_targets(sketch: const Sketch*, curve: i64, run: const f64[], out: Growing[EndTarget]*) -> !:
let e = sketch.entity(curve)
let n = run.length // 2
let (sx, sy, ex, ey) = (run[0], run[1], run[2 * n - 2], run[2 * n - 1])
if e.kind == EntityKind.point:
let to_start = math.hypot(sx - sketch.x(curve), sy - sketch.y(curve))
let to_end = math.hypot(ex - sketch.x(curve), ey - sketch.y(curve))
try out.push(EndTarget(curve, curve, sx if to_start <= to_end else ex, sy if to_start <= to_end else ey))
return
var first: i64 = -1
var last: i64 = -1
var against = false
if e.kind == EntityKind.line:
first = e.first
last = e.second
against = runs_against(sketch, first, last, run)
elif e.kind == EntityKind.arc:
let circle = circle_through(run, 1e300) else return
first = e.third
last = e.fourth
# Counterclockwise: from the samples' end when they turn clockwise.
against = (run[2] - run[0]) * (run[1] - circle[1]) - (run[3] - run[1]) * (run[0] - circle[0]) > 0.0
elif e.kind == EntityKind.spline:
first = sketch.spline_point(e, 0)
last = sketch.spline_point(e, e.second - 1)
against = runs_against(sketch, first, last, run)
else:
return
try out.push(EndTarget(curve, first, ex if against else sx, ey if against else sy))
if last != first: try out.push(EndTarget(curve, last, sx if against else ex, sy if against else ey))
## Curve `curve` drawn on point `after` where it was on point `before`.
func rewire(sketch: Sketch*, curve: i64, before: i64, after: i64):
let e = &sketch.entities.items[(usize)curve]
if e.kind == EntityKind.line:
if e.first == before: e.first = after
if e.second == before: e.second = after
elif e.kind == EntityKind.arc:
if e.third == before: e.third = after
if e.fourth == before: e.fourth = after
elif e.kind == EntityKind.spline:
for k in 0..<e.second:
let at = (usize)(e.first + k)
if sketch.lists.items[at] == before: sketch.lists.items[at] = after
## What follows a curve's ends onto its edge's samples `run`: a circle's
## or arc's center and radius, a spline's inner points over the samples
## evenly (its ends are placed).
func follow_inside(sketch: Sketch*, curve: i64, run: const f64[]) -> !:
let e = sketch.entity(curve)
let n = run.length // 2
if e.kind == EntityKind.circle or e.kind == EntityKind.arc:
let circle = circle_through(run, 1e300) else return
sketch.place(e.first, circle[0], circle[1])
sketch.params.items[(usize)e.second] = circle[2]
elif e.kind == EntityKind.spline:
let count = (usize)e.second
let first = sketch.spline_point(e, 0)
let last = sketch.spline_point(e, (i64)count - 1)
# Its ends are placed: the way it runs is the way they lie now.
let against = first != last and math.hypot(sketch.x(first) - run[2 * n - 2], sketch.y(first) - run[2 * n - 1]) < math.hypot(sketch.x(first) - run[0], sketch.y(first) - run[1])
for k in 1..<count - 1:
let sample = (k * (n - 1)) // (count - 1)
let point = sketch.spline_point(e, (i64)(count - 1 - k) if against else (i64)k)
sketch.place(point, run[2 * sample], run[2 * sample + 1])
## A fixed point at end `end` (0 its start, 1 its end) of the edge whose
## samples are `run`, linked to `reference`: a body vertex in the sketch.
pub func add_end_point(sketch: Sketch*, run: const f64[], end: i64, reference: str) -> i64!:
let n = run.length // 2
let k = 0 if end == 0 else n - 1
let p = try sketch.add_point(run[2 * k], run[2 * k + 1])
_ = try sketch.constrain(ConstraintKind.fix, p)
try sketch.link(p, reference)
return p
## Whether the curve from point `first` to point `last` runs against its
## edge's samples `run` (the edge may run either way, and a projected
## loop's curves run as the loop does).
func runs_against(sketch: const Sketch*, first: i64, last: i64, run: const f64[]) -> bool:
let n = run.length // 2
let dx = sketch.x(last) - sketch.x(first)
let dy = sketch.y(last) - sketch.y(first)
if dx * dx + dy * dy == 0.0:
# Closed: by the way it leaves its start.
return false
return dx * (run[2 * n - 2] - run[0]) + dy * (run[2 * n - 1] - run[1]) < 0.0