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