dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / tessellation / surface_curvature.lucb
## Principal curvatures of the exact CAD support at tessellated corners, from
## the surface's first and second fundamental forms (rational NURBS second
## derivatives, or the analytic chart's), for curvature analysis shading.
##
## Sign: positive where the surface bends away from its oriented normal, the
## face's outward shading normal. A sphere seen from outside has k1 = k2 = 1/r
## (H = 1/r, K = 1/r^2); a convex cylinder has k1 = 1/r, k2 = 0; the inside
## of a hole is negative. k1 >= k2. Directions are unit tangents (d1 for k1).
pub struct Curvature:
pub var k1: f64 = 0.0
pub var k2: f64 = 0.0
pub var d1: Vector3 = Vector3()
pub var d2: Vector3 = Vector3()
## First and second partial derivatives of a surface chart at one point.
struct Chart:
var su: Vector3 = Vector3()
var sv: Vector3 = Vector3()
var suu: Vector3 = Vector3()
var suv: Vector3 = Vector3()
var svv: Vector3 = Vector3()
## Curvature at `point` of support `s` oriented by `sense`. `seed` carries the
## previous normalized NURBS parameter between neighboring corners.
pub func curvature_at(s: Surface, point: Vector3, sense: bool, seed: Vector3*, tolerance: f64) -> Curvature!:
if s.kind == surface_plane: return flat(s)
var chart = Chart()
var ok = false
if s.kind == surface_spline:
let uv = try chart_parameter(s, point, *seed, tolerance)
*seed = uv
ok = try nurbs_chart(s, uv, &chart)
if not ok:
# A collapsed domain edge: use the limiting interior value, as the
# shading normals do.
ok = try nurbs_chart(s, Vector3(math.clamp(uv.x, 1e-7, 1.0 - 1e-7), math.clamp(uv.y, 1e-7, 1.0 - 1e-7), 0.0), &chart)
else:
let uv = try chart_parameter(s, point, *seed, tolerance, false)
ok = analytic_chart(s, uv, &chart)
if not ok:
# A sphere or torus pole: step off it along the meridian.
ok = analytic_chart(s, Vector3(uv.x, uv.y - math.copysign(1e-6, uv.y), 0.0), &chart)
if not ok: return flat(s)
return principal(chart, sense)
func flat(s: Surface) -> Curvature:
var result = Curvature()
result.d1 = s.x
result.d2 = s.y
return result
## Shape-operator eigenvalues and eigenvectors of one chart point.
func principal(c: Chart, sense: bool) -> Curvature:
let area = c.su.cross(c.sv)
let length = area.length()
var result = Curvature()
let e = c.su.dot(c.su)
let f = c.su.dot(c.sv)
let g = c.sv.dot(c.sv)
let det = e * g - f * f
if not (length > 0.0) or not (det > 0.0): return result
let n = area.multiply_scalar((1.0 if sense else -1.0) / length)
# Second fundamental form with the sign flipped so convex is positive.
let l = -c.suu.dot(n)
let m = -c.suv.dot(n)
let o = -c.svv.dot(n)
let mean = (e * o - 2.0 * f * m + g * l) / (2.0 * det)
let gaussian = (l * o - m * m) / det
let spread = math.sqrt(math.max(mean * mean - gaussian, 0.0))
result.k1 = mean + spread
result.k2 = mean - spread
result.d1 = principal_direction(c, n, l, m, o, e, f, g, result.k1)
result.d2 = n.cross(result.d1)
return result
## Eigenvector of (II - k I) as a unit tangent; any tangent at an umbilic.
func principal_direction(c: Chart, n: Vector3, l: f64, m: f64, o: f64, e: f64, f: f64, g: f64, k: f64) -> Vector3:
let first = c.su.multiply_scalar(m - k * f).subtract(c.sv.multiply_scalar(l - k * e))
let second = c.su.multiply_scalar(o - k * g).subtract(c.sv.multiply_scalar(m - k * f))
let pick = first if first.length() >= second.length() else second
let size = pick.length()
let scale = math.max(c.su.length(), c.sv.length())
if size > 1e-12 * scale * scale * math.max(math.abs(k), 1.0):
return pick.multiply_scalar(1.0 / size)
let fallback = c.su.length()
if fallback > 0.0: return c.su.multiply_scalar(1.0 / fallback)
return n.cross(c.sv).multiply_scalar(1.0 / math.max(n.cross(c.sv).length(), nonzero))
## Native analytic charts, as mapped_patch.point evaluates them.
func analytic_chart(s: Surface, uv: Vector3, c: Chart*) -> bool:
let radial = s.x.multiply_scalar(math.cos(uv.x)).add(s.y.multiply_scalar(math.sin(uv.x)))
let tangent = s.x.multiply_scalar(-math.sin(uv.x)).add(s.y.multiply_scalar(math.cos(uv.x)))
if s.kind == surface_cylinder or s.kind == surface_cone:
let slope = math.tan(s.angle) if s.kind == surface_cone else 0.0
let rho = s.radius + uv.y * slope
c.su = tangent.multiply_scalar(rho)
c.sv = radial.multiply_scalar(slope).add(s.z)
c.suu = radial.multiply_scalar(-rho)
c.suv = tangent.multiply_scalar(slope)
c.svv = Vector3()
elif s.kind == surface_sphere or s.kind == surface_torus:
# Sphere: tube radius = radius about the center; torus: minor radius
# `angle` about a circle of radius `radius`.
let minor = s.radius if s.kind == surface_sphere else s.angle
let major = 0.0 if s.kind == surface_sphere else s.radius
let ring = major + minor * math.cos(uv.y)
c.su = tangent.multiply_scalar(ring)
c.sv = radial.multiply_scalar(-minor * math.sin(uv.y)).add(s.z.multiply_scalar(minor * math.cos(uv.y)))
c.suu = radial.multiply_scalar(-ring)
c.suv = tangent.multiply_scalar(-minor * math.sin(uv.y))
c.svv = radial.multiply_scalar(-minor * math.cos(uv.y)).add(s.z.multiply_scalar(-minor * math.sin(uv.y)))
else:
return false
return c.su.cross(c.sv).length() > 1e-12 * math.max(c.su.dot(c.su), c.sv.dot(c.sv))
## Rational tensor-product derivatives up to second order at normalized `uv`.
func nurbs_chart(s: Surface, uv: Vector3, c: Chart*) -> bool!:
let u0 = s.ku[(usize)s.du]
let u1 = s.ku[(usize)s.nu]
let v0 = s.kv[(usize)s.dv]
let v1 = s.kv[(usize)s.nv]
let u = math.clamp(u0 + (u1 - u0) * uv.x, u0, u1)
let v = math.clamp(v0 + (v1 - v0) * uv.y, v0, v1)
var bu: f64[36]
var bv: f64[36]
let first_u = basis_derivatives(s.ku, s.nu, s.du, u, &bu)
let first_v = basis_derivatives(s.kv, s.nv, s.dv, v, &bv)
# Homogeneous sums in a local frame: derivatives are translation invariant.
let origin = s.points[first_u * (usize)s.nv + first_v]
var a: Vector3[6] = [Vector3(), Vector3(), Vector3(), Vector3(), Vector3(), Vector3()]
var w: f64[6]
for iu in 0..<(usize)s.du + 1:
for iv in 0..<(usize)s.dv + 1:
let index = (first_u + iu) * (usize)s.nv + first_v + iv
let p = s.points[index].subtract(origin)
let weight = s.weights[index]
# (0,0) (1,0) (0,1) (2,0) (1,1) (0,2) partial orders in u, v.
let factors = [bu[iu] * bv[iv], bu[12 + iu] * bv[iv], bu[iu] * bv[12 + iv], bu[24 + iu] * bv[iv], bu[12 + iu] * bv[12 + iv], bu[iu] * bv[24 + iv]]
for at in 0..<(usize)6:
let scaled = factors[at] * weight
a[at] = a[at].add(p.multiply_scalar(scaled))
w[at] += scaled
if not (w[0] > 0.0) or not math.is_finite(w[0]): error(invalid, "invalid rational surface denominator")
let inverse = 1.0 / w[0]
let point = a[0].multiply_scalar(inverse)
c.su = a[1].subtract(point.multiply_scalar(w[1])).multiply_scalar(inverse)
c.sv = a[2].subtract(point.multiply_scalar(w[2])).multiply_scalar(inverse)
c.suu = a[3].subtract(c.su.multiply_scalar(2.0 * w[1])).subtract(point.multiply_scalar(w[3])).multiply_scalar(inverse)
c.suv = a[4].subtract(c.su.multiply_scalar(w[2])).subtract(c.sv.multiply_scalar(w[1])).subtract(point.multiply_scalar(w[4])).multiply_scalar(inverse)
c.svv = a[5].subtract(c.sv.multiply_scalar(2.0 * w[2])).subtract(point.multiply_scalar(w[5])).multiply_scalar(inverse)
let scale = math.max(c.su.dot(c.su), c.sv.dot(c.sv))
return scale > 0.0 and c.su.cross(c.sv).length() > 1e-12 * scale
## Corner curvatures for one face's contiguous corner range: k1 and k2 per
## corner, and with `directions` d1 and d2 (xyz each). Corners sharing a point
## share its value; placement is rigid, so only directions are transformed.
pub func face_curvatures(points: const Vector3[], corners: const i64[], face: BrepFace, s: Surface, tolerance: f64, k1: f64[], k2: f64[], d1: f64[], d2: f64[]) -> !:
var capacity: usize = 16
while capacity < corners.length * 2: capacity *= 2
let keys = try new i64[capacity] --- in memory.heap
defer free(keys) in memory.heap
let values = try new Curvature[capacity] --- in memory.heap
defer free(values) in memory.heap
for at in 0..<capacity: keys[at] = -1
var seed = Vector3(0.5, 0.5, 0.0)
for corner in 0..<corners.length:
let id = corners[corner]
var slot = (usize)((id * 2654435761) ^ (id >> 11)) % capacity
while keys[slot] >= 0 and keys[slot] != id: slot = (slot + 1) % capacity
if keys[slot] < 0:
var value = try curvature_at(s, points[(usize)id], face.sense, &seed, tolerance)
value.d1 = face.placement.transform_direction(value.d1)
value.d2 = face.placement.transform_direction(value.d2)
values[slot] = value
keys[slot] = id
let value = values[slot]
k1[corner] = value.k1
k2[corner] = value.k2
if d1.length > 0:
d1[corner * 3] = value.d1.x
d1[corner * 3 + 1] = value.d1.y
d1[corner * 3 + 2] = value.d1.z
d2[corner * 3] = value.d2.x
d2[corner * 3 + 1] = value.d2.y
d2[corner * 3 + 2] = value.d2.z
## Corner curvature columns of a whole tessellation.
pub struct CurvatureColumns:
pub var k1: f64[]
pub var k2: f64[]
pub var d1: f64[]
pub var d2: f64[]
pub func close():
if self.k1.length > 0: free(self.k1) in memory.heap
if self.k2.length > 0: free(self.k2) in memory.heap
if self.d1.length > 0: free(self.d1) in memory.heap
if self.d2.length > 0: free(self.d2) in memory.heap
struct CurvatureJob:
let points: const Vector3[]
let corners: const i64[]
let starts: const usize[]
let parents: const i64[]
let faces: const BrepFace[]
let surfaces: const Surface[]
let tolerance: f64
let columns: CurvatureColumns*
let errors: FaceErrors*
func curvature_item(raw: void*, group: usize, worker: usize):
let job = (CurvatureJob*)raw
let first = job.starts[group]
let end = job.starts[group + 1]
let face = job.faces[(usize)job.parents[group]]
let c = job.columns
var none_d: f64[]
let d1 = c.d1[first * 3..<end * 3] if c.d1.length > 0 else none_d
let d2 = c.d2[first * 3..<end * 3] if c.d2.length > 0 else none_d
face_curvatures(job.points, job.corners[first..<end], face, job.surfaces[(usize)face.surface], job.tolerance, c.k1[first..<end], c.k2[first..<end], d1, d2) catch failure:
job.errors.record(group, failure.code, failure.message)
## Corner curvatures of an assembled tessellation, per CAD face on the pool.
## `points` are the unplaced support positions; polygons of one CAD face are
## contiguous, as the tessellator assembles them.
pub func model_curvatures(mesh: MeshBuilder*, points: const Vector3[], faces: const BrepFace[], surfaces: const Surface[], tolerance: f64, directions: bool) -> CurvatureColumns!:
var result = CurvatureColumns()
errdefer result.close()
result.k1 = try new f64[mesh.nc] --- in memory.heap
result.k2 = try new f64[mesh.nc] --- in memory.heap
if directions:
result.d1 = try new f64[mesh.nc * 3] --- in memory.heap
result.d2 = try new f64[mesh.nc * 3] --- in memory.heap
let starts = try new usize[mesh.nf + 1] --- in memory.heap
defer free(starts) in memory.heap
let parents = try new i64[mesh.nf + 1] --- in memory.heap
defer free(parents) in memory.heap
var groups: usize = 0
var corner: usize = 0
for polygon in 0..<mesh.nf:
if polygon == 0 or mesh.face_parents[polygon] != mesh.face_parents[polygon - 1]:
starts[groups] = corner
parents[groups] = mesh.face_parents[polygon]
groups += 1
corner += (usize)mesh.sizes[polygon]
starts[groups] = corner
var errors = try FaceErrors(groups)
defer errors.close()
var job = CurvatureJob(points = points, corners = mesh.corners[..<mesh.nc], starts = starts[..<groups + 1], parents = parents[..<groups], faces = faces, surfaces = surfaces, tolerance = tolerance, columns = &result, errors = &errors)
try parallel.for_each(groups, (void*)&job, curvature_item)
try errors.raise()
return result