Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.6

0.7.6 / src / verbs / bevel_setup.lucb

## Which edges or points a PolyBevel run cuts away, and each bevel vertex's
## halves with their widths.
##
## An edge bevels when it is in the group, has exactly two faces and passes
## the Limit (its faces' normals at least Angle apart, or a bevel_weight
## above 0). An edge of one face is skipped with a warning; an edge of three
## or more faces, or a bevel vertex whose faces are not one fan, refuses the
## run: there is no sensible ring of boundary points around it.

func choose_beveled(work: Bevel*, input: const VerbInput*) -> !:
    let topology = &work.topology
    try work.slot_of.fill(topology.points, -1)
    work.beveled = try BitsBuilder.zeros(topology.edges())
    var points = Growing[i32]()
    defer points.close()
    if work.settings.vertices:
        try choose_points(work, input, &points)
        return try add_vertices(work, points.view())
    # Which edges bevel, ranges of whole bit words in parallel; then the
    # bevel vertices in order of their first beveled edge.
    let ranges = (topology.edges() + edge_range - 1) // edge_range
    var refused = try new i64[ranges] --- in memory.heap
    defer free(refused) in memory.heap
    var skipped = try new usize[ranges] --- in memory.heap
    defer free(skipped) in memory.heap
    var choosing = Choosing(work, input, refused[..<ranges], skipped[..<ranges])
    try parallel.for_each_range(topology.edges(), edge_range, (void*)&choosing, choose_range)
    for at in 0..<ranges:
        work.skipped_boundary += skipped[at]
        if refused[at] < 0: continue
        let edge = (usize)refused[at]
        var buffer: u8[120]
        let uses = (usize)topology.edge_corner_offsets[edge + 1] - (usize)topology.edge_corner_offsets[edge]
        error(errors.invalid, strings.format(buffer, f"Bevel needs manifold edges: edge {edge} has {uses} faces") else "Bevel needs manifold edges")
    let words = work.beveled.view().words
    for word_at in 0..<words.length:
        var word = words[word_at]
        while word != 0:
            let edge = word_at * 64 + (usize)trailing_zeros(word)
            word = word & (word - 1)
            for end in 0..<(usize)2:
                let point = topology.edge_points[edge * 2 + end]
                if work.slot_of.items[(usize)point] >= 0: continue
                work.slot_of.items[(usize)point] = (i32)points.count
                try points.push(point)
    try add_vertices(work, points.view())

## Edges a range of choose_beveled takes: whole words of the bits, so
## ranges never share a word.
let edge_range: usize = 64 * 256

struct Choosing:
    var work: Bevel*
    var input: const VerbInput*
    ## Per range: its first edge of three or more faces (-1 none), and its
    ## boundary edges skipped.
    var refused: i64[]
    var skipped: usize[]

func choose_range(context: void*, first: usize, end: usize, worker: usize) -> !:
    let choosing = (Choosing*)context
    let work = choosing.work
    let topology = &work.topology
    let range = first // edge_range
    choosing.refused[range] = -1
    choosing.skipped[range] = 0
    for edge in first..<end:
        if not edge_chosen(choosing.input, topology, edge): continue
        let at = (usize)topology.edge_corner_offsets[edge]
        let uses = (usize)topology.edge_corner_offsets[edge + 1] - at
        if uses == 1:
            choosing.skipped[range] += 1
            continue
        if uses > 2:
            choosing.refused[range] = (i64)edge
            return
        if uses == 0: continue
        let face_a = topology.corner_faces[(usize)topology.edge_corners[at]]
        let face_b = topology.corner_faces[(usize)topology.edge_corners[at + 1]]
        if face_a == face_b: continue
        if work.settings.limit == limit_angle and angle_between(normal_of(work, face_a), normal_of(work, face_b)) < work.settings.angle - 0.0000001: continue
        if work.settings.limit == limit_weight and edge_weight(work, edge) <= 0.0: continue
        work.beveled.set(edge)

## Whether the group names edge `edge`: a point group names the edges
## whose two points it holds.
func edge_chosen(input: const VerbInput*, topology: const Topology*, edge: usize) -> bool:
    if input.domain == Domain.point:
        return input.group.get((usize)topology.edge_points[edge * 2]) and input.group.get((usize)topology.edge_points[edge * 2 + 1])
    return input.group.get(edge)

## Affect Vertices: the group's points (an edge group's points) that have
## faces and pass the Limit, numbered in order.
func choose_points(work: Bevel*, input: const VerbInput*, points: Growing[i32]*) -> !:
    let topology = &work.topology
    for point in 0..<topology.points:
        let first = (usize)topology.point_edge_offsets[point]
        let end = (usize)topology.point_edge_offsets[point + 1]
        if end - first < 2: continue
        var chosen = false
        if input.domain == Domain.point:
            chosen = input.group.get(point)
        else:
            for at in first..<end:
                if input.group.get((usize)topology.point_edges[at]): chosen = true
        if not chosen: continue
        if work.settings.limit == limit_weight and point_weight(work, point) <= 0.0: continue
        if work.settings.limit == limit_angle and not sharp_point(work, point): continue
        work.slot_of.items[point] = (i32)points.count
        try points.push((i32)point)

