dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / layout / trim_alignment.lucb
## Align numerical grid incidence without moving canonical CAD positions.
pub func align(uv: Vector3[], sizes: const i64[], ids: const i64[], canonical: const Vector3[], surface: Surface, plan: GridLayout, tolerance: f64) -> !:
let original_uv = try new Vector3[uv.length] --- in memory.heap
defer free(original_uv) in memory.heap
memory.copy(original_uv, uv, uv.length)
var begin: usize = 0
for size in sizes:
let count = (usize)size
for at in 0..<count:
let index = begin + at
let previous = begin + (at + count - 1) % count
let next = begin + (at + 1) % count
let p = canonical[(usize)ids[index]]
let before = canonical[(usize)ids[previous]]
let after = canonical[(usize)ids[next]]
let spacing = math.min(p.subtract(before).length(), p.subtract(after).length())
let budget = math.min(tolerance * 0.05, spacing * 0.2)
let original = try surface_point(surface, uv[index])
for axis in 0..<(usize)2:
let stations = plan.u if axis == 0 else plan.v
let value = coordinate(uv[index], axis)
let aligned = nearest(stations, value)
let a = coordinate(original_uv[previous], axis)
let b = coordinate(original_uv[next], axis)
let candidate = Vector3(aligned, uv[index].y, 0.0) if axis == 0 else Vector3(uv[index].x, aligned, 0.0)
let incidence = plan.epsilon * 1e-5
# A sampled extremum within the graze budget of a line, on
# either side, touches it: reconcile left an overshooting one
# uncut (trim_crossings.grazes), and one stopping short would
# leave a sub-tolerance gap. Either way it lands on the line.
let grazing = aligned != value and (a - aligned) * (b - aligned) > 0.0
if math.abs(aligned - value) > incidence and not grazing and (aligned <= math.min(a, b) or aligned >= math.max(a, b)): continue
let support = try surface_point(surface, candidate)
let limit = graze_budget(spacing, tolerance) if grazing else budget
if support.subtract(original).length() <= limit and support.subtract(p).length() <= tolerance: uv[index] = candidate
begin += count
# Crossings above can land beside a numerical endpoint that was visited
# earlier. Resolve that incidence only after all crossings are aligned.
# This is not geometric trim smoothing: the allowance is a few incidence
# units, and it must join an existing aligned neighbor without changing
# the directed polygon or moving any canonical 3D vertex.
begin = 0
for size in sizes:
let count = (usize)size
for at in 0..<count:
let index = begin + at
let previous = begin + (at + count - 1) % count
let next = begin + (at + 1) % count
let p = canonical[(usize)ids[index]]
let budget = math.min(tolerance * 0.05, math.min(p.subtract(canonical[(usize)ids[previous]]).length(), p.subtract(canonical[(usize)ids[next]]).length()) * 0.2)
let original = try surface_point(surface, uv[index])
for axis in 0..<(usize)2:
let value = coordinate(uv[index], axis)
let target = nearest(plan.u if axis == 0 else plan.v, value)
let incidence = math.max(1e-13, plan.epsilon * 1e-5)
if target == value or math.abs(target - value) > incidence * 16.0: continue
if math.min(math.abs(coordinate(uv[previous], axis) - target), math.abs(coordinate(uv[next], axis) - target)) > incidence: continue
let candidate = Vector3(target, uv[index].y, 0.0) if axis == 0 else Vector3(uv[index].x, target, 0.0)
if not safe_corner(uv, sizes, ids, begin, count, at, candidate): continue
let support = try surface_point(surface, candidate)
if support.subtract(original).length() <= budget and support.subtract(p).length() <= tolerance: uv[index] = candidate
begin += count
## Put each trim point still beside a grid line by less than the layout's
## own precision (`plan.epsilon`, half of it) onto that line, when the line
## crosses one of the point's sides: crossings are solved only to that
## precision, and clipping takes a trim side that far over a line as not
## crossing it, so a point left a hair beside a line leaves a cell boundary
## that does not close. Only chart coordinates move, by less than the
## crossings' own error; a point whose identity repeats (a seam's two
## images) stays.
pub func settle(uv: Vector3[], sizes: const i64[], ids: const i64[], plan: GridLayout) -> !:
let reach = plan.epsilon * 0.5
let seen = try new i64[ids.length * 2 + 1] --- in memory.heap
defer free(seen) in memory.heap
let repeated = try new bool[ids.length] --- in memory.heap
defer free(repeated) in memory.heap
for at in 0..<seen.length: seen[at] = -1
for at in 0..<ids.length:
repeated[at] = false
var slot = (usize)ids[at] % seen.length
while seen[slot] >= 0 and ids[(usize)seen[slot]] != ids[at]: slot = (slot + 1) % seen.length
if seen[slot] < 0: seen[slot] = (i64)at
else:
repeated[at] = true
repeated[(usize)seen[slot]] = true
var begin: usize = 0
for size in sizes:
let count = (usize)size
for k in 0..<count:
let at = begin + k
if repeated[at]: continue
let previous = uv[begin + (k + count - 1) % count]
let next = uv[begin + (k + 1) % count]
for axis in 0..<(usize)2:
let value = coordinate(uv[at], axis)
let line = nearest(plan.u if axis == 0 else plan.v, value)
let distance = math.abs(line - value)
if distance == 0.0 or distance >= reach: continue
# The line must cross a side of the point's.
if (coordinate(previous, axis) - line) * (value - line) >= 0.0 and (coordinate(next, axis) - line) * (value - line) >= 0.0: continue
uv[at] = Vector3(line, uv[at].y, 0.0) if axis == 0 else Vector3(uv[at].x, line, 0.0)
begin += count
func nearest(stations: Stations, value: f64) -> f64:
var low: usize = 0
var high = stations.count - 1
while high - low > 1:
let mid = (low + high) // 2
if stations.values[mid] <= value: low = mid
else: high = mid
return stations.values[low] if math.abs(stations.values[low] - value) <= math.abs(stations.values[high] - value) else stations.values[high]
func safe_corner(uv: const Vector3[], sizes: const i64[], ids: const i64[], begin: usize, count: usize, at: usize, candidate: Vector3) -> bool:
let index = begin + at
# Moving one occurrence of a pinched/seam identity would separate its UV
# aliases. Those cases need a joint proposal, not this single-corner repair.
for other in 0..<ids.length:
if other != index and ids[other] == ids[index]: return false
for offset in [count - 1, (usize)0, (usize)1]:
let center = (at + offset) % count
let ia = begin + (center + count - 1) % count
let ib = begin + center
let ic = begin + (center + 1) % count
let old = uv[ib].subtract(uv[ia]).cross(uv[ic].subtract(uv[ib])).z
let a = candidate if ia == index else uv[ia]
let b = candidate if ib == index else uv[ib]
let c = candidate if ic == index else uv[ic]
let updated = b.subtract(a).cross(c.subtract(b)).z
if old != 0.0 and old * updated < 0.0: return false
# Resolving numerical incidence may straighten a corner. Collinear
# ordered trim vertices are valid and retain their distinct CAD IDs;
# only collapsed or backtracking segments are forbidden here.
if updated == 0.0 and b.subtract(a).dot(c.subtract(b)) <= 0.0: return false
for neighbor in [begin + (at + count - 1) % count, begin + (at + 1) % count]:
var base: usize = 0
for size in sizes:
for edge in 0..<(usize)size:
let a = base + edge
let b = base + (edge + 1) % (usize)size
if a == index or b == index or a == neighbor or b == neighbor: continue
if intersect(uv[neighbor], candidate, uv[a], uv[b]): return false
base += (usize)size
return true
func intersect(a: Vector3, b: Vector3, c: Vector3, d: Vector3) -> bool:
if math.max(a.x, b.x) < math.min(c.x, d.x) or math.max(c.x, d.x) < math.min(a.x, b.x) or math.max(a.y, b.y) < math.min(c.y, d.y) or math.max(c.y, d.y) < math.min(a.y, b.y): return false
let ab = b.subtract(a)
let cd = d.subtract(c)
return ab.cross(c.subtract(a)).z * ab.cross(d.subtract(a)).z <= 0.0 and cd.cross(a.subtract(c)).z * cd.cross(b.subtract(c)).z <= 0.0