dymokomi/luce-cad
Source of release 0.9.1
0.9.1 / src / surface_trim.lucb
## Trimmed nonperiodic NURBS: bounded UV inversion, constrained meshing, lifting.
import memory
from luce_std import math
import interop
import ownership
from luce_geocore.geocore import Vector3, MeshBuilder, invalid
from tessellation.surface import TrimPolygon, TrimConstraints, nurbs_basis, nurbs_combine
from brep_types import Surface
from adaptive_uv import refine_uv
import strings
pub func evaluate(surface: Surface, uv: Vector3) -> Vector3!:
var u: Knot
var v: Knot
try u.at(surface.ku, surface.nu, surface.du, uv.x)
try v.at(surface.kv, surface.nv, surface.dv, uv.y)
return try point_of(surface, &u, &v)
## One normalized parameter's knot value and nonzero basis. Newton steps
## reuse them: finite differences share one parameter with the current point,
## and an accepted line-search candidate is the next iteration's point.
struct Knot:
var first: usize
var values: f64[9]
## The clamp and domain check of Surface.at, then the basis.
func at(knots: const f64[], count: i64, degree: i64, fraction: f64) -> !:
let low = knots[(usize)degree]
let high = knots[(usize)count]
let t = math.clamp(low + (high - low) * fraction, low, high)
if not math.is_finite(t) or t < low or t > high:
error(invalid, "surface parameter outside knot domain")
self.first = nurbs_basis(knots, count, degree, t, &self.values)
func point_of(surface: Surface, u: Knot*, v: Knot*) -> Vector3!:
return try nurbs_combine(surface.points, surface.weights, surface.nv, surface.du, surface.dv, u.first, &u.values, v.first, &v.values)
## Distance as Vector3.length computes it.
inline func gap(a: Vector3, b: Vector3) -> f64:
return math.hypot(math.hypot(a.x - b.x, a.y - b.y), a.z - b.z)
## Newton inversion with finite-difference tangents. Every evaluation equals
## the plain evaluate() of the same parameters; only repeated bases and the
## accepted candidate's point are reused, so the iterates are unchanged.
func improve(surface: Surface, point: Vector3, seed: Vector3) -> Vector3!:
var uv = seed
var u: Knot
var v: Knot
var p = Vector3()
var known = false
for iteration in 0..<48:
if not known:
# Evaluation order as before: the u check precedes the v check.
try u.at(surface.ku, surface.nu, surface.du, uv.x)
try v.at(surface.kv, surface.nv, surface.dv, uv.y)
p = try point_of(surface, &u, &v)
known = false
let residual = Vector3(point.x - p.x, point.y - p.y, point.z - p.z)
let residual_length = math.hypot(math.hypot(residual.x, residual.y), residual.z)
# Layout intersections need parameter precision finer than a grid snap.
# The acceptance tolerance below is unchanged; this only solves the UV
# inverse more accurately when the edge actually lies on the support.
if residual_length < 0.000000000001:
break
let ua = math.max(0.0, uv.x - 0.00001)
let ub = math.min(1.0, uv.x + 0.00001)
let va = math.max(0.0, uv.y - 0.00001)
let vb = math.min(1.0, uv.y + 0.00001)
var side: Knot
try side.at(surface.ku, surface.nu, surface.du, ub)
let pub_ = try point_of(surface, &side, &v)
try side.at(surface.ku, surface.nu, surface.du, ua)
let pua = try point_of(surface, &side, &v)
try side.at(surface.kv, surface.nv, surface.dv, vb)
let pvb = try point_of(surface, &u, &side)
try side.at(surface.kv, surface.nv, surface.dv, va)
let pva = try point_of(surface, &u, &side)
let su = 1.0 / (ub - ua)
let sv = 1.0 / (vb - va)
let du = Vector3((pub_.x - pua.x) * su, (pub_.y - pua.y) * su, (pub_.z - pua.z) * su)
let dv = Vector3((pvb.x - pva.x) * sv, (pvb.y - pva.y) * sv, (pvb.z - pva.z) * sv)
let aa = du.x * du.x + du.y * du.y + du.z * du.z
let ab = du.x * dv.x + du.y * dv.y + du.z * dv.z
let bb = dv.x * dv.x + dv.y * dv.y + dv.z * dv.z
let det = aa * bb - ab * ab
if det <= aa * bb * 0.000000000001:
break
let ur = du.x * residual.x + du.y * residual.y + du.z * residual.z
let vr = dv.x * residual.x + dv.y * residual.y + dv.z * residual.z
var dx = math.clamp((bb * ur - ab * vr) / det, -0.25, 0.25)
var dy = math.clamp((aa * vr - ab * ur) / det, -0.25, 0.25)
# Solve the remaining tangent when a constrained parameter cannot move.
# Clamping the unconstrained 2D Newton step alone made edge projections
# seed-dependent when STEP curves differ slightly from the support.
if (uv.x <= 1e-12 and dx < 0.0) or (uv.x >= 1.0 - 1e-12 and dx > 0.0):
dx = 0.0
dy = math.clamp(vr / bb, -0.25, 0.25)
if (uv.y <= 1e-12 and dy < 0.0) or (uv.y >= 1.0 - 1e-12 and dy > 0.0):
dy = 0.0
dx = math.clamp(ur / aa, -0.25, 0.25)
var accepted = false
var factor: f64 = 1.0
var cu: Knot
var cv: Knot
for step in 0..<12:
let candidate = Vector3(math.clamp(uv.x + dx * factor, 0.0, 1.0), math.clamp(uv.y + dy * factor, 0.0, 1.0), 0.0)
try cu.at(surface.ku, surface.nu, surface.du, candidate.x)
try cv.at(surface.kv, surface.nv, surface.dv, candidate.y)
let q = try point_of(surface, &cu, &cv)
if gap(q, point) < residual_length:
uv = candidate
u = cu
v = cv
p = q
known = true
accepted = true
break
factor *= 0.5
if not accepted:
break
return uv
pub func project(surface: Surface, point: Vector3, seed: Vector3, tolerance: f64) -> Vector3!:
var uv = try improve(surface, point, seed)
if (try evaluate(surface, uv)).subtract(point).length() <= tolerance:
return uv
let first = uv
var best: f64 = 1e100
for u in 0..<9:
for v in 0..<9:
let candidate = Vector3((f64)u / 8.0, (f64)v / 8.0, 0.0)
let distance = (try evaluate(surface, candidate)).subtract(point).length()
if distance < best:
best = distance
uv = candidate
uv = try improve(surface, point, uv)
# An edited surface's trims may be off it by design: the nearest point
# found from the seed or the lattice is the answer (without the costlier
# local starts below).
if surface.edited:
if (try evaluate(surface, uv)).subtract(point).length() > (try evaluate(surface, first)).subtract(point).length(): return first
return uv
if (try evaluate(surface, uv)).subtract(point).length() > tolerance:
# Narrow knot spans can disappear entirely between uniform seeds. Use
# nearby control points' Greville parameters as additional local starts.
var distances: f64[16]
let seeds = try new Vector3[16] --- in memory.heap
defer free(seeds) in memory.heap
for index in 0..<(usize)16: seeds[index] = Vector3()
for index in 0..<(usize)16: distances[index] = 1e100
for u in 0..<(usize)surface.nu:
for v in 0..<(usize)surface.nv:
let delta = surface.points[u * (usize)surface.nv + v].subtract(point)
let distance = delta.dot(delta)
if distance >= distances[15]: continue
var index: usize = 15
while index > 0 and distance < distances[index - 1]:
distances[index] = distances[index - 1]
seeds[index] = seeds[index - 1]
index -= 1
distances[index] = distance
seeds[index] = Vector3(greville(surface.ku, u, surface.nu, surface.du), greville(surface.kv, v, surface.nv, surface.dv), 0.0)
for index in 0..<(usize)16:
if distances[index] == 1e100: break
let candidate = try improve(surface, point, seeds[index])
if (try evaluate(surface, candidate)).subtract(point).length() <= tolerance: return candidate
if (try evaluate(surface, candidate)).subtract(point).length() < (try evaluate(surface, uv)).subtract(point).length(): uv = candidate
var buffer: u8[512]
let residual = (try evaluate(surface, uv)).subtract(point).length()
let owned = try interop.copy_text(try strings.format(buffer, f"NURBS boundary projection exceeds CAD tolerance: residual {residual}, tolerance {tolerance}"))
if let owner = owned.owner: _ = ownership.pool_object(owner)
error(invalid, owned.value)
return uv
func greville(knots: const f64[], at: usize, count: i64, degree: i64) -> f64:
var sum: f64 = 0.0
for index in 1..<(usize)degree + 1: sum += knots[at + index]
let low = knots[(usize)degree]
return math.clamp((sum / (f64)degree - low) / (knots[(usize)count] - low), 0.0, 1.0)
pub func mesh_trim(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], surface: Surface, sense: bool, divisions: i64, edge_size: f64, tolerance: f64) -> !:
# Approximate metric scaling avoids a square UV lattice on long thin strips.
var u_length: f64 = 0.0
var v_length: f64 = 0.0
for at in 0..<16:
let a = (f64)at / 16.0
let b = (f64)(at + 1) / 16.0
u_length += (try evaluate(surface, Vector3(b, 0.5, 0.0))).subtract(try evaluate(surface, Vector3(a, 0.5, 0.0))).length()
v_length += (try evaluate(surface, Vector3(0.5, b, 0.0))).subtract(try evaluate(surface, Vector3(0.5, a, 0.0))).length()
if u_length <= 0.000000001 or v_length <= 0.000000001:
error(invalid, "degenerate NURBS parameter metric")
let uv = try new Vector3[ids.length] --- in memory.heap
defer free(uv) in memory.heap
var seed = Vector3(0.5, 0.5, 0.0)
for at in 0..<ids.length:
seed = try project(surface, mesh.points[(usize)ids[at]], seed, tolerance)
# Inversion noise along exact domain edges creates microscopic UV ears.
# Snap parameters only near an endpoint, and only after checking the
# actual surface residual. Original shared 3D boundary points stay intact.
let snapped = Vector3(0.0 if seed.x < 0.0000001 else (1.0 if seed.x > 0.9999999 else seed.x),
0.0 if seed.y < 0.0000001 else (1.0 if seed.y > 0.9999999 else seed.y), 0.0)
if (try evaluate(surface, snapped)).subtract(mesh.points[(usize)ids[at]]).length() <= tolerance:
seed = snapped
uv[at] = Vector3(seed.x * u_length, seed.y * v_length, 0.0)
var spacing = u_length / (f64)divisions
var vertical = v_length / (f64)divisions
if edge_size > 0.0:
spacing = math.min(spacing, edge_size)
vertical = math.min(vertical, edge_size)
let initial = try TrimPolygon.quadrangulate_seams(uv, sizes, Vector3(0.0, 0.0, 1.0), ids, spacing, vertical)
defer initial.release()
let chord = math.max(tolerance * 4.0, math.min(u_length, v_length) / ((f64)divisions * (f64)divisions * 4.0))
let constraints = try TrimConstraints.build(uv, ids, sizes)
defer constraints.close()
let part = try refine_uv(initial, surface, u_length, v_length, chord, constraints)
defer part.release()
let mapped = try new i64[(usize)part.value().point_count()] --- in memory.heap
defer free(mapped) in memory.heap
for at in 0..<mapped.length:
let point = try part.value().point((i64)at)
mapped[at] = ids[at] if at < ids.length else (try mesh.point(try evaluate(surface, Vector3(point.x / u_length, point.y / v_length, 0.0))))
for face in 0..<part.value().face_count():
let count = try part.value().face_size(face)
try mesh.face(count)
for at in 0..<count:
try mesh.corner(mapped[(usize)(try part.value().face_point(face, at if sense else count - 1 - at))])