Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / meshing / analytic_trim.lucb

## Periodic analytic support inversion and trim meshing in unwrapped UV space.

pub func analytic_trim(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
    if s.kind == surface_sphere and touches_pole(s, mesh.points[..<mesh.np], ids):
        try local_or_holes(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)
        return
    let np = mesh.np
    let nf = mesh.nf
    let nc = mesh.nc
    mesh_in_chart(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size) catch failure:
        if failure.code != invalid or s.kind != surface_sphere: error(failure.code, failure.message)
        mesh.np = np
        mesh.nf = nf
        mesh.nc = nc
        # Retry a failed angular chart away from an authored pole too, and
        # then a chart of the face's own about an axis away from every trim
        # (sphere_axis). Canonical trim positions/IDs never move.
        try local_or_holes(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)
        recover ()

## A sphere face in a local hemisphere's chart, or else sphere_axis's.
func local_or_holes(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
    let np = mesh.np
    let nf = mesh.nf
    let nc = mesh.nc
    var meshed = true
    local_chart(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size) catch failure:
        if failure.code != invalid: error(failure.code, failure.message)
        mesh.np = np
        mesh.nf = nf
        mesh.nc = nc
        meshed = false
        recover ()
    if not meshed: try sphere_axis(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)

func local_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
    let chart = try local_sphere(s, mesh.points[..<mesh.np], ids)
    defer chart.close()
    try mesh_in_chart(mesh, ids, sizes, chart, sense, divisions, tolerance, edge_size)

func mesh_in_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
    let uv = try new Vector3[ids.length] --- in memory.heap
    defer free(uv) in memory.heap
    let uscale = math.max(s.radius, tolerance)
    let vscale = s.radius if s.kind == surface_sphere else (s.angle if s.kind == surface_torus else 1.0)
    var offset: usize = 0
    var anchor = Vector3()
    for loop in 0..<sizes.length:
        var previous = anchor
        for at in 0..<(usize)sizes[loop]:
            let p = mesh.points[(usize)ids[offset + at]].subtract(s.origin)
            let x = p.dot(s.x)
            let y = p.dot(s.y)
            let z = p.dot(s.z)
            let radius = math.sqrt(x * x + y * y)
            var u = math.atan2(y, x)
            var v = math.atan2(z, radius) if s.kind == surface_sphere else (math.atan2(z, radius - s.radius) if s.kind == surface_torus else z)
            if at > 0 or loop > 0:
                u = wrap(u, previous.x)
                if s.kind == surface_torus:
                    v = wrap(v, previous.y)
            if analytic_point(s, u, v).subtract(mesh.points[(usize)ids[offset + at]]).length() > s.trims_within(tolerance):
                error(invalid, "analytic trim is outside its support tolerance")
            previous = Vector3(u, v, 0.0)
            uv[offset + at] = Vector3(u * uscale, v * vscale, 0.0)
            if loop == 0 and at == 0:
                anchor = previous
        offset += (usize)sizes[loop]
    # Each hole lies in the outer loop's turn: its start is unwrapped near
    # the outer loop's start, which may leave a hole a whole turn off when
    # the outer loop goes once round (a band); moved by whole turns into the
    # outer's span instead, whatever edge each loop starts at.
    if sizes.length > 1:
        var low = uv[0].x
        var high = uv[0].x
        for at in 0..<(usize)sizes[0]:
            low = math.min(low, uv[at].x)
            high = math.max(high, uv[at].x)
        let turn = 2.0 * math.pi * uscale
        var first = (usize)sizes[0]
        for loop in 1..<sizes.length:
            let count = (usize)sizes[loop]
            var middle = 0.0
            for at in first..<first + count: middle += uv[at].x
            middle /= (f64)count
            var shift = 0.0
            while middle + shift < low and high - low >= turn * 0.999: shift += turn
            while middle + shift > high and high - low >= turn * 0.999: shift -= turn
            if shift != 0.0:
                for at in first..<first + count: uv[at] = Vector3(uv[at].x + shift, uv[at].y, 0.0)
            first += count
    # A single loop winding once round the axis bounds a spherical cap
    # (a latitude circle, or a wavy loop such as a variable fillet's
    # contact round a dome); UV has a singular pole.
    if s.kind == surface_sphere and sizes.length == 1 and winds_once(uv, uscale):
        try spherical_cap(mesh, ids, uv, s, sense, divisions, tolerance)
        return
    # Such a loop with holes inside: an azimuthal chart about its pole.
    if s.kind == surface_sphere and sizes.length > 1:
        let outer = winding_loop(uv, sizes, uscale)
        if outer >= 0:
            try sphere_disk(mesh, ids, sizes, uv, (usize)outer, s, sense, divisions, tolerance)
            return
    var spacing = uscale * math.pi / (2.0 * (f64)divisions)
    var vertical = vscale * math.pi / (2.0 * (f64)divisions) if s.kind == surface_sphere or s.kind == surface_torus else spacing
    var minimum = uv[0]
    var maximum = uv[0]
    for p in uv:
        minimum = Vector3(math.min(minimum.x, p.x), math.min(minimum.y, p.y), 0.0)
        maximum = Vector3(math.max(maximum.x, p.x), math.max(maximum.y, p.y), 0.0)
    if edge_size == 0.0:
        # A tiny-radius, long axial strip must not request millions of square
        # cells when target edge length is off. Shared boundary samples retain
        # angular resolution; interior refinement stays bounded by divisions.
        spacing = math.max(math.min(spacing, (maximum.x - minimum.x) / (f64)divisions), (maximum.x - minimum.x) / ((f64)divisions * 4.0))
        vertical = math.max(math.min(vertical, (maximum.y - minimum.y) / (f64)divisions), (maximum.y - minimum.y) / ((f64)divisions * 4.0))
    if edge_size > 0.0:
        spacing = math.min(spacing, edge_size)
        vertical = math.min(vertical, edge_size)
    var low = mesh.points[(usize)ids[0]]
    var high = low
    for id in ids:
        let p = mesh.points[(usize)id]
        low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
        high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
    let deviation = analytic_target(s, high.subtract(low).length(), divisions, tolerance)
    # The lattice a little finer than the target, so the refinement does
    # not have to split every cell: a cylinder's rows round the axis sag
    # under `deviation`; a sphere's or a torus's triangles (whose middles
    # stray twice as far as their sides) at their widest circles and
    # meridians.
    if s.kind == surface_cylinder:
        spacing = math.min(spacing, uscale * sag_step(s.radius, deviation * 0.9))
    elif s.kind == surface_sphere:
        spacing = math.min(spacing, uscale * sag_step(s.radius, deviation * 0.45))
        vertical = math.min(vertical, vscale * sag_step(s.radius, deviation * 0.45))
    elif s.kind == surface_torus:
        spacing = math.min(spacing, uscale * sag_step(s.radius + s.angle, deviation * 0.45))
        vertical = math.min(vertical, vscale * sag_step(s.angle, deviation * 0.45))
    # Along a cylinder's or a cone's axis nothing bends: rows there only
    # shape the cells, so they are at most `divisions` apart over the face
    # and cells at most three times as long as wide.
    if (s.kind == surface_cylinder or s.kind == surface_cone) and edge_size == 0.0:
        vertical = math.min(spacing * 3.0, math.max(vertical, (maximum.y - minimum.y) / (f64)divisions))
    try lift_chart(mesh, ids, sizes, uv, s, uscale, vscale, sense, spacing, vertical, deviation)

## The trim loops `ids` (by `sizes`; their chart points `uv`, scaled by
## `uscale` and `vscale`) of a face on analytic surface `s` meshed in that
## chart: a lattice of `spacing` by `vertical` quadrangulated, refined to
## `deviation`, lifted onto `s`; the polygons face its way (`sense`).
func lift_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], uv: const Vector3[], s: Surface, uscale: f64, vscale: f64, sense: bool, spacing: f64, vertical: f64, deviation: f64) -> !:
    let normal = Vector3(0.0, 0.0, 1.0)
    let triangles = try TrimPolygon.triangulate_seams(uv, sizes, normal, ids)
    defer triangles.release()
    let constraints = try TrimConstraints.build(uv, ids, sizes)
    defer constraints.close()
    let gridded = try insert_grid(triangles, normal, spacing, vertical, constraints)
    defer gridded.release()
    let improved = try improve(gridded, normal, ids, constraints)
    defer improved.release()
    var lift = ChartLift(surface = s, uscale = uscale, vscale = vscale)
    let refined = try chart_refine(improved, &lift, deviation, ids, constraints)
    defer refined.release()
    let part = try recombine(refined, normal, constraints)
    defer part.release()
    let mapped = try new i64[(usize)part.value().point_count()] --- in memory.heap
    defer free(mapped) in memory.heap
    for at in 0..<mapped.length:
        let p = try part.value().point((i64)at)
        mapped[at] = ids[at] if at < ids.length else (try mesh.point(analytic_point(s, p.x / uscale, p.y / vscale)))
    for face in 0..<part.value().face_count():
        let count = try part.value().face_size(face)
        try mesh.face(count)
        for at in 0..<count:
            try mesh.corner(mapped[(usize)(try part.value().face_point(face, at if sense else count - 1 - at))])

