Luce packages
LuceLuce BaseLuciaOS

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