dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / meshing / adaptive_uv.lucb
## Curvature-driven interior refinement. Boundary IDs never change; both faces
## incident to a split UV edge consume its one shared midpoint. No T-junctions.
##
## A face's target is `tolerance`, or, beside a frozen side (the boundary's
## or a trim constraint's, which no pass splits), that side's own sag: a
## triangle on a frozen side keeps it however often it is split, so a
## tighter target there is never met. (The tessellator samples shared
## edges to their faces' targets first, so this matters only for small
## differences.) Refinement also stops when its worst excess stops falling,
## and at the face budget it keeps the mesh it has: a coarser face, never
## a missing one.
func chart_sample(s: Surface, p: Vector3, uscale: f64, vscale: f64) -> Vector3!:
if s.kind != surface_spline: return analytic_point(s, p.x / uscale, p.y / vscale)
let u0 = s.ku[(usize)s.du]
let v0 = s.kv[(usize)s.dv]
return try s.at(math.clamp(u0 + (s.ku[(usize)s.nu] - u0) * p.x / uscale, u0, s.ku[(usize)s.nu]), math.clamp(v0 + (s.kv[(usize)s.nv] - v0) * p.y / vscale, v0, s.kv[(usize)s.nv]))
pub func refine_uv(source: interop.Reference[Mesh], surface: Surface, uscale: f64, vscale: f64, tolerance: f64, constraints: TrimConstraints = TrimConstraints()) -> interop.Reference[Mesh]!:
var current = source.clone()
errdefer current.release()
var previous: f64 = 1e300
for pass in 0..<8:
if current.value().face_count() > face_budget: break
var excess: f64 = 0.0
let next = try refine_pass(current, surface, uscale, vscale, tolerance, constraints, &excess)
let finished = next.value().point_count() == current.value().point_count()
current.release()
current = next
# A pass whose worst triangle is hardly better than the last one's
# is splitting what splitting cannot fix.
if finished or excess > previous * 0.81: break
previous = excess
return current
## The most triangles a face's refinement grows to.
let face_budget: i64 = 131072
## One pass: split the sides whose midpoint, and the faces whose center,
## lie further from the surface than their target. `excess` receives the
## worst squared deviation over its target (1 when nothing is split).
func refine_pass(source: interop.Reference[Mesh], surface: Surface, uscale: f64, vscale: f64, tolerance: f64, constraints: TrimConstraints, excess: f64*) -> interop.Reference[Mesh]!:
let input = source.value()
let worlds = try new Vector3[(usize)input.point_count()] --- in memory.heap
defer free(worlds) in memory.heap
for at in 0..<worlds.length: worlds[at] = try chart_sample(surface, try input.point((i64)at), uscale, vscale)
let uses = try new usize[(usize)(try input.edge_count())] --- in memory.heap
defer free(uses) in memory.heap
let splits = try new i64[uses.length] --- in memory.heap
defer free(splits) in memory.heap
let adjacent = try new i64[uses.length * 2] --- in memory.heap
defer free(adjacent) in memory.heap
for at in 0..<uses.length:
uses[at] = 0
splits[at] = -1
for face in 0..<input.face_count():
for at in 0..<(try input.face_size(face)):
let edge = (usize)(try input.face_edge(face, at))
if uses[edge] < 2: adjacent[edge * 2 + uses[edge]] = face
uses[edge] += 1
# Each face's squared target: the tolerance, or its frozen sides' sag
# (with a margin, as the sag is sampled at one point).
let targets = try new f64[(usize)input.face_count()] --- in memory.heap
defer free(targets) in memory.heap
for at in 0..<targets.length: targets[at] = tolerance * tolerance
for edge in 0..<(try input.edge_count()):
let a = try input.edge_point(edge, 0)
let b = try input.edge_point(edge, 1)
if uses[(usize)edge] == 2 and not constraints.contains(a, b): continue
let midpoint = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
let chord = worlds[(usize)a].add(worlds[(usize)b]).multiply_scalar(0.5)
let sag = (try chart_sample(surface, midpoint, uscale, vscale)).subtract(chord).length() * 1.25
for side in 0..<(uses[(usize)edge] if uses[(usize)edge] < 2 else (usize)2):
let face = (usize)adjacent[(usize)edge * 2 + side]
targets[face] = math.max(targets[face], sag * sag)
var worst: f64 = 0.0
var output = try MeshBuilder(precise = true)
defer output.close()
try output.copy_points(input)
for edge in 0..<(try input.edge_count()):
if uses[(usize)edge] != 2: continue
let a = try input.edge_point(edge, 0)
let b = try input.edge_point(edge, 1)
if constraints.contains(a, b): continue
let midpoint = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
let p = try chart_sample(surface, midpoint, uscale, vscale)
# Measure geometric deflection, not parameterization speed. Comparing
# positions at equal parameters over-refines even a flat skewed patch.
let first = adjacent[(usize)edge * 2]
let second = adjacent[(usize)edge * 2 + 1]
let squared = math.min(try face_deviation(input, worlds, first, p), try face_deviation(input, worlds, second, p))
let target = math.max(targets[(usize)first], targets[(usize)second])
if squared > target:
splits[(usize)edge] = try output.point(midpoint)
worst = math.max(worst, squared / target)
for face in 0..<input.face_count():
let count = try input.face_size(face)
let center = try input.face_center(face)
let world = try chart_sample(surface, center, uscale, vscale)
let target = targets[(usize)face]
var split = false
var all = true
for at in 0..<count:
let exists = splits[(usize)(try input.face_edge(face, at))] >= 0
split = split or exists
all = all and exists
var deviation = try face_deviation(input, worlds, face, world)
if count == 4:
let a = try input.face_point(face, 0)
let b = try input.face_point(face, 2)
let uv = (try input.point(a)).add(try input.point(b)).multiply_scalar(0.5)
deviation = math.max(deviation, try face_deviation(input, worlds, face, try chart_sample(surface, uv, uscale, vscale)))
if deviation > target:
split = true
worst = math.max(worst, deviation / target)
if not split:
try output.copy_face(input, face)
continue
if count == 3:
let vertices = [try input.face_point(face, 0), try input.face_point(face, 1), try input.face_point(face, 2)]
let cuts = [splits[(usize)(try input.face_edge(face, 0))], splits[(usize)(try input.face_edge(face, 1))], splits[(usize)(try input.face_edge(face, 2))]]
let nf = output.nf
let nc = output.nc
if not center_conditioned(&output, vertices, cuts, center) and (try split_triangle(&output, vertices, cuts)):
# A good UV diagonal need not be good on a curved support.
# Keep edge-only refinement only when every lifted child has
# the support's orientation; otherwise retain the center path.
if try faces_outward(&output, nc, surface, uscale, vscale): continue
output.nf = nf
output.nc = nc
let middle = try output.point(center)
for at in 0..<count:
let a = try input.face_point(face, at)
let b = try input.face_point(face, (at + 1) % count)
let cut = splits[(usize)(try input.face_edge(face, at))]
if all and count == 4:
try output.face(4)
for id in [a, cut, middle, splits[(usize)(try input.face_edge(face, (at + count - 1) % count))]]: try output.corner(id)
elif cut >= 0:
try add_triangle(&output, a, cut, middle)
try add_triangle(&output, cut, b, middle)
else:
try add_triangle(&output, a, b, middle)
*excess = worst if worst > 0.0 else 1.0
if output.np == (usize)input.point_count(): return source.clone()
return try output.finish()
func face_deviation(mesh: Mesh*, points: const Vector3[], face: i64, p: Vector3) -> f64!:
let a = points[(usize)(try mesh.face_point(face, 0))]
var distance: f64 = 1e100
for at in 1..<(try mesh.face_size(face)) - 1:
distance = math.min(distance, squared_triangle_distance(p, a, points[(usize)(try mesh.face_point(face, at))], points[(usize)(try mesh.face_point(face, at + 1))]))
return distance
func faces_outward(mesh: const MeshBuilder*, start: usize, surface: Surface, uscale: f64, vscale: f64) -> bool!:
for at in 0..<(mesh.nc - start) // 3:
var uv = [Vector3(), Vector3(), Vector3()]
var p = uv
for i in 0..<(usize)3:
uv[i] = mesh.points[(usize)mesh.corners[start + at * 3 + i]]
p[i] = try chart_sample(surface, uv[i], uscale, vscale)
let cross = p[1].subtract(p[0]).cross(p[2].subtract(p[0]))
for q in uv:
let n = try support_normal(surface, Vector3(q.x / uscale, q.y / vscale, 0.0))
if cross.dot(n) <= cross.length() * 1e-10: return false
return true