Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / modeling / arrangement.lucb

## A sketch's curves as Fusion 360 reads them for profiles: every piece
## split where it meets another (crossing, touching, or a curve's end on
## it), the pieces joined at shared points into a planar graph, dangling
## pieces dropped, and the graph's faces traced: each bounded face is a
## profile. Which faces a feature takes (`chosen`, by key) or, given none,
## islands alternating from the outside in (a plate's hole stays empty,
## overlapping shapes join), and their outline traced together, so faces
## next to each other become one region. Loops leave as profile.lucb's:
## outer loops counterclockwise about the plane's normal, holes clockwise.
##
## A face's key names it by what bounds it: the sorted sketch curves of its
## loops, each with the side it runs (+ along the curve, - against), so it
## stays the same face when dimensions move things (two crescents of
## overlapping circles differ by which circle each runs along).

## Arrange `pieces` (on `result`'s plane) and write the regions of the faces
## `chosen` names (keys apart by `;`; empty: alternating islands) into
## `result`'s loops and regions.
func arrange(result: Profiles*, pieces: const Growing[ProfileEdge]*, chosen: str, tolerance: f64) -> !:
    var a = try arranged(result, pieces, tolerance)
    defer a.close()
    let count = a.areas.count
    var take = Growing[bool]()
    defer take.close()
    try take.fill(count, false)
    if trimmed(chosen) == "":
        try alternate_islands(&a, &take)
    else:
        for f in 0..<count:
            if a.areas.items[f] <= 0.0: continue
            var key = Growing[u8]()
            defer key.close()
            try face_key(&a.subs, &a.halves, a.loop(f), &key)
            take.items[f] = key_listed(chosen, (str)key.view())
    # A piece's outside (a clockwise face) belongs to the face around it:
    # the smallest bounded face holding a point just outside it.
    for f in 0..<count:
        if a.areas.items[f] > 0.0: continue
        let owner = a.holding(a.left_point(f), (i64)f)
        take.items[f] = owner >= 0 and take.items[(usize)owner]
    try chosen_regions(result, &a.subs, &a.halves, a.vertex_count, &take, tolerance)

## A sketch's arrangement: its sub-edges, half-edges and faces, each face's
## signed area (positive: bounded) and outline in plane coordinates.
struct Arranged:
    var subs: Growing[ProfileEdge]
    var halves: Growing[SketchHalf]
    var vertex_count: usize
    var faces: Growing[usize]
    var face_offsets: Growing[usize]
    var areas: Growing[f64]
    var outlines: Growing[Vector3]
    var outline_offsets: Growing[usize]
    ## Per face: the connected piece of the graph it belongs to (faces of
    ## one piece never hold each other).
    var pieces_of: Growing[usize]

    func close():
        self.subs.close()
        self.halves.close()
        self.faces.close()
        self.face_offsets.close()
        self.areas.close()
        self.outlines.close()
        self.outline_offsets.close()
        self.pieces_of.close()

    ## Face `f`'s half-edges, in order round it.
    func loop(f: usize) -> const usize[]:
        return self.faces.view()[self.face_offsets.items[f]..<self.face_offsets.items[f + 1]]

    func outline_of(f: usize) -> const Vector3[]:
        return self.outlines.view()[self.outline_offsets.items[f]..<self.outline_offsets.items[f + 1]]

    ## A point just left of face `f`'s first edge (inside a bounded face,
    ## outside a piece's outer face).
    func left_point(f: usize) -> Vector3:
        return left_of_start(self.outline_of(f))

    ## The smallest bounded face holding plane point `p`, or -1; with
    ## `apart`, only faces of other pieces than face `apart`'s.
    func holding(p: Vector3, apart: i64 = -1) -> i64:
        var owner: i64 = -1
        for other in 0..<self.areas.count:
            if apart >= 0 and self.pieces_of.items[other] == self.pieces_of.items[(usize)apart]: continue
            if self.areas.items[other] <= 0.0 or not inside(self.outline_of(other), p): continue
            if owner < 0 or self.areas.items[other] < self.areas.items[(usize)owner]: owner = (i64)other
        return owner

