dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / polygons / improve.lucb
## Lawson edge flips towards a Delaunay triangulation; trim boundaries remain
## constrained.
##
## The flips run from a queue of sides to check: each flip queues the four
## sides of its quad, so a change travels as far as it has to in one run.
## (Sweeps over every side, each flipping disjoint pairs, need a sweep per
## step of travel: a fan of long slivers from one boundary point across a
## row of grid points unwinds one triangle per sweep, and a bounded number
## of sweeps left such fans for the refinement to split until it ran out of
## budget.)
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 points = try new Vector3[(usize)mesh.point_count()] --- in memory.heap
defer free(points) in memory.heap
for at in 0..<points.length: points[at] = try mesh.point((i64)at)
# twin[k]: the corner whose side runs back along corner k's side (from
# corners[k] to the next corner), or -1 on the boundary, on a constraint
# and on a side more than two triangles share.
let twin = try twins(corners, constraints)
defer free(twin) in memory.heap
let n = try normal.normalized()
var queue = Growing[i64]()
defer queue.close()
for corner in 0..<corners.length:
if twin[corner] > (i64)corner: try queue.push((i64)corner)
# Delaunay flips end on their own; the bound only guards rounding.
var budget = corners.length * 16
while queue.count > 0 and budget > 0:
queue.count -= 1
let corner = (usize)queue.items[queue.count]
let other = twin[corner]
if other < 0: continue
let a = corners[corner]
let b = corners[after_corner(corner)]
let c = corners[before_corner(corner)]
let d = corners[before_corner((usize)other)]
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
if not should_flip(points[(usize)a], points[(usize)b], points[(usize)c], points[(usize)d], n):
continue
budget -= 1
flip(corners, twin, corner, (usize)other)
let face = corner // 3
let o = (usize)other // 3
for k in [face * 3, face * 3 + 1, o * 3 + 1, o * 3 + 2]:
if twin[k] >= 0: try queue.push((i64)k)
var output = try MeshBuilder(precise = true)
defer output.close()
for point in points:
_ = try output.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 after_corner(corner: usize) -> usize:
return corner - corner % 3 + (corner % 3 + 1) % 3
func before_corner(corner: usize) -> usize:
return corner - corner % 3 + (corner % 3 + 2) % 3
## Each corner's twin (see improve), found through a table of sides keyed
## by their lower and higher point.
func twins(corners: const i64[], constraints: TrimConstraints) -> i64[]!:
let twin = try new i64[corners.length] --- in memory.heap
errdefer free(twin) in memory.heap
let slots = try new i64[corners.length * 2 + 1] --- in memory.heap
defer free(slots) in memory.heap
for index in 0..<slots.length: slots[index] = -1
for corner in 0..<corners.length: twin[corner] = -1
# -2 marks a side met a third time, or twice the same way: no twin.
for corner in 0..<corners.length:
let a = corners[corner]
let b = corners[after_corner(corner)]
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 seen = (usize)slots[slot]
let sa = corners[seen]
let sb = corners[after_corner(seen)]
if (sa == lo and sb == hi) or (sa == hi and sb == lo): break
slot = (slot + 1) % slots.length
if slots[slot] < 0:
slots[slot] = (i64)corner
continue
let seen = (usize)slots[slot]
if twin[seen] == -1 and corners[seen] == b and corners[after_corner(seen)] == a:
twin[seen] = (i64)corner
twin[corner] = (i64)seen
else:
if twin[seen] >= 0: twin[(usize)twin[seen]] = -2
twin[seen] = -2
twin[corner] = -2
for corner in 0..<corners.length:
if twin[corner] < 0: twin[corner] = -1
return twin
## Flip the side at `corner` (face a b c) and its twin `other` (face b a d)
## to the diagonal c d: the faces become c a d and c d b, and the four outer
## sides' twins follow them.
func flip(corners: i64[], twin: i64[], corner: usize, other: usize):
let face = corner // 3
let o = other // 3
let a = corners[corner]
let b = corners[after_corner(corner)]
let c = corners[before_corner(corner)]
let d = corners[before_corner(other)]
let bc = twin[after_corner(corner)]
let ca = twin[before_corner(corner)]
let ad = twin[after_corner(other)]
let db = twin[before_corner(other)]
corners[face * 3] = c
corners[face * 3 + 1] = a
corners[face * 3 + 2] = d
corners[o * 3] = c
corners[o * 3 + 1] = d
corners[o * 3 + 2] = b
link(twin, face * 3, ca)
link(twin, face * 3 + 1, ad)
twin[face * 3 + 2] = (i64)(o * 3)
twin[o * 3] = (i64)(face * 3 + 2)
link(twin, o * 3 + 1, db)
link(twin, o * 3 + 2, bc)
func link(twin: i64[], corner: usize, other: i64):
twin[corner] = other
if other >= 0: twin[(usize)other] = (i64)corner
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(degenerate, scale * conditioning)
# 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