Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / modeling / arrangement_graph.lucb

## A sketch arrangement's graph (arrangement.lucb): sub-edges' ends merged
## into vertices, half-edges sorted round each vertex, faces traced as the
## next half-edge clockwise.

## A half-edge: sub-edge `edge` run forward or backward, from vertex `tail`
## to `head`, leaving at angle `angle` turning by `curving` (signed
## curvature, for touching curves), on face `face`.
struct SketchHalf:
    var edge: usize
    var backward: bool
    var tail: usize
    var head: usize
    var angle: f64
    var curving: f64
    var face: i64
    var alive: bool

## The sub-edges as a graph: their ends merged into vertices within
## `tolerance`, each a pair of half-edges (repeats of one sub-edge, as
## overlapping curves make, kept once), and pieces left dangling dropped.
func build_graph(result: Profiles*, subs: Growing[ProfileEdge]*, tolerance: f64, vertices: Growing[Vector3]*, halves: Growing[SketchHalf]*) -> !:
    var ends = Growing[usize]()
    defer ends.close()
    for e in subs.view():
        try ends.push(try vertex_of(vertices, e.start, tolerance))
        try ends.push(try vertex_of(vertices, e.end, tolerance))
    for index in 0..<subs.count:
        let tail = ends.items[2 * index]
        let head = ends.items[2 * index + 1]
        let e = subs.items[index]
        if tail == head and e.kind == profile_line: continue
        if try repeats_earlier(result, subs, &ends, index, tolerance): continue
        let (forward_angle, forward_curving) = try leaving_way(result, &e, false)
        let (backward_angle, backward_curving) = try leaving_way(result, &e, true)
        try halves.push(SketchHalf(index, false, tail, head, forward_angle, forward_curving, -1, true))
        try halves.push(SketchHalf(index, true, head, tail, backward_angle, backward_curving, -1, true))
    # Dangling pieces go, one end at a time.
    var degree = Growing[i64]()
    defer degree.close()
    try degree.fill(vertices.count, 0)
    for h in halves.view(): degree.items[h.tail] += 1
    var pruned = true
    while pruned:
        pruned = false
        var at: usize = 0
        while at < halves.count:
            let h = halves.items[at]
            if h.alive and (degree.items[h.tail] == 1 or degree.items[h.head] == 1):
                halves.items[at].alive = false
                halves.items[at + 1].alive = false
                degree.items[h.tail] -= 1
                degree.items[h.head] -= 1
                pruned = true
            at += 2

## Whether sub-edge `index` repeats an earlier one: the same ends and the
## same middle.
func repeats_earlier(result: Profiles*, subs: Growing[ProfileEdge]*, ends: const Growing[usize]*, index: usize, tolerance: f64) -> bool!:
    let a = ends.items[2 * index]
    let b = ends.items[2 * index + 1]
    let middle = try result.edge_at(&subs.items[index], 0.5)
    for other in 0..<index:
        let c = ends.items[2 * other]
        let d = ends.items[2 * other + 1]
        if not ((a == c and b == d) or (a == d and b == c)): continue
        if middle.subtract(try result.edge_at(&subs.items[other], 0.5)).length() <= tolerance: return true
    return false

## The vertex at `p` (an existing one within `tolerance`, else a new one).
func vertex_of(vertices: Growing[Vector3]*, p: Vector3, tolerance: f64) -> usize!:
    for at in 0..<vertices.count:
        if vertices.items[at].subtract(p).length() <= tolerance: return at
    try vertices.push(p)
    return vertices.count - 1