## The arrangement of `pieces` on `result`'s plane.
func arranged(result: Profiles*, pieces: const Growing[ProfileEdge]*, tolerance: f64) -> Arranged!:
    var a = Arranged(Growing[ProfileEdge](), Growing[SketchHalf](), 0, Growing[usize](), Growing[usize](), Growing[f64](), Growing[Vector3](), Growing[usize](), Growing[usize]())
    errdefer a.close()
    try split_pieces(result, pieces, tolerance, &a.subs)
    var vertices = Growing[Vector3]()
    defer vertices.close()
    try build_graph(result, &a.subs, tolerance, &vertices, &a.halves)
    a.vertex_count = vertices.count
    try trace_faces(&a.halves, vertices.count, &a.faces, &a.face_offsets)
    var outline = Growing[Vector3]()
    defer outline.close()
    try a.outline_offsets.push(0)
    for f in 0..<a.face_offsets.count - 1:
        try face_outline(result, &a.subs, &a.halves, a.loop(f), &outline)
        try a.areas.push(signed_area(outline.view()))
        for p in outline.view(): try a.outlines.push(p)
        try a.outline_offsets.push(a.outlines.count)
    # Pieces: vertices joined by live edges.
    var parent = Growing[usize]()
    defer parent.close()
    for v in 0..<vertices.count: try parent.push(v)
    for h in a.halves.view():
        if not h.alive: continue
        let x = union_root(parent.items, h.tail)
        let y = union_root(parent.items, h.head)
        if x != y: parent.items[x] = y
    for f in 0..<a.face_offsets.count - 1:
        try a.pieces_of.push(union_root(parent.items, a.halves.items[a.loop(f)[0]].tail))
    return a

## The outlines of `set`'s faces named by `keys` (apart by `;`), as closed
## polylines on the sketch plane (arcs and splines sampled): what a viewport
## draws to show chosen or hovered profiles.
func face_outlines(set: const GeometrySet*, tolerance: f64, keys: str, out: CurvesBuilder*) -> !:
    var result = try empty_profiles(set)
    defer result.close()
    var pieces = Growing[ProfileEdge]()
    defer pieces.close()
    try read_pieces(set, &result, &pieces, tolerance)
    var a = try arranged(&result, &pieces, tolerance)
    defer a.close()
    for f in 0..<a.areas.count:
        if a.areas.items[f] <= 0.0: continue
        var key = Growing[u8]()
        defer key.close()
        try face_key(&a.subs, &a.halves, a.loop(f), &key)
        if not key_listed(keys, (str)key.view()): continue
        try out.begin(CurveType.poly, true)
        for p in a.outline_of(f):
            try out.point(result.origin.add(result.u.multiply_scalar(p.x)).add(result.v.multiply_scalar(p.y)))

## The keys of `set`'s profiles (its arrangement's bounded faces) apart by
## `;` onto `out`; with `probe`, only the face holding plane point `at`.
func face_keys(set: const GeometrySet*, tolerance: f64, probe: bool, at: Vector3, out: Growing[u8]*) -> !:
    var result = try empty_profiles(set)
    defer result.close()
    var pieces = Growing[ProfileEdge]()
    defer pieces.close()
    try read_pieces(set, &result, &pieces, tolerance)
    var a = try arranged(&result, &pieces, tolerance)
    defer a.close()
    let (x, y) = result.planar(at)
    let target = a.holding(Vector3(x, y, 0.0)) if probe else -1
    for f in 0..<a.areas.count:
        if a.areas.items[f] <= 0.0 or (probe and (i64)f != target): continue
        if out.count > 0: try out.push(59)
        try face_key(&a.subs, &a.halves, a.loop(f), out)

