Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / meshing / mapped_spacing.lucb

## Physical spacing of mapped interiors; every trim/boundary vertex stays fixed.

## Redistribute complete interior rows, including their first/last intervals.
## Accept only improved spacing, an unfolded UV grid, and sampled display error
## no greater than the original grid or the tessellation display-error budget.
## The CAD boundary tolerance remains unchanged. Work is bounded.
pub func redistribute_grid(grid: Vector3[], nx: usize, ny: usize, s: Surface, tolerance: f64, forward: bool = true, divisions: i64 = 16) -> !:
    if s.kind != surface_spline or nx < 2 or ny < 2: return
    let points = try new Vector3[grid.length] --- in memory.heap
    defer free(points) in memory.heap
    for at in 0..<grid.length: points[at] = try evaluate(s, grid[at])
    var quality = uneven(points, nx, ny)
    if quality < 1.5: return
    let candidate = try new Vector3[grid.length] --- in memory.heap
    defer free(candidate) in memory.heap
    let proposed = try new Vector3[grid.length] --- in memory.heap
    defer free(proposed) in memory.heap
    let lengths = try new f64[(nx if nx > ny else ny) + 1] --- in memory.heap
    defer free(lengths) in memory.heap
    var low = points[0]
    var high = points[0]
    for p in points:
        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 target = math.max(tolerance, high.subtract(low).length() / ((f64)divisions * (f64)divisions * 16.0))
    let limit = math.max(target * target, (try grid_deviation(grid, points, nx, ny, s, forward)) * (1.0 + 1e-8))
    for pass in 0..<3:
        var accepted = false
        for axis in 0..<(usize)2:
            memory.copy(candidate, grid, grid.length)
            let along = nx if axis == 0 else ny
            let across = ny if axis == 0 else nx
            let stride = 1 if axis == 0 else nx + 1
            for line in 1..<across:
                let start = line * (nx + 1) if axis == 0 else line
                lengths[0] = 0.0
                for at in 1..<along + 1:
                    lengths[at] = lengths[at - 1] + points[start + at * stride].subtract(points[start + (at - 1) * stride]).length()
                var segment: usize = 0
                for at in 1..<along:
                    let distance = lengths[along] * (f64)at / (f64)along
                    while segment + 1 < along and lengths[segment + 1] < distance: segment += 1
                    let span = lengths[segment + 1] - lengths[segment]
                    let t = (distance - lengths[segment]) / span if span > 1e-30 else 0.5
                    candidate[start + at * stride] = grid[start + segment * stride].multiply_scalar(1.0 - t).add(grid[start + (segment + 1) * stride].multiply_scalar(t))
            if not grid_oriented(candidate, grid, nx, ny): continue
            for at in 0..<candidate.length: proposed[at] = try evaluate(s, candidate[at])
            let updated = uneven(proposed, nx, ny)
            if updated > quality * (1.0 + 1e-6) or grid_energy(proposed, nx, ny) >= grid_energy(points, nx, ny) * (1.0 - 1e-6): continue
            if try grid_deviation(candidate, proposed, nx, ny, s, forward) > limit: continue
            memory.copy(grid, candidate, grid.length)
            memory.copy(points, proposed, grid.length)
            quality = updated
            accepted = true
        if not accepted or quality < 1.05: break

# Sum normalized gap variance so improving one direction is not blocked by an
# unchanged worst row in the other direction. Keep the worst-ratio guard too.
func grid_energy(points: const Vector3[], nx: usize, ny: usize) -> f64:
    var result: f64 = 0.0
    for axis in 0..<(usize)2:
        let along = nx if axis == 0 else ny
        let across = ny if axis == 0 else nx
        let stride = 1 if axis == 0 else nx + 1
        for line in 1..<across:
            let start = line * (nx + 1) if axis == 0 else line
            var length: f64 = 0.0
            var square: f64 = 0.0
            for at in 0..<along:
                let gap = points[start + (at + 1) * stride].subtract(points[start + at * stride]).length()
                length += gap
                square += gap * gap
            if length > 1e-14: result += math.max(0.0, (f64)along * square / (length * length) - 1.0)
    return result

func uneven(points: const Vector3[], nx: usize, ny: usize) -> f64:
    var result: f64 = 1.0
    for axis in 0..<(usize)2:
        let along = nx if axis == 0 else ny
        let across = ny if axis == 0 else nx
        let stride = 1 if axis == 0 else nx + 1
        for line in 1..<across:
            let start = line * (nx + 1) if axis == 0 else line
            var low: f64 = 1e100
            var high: f64 = 0.0
            for at in 0..<along:
                let gap = points[start + (at + 1) * stride].subtract(points[start + at * stride]).length()
                low = math.min(low, gap)
                high = math.max(high, gap)
            if low > 1e-14: result = math.max(result, high / low)
    return result

func grid_oriented(candidate: const Vector3[], original: const Vector3[], nx: usize, ny: usize) -> bool:
    for row in 0..<ny:
        for column in 0..<nx:
            let at = row * (nx + 1) + column
            let ids = [at, at + 1, at + nx + 2, at + nx + 1]
            for corner in 0..<(usize)4:
                let a = ids[corner]
                let b = ids[(corner + 1) % 4]
                let c = ids[(corner + 2) % 4]
                let before = original[b].subtract(original[a]).cross(original[c].subtract(original[b])).z
                let after = candidate[b].subtract(candidate[a]).cross(candidate[c].subtract(candidate[b])).z
                if math.abs(after) < 1e-16 or before * after <= 0.0: return false
    return true

# Same diagonal as the convex-quad display triangulator, with edge midpoints
# and centroids sampled on the exact surface. Not a certified deviation bound.
func grid_deviation(uv: const Vector3[], points: const Vector3[], nx: usize, ny: usize, s: Surface, forward: bool) -> f64!:
    var maximum: f64 = 0.0
    for row in 0..<ny:
        for column in 0..<nx:
            let at = row * (nx + 1) + column
            let ids = [at, at + 1, at + nx + 2, at + nx + 1]
            for triangle in 0..<(usize)2:
                let a = ids[3 if forward else 0] if triangle == 0 else ids[1 if forward else 2]
                let b = ids[0 if forward else 3] if triangle == 0 else ids[2 if forward else 1]
                let c = ids[1 if forward else 2] if triangle == 0 else ids[3 if forward else 0]
                for p in [uv[a].add(uv[b]).add(uv[c]).multiply_scalar(1.0 / 3.0), uv[a].add(uv[b]).multiply_scalar(0.5), uv[b].add(uv[c]).multiply_scalar(0.5), uv[c].add(uv[a]).multiply_scalar(0.5)]:
                    maximum = math.max(maximum, squared_triangle_distance(try evaluate(s, p), points[a], points[b], points[c]))
    return maximum