## Whether a loop's chart points (u unwrapped, scaled by `uscale`) go
## round the axis once, every step turning the same way: rows from each
## point straight to the pole then never cross.
func winds_once(uv: const Vector3[], uscale: f64) -> bool:
    let turn = 2.0 * math.pi * uscale
    var total: f64 = 0.0
    var sign: f64 = 0.0
    for at in 0..<uv.length:
        let next = uv[(at + 1) % uv.length].x
        var step = next - uv[at].x
        # The closing step comes back from the unwrapped end.
        if at + 1 == uv.length: step = wrap(next / uscale, uv[at].x / uscale) * uscale - uv[at].x
        if step == 0.0 or step * sign < 0.0: return false
        sign = step
        total += step
    return math.abs(math.abs(total) - turn) <= turn * 1e-9

## A spherical cap's mesh: rows from each boundary point along its
## meridian to the pole the loop goes round (north when it turns
## counterclockwise about the face's normal), `divisions` of them or as
## many as keep the sphere's target inside the cells, thinning out towards
## the pole and closed by a fan there (polar_rows). Going east along the
## loop and north to the pole faces out, so the corners' own order faces
## the face's way.
func spherical_cap(mesh: MeshBuilder*, ids: const i64[], uv: const Vector3[], s: Surface, sense: bool, divisions: i64, tolerance: f64) -> !:
    let north = (uv[uv.length - 1].x > uv[0].x) == sense
    let pole_v = math.pi * (0.5 if north else -0.5)
    let longitudes = try new f64[ids.length] --- in memory.heap
    defer free(longitudes) in memory.heap
    let starts = try new f64[ids.length] --- in memory.heap
    defer free(starts) in memory.heap
    var mean: f64 = 0.0
    for at in 0..<ids.length:
        longitudes[at] = uv[at].x / s.radius
        starts[at] = uv[at].y / s.radius
        mean += starts[at]
    mean /= (f64)ids.length
    let step = sag_step(s.radius, analytic_target(s, 0.0, divisions, tolerance) * 0.45)
    let rows = (usize)math.max((f64)divisions, math.ceil(math.abs(pole_v - mean) / step))
    try polar_rows(mesh, s, ids, longitudes, starts, pole_v, rows, false)