Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / src / layout / trim_alignment.lucb

## Align numerical grid incidence without moving canonical CAD positions.

pub func align(uv: Vector3[], sizes: const i64[], ids: const i64[], canonical: const Vector3[], surface: Surface, plan: GridLayout, tolerance: f64) -> !:
    let original_uv = try new Vector3[uv.length] --- in memory.heap
    defer free(original_uv) in memory.heap
    memory.copy(original_uv, uv, uv.length)
    var begin: usize = 0
    for size in sizes:
        let count = (usize)size
        for at in 0..<count:
            let index = begin + at
            let previous = begin + (at + count - 1) % count
            let next = begin + (at + 1) % count
            let p = canonical[(usize)ids[index]]
            let before = canonical[(usize)ids[previous]]
            let after = canonical[(usize)ids[next]]
            let spacing = math.min(p.subtract(before).length(), p.subtract(after).length())
            let budget = math.min(tolerance * 0.05, spacing * 0.2)
            let original = try surface_point(surface, uv[index])
            for axis in 0..<(usize)2:
                let stations = plan.u if axis == 0 else plan.v
                let value = coordinate(uv[index], axis)
                let aligned = nearest(stations, value)
                let a = coordinate(original_uv[previous], axis)
                let b = coordinate(original_uv[next], axis)
                let candidate = Vector3(aligned, uv[index].y, 0.0) if axis == 0 else Vector3(uv[index].x, aligned, 0.0)
                let incidence = plan.epsilon * 1e-5
                # A sampled extremum within the graze budget of a line, on
                # either side, touches it: reconcile left an overshooting one
                # uncut (trim_crossings.grazes), and one stopping short would
                # leave a sub-tolerance gap. Either way it lands on the line.
                let grazing = aligned != value and (a - aligned) * (b - aligned) > 0.0
                if math.abs(aligned - value) > incidence and not grazing and (aligned <= math.min(a, b) or aligned >= math.max(a, b)): continue
                let support = try surface_point(surface, candidate)
                let limit = graze_budget(spacing, tolerance) if grazing else budget
                if support.subtract(original).length() <= limit and support.subtract(p).length() <= tolerance: uv[index] = candidate
        begin += count
    # Crossings above can land beside a numerical endpoint that was visited
    # earlier. Resolve that incidence only after all crossings are aligned.
    # This is not geometric trim smoothing: the allowance is a few incidence
    # units, and it must join an existing aligned neighbor without changing
    # the directed polygon or moving any canonical 3D vertex.
    begin = 0
    for size in sizes:
        let count = (usize)size
        for at in 0..<count:
            let index = begin + at
            let previous = begin + (at + count - 1) % count
            let next = begin + (at + 1) % count
            let p = canonical[(usize)ids[index]]
            let budget = math.min(tolerance * 0.05, math.min(p.subtract(canonical[(usize)ids[previous]]).length(), p.subtract(canonical[(usize)ids[next]]).length()) * 0.2)
            let original = try surface_point(surface, uv[index])
            for axis in 0..<(usize)2:
                let value = coordinate(uv[index], axis)
                let target = nearest(plan.u if axis == 0 else plan.v, value)
                let incidence = math.max(1e-13, plan.epsilon * 1e-5)
                if target == value or math.abs(target - value) > incidence * 16.0: continue
                if math.min(math.abs(coordinate(uv[previous], axis) - target), math.abs(coordinate(uv[next], axis) - target)) > incidence: continue
                let candidate = Vector3(target, uv[index].y, 0.0) if axis == 0 else Vector3(uv[index].x, target, 0.0)
                if not safe_corner(uv, sizes, ids, begin, count, at, candidate): continue
                let support = try surface_point(surface, candidate)
                if support.subtract(original).length() <= budget and support.subtract(p).length() <= tolerance: uv[index] = candidate
        begin += count

