dymokomi/luce-cad
Source of release 0.9.1
0.9.1 / src / tessellation / improve.lucb
## Bounded Lawson-style interior edge flips; trim boundaries remain constrained.
import interop
import memory
from luce_std import math
from luce_geocore.geocore import Mesh, MeshBuilder, Vector3, invalid
from tessellation.constraints import TrimConstraints
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