Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / polygons / recombine.lucb

## Conservative planar triangle pairing. Never moves points or removes boundaries.
## Greedy quality-ranked matching, not Blossom or field-aligned remeshing.

struct Candidate:
    let first: i64
    let second: i64
    let a: i64
    let b: i64
    let c: i64
    let d: i64
    var quality: f64

pub func recombine(source: interop.Reference[Mesh], normal: Vector3, constraints: TrimConstraints = TrimConstraints()) -> interop.Reference[Mesh]!:
    let input = source.value()
    let count = (usize)input.face_count()
    if count > 262144:
        error(invalid, "planar recombination exceeds face budget")
    let n = try normal.normalized()
    let owners = try new i64[count * 6 + 1] --- in memory.heap
    defer free(owners) in memory.heap
    let starts = try new i64[owners.length] --- in memory.heap
    defer free(starts) in memory.heap
    let ends = try new i64[owners.length] --- in memory.heap
    defer free(ends) in memory.heap
    let candidates = try new Candidate[count * 3] --- in memory.heap
    defer free(candidates) in memory.heap
    let matched = try new i64[count] --- in memory.heap
    defer free(matched) in memory.heap
    for index in 0..<owners.length:
        owners[index] = -1
    for index in 0..<count:
        matched[index] = -1
    var used: usize = 0
    for face in 0..<count:
        if (try input.face_size((i64)face)) != 3:
            error(invalid, "planar recombination requires triangles")
        for corner in 0..<3:
            let a = try input.face_point((i64)face, corner)
            let b = try input.face_point((i64)face, (corner + 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) % owners.length
            while owners[slot] >= 0 and (starts[slot] != lo or ends[slot] != hi):
                slot = (slot + 1) % owners.length
            if owners[slot] < 0:
                owners[slot] = (i64)face
                starts[slot] = lo
                ends[slot] = hi
                continue
            let other = owners[slot]
            let c = try input.face_point((i64)face, (corner + 2) % 3)
            var d: i64 = -1
            for item in 0..<3:
                let p = try input.face_point(other, item)
                if p != a and p != b:
                    d = p
            if d < 0 or d == c:
                continue
            let quality = quad_quality(try input.point(c), try input.point(a), try input.point(d), try input.point(b), n)
            if quality > 0.3420201433256687:
                candidates[used] = Candidate((i64)face, other, c, a, d, b, quality)
                used += 1
    # Higher minimum corner sine first; deterministic ties by traversal order.
    # A stable max heap preserves the previous greedy ordering in O(n log n),
    # instead of scanning every candidate for every matched pair (quadratic).
    let heap = try new usize[used] --- in memory.heap
    defer free(heap) in memory.heap
    for index in 0..<used:
        heap[index] = index
        var at = index
        while at > 0:
            let parent = (at - 1) // 2
            if not better(candidates, heap[at], heap[parent]):
                break
            let swap = heap[at]
            heap[at] = heap[parent]
            heap[parent] = swap
            at = parent
    var remaining = used
    while remaining > 0:
        let best = (i64)heap[0]
        remaining -= 1
        heap[0] = heap[remaining]
        var at: usize = 0
        while at * 2 + 1 < remaining:
            var child = at * 2 + 1
            if child + 1 < remaining and better(candidates, heap[child + 1], heap[child]):
                child += 1
            if not better(candidates, heap[child], heap[at]):
                break
            let swap = heap[at]
            heap[at] = heap[child]
            heap[child] = swap
            at = child
        let candidate = candidates[(usize)best]
        if matched[(usize)candidate.first] >= 0 or matched[(usize)candidate.second] >= 0:
            continue
        matched[(usize)candidate.first] = best
        matched[(usize)candidate.second] = best
    var output = try MeshBuilder(precise = true)
    defer output.close()
    for point in 0..<input.point_count():
        _ = try output.point(try input.point(point))
    for face in 0..<count:
        let index = matched[face]
        if index < 0:
            try output.face(3)
            for corner in 0..<3:
                try output.corner(try input.face_point((i64)face, corner))
        else:
            let candidate = candidates[(usize)index]
            if candidate.first != (i64)face:
                continue
            try output.face(4)
            for point in [candidate.a, candidate.b, candidate.c, candidate.d]:
                try output.corner(point)
    return try output.finish()

func better(candidates: const Candidate[], a: usize, b: usize) -> bool:
    return candidates[a].quality > candidates[b].quality or (candidates[a].quality == candidates[b].quality and a < b)

func quad_quality(a: Vector3, b: Vector3, c: Vector3, d: Vector3, normal: Vector3) -> f64:
    let points = [a, b, c, d]
    var score: f64 = 1.0
    var shortest: f64 = 1e100
    var longest: f64 = 0.0
    for index in 0..<4:
        let incoming = points[index].subtract(points[(index + 3) % 4])
        let outgoing = points[(index + 1) % 4].subtract(points[index])
        let il = incoming.length()
        let ol = outgoing.length()
        if il <= 0.000000001 or ol <= 0.000000001:
            return 0.0
        let corner = incoming.cross(outgoing).dot(normal) / (il * ol)
        if corner <= 0.0:
            return 0.0
        score = math.min(score, corner)
        shortest = math.min(shortest, ol)
        longest = math.max(longest, ol)
    return score if longest <= shortest * 10.0 else 0.0