## Whether some edge at `point` has faces at least Angle apart.
func sharp_point(work: const Bevel*, point: usize) -> bool:
    let topology = &work.topology
    for at in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
        let edge = (usize)topology.point_edges[at]
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let face_a = topology.corner_faces[(usize)topology.edge_corners[first]]
        let face_b = topology.corner_faces[(usize)topology.edge_corners[first + 1]]
        if angle_between(normal_of(work, face_a), normal_of(work, face_b)) >= work.settings.angle - 0.0000001: return true
    return false

## Edge `edge`'s bevel_weight with Limit Weight (1 otherwise).
func edge_weight(work: const Bevel*, edge: usize) -> f64:
    if work.settings.limit != limit_weight: return 1.0
    let entry = work.edge_weights else return 0.0
    return entry.number(edge, 0)

func point_weight(work: const Bevel*, point: usize) -> f64:
    if work.settings.limit != limit_weight: return 1.0
    let entry = work.point_weights else return 0.0
    return entry.number(point, 0)

## Make `points` the bevel vertices, slot by slot (slot_of numbers them
## already): each vertex's halves counterclockwise from outside, from the
## boundary edge when its fan is open. A vertex has a half per edge, so
## every vertex's room is known first and the vertices are built in
## parallel; a vertex that refuses (not one fan, or an edge of three or
## more faces) is built again alone to report it, the first one in order.
func add_vertices(work: Bevel*, points: const i32[]) -> !:
    let topology = &work.topology
    var halves: usize = 0
    try work.vertices.fill(points.length, BevelVertex(-1, 0, 0, 0, false, 0.0, Vector3(), 0, 0, mesh_none, -1, false, -1, true, false))
    for slot in 0..<points.length:
        let point = (usize)points[slot]
        let count = (usize)topology.point_edge_offsets[point + 1] - (usize)topology.point_edge_offsets[point]
        work.vertices.items[slot].point = points[slot]
        work.vertices.items[slot].first_half = (u32)halves
        work.vertices.items[slot].halves = (u32)count
        halves += count
    try work.halves.fill(halves, Half(-1, -1, -1, -1, -1, false, -1, -1, 0, 0.0, 0.0, 0.0, 0.0, false))
    let ranges = (points.length + vertex_range - 1) // vertex_range
    var refused = try new i64[ranges] --- in memory.heap
    defer free(refused) in memory.heap
    var adding = Adding(work, refused[..<ranges])
    try parallel.for_each_range(points.length, vertex_range, (void*)&adding, add_range)
    for at in 0..<ranges:
        if refused[at] >= 0: try build_vertex(work, (usize)refused[at])

let vertex_range: usize = 1024

struct Adding:
    var work: Bevel*
    ## Per range: its first vertex that refused, or -1.
    var refused: i64[]

func add_range(context: void*, first: usize, end: usize, worker: usize) -> !:
    let adding = (Adding*)context
    let range = first // vertex_range
    adding.refused[range] = -1
    for slot in first..<end:
        build_vertex(adding.work, slot) catch failure:
            adding.refused[range] = (i64)slot
            return

