dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / meshing / spherical_triangle.lucb
## A sphere patch bounded by three great-circle arcs (a rounded corner,
## where three fillets meet) meshed on a barycentric grid, its border the
## arcs' own shared samples. Interior point (a, b) lies on three great
## circles between border samples, one per family of grid lines (a fixed,
## b fixed, a + b fixed), at its fraction along each; it is their mean.
## Every triangle is near equilateral and about as large as the arcs'
## steps (weighting the corners' directions instead stretches the middle
## of an octant by the square root of three); there is no pole and no seam
## (a latitude-longitude chart crowds or folds triangles about its pole).
## Arcs sampled unequally are left to the general meshers.
pub func barycentric_sphere(mesh: MeshBuilder*, face: BrepFace, surface: Surface, samples: const Samples[], tolerance: f64, divisions: i64) -> !:
# Each side's samples the way the loop runs, one after another.
var ids = Growing[i64]()
defer ids.close()
var starts: usize[4] = [0, 0, 0, 0]
for at in 0..<(usize)3:
let use = face.uses[at]
let own = samples[edge_index(use)].ids
starts[at] = ids.count
for k in 0..<own.length: try ids.push(own[k] if use > 0 else own[own.length - 1 - k])
starts[3] = ids.count
let n = starts[1] - starts[0] - 1
if n < 1 or starts[2] - starts[1] - 1 != n or starts[3] - starts[2] - 1 != n:
error(invalid, "a sphere triangle's sides are sampled unequally")
for at in 0..<(usize)3:
if ids.items[starts[at] + n] != ids.items[starts[(at + 1) % 3]]: error(invalid, "a sphere triangle's sides do not chain")
let sides = ids.view()
# Its triangles are about as fine as the arcs' samples: those must keep
# the target the general meshers keep (analytic_trim's, for a whole
# sphere), with room for the grid's stretch, or they mesh it.
let c = surface.origin
let deviation = analytic_target(surface, 0.0, divisions, tolerance) / grid_stretch
for at in 0..<(usize)3:
for k in 0..<n:
let p = mesh.points[(usize)ids.items[starts[at] + k]].subtract(c)
let q = mesh.points[(usize)ids.items[starts[at] + k + 1]].subtract(c)
let half = 0.5 * math.acos(math.clamp(p.dot(q) / (p.length() * q.length()), -1.0, 1.0))
if surface.radius * (1.0 - math.cos(half)) > deviation: error(invalid, "a sphere triangle's arcs are sampled too coarsely for a grid")
# Point (a, b): side 0 is b = 0 (A to B), side 1 is a + b = n (B to
# C), side 2 is a = 0 (C to A).
let width = n + 1
let grid = try new i64[width * width] --- in memory.heap
defer free(grid) in memory.heap
for a in 0..<width:
for b in 0..<width - a:
var id: i64 = -1
if b == 0: id = sides[starts[0] + a]
elif a + b == n: id = sides[starts[1] + b]
elif a == 0: id = sides[starts[2] + n - b]
grid[a * width + b] = id
for a in 1..<n:
for b in 1..<n - a:
let rest = n - a - b
# Along a fixed a, b fixed, and a + b fixed.
let first = try arc_point(mesh.points[(usize)grid[a * width]], mesh.points[(usize)grid[a * width + n - a]], c, (f64)b / (f64)(n - a))
let second = try arc_point(mesh.points[(usize)grid[b]], mesh.points[(usize)grid[(n - b) * width + b]], c, (f64)a / (f64)(n - b))
let third = try arc_point(mesh.points[(usize)grid[(n - rest) * width]], mesh.points[(usize)grid[n - rest]], c, (f64)b / (f64)(n - rest))
let mean = try first.add(second).add(third).normalized()
grid[a * width + b] = try mesh.point(c.add(mean.multiply_scalar(surface.radius)))
# Wind the triangles so their normals leave the sphere as the face's do.
let p0 = mesh.points[(usize)grid[0]]
let p1 = mesh.points[(usize)grid[width]]
let p2 = mesh.points[(usize)grid[1]]
let outward = p0.add(p1).add(p2).multiply_scalar(1.0 / 3.0).subtract(c)
let forward = (p1.subtract(p0).cross(p2.subtract(p0)).dot(outward) > 0.0) == face.sense
for a in 0..<n:
for b in 0..<n - a:
let first: i64[3] = [grid[a * width + b], grid[(a + 1) * width + b], grid[a * width + b + 1]]
try push_triangle(mesh, first, forward)
if a + b + 1 < n:
let second: i64[3] = [grid[(a + 1) * width + b], grid[(a + 1) * width + b + 1], grid[a * width + b + 1]]
try push_triangle(mesh, second, forward)
func push_triangle(mesh: MeshBuilder*, corners: i64[3], forward: bool) -> !:
try mesh.face(3)
for at in 0..<(usize)3:
try mesh.corner(corners[at if forward else 2 - at])
## The unit direction from `center` a `fraction` of the way along the
## great circle from `start` to `end`.
func arc_point(start: Vector3, end: Vector3, center: Vector3, fraction: f64) -> Vector3!:
let p = try start.subtract(center).normalized()
let q = try end.subtract(center).normalized()
let angle = math.acos(math.clamp(p.dot(q), -1.0, 1.0))
if angle < 1e-12: return p
let sine = math.sin(angle)
return p.multiply_scalar(math.sin((1.0 - fraction) * angle) / sine).add(q.multiply_scalar(math.sin(fraction * angle) / sine))