## Put each trim point still beside a grid line by less than the layout's
## own precision (`plan.epsilon`, half of it) onto that line, when the line
## crosses one of the point's sides: crossings are solved only to that
## precision, and clipping takes a trim side that far over a line as not
## crossing it, so a point left a hair beside a line leaves a cell boundary
## that does not close. Only chart coordinates move, by less than the
## crossings' own error; a point whose identity repeats (a seam's two
## images) stays.
pub func settle(uv: Vector3[], sizes: const i64[], ids: const i64[], plan: GridLayout) -> !:
    let reach = plan.epsilon * 0.5
    let seen = try new i64[ids.length * 2 + 1] --- in memory.heap
    defer free(seen) in memory.heap
    let repeated = try new bool[ids.length] --- in memory.heap
    defer free(repeated) in memory.heap
    for at in 0..<seen.length: seen[at] = -1
    for at in 0..<ids.length:
        repeated[at] = false
        var slot = (usize)ids[at] % seen.length
        while seen[slot] >= 0 and ids[(usize)seen[slot]] != ids[at]: slot = (slot + 1) % seen.length
        if seen[slot] < 0: seen[slot] = (i64)at
        else:
            repeated[at] = true
            repeated[(usize)seen[slot]] = true
    var begin: usize = 0
    for size in sizes:
        let count = (usize)size
        for k in 0..<count:
            let at = begin + k
            if repeated[at]: continue
            let previous = uv[begin + (k + count - 1) % count]
            let next = uv[begin + (k + 1) % count]
            for axis in 0..<(usize)2:
                let value = coordinate(uv[at], axis)
                let line = nearest(plan.u if axis == 0 else plan.v, value)
                let distance = math.abs(line - value)
                if distance == 0.0 or distance >= reach: continue
                # The line must cross a side of the point's.
                if (coordinate(previous, axis) - line) * (value - line) >= 0.0 and (coordinate(next, axis) - line) * (value - line) >= 0.0: continue
                uv[at] = Vector3(line, uv[at].y, 0.0) if axis == 0 else Vector3(uv[at].x, line, 0.0)
        begin += count

func nearest(stations: Stations, value: f64) -> f64:
    var low: usize = 0
    var high = stations.count - 1
    while high - low > 1:
        let mid = (low + high) // 2
        if stations.values[mid] <= value: low = mid
        else: high = mid
    return stations.values[low] if math.abs(stations.values[low] - value) <= math.abs(stations.values[high] - value) else stations.values[high]

func safe_corner(uv: const Vector3[], sizes: const i64[], ids: const i64[], begin: usize, count: usize, at: usize, candidate: Vector3) -> bool:
    let index = begin + at
    # Moving one occurrence of a pinched/seam identity would separate its UV
    # aliases. Those cases need a joint proposal, not this single-corner repair.
    for other in 0..<ids.length:
        if other != index and ids[other] == ids[index]: return false
    for offset in [count - 1, (usize)0, (usize)1]:
        let center = (at + offset) % count
        let ia = begin + (center + count - 1) % count
        let ib = begin + center
        let ic = begin + (center + 1) % count
        let old = uv[ib].subtract(uv[ia]).cross(uv[ic].subtract(uv[ib])).z
        let a = candidate if ia == index else uv[ia]
        let b = candidate if ib == index else uv[ib]
        let c = candidate if ic == index else uv[ic]
        let updated = b.subtract(a).cross(c.subtract(b)).z
        if old != 0.0 and old * updated < 0.0: return false
        # Resolving numerical incidence may straighten a corner. Collinear
        # ordered trim vertices are valid and retain their distinct CAD IDs;
        # only collapsed or backtracking segments are forbidden here.
        if updated == 0.0 and b.subtract(a).dot(c.subtract(b)) <= 0.0: return false
    for neighbor in [begin + (at + count - 1) % count, begin + (at + 1) % count]:
        var base: usize = 0
        for size in sizes:
            for edge in 0..<(usize)size:
                let a = base + edge
                let b = base + (edge + 1) % (usize)size
                if a == index or b == index or a == neighbor or b == neighbor: continue
                if intersect(uv[neighbor], candidate, uv[a], uv[b]): return false
            base += (usize)size
    return true

func intersect(a: Vector3, b: Vector3, c: Vector3, d: Vector3) -> bool:
    if math.max(a.x, b.x) < math.min(c.x, d.x) or math.max(c.x, d.x) < math.min(a.x, b.x) or math.max(a.y, b.y) < math.min(c.y, d.y) or math.max(c.y, d.y) < math.min(a.y, b.y): return false
    let ab = b.subtract(a)
    let cd = d.subtract(c)
    return ab.cross(c.subtract(a)).z * ab.cross(d.subtract(a)).z <= 0.0 and cd.cross(a.subtract(c)).z * cd.cross(b.subtract(c)).z <= 0.0