dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / meshing / analytic_trim.lucb
## Periodic analytic support inversion and trim meshing in unwrapped UV space.
pub func analytic_trim(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
if s.kind == surface_sphere and touches_pole(s, mesh.points[..<mesh.np], ids):
try local_or_holes(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)
return
let np = mesh.np
let nf = mesh.nf
let nc = mesh.nc
mesh_in_chart(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size) catch failure:
if failure.code != invalid or s.kind != surface_sphere: error(failure.code, failure.message)
mesh.np = np
mesh.nf = nf
mesh.nc = nc
# Retry a failed angular chart away from an authored pole too, and
# then a chart of the face's own about an axis away from every trim
# (sphere_axis). Canonical trim positions/IDs never move.
try local_or_holes(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)
recover ()
## A sphere face in a local hemisphere's chart, or else sphere_axis's.
func local_or_holes(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
let np = mesh.np
let nf = mesh.nf
let nc = mesh.nc
var meshed = true
local_chart(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
mesh.np = np
mesh.nf = nf
mesh.nc = nc
meshed = false
recover ()
if not meshed: try sphere_axis(mesh, ids, sizes, s, sense, divisions, tolerance, edge_size)
func local_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
let chart = try local_sphere(s, mesh.points[..<mesh.np], ids)
defer chart.close()
try mesh_in_chart(mesh, ids, sizes, chart, sense, divisions, tolerance, edge_size)
func mesh_in_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], s: Surface, sense: bool, divisions: i64, tolerance: f64, edge_size: f64) -> !:
let uv = try new Vector3[ids.length] --- in memory.heap
defer free(uv) in memory.heap
let uscale = math.max(s.radius, tolerance)
let vscale = s.radius if s.kind == surface_sphere else (s.angle if s.kind == surface_torus else 1.0)
var offset: usize = 0
var anchor = Vector3()
for loop in 0..<sizes.length:
var previous = anchor
for at in 0..<(usize)sizes[loop]:
let p = mesh.points[(usize)ids[offset + at]].subtract(s.origin)
let x = p.dot(s.x)
let y = p.dot(s.y)
let z = p.dot(s.z)
let radius = math.sqrt(x * x + y * y)
var u = math.atan2(y, x)
var v = math.atan2(z, radius) if s.kind == surface_sphere else (math.atan2(z, radius - s.radius) if s.kind == surface_torus else z)
if at > 0 or loop > 0:
u = wrap(u, previous.x)
if s.kind == surface_torus:
v = wrap(v, previous.y)
if analytic_point(s, u, v).subtract(mesh.points[(usize)ids[offset + at]]).length() > s.trims_within(tolerance):
error(invalid, "analytic trim is outside its support tolerance")
previous = Vector3(u, v, 0.0)
uv[offset + at] = Vector3(u * uscale, v * vscale, 0.0)
if loop == 0 and at == 0:
anchor = previous
offset += (usize)sizes[loop]
# Each hole lies in the outer loop's turn: its start is unwrapped near
# the outer loop's start, which may leave a hole a whole turn off when
# the outer loop goes once round (a band); moved by whole turns into the
# outer's span instead, whatever edge each loop starts at.
if sizes.length > 1:
var low = uv[0].x
var high = uv[0].x
for at in 0..<(usize)sizes[0]:
low = math.min(low, uv[at].x)
high = math.max(high, uv[at].x)
let turn = 2.0 * math.pi * uscale
var first = (usize)sizes[0]
for loop in 1..<sizes.length:
let count = (usize)sizes[loop]
var middle = 0.0
for at in first..<first + count: middle += uv[at].x
middle /= (f64)count
var shift = 0.0
while middle + shift < low and high - low >= turn * 0.999: shift += turn
while middle + shift > high and high - low >= turn * 0.999: shift -= turn
if shift != 0.0:
for at in first..<first + count: uv[at] = Vector3(uv[at].x + shift, uv[at].y, 0.0)
first += count
# A single loop winding once round the axis bounds a spherical cap
# (a latitude circle, or a wavy loop such as a variable fillet's
# contact round a dome); UV has a singular pole.
if s.kind == surface_sphere and sizes.length == 1 and winds_once(uv, uscale):
try spherical_cap(mesh, ids, uv, s, sense, divisions, tolerance)
return
# Such a loop with holes inside: an azimuthal chart about its pole.
if s.kind == surface_sphere and sizes.length > 1:
let outer = winding_loop(uv, sizes, uscale)
if outer >= 0:
try sphere_disk(mesh, ids, sizes, uv, (usize)outer, s, sense, divisions, tolerance)
return
var spacing = uscale * math.pi / (2.0 * (f64)divisions)
var vertical = vscale * math.pi / (2.0 * (f64)divisions) if s.kind == surface_sphere or s.kind == surface_torus else spacing
var minimum = uv[0]
var maximum = uv[0]
for p in uv:
minimum = Vector3(math.min(minimum.x, p.x), math.min(minimum.y, p.y), 0.0)
maximum = Vector3(math.max(maximum.x, p.x), math.max(maximum.y, p.y), 0.0)
if edge_size == 0.0:
# A tiny-radius, long axial strip must not request millions of square
# cells when target edge length is off. Shared boundary samples retain
# angular resolution; interior refinement stays bounded by divisions.
spacing = math.max(math.min(spacing, (maximum.x - minimum.x) / (f64)divisions), (maximum.x - minimum.x) / ((f64)divisions * 4.0))
vertical = math.max(math.min(vertical, (maximum.y - minimum.y) / (f64)divisions), (maximum.y - minimum.y) / ((f64)divisions * 4.0))
if edge_size > 0.0:
spacing = math.min(spacing, edge_size)
vertical = math.min(vertical, edge_size)
var low = mesh.points[(usize)ids[0]]
var high = low
for id in ids:
let p = mesh.points[(usize)id]
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 deviation = analytic_target(s, high.subtract(low).length(), divisions, tolerance)
# The lattice a little finer than the target, so the refinement does
# not have to split every cell: a cylinder's rows round the axis sag
# under `deviation`; a sphere's or a torus's triangles (whose middles
# stray twice as far as their sides) at their widest circles and
# meridians.
if s.kind == surface_cylinder:
spacing = math.min(spacing, uscale * sag_step(s.radius, deviation * 0.9))
elif s.kind == surface_sphere:
spacing = math.min(spacing, uscale * sag_step(s.radius, deviation * 0.45))
vertical = math.min(vertical, vscale * sag_step(s.radius, deviation * 0.45))
elif s.kind == surface_torus:
spacing = math.min(spacing, uscale * sag_step(s.radius + s.angle, deviation * 0.45))
vertical = math.min(vertical, vscale * sag_step(s.angle, deviation * 0.45))
# Along a cylinder's or a cone's axis nothing bends: rows there only
# shape the cells, so they are at most `divisions` apart over the face
# and cells at most three times as long as wide.
if (s.kind == surface_cylinder or s.kind == surface_cone) and edge_size == 0.0:
vertical = math.min(spacing * 3.0, math.max(vertical, (maximum.y - minimum.y) / (f64)divisions))
try lift_chart(mesh, ids, sizes, uv, s, uscale, vscale, sense, spacing, vertical, deviation)
## The trim loops `ids` (by `sizes`; their chart points `uv`, scaled by
## `uscale` and `vscale`) of a face on analytic surface `s` meshed in that
## chart: a lattice of `spacing` by `vertical` quadrangulated, refined to
## `deviation`, lifted onto `s`; the polygons face its way (`sense`).
func lift_chart(mesh: MeshBuilder*, ids: const i64[], sizes: const i64[], uv: const Vector3[], s: Surface, uscale: f64, vscale: f64, sense: bool, spacing: f64, vertical: f64, deviation: f64) -> !:
let normal = Vector3(0.0, 0.0, 1.0)
let triangles = try TrimPolygon.triangulate_seams(uv, sizes, normal, ids)
defer triangles.release()
let constraints = try TrimConstraints.build(uv, ids, sizes)
defer constraints.close()
let gridded = try insert_grid(triangles, normal, spacing, vertical, constraints)
defer gridded.release()
let improved = try improve(gridded, normal, ids, constraints)
defer improved.release()
var lift = ChartLift(surface = s, uscale = uscale, vscale = vscale)
let refined = try chart_refine(improved, &lift, deviation, ids, constraints)
defer refined.release()
let part = try recombine(refined, normal, 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 p = try part.value().point((i64)at)
mapped[at] = ids[at] if at < ids.length else (try mesh.point(analytic_point(s, p.x / uscale, p.y / vscale)))
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))])
## Whether a loop's chart points (u unwrapped, scaled by `uscale`) go
## round the axis once, every step turning the same way: rows from each
## point straight to the pole then never cross.
func winds_once(uv: const Vector3[], uscale: f64) -> bool:
let turn = 2.0 * math.pi * uscale
var total: f64 = 0.0
var sign: f64 = 0.0
for at in 0..<uv.length:
let next = uv[(at + 1) % uv.length].x
var step = next - uv[at].x
# The closing step comes back from the unwrapped end.
if at + 1 == uv.length: step = wrap(next / uscale, uv[at].x / uscale) * uscale - uv[at].x
if step == 0.0 or step * sign < 0.0: return false
sign = step
total += step
return math.abs(math.abs(total) - turn) <= turn * 1e-9
## A spherical cap's mesh: rows from each boundary point along its
## meridian to the pole the loop goes round (north when it turns
## counterclockwise about the face's normal), `divisions` of them or as
## many as keep the sphere's target inside the cells, thinning out towards
## the pole and closed by a fan there (polar_rows). Going east along the
## loop and north to the pole faces out, so the corners' own order faces
## the face's way.
func spherical_cap(mesh: MeshBuilder*, ids: const i64[], uv: const Vector3[], s: Surface, sense: bool, divisions: i64, tolerance: f64) -> !:
let north = (uv[uv.length - 1].x > uv[0].x) == sense
let pole_v = math.pi * (0.5 if north else -0.5)
let longitudes = try new f64[ids.length] --- in memory.heap
defer free(longitudes) in memory.heap
let starts = try new f64[ids.length] --- in memory.heap
defer free(starts) in memory.heap
var mean: f64 = 0.0
for at in 0..<ids.length:
longitudes[at] = uv[at].x / s.radius
starts[at] = uv[at].y / s.radius
mean += starts[at]
mean /= (f64)ids.length
let step = sag_step(s.radius, analytic_target(s, 0.0, divisions, tolerance) * 0.45)
let rows = (usize)math.max((f64)divisions, math.ceil(math.abs(pole_v - mean) / step))
try polar_rows(mesh, s, ids, longitudes, starts, pole_v, rows, false)