Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / src / meshing / adaptive_uv.lucb

## Curvature-driven interior refinement. Boundary IDs never change; both faces
## incident to a split UV edge consume its one shared midpoint. No T-junctions.
##
## A face's target is `tolerance`, or, beside a frozen side (the boundary's
## or a trim constraint's, which no pass splits), that side's own sag: a
## triangle on a frozen side keeps it however often it is split, so a
## tighter target there is never met. (The tessellator samples shared
## edges to their faces' targets first, so this matters only for small
## differences.) Refinement also stops when its worst excess stops falling,
## and at the face budget it keeps the mesh it has: a coarser face, never
## a missing one.

func chart_sample(s: Surface, p: Vector3, uscale: f64, vscale: f64) -> Vector3!:
    if s.kind != surface_spline: return analytic_point(s, p.x / uscale, p.y / vscale)
    let u0 = s.ku[(usize)s.du]
    let v0 = s.kv[(usize)s.dv]
    return try s.at(math.clamp(u0 + (s.ku[(usize)s.nu] - u0) * p.x / uscale, u0, s.ku[(usize)s.nu]), math.clamp(v0 + (s.kv[(usize)s.nv] - v0) * p.y / vscale, v0, s.kv[(usize)s.nv]))

pub func refine_uv(source: interop.Reference[Mesh], surface: Surface, uscale: f64, vscale: f64, tolerance: f64, constraints: TrimConstraints = TrimConstraints()) -> interop.Reference[Mesh]!:
    var current = source.clone()
    errdefer current.release()
    var previous: f64 = 1e300
    for pass in 0..<8:
        if current.value().face_count() > face_budget: break
        var excess: f64 = 0.0
        let next = try refine_pass(current, surface, uscale, vscale, tolerance, constraints, &excess)
        let finished = next.value().point_count() == current.value().point_count()
        current.release()
        current = next
        # A pass whose worst triangle is hardly better than the last one's
        # is splitting what splitting cannot fix.
        if finished or excess > previous * 0.81: break
        previous = excess
    return current

## The most triangles a face's refinement grows to.
let face_budget: i64 = 131072

