dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / meshing / clipped_merge.lucb
## A grazing grid line can isolate a thin trim sliver with no valid lifted
## triangulation. Agglomerate only that small cell across a manifold grid edge.
## All vertices, canonical boundary segments and holes remain unchanged.
pub func append_repaired(lifted: MeshBuilder*, source: interop.Reference[Mesh], forward: bool, normals: const Vector3[]) -> interop.Reference[Mesh]!:
var current = source.clone()
errdefer current.release()
for pass in 0..<(usize)33:
lifted.nf = 0
lifted.nc = 0
var failed: i64 = -1
var accepted = true
append_cells(lifted, current.value(), forward, normals, &failed) catch failure:
if failure.code != invalid or failed < 0: error(failure.code, failure.message)
accepted = false
recover ()
if accepted: return current
if pass == 32: error(invalid, "trim sliver agglomeration exceeds budget")
let edge = try merge_edge(current.value(), failed, lifted.points[..<lifted.np])
if edge < 0: error(invalid, "trimmed cell cannot safely agglomerate")
let next = try dissolve_edge(current.value(), edge)
current.release()
current = next
error(invalid, "trim sliver agglomeration exceeds budget")
func face_area[M: PolygonTopology](mesh: const M*, face: i64) -> f64!:
let count = try mesh.face_size(face)
let origin = try mesh.point(try mesh.face_point(face, 0))
var result: f64 = 0.0
for at in 1..<count - 1:
let a = (try mesh.point(try mesh.face_point(face, at))).subtract(origin)
let b = (try mesh.point(try mesh.face_point(face, at + 1))).subtract(origin)
result += a.cross(b).z
return math.abs(result) * 0.5
## Ordinary candidates are at most one eighth of their neighbor's chart area.
## Physically collapsed ribbons instead require the spanning internal chord,
## including through another collapsed cell. Final support checks still apply.
pub func merge_edge(mesh: const Mesh*, face: i64, positions: const Vector3[]? = none) -> i64!:
let count = try mesh.face_size(face)
let neighbors = try new i64[(usize)(try mesh.edge_count())] --- in memory.heap
defer free(neighbors) in memory.heap
for at in 0..<neighbors.length: neighbors[at] = -2
for at in 0..<count: neighbors[(usize)(try mesh.face_edge(face, at))] = -1
for corner in 0..<mesh.vertex_count():
let candidate = try mesh.corner_face(corner)
if candidate == face: continue
let edge = (usize)(try mesh.corner_edge(corner))
if neighbors[edge] == -2: continue
neighbors[edge] = candidate if neighbors[edge] == -1 else -3
let candidates = try new i64[(usize)count] --- in memory.heap
defer free(candidates) in memory.heap
for side in 0..<count: candidates[(usize)side] = neighbors[(usize)(try mesh.face_edge(face, side))]
return try choose_edge(mesh, face, candidates, positions)
## Identical merge policy over immutable meshes or native dissolve workspaces.
## The caller supplies one opposite face per side, -1 for unavailable neighbors.
pub func choose_edge[M: PolygonTopology](mesh: const M*, face: i64, neighbors: const i64[], positions: const Vector3[]? = none) -> i64!:
let count = try mesh.face_size(face)
if neighbors.length != (usize)count: error(invalid, "sliver adjacency must cover every side")
let measure = try face_area(mesh, face)
let span = try collapsed_span(mesh, face, positions)
var best: i64 = -1
var longest: f64 = 0.0
# Only failed cells or physically tiny boundary slivers enter this search,
# bounded to a small patch arrangement. Ordinary cells stay unchanged.
for side in 0..<count:
let candidate = neighbors[(usize)side]
if candidate < 0: continue
let size = try mesh.face_size(candidate)
if count + size - 2 > 256: continue
if span >= 0:
if (try mesh.face_edge(face, side)) != span: continue
elif measure > (try face_area(mesh, candidate)) * 0.125: continue
var shared: i64 = -1
var connections: usize = 0
var shared_vertices: usize = 0
for at in 0..<count:
let a = try mesh.face_point(face, at)
let b = try mesh.face_point(face, (at + 1) % count)
for other in 0..<size:
let c = try mesh.face_point(candidate, other)
if a == c: shared_vertices += 1
if b == c and a == (try mesh.face_point(candidate, (other + 1) % size)):
shared = try mesh.face_edge(face, at)
connections += 1
# Exactly one shared side and no other touching vertices guarantees a
# simple union, not a hole, bridge or pinched polygon.
if connections != 1 or shared_vertices != 2: continue
let a = try mesh.point(try mesh.edge_point(shared, 0))
let b = try mesh.point(try mesh.edge_point(shared, 1))
let length = b.subtract(a).length()
if length > longest:
best = shared
longest = length
return best
## Roundoff in a support projection can enclose a UV ribbon whose lifted
## vertices are collinear. Only its spanning chord can be removed safely:
## dissolving a shorter side leaves a physically retracing polygon boundary.
## The neighbor may itself be collapsed; allow the ribbon to reach a real
## cell before applying the ordinary small-to-large area test again.
func collapsed_span[M: PolygonTopology](mesh: const M*, face: i64, positions: const Vector3[]?) -> i64!:
if let points = positions:
if points.length != (usize)mesh.point_count(): error(invalid, "cut-cell metric must cover every chart point")
let count = try mesh.face_size(face)
var side: i64 = -1
var length: f64 = 0.0
for at in 0..<count:
let a = points[(usize)(try mesh.face_point(face, at))]
let b = points[(usize)(try mesh.face_point(face, (at + 1) % count))]
let distance = b.subtract(a).length()
if distance > length:
length = distance
side = at
if side < 0: return -1
let origin = points[(usize)(try mesh.face_point(face, side))]
let direction = points[(usize)(try mesh.face_point(face, (side + 1) % count))].subtract(origin).multiply_scalar(1.0 / length)
var magnitude = length
for at in 0..<count:
let p = points[(usize)(try mesh.face_point(face, at))]
magnitude = math.max(magnitude, math.max(math.abs(p.x), math.max(math.abs(p.y), math.abs(p.z))))
# Subtraction inherits the precision of absolute support coordinates,
# especially on a tiny sliver far from the origin. This is a numerical
# classification only: no point is snapped, welded or removed.
let epsilon = length * 1e-14 + magnitude * 8e-16
# If the entire cell approaches coordinate resolution, this test no
# longer establishes a thin ribbon. Leave it to ordinary validation.
if epsilon > length * 1e-8: return -1
for at in 0..<count:
let offset = points[(usize)(try mesh.face_point(face, at))].subtract(origin)
let along = offset.dot(direction)
if along < -epsilon or along > length + epsilon or offset.cross(direction).length() > epsilon: return -1
return try mesh.face_edge(face, side)
return -1