Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / meshing / shaped_display.lucb

## The display triangles of a polygon whose worst is the roundest. A cell a
## seam conformed (conform_seams: a denser neighbor's samples on its side)
## or a trim cut has corners close together along one side; ear clipping or
## a fan from a fixed corner can join three of them (nearly on one line)
## into a needle. Of every triangulation of the polygon, the one whose least
## round triangle is roundest is shown: a minimax triangulation, by dynamic
## programming over the polygon's corner chains (Klincsek; Bern and
## Eppstein, "Mesh generation and optimal triangulation", 1992).

## The most corners a polygon is shaped for: the search is cubic in them
## (and each triangle's check linear), so beyond it a polygon keeps the
## display it has. Conformed and cut cells are well under it.
pub let shaped_most: usize = 24

## Display triangles of polygon `ids` (indices into its corners) into `out`,
## the triangulation whose least round triangle (roundness: twice its area
## over its longest side squared) is roundest, of those whose every triangle
## lies inside the polygon (as it faces, in its own plane), holds no other
## corner and is thick enough for the single-precision display to show
## (ear). Returns that least roundness, or 0 (and nothing in `out`) when the
## polygon has more than `shaped_most` corners or no such triangulation.
pub func shaped_display(mesh: const MeshBuilder*, ids: const i64[], out: Growing[i64]*) -> f64!:
    out.clear()
    let n = ids.length
    if n < 4 or n > shaped_most: return 0.0
    var normal = Vector3()
    for at in 0..<n: normal = normal.add(mesh.points[(usize)ids[at]].cross(mesh.points[(usize)ids[(at + 1) % n]]))
    let length = normal.length()
    if not (length > nonzero): return 0.0
    let facing = normal.multiply_scalar(1.0 / length)
    # The polygon in its own plane: two axes across its facing.
    let helper = Vector3(1.0, 0.0, 0.0) if math.abs(facing.x) < 0.5 else Vector3(0.0, 1.0, 0.0)
    let first_axis = helper.cross(facing).normalized() catch failure: recover Vector3(1.0, 0.0, 0.0)
    let second_axis = facing.cross(first_axis)
    let plane = try new Vector3[n] --- in memory.heap
    defer free(plane) in memory.heap
    let origin = mesh.points[(usize)ids[0]]
    for at in 0..<n:
        let p = mesh.points[(usize)ids[at]].subtract(origin)
        plane[at] = Vector3(p.dot(first_axis), p.dot(second_axis), 0.0)
    # Which corner pairs may be joined: a side, or a diagonal crossing no
    # side and leaving its corner into the polygon.
    var joins: bool[576]
    for i in 0..<n:
        for j in 0..<n: joins[i * n + j] = false
    for i in 0..<n:
        joins[i * n + (i + 1) % n] = true
        joins[((i + 1) % n) * n + i] = true
        for j in i + 2..<n:
            if i == 0 and j == n - 1: continue
            let inside = sees_inside(plane, i, j)
            joins[i * n + j] = inside
            joins[j * n + i] = inside
    # best[i * n + j]: the roundest least roundness of chain i..j closed by
    # the join j-i (-1: none); split: the corner its triangle takes.
    var best: f64[576]
    var split: usize[576]
    for at in 0..<n * n:
        best[at] = -1.0
        split[at] = n
    for i in 0..<n - 1: best[i * n + i + 1] = 1.0e300
    for span in 2..<n:
        for i in 0..<n - span:
            let j = i + span
            if not joins[i * n + j]: continue
            for k in i + 1..<j:
                let left = best[i * n + k]
                let right = best[k * n + j]
                if left < 0.0 or right < 0.0: continue
                let shape = math.min(left, right)
                if shape <= best[i * n + j]: continue
                let round = triangle_shape(mesh, ids, plane, i, k, j, facing)
                if round <= 0.0: continue
                let worst = math.min(shape, round)
                if worst > best[i * n + j]:
                    best[i * n + j] = worst
                    split[i * n + j] = k
    let result = best[n - 1]
    if result <= 0.0 or result >= 1.0e300: return 0.0
    try emit_shaped(split[..<n * n], n, 0, n - 1, out)
    return result

## Chain i..j's triangles (polygon i..j closed by j-i), as split chose.
func emit_shaped(split: const usize[], n: usize, i: usize, j: usize, out: Growing[i64]*) -> !:
    if j <= i + 1: return
    let k = split[i * n + j]
    try out.push((i64)i)
    try out.push((i64)k)
    try out.push((i64)j)
    try emit_shaped(split, n, i, k, out)
    try emit_shaped(split, n, k, j, out)

## Triangle i, k, j's roundness when the display can show it inside the
## polygon (turning its way, thick to the display, no other corner in or on
## it), else 0.
func triangle_shape(mesh: const MeshBuilder*, ids: const i64[], plane: const Vector3[], i: usize, k: usize, j: usize, facing: Vector3) -> f64:
    let a = plane[i]
    let b = plane[k]
    let c = plane[j]
    if plane_turn(a, b, c) <= 0.0: return 0.0
    if ear(mesh, ids, i, k, j, facing) < 1.0: return 0.0
    for at in 0..<plane.length:
        if at == i or at == k or at == j: continue
        let p = plane[at]
        if plane_turn(a, b, p) >= 0.0 and plane_turn(b, c, p) >= 0.0 and plane_turn(c, a, p) >= 0.0: return 0.0
    return roundness(mesh.points[(usize)ids[i]], mesh.points[(usize)ids[k]], mesh.points[(usize)ids[j]])

## Twice the signed area of a, b, c in the plane.
func plane_turn(a: Vector3, b: Vector3, c: Vector3) -> f64:
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

## Whether corners i and j (not neighbors) of the counterclockwise polygon
## `plane` see each other inside it: the segment leaves i into the polygon
## (within its corner's cone) and crosses no side it does not end on.
func sees_inside(plane: const Vector3[], i: usize, j: usize) -> bool:
    let n = plane.length
    let a = plane[i]
    let b = plane[j]
    let before = plane[(i + n - 1) % n]
    let after = plane[(i + 1) % n]
    # Within the cone at i (convex corner: left of both sides; reflex: not
    # right of both).
    let convex = plane_turn(before, a, after) > 0.0
    let left_after = plane_turn(a, after, b) > 0.0
    let left_before = plane_turn(before, a, b) > 0.0
    if convex and not (left_after and left_before): return false
    if not convex and not (left_after or left_before): return false
    for at in 0..<n:
        let next = (at + 1) % n
        if at == i or next == i or at == j or next == j: continue
        let c = plane[at]
        let d = plane[next]
        let d1 = plane_turn(a, b, c)
        let d2 = plane_turn(a, b, d)
        let d3 = plane_turn(c, d, a)
        let d4 = plane_turn(c, d, b)
        if ((d1 > 0.0 and d2 < 0.0) or (d1 < 0.0 and d2 > 0.0)) and ((d3 > 0.0 and d4 < 0.0) or (d3 < 0.0 and d4 > 0.0)): return false
        # A corner on the segment blocks it.
        if d1 == 0.0 and (c.subtract(a).dot(c.subtract(b)) <= 0.0): return false
    return true