Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / polygons / improve.lucb

## Bounded Lawson-style interior edge flips; trim boundaries remain constrained.

pub func improve(source: interop.Reference[Mesh], normal: Vector3, boundary_ids: const i64[], constraints: TrimConstraints = TrimConstraints()) -> interop.Reference[Mesh]!:
    let mesh = source.value()
    let count = (usize)mesh.face_count()
    if count > 262144:
        error(invalid, "planar improvement exceeds triangle budget")
    let corners = try new i64[count * 3] --- in memory.heap
    defer free(corners) in memory.heap
    for face in 0..<count:
        if (try mesh.face_size((i64)face)) != 3:
            error(invalid, "planar improvement requires triangles")
        for at in 0..<3:
            corners[face * 3 + (usize)at] = try mesh.face_point((i64)face, at)
    let slots = try new i64[count * 6 + 1] --- in memory.heap
    defer free(slots) in memory.heap
    let dirty = try new bool[count] --- in memory.heap
    defer free(dirty) in memory.heap
    let n = try normal.normalized()
    # Rebuild adjacency per sweep; only disjoint pairs change in each sweep.
    # This keeps queued/stale edges from modifying a triangle twice.
    for pass in 0..<128:
        for index in 0..<slots.length:
            slots[index] = -1
        for face in 0..<count:
            dirty[face] = false
        var changes: usize = 0
        for corner in 0..<corners.length:
            let face = corner // 3
            if dirty[face]:
                continue
            let at = corner % 3
            let a = corners[corner]
            let b = corners[face * 3 + (at + 1) % 3]
            if constraints.contains(a, b): continue
            let lo = a if a < b else b
            let hi = b if a < b else a
            var slot = (usize)(lo * 8388609 + hi) % slots.length
            while slots[slot] >= 0:
                let previous = (usize)slots[slot]
                let pa = corners[previous]
                let pb = corners[previous // 3 * 3 + (previous % 3 + 1) % 3]
                if (pa == a and pb == b) or (pa == b and pb == a):
                    break
                slot = (slot + 1) % slots.length
            if slots[slot] < 0:
                slots[slot] = (i64)corner
                continue
            let previous = (usize)slots[slot]
            let other = previous // 3
            if dirty[other] or other == face:
                continue
            let c = corners[face * 3 + (at + 2) % 3]
            let d = corners[other * 3 + (previous % 3 + 2) % 3]
            if a == d or b == d or c == d:
                continue
            # Distinct UV seam vertices may identify the same CAD vertex.
            # A new diagonal must not collapse when lifted into the solid.
            if (usize)c < boundary_ids.length and (usize)d < boundary_ids.length and boundary_ids[(usize)c] == boundary_ids[(usize)d]:
                continue
            let pa = try mesh.point(a)
            let pb = try mesh.point(b)
            let pc = try mesh.point(c)
            let pd = try mesh.point(d)
            if not should_flip(pa, pb, pc, pd, n):
                continue
            corners[face * 3] = c
            corners[face * 3 + 1] = a
            corners[face * 3 + 2] = d
            corners[other * 3] = c
            corners[other * 3 + 1] = d
            corners[other * 3 + 2] = b
            dirty[face] = true
            dirty[other] = true
            changes += 1
        if changes == 0:
            break
    var output = try MeshBuilder(precise = true)
    defer output.close()
    for point in 0..<mesh.point_count():
        _ = try output.point(try mesh.point(point))
    for face in 0..<count:
        try output.face(3)
        for at in 0..<3:
            try output.corner(corners[face * 3 + (usize)at])
    return try output.finish()

func should_flip(a: Vector3, b: Vector3, c: Vector3, d: Vector3, normal: Vector3) -> bool:
    let ad = a.subtract(d)
    let bd = b.subtract(d)
    let cd = c.subtract(d)
    let aa = ad.dot(ad)
    let bb = bd.dot(bd)
    let cc = cd.dot(cd)
    let scale = math.max(aa, math.max(bb, cc))
    # Convexity has area units. A fixed world-space floor prevents legitimate
    # flips on small CAD parts, leaving refinement to repeatedly split slivers.
    let epsilon = math.max(1e-30, scale * 1e-14)
    # Only a strictly convex union can exchange its interior diagonal.
    if a.subtract(c).cross(d.subtract(c)).dot(normal) <= epsilon or d.subtract(c).cross(b.subtract(c)).dot(normal) <= epsilon:
        return false
    let determinant = aa * bd.cross(cd).dot(normal) - bb * ad.cross(cd).dot(normal) + cc * ad.cross(bd).dot(normal)
    return determinant > scale * epsilon