## The faces taken by default: bounded faces of islands alternating from
## the outside in (a face's depth: how many bounded faces of other pieces
## hold it).
func alternate_islands(a: const Arranged*, take: Growing[bool]*) -> !:
    let count = a.areas.count
    for f in 0..<count:
        if a.areas.items[f] <= 0.0: continue
        let probe = a.left_point(f)
        var depth = 0
        for other in 0..<count:
            if a.areas.items[other] <= 0.0 or a.pieces_of.items[other] == a.pieces_of.items[f]: continue
            if inside(a.outline_of(other), probe): depth += 1
        take.items[f] = depth % 2 == 0

## A point just left of an outline's first segment's middle: inside a
## counterclockwise outline, outside a clockwise one.
func left_of_start(points: const Vector3[]) -> Vector3:
    let a = points[0]
    let b = points[1 % points.length]
    let dx = b.x - a.x
    let dy = b.y - a.y
    let l = math.max(math.hypot(dx, dy), 1e-300)
    let reach = l * 1e-3
    return Vector3((a.x + b.x) * 0.5 - dy / l * reach, (a.y + b.y) * 0.5 + dx / l * reach, 0.0)

## Face key: its half-edges' sketch curves and the way each is run.
func face_key(subs: Growing[ProfileEdge]*, halves: Growing[SketchHalf]*, loop: const usize[], out: Growing[u8]*) -> !:
    var parts = Growing[i64]()
    defer parts.close()
    for at in loop:
        let h = halves.items[at]
        let e = subs.items[h.edge]
        let code = e.curve * 2 + (1 if h.backward else 0)
        var seen = false
        for p in parts.view():
            if p == code: seen = true
        if not seen: try parts.push(code)
    sort.sort(parts.items[..<parts.count])
    for index in 0..<parts.count:
        if index > 0: try out.push(44)
        try push_decimal(out, parts.items[index] // 2)
        try out.push(45 if parts.items[index] % 2 == 1 else 43)

## Whether `key` is one of `keys` (apart by `;`).
func key_listed(keys: str, key: str) -> bool:
    var start: usize = 0
    let bytes = keys.bytes
    while start <= bytes.length:
        var end = start
        while end < bytes.length and bytes[end] != 59: end += 1
        if trimmed((str)bytes[start..<end]) == key: return true
        start = end + 1
    return false

## The outline of the taken faces together: the half-edges with a taken
## face on their left and none on their right, traced into loops (around
## each vertex, the next such edge clockwise), then nested into regions
## (counterclockwise loops outer, clockwise ones holes of the smallest
## outer loop holding them).
func chosen_regions(result: Profiles*, subs: Growing[ProfileEdge]*, halves: Growing[SketchHalf]*, vertex_count: usize, take: const Growing[bool]*, tolerance: f64) -> !:
    # Boundary half-edges stay alive; the rest leave the tracing (decided
    # for all before any face is cleared).
    var boundary = Growing[bool]()
    defer boundary.close()
    for at in 0..<halves.count:
        let h = halves.items[at]
        let twin = halves.items[twin_of(at)]
        let left = h.alive and h.face >= 0 and take.items[(usize)h.face]
        let right = twin.alive and twin.face >= 0 and take.items[(usize)twin.face]
        try boundary.push(left and not right)
    for at in 0..<halves.count:
        halves.items[at].alive = boundary.items[at]
        halves.items[at].face = -1
    try result.loop_offsets.push(0)
    for start in 0..<halves.count:
        if not halves.items[start].alive or halves.items[start].face >= 0: continue
        var at = start
        var guard: usize = 0
        while halves.items[at].face < 0:
            halves.items[at].face = 0
            let h = halves.items[at]
            var e = subs.items[h.edge]
            try result.edges.push(e)
            if h.backward: try result.reverse_edge(result.edges.count - 1)
            at = next_boundary(halves, at)
            guard += 1
            if guard > halves.count: error(invalid, "a sketch's profile could not be traced")
        let first = result.loop_offsets.items[result.loop_offsets.count - 1]
        try join_parts(result, first, tolerance)
        # Ends that met within tolerance meet exactly.
        let last = result.edges.count - 1
        for index in first..<last:
            result.edges.items[index + 1].start = result.edges.items[index].end
        result.edges.items[first].start = result.edges.items[last].end
        try result.loop_offsets.push(result.edges.count)
    _ = vertex_count
    _ = tolerance
    try nest_oriented(result)

## Loop edges from `first` on: neighbors that are parts of one sketch curve
## going on the same way (a line straight on, an arc round the same circle)
## joined into one, the loop's last and first included.
func join_parts(result: Profiles*, first: usize, tolerance: f64) -> !:
    var at = first
    while at + 1 < result.edges.count:
        if continues(&result.edges.items[at], &result.edges.items[at + 1], tolerance):
            result.edges.items[at].end = result.edges.items[at + 1].end
            result.edges.items[at].sweep += result.edges.items[at + 1].sweep
            for move in at + 1..<result.edges.count - 1:
                result.edges.items[move] = result.edges.items[move + 1]
            result.edges.count -= 1
        else:
            at += 1
    # Round the loop's seam: the last edge going on into the first.
    let last = result.edges.count - 1
    if last > first and continues(&result.edges.items[last], &result.edges.items[first], tolerance):
        var joined = result.edges.items[last]
        joined.end = result.edges.items[first].end
        joined.sweep += result.edges.items[first].sweep
        result.edges.items[first] = joined
        result.edges.count -= 1

## Whether `b` goes on from `a` as one curve: the same sketch curve, both
## lines in line, or both arcs of one circle turning one way.
func continues(a: const ProfileEdge*, b: const ProfileEdge*, tolerance: f64) -> bool:
    if a.curve < 0 or a.curve != b.curve or a.kind != b.kind or a.kind == profile_spline: return false
    if a.kind == profile_line:
        let d1 = a.end.subtract(a.start)
        let d2 = b.end.subtract(b.start)
        return d1.cross(d2).length() <= tolerance * math.max(d1.length(), d2.length()) and d1.dot(d2) > 0.0
    return a.center.subtract(b.center).length() <= tolerance and math.abs(a.radius - b.radius) <= tolerance and (a.sweep > 0.0) == (b.sweep > 0.0)

## The next boundary half-edge after `at`: at its head, the alive one
## leaving most clockwise from the way back.
func next_boundary(halves: Growing[SketchHalf]*, at: usize) -> usize:
    let h = halves.items[at]
    let back = halves.items[twin_of(at)]
    var best: usize = at
    var best_turn = 10.0
    for index in 0..<halves.count:
        let o = halves.items[index]
        if not o.alive or o.tail != h.head or o.face >= 0: continue
        let turn = clockwise_turn(&back, &o)
        if turn < best_turn:
            best_turn = turn
            best = index
    return best

## Loops already oriented (outer counterclockwise, holes clockwise) into
## regions: each hole in the smallest outer loop holding it.
func nest_oriented(result: Profiles*) -> !:
    let count = result.loop_count()
    var outlines = Growing[Vector3]()
    defer outlines.close()
    var offsets = Growing[usize]()
    defer offsets.close()
    var scratch = Growing[Vector3]()
    defer scratch.close()
    var areas = Growing[f64]()
    defer areas.close()
    try offsets.push(0)
    for loop in 0..<count:
        try result.outline(loop, &scratch)
        try areas.push(signed_area(scratch.view()))
        for p in scratch.view(): try outlines.push(p)
        try offsets.push(outlines.count)
    try result.region_offsets.push(0)
    for loop in 0..<count:
        if areas.items[loop] <= 0.0: continue
        try result.region_loops.push(loop)
        for hole in 0..<count:
            if areas.items[hole] >= 0.0: continue
            let probe = outlines.items[offsets.items[hole]]
            if not inside(outlines.view()[offsets.items[loop]..<offsets.items[loop + 1]], probe): continue
            # The smallest outer loop holding it.
            var smallest = true
            for other in 0..<count:
                if other == loop or areas.items[other] <= 0.0 or areas.items[other] >= areas.items[loop]: continue
                if inside(outlines.view()[offsets.items[other]..<offsets.items[other + 1]], probe): smallest = false
            if smallest: try result.region_loops.push(hole)
        try result.region_offsets.push(result.region_loops.count)