## The direction (angle in plane coordinates) a sub-edge leaves its tail
## (`backward`: leaves its end going back), and how it turns from there
## (signed curvature: positive to the left).
func leaving_way(result: Profiles*, e: const ProfileEdge*, backward: bool) -> (f64, f64)!:
    if e.kind == profile_line:
        let (sx, sy) = result.planar(e.start)
        let (ex, ey) = result.planar(e.end)
        return (math.atan2(sy - ey, sx - ex), 0.0) if backward else (math.atan2(ey - sy, ex - sx), 0.0)
    if e.kind == profile_arc:
        let (cx, cy) = result.planar(e.center)
        let (px, py) = result.planar(e.end if backward else e.start)
        # Counterclockwise arcs leave square to the radius, to the left.
        let left = (e.sweep > 0.0) != backward
        let rx = px - cx
        let ry = py - cy
        let direction = math.atan2(rx, -ry) if left else math.atan2(-rx, ry)
        return (direction, (1.0 if left else -1.0) / e.radius)
    # A spline: its first and second differences at the end it leaves.
    let h = 1e-5
    let f0 = 1.0 if backward else 0.0
    let s = -1.0 if backward else 1.0
    let (x0, y0) = result.planar(try result.edge_at(e, f0))
    let (x1, y1) = result.planar(try result.edge_at(e, f0 + s * h))
    let (x2, y2) = result.planar(try result.edge_at(e, f0 + s * 2.0 * h))
    let dx = (x1 - x0) / h
    let dy = (y1 - y0) / h
    let ddx = (x2 - 2.0 * x1 + x0) / (h * h)
    let ddy = (y2 - 2.0 * y1 + y0) / (h * h)
    let speed = math.hypot(dx, dy)
    let curving = (dx * ddy - dy * ddx) / math.max(speed * speed * speed, nonzero)
    return (math.atan2(dy, dx), curving)

## The faces: from each half-edge not yet on one, at its head the next
## edge clockwise from the way back (the face kept on the left), until
## back where it began.
func trace_faces(halves: Growing[SketchHalf]*, vertex_count: usize, faces: Growing[usize]*, offsets: Growing[usize]*) -> !:
    try offsets.push(0)
    for start in 0..<halves.count:
        if not halves.items[start].alive or halves.items[start].face >= 0: continue
        let face = (i64)offsets.count - 1
        var at = start
        var guard: usize = 0
        while halves.items[at].face < 0:
            halves.items[at].face = face
            try faces.push(at)
            at = next_of(halves, at)
            guard += 1
            if guard > halves.count: error(invalid, "a sketch's curves could not be traced into faces")
        try offsets.push(faces.count)
    _ = vertex_count

## The half-edge after `at` round its face: at its head, the outgoing edge
## just clockwise of the twin (the way back).
func next_of(halves: Growing[SketchHalf]*, at: usize) -> usize:
    let h = halves.items[at]
    let twin = twin_of(at)
    let back = halves.items[twin]
    var best: usize = twin
    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 index == twin: continue
        let turn = clockwise_turn(&back, &o)
        if turn < best_turn:
            best_turn = turn
            best = index
    return best

## The outline of a face's half-edges (plane coordinates), for its area.
func face_outline(result: Profiles*, subs: Growing[ProfileEdge]*, halves: Growing[SketchHalf]*, loop: const usize[], out: Growing[Vector3]*) -> !:
    out.clear()
    for at in loop:
        let h = halves.items[at]
        let e = subs.items[h.edge]
        var steps: usize = 1
        if e.kind == profile_arc: steps = (usize)math.max(2.0, math.ceil(math.abs(e.sweep) / 0.1745))
        if e.kind == profile_spline: steps = 32
        for step in 0..<steps:
            let f = (f64)step / (f64)steps
            let (x, y) = result.planar(try result.edge_at(&e, 1.0 - f if h.backward else f))
            try out.push(Vector3(x, y, 0.0))

## How far clockwise from the way back (`back`'s direction) `o` leaves,
## in (0, 2π]: among edges leaving the same way, one curving more to the
## right of it comes first.
func clockwise_turn(back: const SketchHalf*, o: const SketchHalf*) -> f64:
    var turn = back.angle - o.angle
    while turn <= 0.0: turn += 2.0 * math.pi
    while turn > 2.0 * math.pi: turn -= 2.0 * math.pi
    if turn <= 1e-9 or turn >= 2.0 * math.pi - 1e-9:
        turn = 2.0 * math.pi if o.curving > back.curving else 1e-10
    return turn

## The other half of half-edge `at`'s pair.
func twin_of(at: usize) -> usize:
    return at + 1 if at % 2 == 0 else at - 1