Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / bevel_boundary.lucb

## Each bevel vertex's ring of boundary points, counterclockwise from
## outside, and the kind of mesh that fills it.
##
## Between each beveled half and the next beveled half around the vertex
## goes one boundary point: where their offset lines meet (on the face
## between them, or dropped onto a face when unbeveled edges lie between;
## with Loop slide and one unbeveled edge between, on that edge). Every
## unbeveled half in between attaches to it. A miter adds points: an outer
## miter (round a reflex corner, three or more beveled edges) makes an arc
## or a patch, an inner miter an arc whose ends spread apart along their
## edges. A vertex with one beveled edge (a terminal edge) gets a point on
## each neighbouring edge and slides the rest along their edges; a vertex
## cut off (Affect Vertices) gets a point on each edge.
##
## With `construct` false the ring exists and only its positions change
## (after Clamp overlap or the even-widths pass changed the widths).
##
## Every ring's size is known before it is built (`ring_size`), so each
## vertex fills its own room and the rings and vertex meshes are built in
## parallel.

## Room for every vertex's ring and mesh: each ring's size (in parallel),
## then each vertex's room, which it clears itself (in parallel again).
func reserve_rings(work: Bevel*) -> !:
    try parallel.for_each_range(work.vertices.count, 4096, (void*)work, size_range)
    let segments = work.settings.segments
    let per_bound = (segments // 2 + 1) * (segments + 1)
    var bounds: usize = 0
    var grid: usize = 0
    for slot in 0..<work.vertices.count:
        let count = (usize)work.vertices.items[slot].bounds
        work.vertices.items[slot].first_bound = (u32)bounds
        work.vertices.items[slot].bounds = 0
        work.vertices.items[slot].grid = (i64)grid
        bounds += count
        grid += count * per_bound
    try work.bounds.reserve(bounds)
    work.bounds.count = bounds
    try work.grid.reserve(grid)
    work.grid.count = grid
    try work.grid_links.reserve(grid)
    work.grid_links.count = grid
    try parallel.for_each_range(work.vertices.count, 4096, (void*)work, clear_range)

## Each vertex's ring size, kept in `bounds` until its room is placed.
func size_range(context: void*, first: usize, end: usize, worker: usize) -> !:
    let work = (Bevel*)context
    for slot in first..<end: work.vertices.items[slot].bounds = ring_size(work, (i32)slot)

## Clear each vertex's room: its boundary points and its mesh's points.
func clear_range(context: void*, first: usize, end: usize, worker: usize) -> !:
    let work = (Bevel*)context
    let blank = Bound(Vector3(), -1, 0, -1, -1, -1, -1, 1.0, -1, false, false, false, false, 0, 0, blank_profile())
    let bound_end = (usize)work.vertices.items[end].first_bound if end < work.vertices.count else work.bounds.count
    for at in (usize)work.vertices.items[first].first_bound..<bound_end: work.bounds.items[at] = blank
    let grid_end = (usize)work.vertices.items[end].grid if end < work.vertices.count else work.grid.count
    for at in (usize)work.vertices.items[first].grid..<grid_end:
        work.grid.items[at] = Vector3()
        work.grid_links.items[at] = -1

## How many boundary points vertex `slot`'s ring takes: one per edge cut
## off (Affect Vertices); three, or one fewer than its edges, at a terminal
## edge; else one per beveled edge and a miter's extra one or two.
func ring_size(work: const Bevel*, slot: i32) -> u32:
    let vertex = &work.vertices.items[(usize)slot]
    if vertex.halves <= 1: return 0
    if work.settings.vertices: return vertex.halves
    if vertex.selected == 1: return 3 if vertex.halves == 2 else vertex.halves - 1
    let outer = work.settings.miter_outer if vertex.selected >= 3 else miter_sharp
    let inner = work.settings.miter_inner
    var first = (i32)vertex.first_half
    while not work.halves.items[(usize)first].beveled: first = next_half(work, first)
    var count: u32 = 0
    var mitered = false
    var half = first
    while true:
        var following = next_half(work, half)
        while not work.halves.items[(usize)following].beveled: following = next_half(work, following)
        count += 1
        let kind = angle_kind(work, half, following)
        if (outer != miter_sharp and not mitered and kind == 1) or (inner != miter_sharp and kind == -1):
            if kind == 1: mitered = true
            count += 2 if kind == 1 and outer == miter_patch else 1
        half = following
        if half == first: break
    return count

## Build every ring, vertices in parallel.
func build_rings(work: Bevel*) -> !:
    try parallel.for_each_range(work.vertices.count, 256, (void*)work, ring_range)

func ring_range(context: void*, first: usize, end: usize, worker: usize) -> !:
    let work = (Bevel*)context
    for slot in first..<end: try build_boundary(work, slot, true)

## A new boundary point of vertex `slot` at `position`, next in its ring's
## room.
func add_bound(work: Bevel*, slot: i32, position: Vector3) -> i32!:
    let count = work.vertices.items[(usize)slot].bounds
    let room_end = work.vertices.items[(usize)slot + 1].first_bound if (usize)slot + 1 < work.vertices.count else (u32)work.bounds.count
    if work.vertices.items[(usize)slot].first_bound + count >= room_end: error(errors.invalid, "a bevel ring outgrew its room")
    let index = (i32)(work.vertices.items[(usize)slot].first_bound + count)
    work.bounds.items[(usize)index] = Bound(position, slot, (i32)count, -1, -1, -1, -1, 1.0, -1, false, false, false, false, 0, 0, blank_profile())
    work.vertices.items[(usize)slot].bounds = count + 1
    return index

func move_bound(work: Bevel*, bound: i32, position: Vector3):
    work.bounds.items[(usize)bound].position = position

## Place (or, with `construct`, make) bevel vertex `slot`'s ring.
func build_boundary(work: Bevel*, slot: usize, construct: bool) -> !:
    let vertex = work.vertices.items[slot]
    if vertex.halves <= 1: return
    if work.settings.vertices: return try vertex_only(work, (i32)slot, construct)
    var first = (i32)vertex.first_half
    while not work.halves.items[(usize)first].beveled: first = next_half(work, first)
    if vertex.selected == 1: return try terminal_edge(work, (i32)slot, first, construct)
    let outer = work.settings.miter_outer if vertex.selected >= 3 else miter_sharp
    let inner = work.settings.miter_inner
    var mitered: i32 = -1
    var half = first
    while true:
        # The halves up to the next beveled one: in the plane of the faces
        # either side (an edge across a flat region) or not.
        var flat_count = 0
        var out_of_plane = 0
        var plane_half: i32 = -1
        var bent_half: i32 = -1
        var following = next_half(work, half)
        while not work.halves.items[(usize)following].beveled:
            if flat_half(work, following):
                flat_count += 1
                plane_half = following
            else:
                out_of_plane += 1
                bent_half = following
            following = next_half(work, following)
        var position = Vector3()
        var on: i32 = -1
        var ratio = 1.0
        let after = work.halves.items[(usize)half].after
        if flat_count == 0 and out_of_plane == 0:
            position = offset_meet(work, half, following, after, false, -1)
        elif out_of_plane > 0:
            if work.settings.loop_slide and out_of_plane == 1 and good_on_edge(work, half, following, bent_half):
                let (placed, point, sines) = offset_on_edge(work, half, following, bent_half)
                position = point
                if placed:
                    on = bent_half
                    ratio = sines
            else:
                position = offset_meet(work, half, following, -1, true, plane_half)
        elif work.settings.loop_slide and flat_count == 1 and good_on_edge(work, half, following, plane_half):
            let (placed, point, sines) = offset_on_edge(work, half, following, plane_half)
            position = point
            if placed:
                on = plane_half
                ratio = sines
        else:
            # Every edge between lies in one plane: as if there were none.
            position = offset_meet(work, half, following, after, false, -1)
        let kind = angle_kind(work, half, following)
        let miter = (outer != miter_sharp and mitered < 0 and kind == 1) or (inner != miter_sharp and kind == -1)
        if construct:
            let bound = try add_bound(work, (i32)slot, position)
            set_bound_halves(work, bound, half, following, following)
            work.bounds.items[(usize)bound].on = on
            work.bounds.items[(usize)bound].sine_ratio = ratio
            work.halves.items[(usize)half].right = bound
            work.halves.items[(usize)following].left = bound
            var between = next_half(work, half)
            while between != following:
                work.halves.items[(usize)between].left = bound
                work.halves.items[(usize)between].right = bound
                between = next_half(work, between)
            if miter:
                if kind == 1: mitered = half
                try make_miter(work, (i32)slot, bound, half, following, kind == 1 and outer == miter_patch, flat_count + out_of_plane, position)
        else:
            if miter:
                if kind == 1: mitered = half
                let first_bound = work.halves.items[(usize)half].right
                var last_bound = next_bound(work, first_bound)
                if kind == 1 and outer == miter_patch:
                    move_bound(work, last_bound, position)
                    last_bound = next_bound(work, last_bound)
                move_bound(work, first_bound, position)
                move_bound(work, last_bound, position)
            else:
                move_bound(work, work.halves.items[(usize)half].right, position)
        half = following
        if half == first: break
    if inner != miter_sharp: spread_inner_miters(work, (i32)slot, mitered)
    if mitered >= 0: adjust_outer_miter(work, (i32)slot, mitered)
    if construct:
        let count = work.vertices.items[slot].bounds
        var kind = mesh_grid
        if count == 2: kind = mesh_none
        elif work.settings.segments == 1: kind = mesh_polygon
        elif work.settings.cutoff: kind = mesh_cutoff
        work.vertices.items[slot].kind = kind

func set_bound_halves(work: Bevel*, bound: i32, first: i32, last: i32, bevel: i32):
    work.bounds.items[(usize)bound].first = first
    work.bounds.items[(usize)bound].last = last
    work.bounds.items[(usize)bound].bevel = bevel

## Whether the faces either side of `half` lie in one plane (facing the same
## way or opposite).
func flat_half(work: const Bevel*, half: i32) -> bool:
    let item = work.halves.items[(usize)half]
    if item.before < 0 or item.after < 0: return false
    let dot = normal_of(work, item.before).dot(normal_of(work, item.after))
    return math.abs(dot + 1.0) <= tiny_big or math.abs(dot - 1.0) <= tiny_big

## A miter's points after `bound` (the point between `half` and the next
## beveled `following`): for a patch, a middle point and an end point; for
## an arc, an end point, the arc's profile from `bound`, and the unbeveled
## edges between attached along the arc.
func make_miter(work: Bevel*, slot: i32, bound: i32, half: i32, following: i32, patch: bool, between: i64, position: Vector3) -> !:
    work.bounds.items[(usize)bound].bevel = -1
    var middle: i32 = -1
    if patch: middle = try add_bound(work, slot, position)
    let end = try add_bound(work, slot, position)
    set_bound_halves(work, end, following, following, following)
    work.halves.items[(usize)following].left = end
    if patch:
        work.bounds.items[(usize)bound].patch_start = true
        work.bounds.items[(usize)middle].on = work.bounds.items[(usize)bound].on
        work.bounds.items[(usize)middle].sine_ratio = work.bounds.items[(usize)bound].sine_ratio
        work.bounds.items[(usize)bound].on = -1
        work.bounds.items[(usize)bound].sine_ratio = 1.0
        work.bounds.items[(usize)bound].last = half
        if next_half(work, half) == following:
            work.bounds.items[(usize)middle].first = -1
            work.bounds.items[(usize)middle].last = -1
        else:
            work.bounds.items[(usize)middle].first = next_half(work, half)
            var other = next_half(work, half)
            while other != following:
                work.halves.items[(usize)other].left = middle
                work.halves.items[(usize)other].right = middle
                work.bounds.items[(usize)middle].last = other
                other = next_half(work, other)
        return
    work.bounds.items[(usize)bound].arc_start = true
    work.bounds.items[(usize)bound].profile.middle = position
    if next_half(work, half) == following:
        work.bounds.items[(usize)bound].last = work.bounds.items[(usize)bound].first
        return
    # The unbeveled edges between attach to the arc: the first half of them
    # at its start, the second half at its end, an odd middle one halfway.
    let segments = (i32)work.settings.segments
    let pairs = between // 2
    let odd = between % 2 == 1
    var at: i64 = 0
    var other = next_half(work, half)
    while other != following:
        work.bounds.items[(usize)bound].last = other
        var index = segments
        if at < pairs: index = 0
        elif odd and at == pairs: index = segments // 2
        work.halves.items[(usize)other].profile_index = index
        at += 1
        other = next_half(work, other)

## An outer miter's end points moved out along their edges to where the
## planes across the edges through the neighbouring boundary points cross
## the line from the miter's corner.
func adjust_outer_miter(work: Bevel*, slot: i32, mitered: i32):
    let start = work.halves.items[(usize)mitered].right
    var end = next_bound(work, start)
    if work.settings.miter_outer == miter_patch: end = next_bound(work, end)
    let before = previous_bound(work, start)
    let after = next_bound(work, end)
    let corner = work.bounds.items[(usize)start].position
    if work.bounds.items[(usize)start].arc_start: work.bounds.items[(usize)start].profile.middle = corner
    let fallback = work.width / ((f64)work.settings.segments / 2.0)
    let way1 = half_direction(work, mitered).multiply_scalar(-1.0)
    let reach1 = corner.add(way1.multiply_scalar(fallback))
    var moved1 = reach1
    if let crossing = line_plane(corner, reach1, work.bounds.items[(usize)before].position, way1): moved1 = crossing
    move_bound(work, start, moved1)
    let other_half = work.bounds.items[(usize)end].last
    let way3 = half_direction(work, other_half).multiply_scalar(-1.0)
    let reach3 = corner.add(way3.multiply_scalar(fallback))
    var moved3 = reach3
    if let crossing = line_plane(corner, reach3, work.bounds.items[(usize)after].position, way3): moved3 = crossing
    move_bound(work, end, moved3)

## Inner arc miters: each arc's two end points spread apart along their own
## edges by Spread (the outer miter's arc keeps its place).
func spread_inner_miters(work: Bevel*, slot: i32, mitered: i32):
    let vertex = work.vertices.items[(usize)slot]
    let start = (i32)vertex.first_bound
    var bound = start
    var steps: u32 = 0
    while steps < vertex.bounds:
        if work.bounds.items[(usize)bound].arc_start:
            let end = next_bound(work, bound)
            let half = work.bounds.items[(usize)bound].first
            if half != mitered:
                let corner = work.bounds.items[(usize)bound].position
                move_bound(work, bound, corner.add(half_direction(work, half).multiply_scalar(work.settings.spread)))
                let other = work.bounds.items[(usize)end].last
                move_bound(work, end, corner.add(half_direction(work, other).multiply_scalar(work.settings.spread)))
            bound = next_bound(work, end)
            steps += 2
        else:
            bound = next_bound(work, bound)
            steps += 1

## A vertex with one beveled edge `first`. With only two edges at the
## vertex the strip ends in a point slid along the other edge (a triangle);
## otherwise its sides meet the neighbouring edges and the rest of the
## edges slide back far enough to leave room for the profile.
func terminal_edge(work: Bevel*, slot: i32, first: i32, construct: bool) -> !:
    let vertex = work.vertices.items[(usize)slot]
    let item = work.halves.items[(usize)first]
    let following = next_half(work, first)
    let previous = previous_half(work, first)
    if vertex.halves == 2:
        var before_normal: Vector3? = none
        if item.before >= 0: before_normal = normal_of(work, item.before)
        elif item.after >= 0: before_normal = normal_of(work, item.after)
        var after_normal: Vector3? = none
        if item.after >= 0: after_normal = normal_of(work, item.after)
        elif item.before >= 0: after_normal = normal_of(work, item.before)
        let left = offset_in_plane(work, first, before_normal, true)
        let right = offset_in_plane(work, first, after_normal, false)
        let tip = slide_half(work, following, item.offset_left)
        if construct:
            let a = try add_bound(work, slot, left)
            set_bound_halves(work, a, first, first, first)
            work.halves.items[(usize)first].left = a
            let b = try add_bound(work, slot, right)
            set_bound_halves(work, b, first, first, -1)
            work.halves.items[(usize)first].right = b
            let c = try add_bound(work, slot, tip)
            set_bound_halves(work, c, following, following, -1)
            work.halves.items[(usize)following].left = c
            work.halves.items[(usize)following].right = c
        else:
            move_bound(work, item.left, left)
            move_bound(work, item.right, right)
            move_bound(work, work.halves.items[(usize)following].left, tip)
    else:
        let leg_slide = work.settings.width_type == width_percent or work.settings.width_type == width_absolute
        let left = slide_half(work, previous, item.offset_left) if leg_slide else offset_meet(work, previous, first, item.before, false, -1)
        let right = slide_half(work, following, item.offset_right) if leg_slide else offset_meet(work, first, following, work.halves.items[(usize)following].before, false, -1)
        if construct:
            let a = try add_bound(work, slot, left)
            set_bound_halves(work, a, previous, first, first)
            work.halves.items[(usize)first].left = a
            work.halves.items[(usize)previous].left = a
            work.halves.items[(usize)previous].right = a
            let b = try add_bound(work, slot, right)
            set_bound_halves(work, b, first, following, -1)
            work.halves.items[(usize)following].left = b
            work.halves.items[(usize)following].right = b
            work.halves.items[(usize)first].right = b
        else:
            move_bound(work, item.left, left)
            move_bound(work, work.halves.items[(usize)following].left, right)
        # The edges not beside the beveled one slide back by its width (more
        # for profiles fuller than a chamfer's, which need the room).
        var distance = item.spec_left
        if work.settings.custom or work.settings.shape < 0.25: distance *= math.sqrt(2.0)
        var other = next_half(work, following)
        while next_half(work, other) != first:
            let position = slide_half(work, other, distance)
            if construct:
                let c = try add_bound(work, slot, position)
                set_bound_halves(work, c, other, other, -1)
                work.halves.items[(usize)other].left = c
                work.halves.items[(usize)other].right = c
            else:
                move_bound(work, work.halves.items[(usize)other].left, position)
            other = next_half(work, other)
    if vertex.halves >= 3:
        # The strip's end profile snaps to the plane of the two edges beside.
        let start = (i32)work.vertices.items[(usize)slot].first_bound
        set_profile(work, slot, start)
        move_profile_plane(work, start, vertex_at(work, slot))
    if construct:
        let count = work.vertices.items[(usize)slot].bounds
        var kind = mesh_polygon
        if count == 2 and vertex.halves == 3: kind = mesh_none
        elif count == 3:
            kind = mesh_fan
            if work.settings.custom and profile_holds_tip(work, slot, first): kind = mesh_polygon
        work.vertices.items[(usize)slot].kind = kind

## Custom profile at a terminal edge: whether the extra point (on the edge
## past the strip) lies in the strip's profile plane, where a fan would
## fold over.
func profile_holds_tip(work: const Bevel*, slot: i32, first: i32) -> bool:
    let start = work.halves.items[(usize)first].left
    let profile = work.bounds.items[(usize)start].profile
    let tip = next_bound(work, work.halves.items[(usize)first].right)
    let offset = work.bounds.items[(usize)tip].position.subtract(profile.plane_point).dot(unit_of(profile.plane_normal))
    return offset * offset < tiny_big

## Affect Vertices: a boundary point slid along each edge by its width.
func vertex_only(work: Bevel*, slot: i32, construct: bool) -> !:
    let vertex = work.vertices.items[(usize)slot]
    for at in vertex.first_half..<vertex.first_half + vertex.halves:
        let half = (i32)at
        let position = slide_half(work, half, work.halves.items[at].offset_left)
        if construct:
            let bound = try add_bound(work, slot, position)
            set_bound_halves(work, bound, half, half, -1)
            work.halves.items[at].left = bound
            work.halves.items[at].right = bound
        else:
            move_bound(work, work.halves.items[at].left, position)
    if construct:
        let count = work.vertices.items[(usize)slot].bounds
        var kind = mesh_grid
        if count == 2: kind = mesh_none
        elif work.settings.segments == 1: kind = mesh_polygon
        work.vertices.items[(usize)slot].kind = kind