dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / meshing / mapped_spacing.lucb
## Physical spacing of mapped interiors; every trim/boundary vertex stays fixed.
## Redistribute complete interior rows, including their first/last intervals.
## Accept only improved spacing, an unfolded UV grid, and sampled display error
## no greater than the original grid or the tessellation display-error budget.
## The CAD boundary tolerance remains unchanged. Work is bounded.
pub func redistribute_grid(grid: Vector3[], nx: usize, ny: usize, s: Surface, tolerance: f64, forward: bool = true, divisions: i64 = 16) -> !:
if s.kind != surface_spline or nx < 2 or ny < 2: return
let points = try new Vector3[grid.length] --- in memory.heap
defer free(points) in memory.heap
for at in 0..<grid.length: points[at] = try evaluate(s, grid[at])
var quality = uneven(points, nx, ny)
if quality < 1.5: return
let candidate = try new Vector3[grid.length] --- in memory.heap
defer free(candidate) in memory.heap
let proposed = try new Vector3[grid.length] --- in memory.heap
defer free(proposed) in memory.heap
let lengths = try new f64[(nx if nx > ny else ny) + 1] --- in memory.heap
defer free(lengths) in memory.heap
var low = points[0]
var high = points[0]
for p in points:
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
let target = math.max(tolerance, high.subtract(low).length() / ((f64)divisions * (f64)divisions * 16.0))
let limit = math.max(target * target, (try grid_deviation(grid, points, nx, ny, s, forward)) * (1.0 + 1e-8))
for pass in 0..<3:
var accepted = false
for axis in 0..<(usize)2:
memory.copy(candidate, grid, grid.length)
let along = nx if axis == 0 else ny
let across = ny if axis == 0 else nx
let stride = 1 if axis == 0 else nx + 1
for line in 1..<across:
let start = line * (nx + 1) if axis == 0 else line
lengths[0] = 0.0
for at in 1..<along + 1:
lengths[at] = lengths[at - 1] + points[start + at * stride].subtract(points[start + (at - 1) * stride]).length()
var segment: usize = 0
for at in 1..<along:
let distance = lengths[along] * (f64)at / (f64)along
while segment + 1 < along and lengths[segment + 1] < distance: segment += 1
let span = lengths[segment + 1] - lengths[segment]
let t = (distance - lengths[segment]) / span if span > 1e-30 else 0.5
candidate[start + at * stride] = grid[start + segment * stride].multiply_scalar(1.0 - t).add(grid[start + (segment + 1) * stride].multiply_scalar(t))
if not grid_oriented(candidate, grid, nx, ny): continue
for at in 0..<candidate.length: proposed[at] = try evaluate(s, candidate[at])
let updated = uneven(proposed, nx, ny)
if updated > quality * (1.0 + 1e-6) or grid_energy(proposed, nx, ny) >= grid_energy(points, nx, ny) * (1.0 - 1e-6): continue
if try grid_deviation(candidate, proposed, nx, ny, s, forward) > limit: continue
memory.copy(grid, candidate, grid.length)
memory.copy(points, proposed, grid.length)
quality = updated
accepted = true
if not accepted or quality < 1.05: break
# Sum normalized gap variance so improving one direction is not blocked by an
# unchanged worst row in the other direction. Keep the worst-ratio guard too.
func grid_energy(points: const Vector3[], nx: usize, ny: usize) -> f64:
var result: f64 = 0.0
for axis in 0..<(usize)2:
let along = nx if axis == 0 else ny
let across = ny if axis == 0 else nx
let stride = 1 if axis == 0 else nx + 1
for line in 1..<across:
let start = line * (nx + 1) if axis == 0 else line
var length: f64 = 0.0
var square: f64 = 0.0
for at in 0..<along:
let gap = points[start + (at + 1) * stride].subtract(points[start + at * stride]).length()
length += gap
square += gap * gap
if length > 1e-14: result += math.max(0.0, (f64)along * square / (length * length) - 1.0)
return result
func uneven(points: const Vector3[], nx: usize, ny: usize) -> f64:
var result: f64 = 1.0
for axis in 0..<(usize)2:
let along = nx if axis == 0 else ny
let across = ny if axis == 0 else nx
let stride = 1 if axis == 0 else nx + 1
for line in 1..<across:
let start = line * (nx + 1) if axis == 0 else line
var low: f64 = 1e100
var high: f64 = 0.0
for at in 0..<along:
let gap = points[start + (at + 1) * stride].subtract(points[start + at * stride]).length()
low = math.min(low, gap)
high = math.max(high, gap)
if low > 1e-14: result = math.max(result, high / low)
return result
func grid_oriented(candidate: const Vector3[], original: const Vector3[], nx: usize, ny: usize) -> bool:
for row in 0..<ny:
for column in 0..<nx:
let at = row * (nx + 1) + column
let ids = [at, at + 1, at + nx + 2, at + nx + 1]
for corner in 0..<(usize)4:
let a = ids[corner]
let b = ids[(corner + 1) % 4]
let c = ids[(corner + 2) % 4]
let before = original[b].subtract(original[a]).cross(original[c].subtract(original[b])).z
let after = candidate[b].subtract(candidate[a]).cross(candidate[c].subtract(candidate[b])).z
if math.abs(after) < 1e-16 or before * after <= 0.0: return false
return true
# Same diagonal as the convex-quad display triangulator, with edge midpoints
# and centroids sampled on the exact surface. Not a certified deviation bound.
func grid_deviation(uv: const Vector3[], points: const Vector3[], nx: usize, ny: usize, s: Surface, forward: bool) -> f64!:
var maximum: f64 = 0.0
for row in 0..<ny:
for column in 0..<nx:
let at = row * (nx + 1) + column
let ids = [at, at + 1, at + nx + 2, at + nx + 1]
for triangle in 0..<(usize)2:
let a = ids[3 if forward else 0] if triangle == 0 else ids[1 if forward else 2]
let b = ids[0 if forward else 3] if triangle == 0 else ids[2 if forward else 1]
let c = ids[1 if forward else 2] if triangle == 0 else ids[3 if forward else 0]
for p in [uv[a].add(uv[b]).add(uv[c]).multiply_scalar(1.0 / 3.0), uv[a].add(uv[b]).multiply_scalar(0.5), uv[b].add(uv[c]).multiply_scalar(0.5), uv[c].add(uv[a]).multiply_scalar(0.5)]:
maximum = math.max(maximum, squared_triangle_distance(try evaluate(s, p), points[a], points[b], points[c]))
return maximum