Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / 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