dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / meshing / clipped_rows.lucb
## Original grid-line chains in a clipped chart. Trims, holes and ambiguous
## junctions stop chains; only complete boundary-to-boundary runs can move.
pub struct Rows:
pub let ids: usize[]
pub let offsets: usize[]
pub let axes: usize[]
pub let active: bool[]
pub var count: usize
## Boundary points occupy the chart's fixed prefix; points are its lift.
pub func init(chart: const Mesh*, boundary: usize, points: const Vector3[]) -> !:
let count = (usize)chart.point_count()
let ids = try new usize[count * 6] --- in memory.heap
errdefer free(ids) in memory.heap
let offsets = try new usize[count * 2 + 1] --- in memory.heap
errdefer free(offsets) in memory.heap
let axes = try new usize[count * 2] --- in memory.heap
errdefer free(axes) in memory.heap
let active = try new bool[count * 2] --- in memory.heap
errdefer free(active) in memory.heap
let neighbors = try new i64[count * 4] --- in memory.heap
defer free(neighbors) in memory.heap
for at in 0..<neighbors.length: neighbors[at] = -1
let extent = chart.bounds().maximum.subtract(chart.bounds().minimum).length()
let epsilon = math.max(1e-14, extent * 1e-12)
for edge in 0..<(try chart.edge_count()):
let a = (usize)(try chart.edge_point(edge, 0))
let b = (usize)(try chart.edge_point(edge, 1))
if a < boundary and b < boundary: continue
let delta = (try chart.point((i64)b)).subtract(try chart.point((i64)a))
for axis in 0..<(usize)2:
let along = delta.x if axis == 0 else delta.y
let across = delta.y if axis == 0 else delta.x
if math.abs(across) > epsilon or math.abs(along) <= epsilon: continue
let side: usize = 1 if along > 0.0 else 0
for pair in [a * 4 + axis * 2 + side, b * 4 + axis * 2 + 1 - side]:
let other = (i64)b if pair == a * 4 + axis * 2 + side else (i64)a
neighbors[pair] = other if neighbors[pair] == -1 or neighbors[pair] == other else -2
var written: usize = 0
var rows: usize = 0
offsets[0] = 0
for axis in 0..<(usize)2:
for start in boundary..<count:
let before = neighbors[start * 4 + axis * 2]
if before < 0 or (usize)before >= boundary: continue
var previous = (usize)before
var at = start
let begin = written
ids[written] = previous
written += 1
var complete = false
for step in 0..<count:
if neighbors[at * 4 + axis * 2] != (i64)previous: break
ids[written] = at
written += 1
let next = neighbors[at * 4 + axis * 2 + 1]
if next < 0: break
if (usize)next < boundary:
ids[written] = (usize)next
written += 1
complete = true
break
previous = at
at = (usize)next
if not complete:
written = begin
continue
axes[rows] = axis
# A tiny final cut interval alone is not a crowded grid family.
# Diagnose only interior-to-interior gaps, then include the
# boundary gaps when measuring and redistributing that family.
var low: f64 = 1e100
var high: f64 = 0.0
for i in begin + 1..<written - 2:
let gap = points[ids[i + 1]].subtract(points[ids[i]]).length()
low = math.min(low, gap)
high = math.max(high, gap)
let first = points[ids[begin + 1]].subtract(points[ids[begin]]).length()
let last = points[ids[written - 1]].subtract(points[ids[written - 2]]).length()
# A *large* trim-to-first-row gap is missing support, unlike a
# tiny Boolean cut interval. Include it even when all interior
# gaps agree, otherwise the first and last rows never improve.
active[rows] = written - begin >= 5 and low > 1e-14 and (high > low * 8.0 or math.max(first, last) > high * 2.0)
rows += 1
offsets[rows] = written
self.ids = ids
self.offsets = offsets
self.axes = axes
self.active = active
self.count = rows
## Release the owned chain index and diagnostic flags.
pub func close():
free(self.ids) in memory.heap
free(self.offsets) in memory.heap
free(self.axes) in memory.heap
free(self.active) in memory.heap
## At least one complete chain contains an uneven interior station family.
pub func crowded() -> bool:
for row in 0..<self.count:
if self.active[row]: return true
return false
## All complete chains contribute, so smoothing one family may not hide a
## worse distribution in its transverse family. Return energy and max ratio.
pub func quality(points: const Vector3[]) -> Vector3:
var energy: f64 = 0.0
var worst: f64 = 1.0
for row in 0..<self.count:
let start = self.offsets[row]
let end = self.offsets[row + 1]
var sum: f64 = 0.0
var square: f64 = 0.0
var low: f64 = 1e100
var high: f64 = 0.0
for at in start..<end - 1:
let gap = points[self.ids[at + 1]].subtract(points[self.ids[at]]).length()
sum += gap
square += gap * gap
low = math.min(low, gap)
high = math.max(high, gap)
if sum > 1e-14: energy += math.max(0.0, (f64)(end - start - 1) * square / (sum * sum) - 1.0)
if low > 1e-14: worst = math.max(worst, high / low)
return Vector3(energy, worst, 0.0)
## Write a physical chord-length proposal; never write either trim endpoint.
pub func propose(axis: usize, uv: const Vector3[], points: const Vector3[], candidate: Vector3[], lengths: f64[]):
memory.copy(candidate, uv, uv.length)
for row in 0..<self.count:
if self.axes[row] != axis or not self.active[row]: continue
let start = self.offsets[row]
let count = self.offsets[row + 1] - start
lengths[0] = 0.0
for at in 1..<count:
lengths[at] = lengths[at - 1] + points[self.ids[start + at]].subtract(points[self.ids[start + at - 1]]).length()
var segment: usize = 0
for at in 1..<count - 1:
let distance = lengths[count - 1] * (f64)at / (f64)(count - 1)
while segment + 1 < count - 1 and lengths[segment + 1] < distance: segment += 1
let span = lengths[segment + 1] - lengths[segment]
let t = (distance - lengths[segment]) / span if span > degenerate else 0.5
candidate[self.ids[start + at]] = uv[self.ids[start + segment]].multiply_scalar(1.0 - t).add(uv[self.ids[start + segment + 1]].multiply_scalar(t))