## Build bevel vertex `slot` in its room: its halves round its point and
## their widths.
func build_vertex(work: Bevel*, slot: usize) -> !:
    let topology = &work.topology
    let point = work.vertices.items[slot].point
    let half_first = (usize)work.vertices.items[slot].first_half
    let room = (usize)work.vertices.items[slot].halves
    let edge_first = (usize)topology.point_edge_offsets[(usize)point]
    let edge_end = (usize)topology.point_edge_offsets[(usize)point + 1]
    var start: i64 = -1
    for at in edge_first..<edge_end:
        let edge = (usize)topology.point_edges[at]
        let first = (usize)topology.edge_corner_offsets[edge]
        let end = (usize)topology.edge_corner_offsets[edge + 1]
        if end - first > 2:
            var buffer: u8[120]
            error(errors.invalid, strings.format(buffer, f"Bevel needs manifold edges: edge {edge} at point {point} has {end - first} faces") else "Bevel needs manifold edges")
        for corner_at in first..<end:
            let corner = (usize)topology.edge_corners[corner_at]
            if start < 0 and topology.corners[corner] == point: start = (i64)corner
    if start < 0:
        # No face at the point: nothing bevels there.
        work.vertices.items[slot].halves = 0
        work.slot_of.items[(usize)point] = -1
        return
    let limit = (edge_end - edge_first) * 2 + 2
    # Clockwise (across the edge each corner leaves along) to an open fan's
    # first corner, whose leaving edge is on the boundary.
    var first = (usize)start
    for _ in 0..<limit:
        let across = topology.twin(first)
        if across < 0: break
        let back = topology.next((usize)across)
        if topology.corners[back] != point: try not_a_fan(point)
        if back == (usize)start: break
        first = back
    let id = (i32)slot
    var corner = first
    var closed = false
    var count: usize = 0
    while true:
        if count >= room: try not_a_fan(point)
        work.halves.items[half_first + count] = new_half(work, id, topology.corner_edges[corner], point, -1, topology.corner_faces[corner])
        count += 1
        let previous = topology.previous(corner)
        let across = topology.twin(previous)
        if across < 0:
            # Open: the last half is the edge arriving in the last face.
            if count >= room: try not_a_fan(point)
            work.halves.items[half_first + count] = new_half(work, id, topology.corner_edges[previous], point, topology.corner_faces[corner], -1)
            count += 1
            break
        if topology.corners[(usize)across] != point: try not_a_fan(point)
        if (usize)across == first:
            closed = true
            break
        corner = (usize)across
    if count != room: try not_a_fan(point)
    # Each half's face before is the face after the one before it.
    for at in 0..<count:
        let previous_at = half_first + (at + count - 1) % count
        if at > 0 or closed: work.halves.items[half_first + at].before = work.halves.items[previous_at].after
    var selected: u32 = 0
    var normal = Vector3()
    for at in half_first..<half_first + count:
        if work.halves.items[at].beveled: selected += 1
        normal = normal.add(normal_of(work, work.halves.items[at].after))
    var width = work.width
    if work.settings.vertices: width *= point_weight(work, (usize)point)
    work.vertices.items[slot] = BevelVertex(point, (u32)half_first, (u32)count, selected, closed, width, unit_of(normal), 0, 0, mesh_none, -1, false, -1, true, false)
    for at in half_first..<half_first + count: set_offsets(work, (i32)at)

func not_a_fan(point: i32) -> !:
    var buffer: u8[120]
    error(errors.invalid, strings.format(buffer, f"Bevel needs one fan of faces around each bevel vertex; point {point} is not manifold") else "Bevel needs one fan of faces around each bevel vertex")

## A half of edge `edge` at `point` (bevel vertex `slot`) between the faces
## `before` and `after`.
func new_half(work: const Bevel*, slot: i32, edge: i32, point: i32, before: i32, after: i32) -> Half:
    let a = work.topology.edge_points[(usize)edge * 2]
    let other = work.topology.edge_points[(usize)edge * 2 + 1] if a == point else a
    let beveled = not work.settings.vertices and work.beveled.view().get((usize)edge)
    return Half(edge, slot, other, before, after, beveled, -1, -1, 0, 0.0, 0.0, 0.0, 0.0, false)

## The angle between the faces either side of `half` (pi when flat), or 0
## on a boundary.
func face_angle(work: const Bevel*, half: i32) -> f64:
    let item = work.halves.items[(usize)half]
    if item.before < 0 or item.after < 0: return 0.0
    return math.pi - angle_between(normal_of(work, item.before), normal_of(work, item.after))

## The width a half asks for on each side, by the Width Type: Offset across
## the faces; Width the strip's own width (Offset / (2 sin(a/2)) for faces
## an angle a apart); Depth straight in from the edge (Offset / cos(a/2));
## Percent and Absolute along the edges beside (left and right apart). With
## Affect Vertices every edge of the point slides by its width.
func set_offsets(work: Bevel*, half: i32):
    let item = work.halves.items[(usize)half]
    let vertex = work.vertices.items[(usize)item.slot]
    let kind = work.settings.width_type
    var left = 0.0
    var right = 0.0
    if item.beveled:
        let width = work.width
        if kind == width_width or kind == width_depth:
            let half_angle = face_angle(work, half) * 0.5
            let z = math.abs(2.0 * math.sin(half_angle)) if kind == width_width else math.abs(math.cos(half_angle))
            left = 0.01 * width if z < tiny else width / z
            right = left
        elif kind == width_percent:
            left = half_length(work, previous_half(work, half)) * width / 100.0
            right = half_length(work, next_half(work, half)) * width / 100.0
        else:
            left = width
            right = width
        let weight = edge_weight(work, (usize)item.edge)
        left *= weight
        right *= weight
    elif work.settings.vertices:
        let width = vertex.width
        if kind == width_width or kind == width_depth:
            var axis = Vector3()
            for at in vertex.first_half..<vertex.first_half + vertex.halves:
                axis = axis.add(half_direction(work, (i32)at).multiply_scalar(-1.0))
            let angle = angle_between(axis, half_direction(work, half).multiply_scalar(-1.0))
            let z = math.abs(2.0 * math.sin(angle)) if kind == width_width else math.abs(math.cos(angle))
            left = 0.01 * width if z < tiny else width / z
        elif kind == width_percent:
            left = half_length(work, half) * width / 100.0
        else:
            left = width
        right = left
    work.halves.items[(usize)half].spec_left = left
    work.halves.items[(usize)half].spec_right = right
    work.halves.items[(usize)half].offset_left = left
    work.halves.items[(usize)half].offset_right = right