## One pass: split the sides whose midpoint, and the faces whose center,
## lie further from the surface than their target. `excess` receives the
## worst squared deviation over its target (1 when nothing is split).
func refine_pass(source: interop.Reference[Mesh], surface: Surface, uscale: f64, vscale: f64, tolerance: f64, constraints: TrimConstraints, excess: f64*) -> interop.Reference[Mesh]!:
    let input = source.value()
    let worlds = try new Vector3[(usize)input.point_count()] --- in memory.heap
    defer free(worlds) in memory.heap
    for at in 0..<worlds.length: worlds[at] = try chart_sample(surface, try input.point((i64)at), uscale, vscale)
    let uses = try new usize[(usize)(try input.edge_count())] --- in memory.heap
    defer free(uses) in memory.heap
    let splits = try new i64[uses.length] --- in memory.heap
    defer free(splits) in memory.heap
    let adjacent = try new i64[uses.length * 2] --- in memory.heap
    defer free(adjacent) in memory.heap
    for at in 0..<uses.length:
        uses[at] = 0
        splits[at] = -1
    for face in 0..<input.face_count():
        for at in 0..<(try input.face_size(face)):
            let edge = (usize)(try input.face_edge(face, at))
            if uses[edge] < 2: adjacent[edge * 2 + uses[edge]] = face
            uses[edge] += 1
    # Each face's squared target: the tolerance, or its frozen sides' sag
    # (with a margin, as the sag is sampled at one point).
    let targets = try new f64[(usize)input.face_count()] --- in memory.heap
    defer free(targets) in memory.heap
    for at in 0..<targets.length: targets[at] = tolerance * tolerance
    for edge in 0..<(try input.edge_count()):
        let a = try input.edge_point(edge, 0)
        let b = try input.edge_point(edge, 1)
        if uses[(usize)edge] == 2 and not constraints.contains(a, b): continue
        let midpoint = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
        let chord = worlds[(usize)a].add(worlds[(usize)b]).multiply_scalar(0.5)
        let sag = (try chart_sample(surface, midpoint, uscale, vscale)).subtract(chord).length() * 1.25
        for side in 0..<(uses[(usize)edge] if uses[(usize)edge] < 2 else (usize)2):
            let face = (usize)adjacent[(usize)edge * 2 + side]
            targets[face] = math.max(targets[face], sag * sag)
    var worst: f64 = 0.0
    var output = try MeshBuilder(precise = true)
    defer output.close()
    try output.copy_points(input)
    for edge in 0..<(try input.edge_count()):
        if uses[(usize)edge] != 2: continue
        let a = try input.edge_point(edge, 0)
        let b = try input.edge_point(edge, 1)
        if constraints.contains(a, b): continue
        let midpoint = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
        let p = try chart_sample(surface, midpoint, uscale, vscale)
        # Measure geometric deflection, not parameterization speed. Comparing
        # positions at equal parameters over-refines even a flat skewed patch.
        let first = adjacent[(usize)edge * 2]
        let second = adjacent[(usize)edge * 2 + 1]
        let squared = math.min(try face_deviation(input, worlds, first, p), try face_deviation(input, worlds, second, p))
        let target = math.max(targets[(usize)first], targets[(usize)second])
        if squared > target:
            splits[(usize)edge] = try output.point(midpoint)
            worst = math.max(worst, squared / target)
    for face in 0..<input.face_count():
        let count = try input.face_size(face)
        let center = try input.face_center(face)
        let world = try chart_sample(surface, center, uscale, vscale)
        let target = targets[(usize)face]
        var split = false
        var all = true
        for at in 0..<count:
            let exists = splits[(usize)(try input.face_edge(face, at))] >= 0
            split = split or exists
            all = all and exists
        var deviation = try face_deviation(input, worlds, face, world)
        if count == 4:
            let a = try input.face_point(face, 0)
            let b = try input.face_point(face, 2)
            let uv = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
            deviation = math.max(deviation, try face_deviation(input, worlds, face, try chart_sample(surface, uv, uscale, vscale)))
        if deviation > target:
            split = true
            worst = math.max(worst, deviation / target)
        if not split:
            try output.copy_face(input, face)
            continue
        if count == 3:
            let vertices = [try input.face_point(face, 0), try input.face_point(face, 1), try input.face_point(face, 2)]
            let cuts = [splits[(usize)(try input.face_edge(face, 0))], splits[(usize)(try input.face_edge(face, 1))], splits[(usize)(try input.face_edge(face, 2))]]
            let nf = output.nf
            let nc = output.nc
            if not center_conditioned(&output, vertices, cuts, center) and (try split_triangle(&output, vertices, cuts)):
                # A good UV diagonal need not be good on a curved support.
                # Keep edge-only refinement only when every lifted child has
                # the support's orientation; otherwise retain the center path.
                if try faces_outward(&output, nc, surface, uscale, vscale): continue
                output.nf = nf
                output.nc = nc
        let middle = try output.point(center)
        for at in 0..<count:
            let a = try input.face_point(face, at)
            let b = try input.face_point(face, (at + 1) % count)
            let cut = splits[(usize)(try input.face_edge(face, at))]
            if all and count == 4:
                try output.face(4)
                for id in [a, cut, middle, splits[(usize)(try input.face_edge(face, (at + count - 1) % count))]]: try output.corner(id)
            elif cut >= 0:
                try add_triangle(&output, a, cut, middle)
                try add_triangle(&output, cut, b, middle)
            else:
                try add_triangle(&output, a, b, middle)
    *excess = worst if worst > 0.0 else 1.0
    if output.np == (usize)input.point_count(): return source.clone()
    return try output.finish()

func face_deviation(mesh: Mesh*, points: const Vector3[], face: i64, p: Vector3) -> f64!:
    let a = points[(usize)(try mesh.face_point(face, 0))]
    var distance: f64 = 1e100
    for at in 1..<(try mesh.face_size(face)) - 1:
        distance = math.min(distance, squared_triangle_distance(p, a, points[(usize)(try mesh.face_point(face, at))], points[(usize)(try mesh.face_point(face, at + 1))]))
    return distance

func faces_outward(mesh: const MeshBuilder*, start: usize, surface: Surface, uscale: f64, vscale: f64) -> bool!:
    for at in 0..<(mesh.nc - start) // 3:
        var uv = [Vector3(), Vector3(), Vector3()]
        var p = uv
        for i in 0..<(usize)3:
            uv[i] = mesh.points[(usize)mesh.corners[start + at * 3 + i]]
            p[i] = try chart_sample(surface, uv[i], uscale, vscale)
        let cross = p[1].subtract(p[0]).cross(p[2].subtract(p[0]))
        for q in uv:
            let n = try support_normal(surface, Vector3(q.x / uscale, q.y / vscale, 0.0))
            if cross.dot(n) <= cross.length() * 1e-10: return false
    return true