Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / modeling / intersect.lucb

## Where two analytic surfaces meet, exactly, as full curves (carriers): the
## table of cases Fusion-style parts need (docs/research/CAD-MODELING-STUDY.md
## ยง5 Phase 3), every one closed form. Lines are unbounded here; the caller
## bounds and clips them to the faces.
##
##   plane / plane        a line, or coincident (same or opposite facing)
##   plane / cylinder     a circle (axis across the plane), two lines or one
##                        (axis along it), an ellipse (at an angle)
##   plane / cone         a circle (axis across the plane), two lines (the
##                        plane through the axis)
##   plane / sphere       a circle
##   cylinder / cylinder  lines (parallel axes), coincident (one axis, one
##                        radius), two ellipses (one radius, axes crossing:
##                        two fillets meeting at a corner)
##   cylinder / sphere    circles (the center on the axis), one where they
##                        touch (a fillet ending in a rounded corner)
##   sphere / sphere      a circle
##   cone / cone, torus / torus   coincident when one surface twice
##   plane / torus        circles (axis across the plane), the tube's two
##                        sections (the plane through the axis)
## Anything else is not supported yet: the operation says which surfaces.

## What two surfaces share: 0 curves (`out`, maybe none), 1 the same surface
## facing the same way, 2 the same surface facing opposite ways.
pub let meet_curves: i64 = 0
pub let meet_same: i64 = 1
pub let meet_opposite: i64 = 2
## No closed form: the curves are traced (march.lucb).
pub let meet_march: i64 = 3

## A unit vector across `n`.
func across(n: Vector3) -> Vector3!:
    let seed = Vector3(1.0, 0.0, 0.0) if math.abs(n.x) < 0.9 else Vector3(0.0, 1.0, 0.0)
    return try seed.subtract(n.multiply_scalar(seed.dot(n))).normalized()

## Where `s1` and `s2` meet (see above); `tol` is the model's tolerance.
pub func meet(s1: const Surface*, s2: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    if s1.kind > s2.kind: return try meet(s2, s1, tol, out)
    let k1 = s1.kind
    let k2 = s2.kind
    if k1 == surface_plane and k2 == surface_plane: return try plane_plane(s1, s2, tol, out)
    if k1 == surface_plane and k2 == surface_cylinder: return try plane_cylinder(s1, s2, tol, out)
    if k1 == surface_plane and k2 == surface_cone: return try plane_cone(s1, s2, tol, out)
    if k1 == surface_plane and k2 == surface_sphere: return try plane_sphere(s1, s2, tol, out)
    if k1 == surface_cylinder and k2 == surface_cylinder: return try cylinder_cylinder(s1, s2, tol, out)
    if k1 == surface_cylinder and k2 == surface_sphere: return try cylinder_sphere(s1, s2, tol, out)
    if k1 == surface_sphere and k2 == surface_sphere: return try sphere_sphere(s1, s2, tol, out)
    if k1 == surface_plane and k2 == surface_torus: return try plane_torus(s1, s2, tol, out)
    # One cone or torus twice (a blend tool's side lying on the body's).
    if k1 == k2 and (k1 == surface_cone or k1 == surface_torus) and try same_revolution(s1, s2, tol): return meet_same
    # Surfaces of revolution about one axis meet in circles.
    if k1 != surface_plane and k1 != surface_spline and k2 != surface_plane and k2 != surface_spline:
        if try coaxial(s1, s2, tol, out): return meet_curves
    return meet_march

func plane_plane(a: const Surface*, b: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let direction = a.z.cross(b.z)
    # Parallel within noise (a plane turned to where another is): a tilt
    # of 1e-7 moves a model-sized plane less than its tolerance.
    if direction.length() < 1e-7:
        if math.abs(b.origin.subtract(a.origin).dot(a.z)) > tol: return meet_curves
        return meet_same if a.z.dot(b.z) > 0.0 else meet_opposite
    let d = try direction.normalized()
    # The point of both planes nearest the first's origin.
    let h1 = a.z.dot(a.origin)
    let h2 = b.z.dot(b.origin)
    let n12 = a.z.dot(b.z)
    let det = 1.0 - n12 * n12
    let c1 = (h1 - h2 * n12) / det
    let c2 = (h2 - h1 * n12) / det
    let point = a.z.multiply_scalar(c1).add(b.z.multiply_scalar(c2))
    try out.push(Carrier(0, point, d, Vector3(), 0.0, 0.0, -1))
    return meet_curves

func plane_cylinder(p: const Surface*, c: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let n = p.z
    let axis = c.z
    let tilt = n.dot(axis)
    if math.abs(tilt) > 1.0 - 1e-12:
        # Across: the circle where the plane cuts the axis.
        let center = c.origin.add(axis.multiply_scalar(p.origin.subtract(c.origin).dot(n) / tilt))
        try out.push(Carrier(1, center, c.x, axis.cross(c.x), c.radius, c.radius, -1))
        return meet_curves
    if math.abs(tilt) < 1e-12:
        # Along: lines where the plane cuts the cross-section circle.
        let d = c.origin.subtract(p.origin).dot(n)
        if math.abs(d) > c.radius + tol: return meet_curves
        let foot = c.origin.subtract(n.multiply_scalar(d))
        let side = try axis.cross(n).normalized()
        if math.abs(math.abs(d) - c.radius) <= tol:
            try out.push(Carrier(0, foot, axis, Vector3(), 0.0, 0.0, -1))
            return meet_curves
        let half = math.sqrt(c.radius * c.radius - d * d)
        try out.push(Carrier(0, foot.add(side.multiply_scalar(half)), axis, Vector3(), 0.0, 0.0, -1))
        try out.push(Carrier(0, foot.subtract(side.multiply_scalar(half)), axis, Vector3(), 0.0, 0.0, -1))
        return meet_curves
    # At an angle: an ellipse, its major axis the axis's shadow on the plane.
    let center = c.origin.add(axis.multiply_scalar(p.origin.subtract(c.origin).dot(n) / tilt))
    let major_axis = try axis.subtract(n.multiply_scalar(tilt)).normalized()
    let minor_axis = n.cross(major_axis)
    try out.push(Carrier(3, center, major_axis, minor_axis, c.radius / math.abs(tilt), c.radius, -1))
    return meet_curves

func plane_cone(p: const Surface*, c: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let tilt = p.z.dot(c.z)
    if math.abs(tilt) < 1e-12 and math.abs(c.origin.subtract(p.origin).dot(p.z)) <= tol:
        # Through the axis: the two lines of the cone in the plane, radius
        # r + h tan(angle) either side.
        let side = p.z.cross(c.z)
        let k = math.tan(c.angle)
        try out.push(Carrier(0, c.origin.add(side.multiply_scalar(c.radius)), try c.z.add(side.multiply_scalar(k)).normalized(), Vector3(), 0.0, 0.0, -1))
        try out.push(Carrier(0, c.origin.subtract(side.multiply_scalar(c.radius)), try c.z.subtract(side.multiply_scalar(k)).normalized(), Vector3(), 0.0, 0.0, -1))
        return meet_curves
    if math.abs(tilt) < 1.0 - 1e-12: return meet_march
    let height = p.origin.subtract(c.origin).dot(c.z)
    let radius = c.radius + height * math.tan(c.angle)
    if radius <= tol: return meet_curves
    try out.push(Carrier(1, c.origin.add(c.z.multiply_scalar(height)), c.x, c.z.cross(c.x), radius, radius, -1))
    return meet_curves

func plane_sphere(p: const Surface*, s: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let d = s.origin.subtract(p.origin).dot(p.z)
    if math.abs(d) >= s.radius - tol: return meet_curves
    let x = try across(p.z)
    try out.push(Carrier(1, s.origin.subtract(p.z.multiply_scalar(d)), x, p.z.cross(x), math.sqrt(s.radius * s.radius - d * d), 0.0, -1))
    return meet_curves

func cylinder_cylinder(a: const Surface*, b: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    if a.z.cross(b.z).length() > 1e-9: return try crossing_cylinders(a, b, tol, out)
    # Parallel: circles meeting in the cross-section through a's origin.
    let offset = b.origin.subtract(a.origin)
    let planar = offset.subtract(a.z.multiply_scalar(offset.dot(a.z)))
    let distance = planar.length()
    if distance <= tol:
        # One axis and radius: one surface, its normals both outward.
        if math.abs(a.radius - b.radius) <= tol: return meet_same
        return meet_curves
    if distance > a.radius + b.radius + tol or distance < math.abs(a.radius - b.radius) - tol: return meet_curves
    let toward = try planar.normalized()
    let along = (distance * distance + a.radius * a.radius - b.radius * b.radius) / (2.0 * distance)
    let half = math.sqrt(math.max(0.0, a.radius * a.radius - along * along))
    let side = a.z.cross(toward)
    let foot = a.origin.add(toward.multiply_scalar(along))
    try out.push(Carrier(0, foot.add(side.multiply_scalar(half)), a.z, Vector3(), 0.0, 0.0, -1))
    if half > tol:
        try out.push(Carrier(0, foot.subtract(side.multiply_scalar(half)), a.z, Vector3(), 0.0, 0.0, -1))
    return meet_curves

## Cylinders of one radius whose axes cross at a point meet in two ellipses,
## one in each plane bisecting the axes (Steinmetz's curves): each cuts
## either cylinder at the same angle. Two fillets of one radius meeting at
## a corner meet so. Anything else is traced.
func crossing_cylinders(a: const Surface*, b: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    if math.abs(a.radius - b.radius) > tol: return meet_march
    # The axes' common perpendicular must be (nearly) nothing.
    let normal = try a.z.cross(b.z).normalized()
    if math.abs(b.origin.subtract(a.origin).dot(normal)) > tol: return meet_march
    # Where they cross: a's axis at the parameter nearest b's.
    let w = a.origin.subtract(b.origin)
    let c = a.z.dot(b.z)
    let t = (c * w.dot(b.z) - w.dot(a.z)) / (1.0 - c * c)
    let center = a.origin.add(a.z.multiply_scalar(t))
    for k in 0..<2:
        let plane = try (a.z.subtract(b.z) if k == 0 else a.z.add(b.z)).normalized()
        let tilt = math.abs(a.z.dot(plane))
        let major_axis = try a.z.subtract(plane.multiply_scalar(a.z.dot(plane))).normalized()
        try out.push(Carrier(3, center, major_axis, plane.cross(major_axis), a.radius / tilt, a.radius, -1))
    return meet_curves

## A cylinder and a sphere centered on its axis meet in circles where the
## sphere's radius across the axis is the cylinder's: two, or one where they
## touch (the sphere's radius is the cylinder's). Off the axis: traced.
func cylinder_sphere(c: const Surface*, s: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let offset = s.origin.subtract(c.origin)
    let along = offset.dot(c.z)
    if offset.subtract(c.z.multiply_scalar(along)).length() > tol: return meet_march
    let center = c.origin.add(c.z.multiply_scalar(along))
    if s.radius < c.radius - tol: return meet_curves
    let y = c.z.cross(c.x)
    if math.abs(s.radius - c.radius) <= tol:
        try out.push(Carrier(1, center, c.x, y, c.radius, c.radius, -1))
        return meet_curves
    let half = math.sqrt(s.radius * s.radius - c.radius * c.radius)
    try out.push(Carrier(1, center.add(c.z.multiply_scalar(half)), c.x, y, c.radius, c.radius, -1))
    try out.push(Carrier(1, center.subtract(c.z.multiply_scalar(half)), c.x, y, c.radius, c.radius, -1))
    return meet_curves

func sphere_sphere(a: const Surface*, b: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    let offset = b.origin.subtract(a.origin)
    let distance = offset.length()
    if distance <= tol:
        if math.abs(a.radius - b.radius) <= tol: return meet_same
        return meet_curves
    if distance >= a.radius + b.radius - tol or distance <= math.abs(a.radius - b.radius) + tol: return meet_curves
    let toward = try offset.normalized()
    let along = (distance * distance + a.radius * a.radius - b.radius * b.radius) / (2.0 * distance)
    let x = try across(toward)
    try out.push(Carrier(1, a.origin.add(toward.multiply_scalar(along)), x, toward.cross(x), math.sqrt(a.radius * a.radius - along * along), 0.0, -1))
    return meet_curves

## Where a plane across a torus's axis cuts it: circles (two, one, none).
func plane_torus(p: const Surface*, t: const Surface*, tol: f64, out: Growing[Carrier]*) -> i64!:
    if math.abs(p.z.dot(t.z)) < 1e-12 and math.abs(t.origin.subtract(p.origin).dot(p.z)) <= tol:
        # Through the axis: the tube's two sections, circles of the minor
        # radius about the ring either side.
        let side = p.z.cross(t.z)
        try out.push(Carrier(1, t.origin.add(side.multiply_scalar(t.radius)), side, t.z, t.angle, t.angle, -1))
        try out.push(Carrier(1, t.origin.subtract(side.multiply_scalar(t.radius)), side, t.z, t.angle, t.angle, -1))
        return meet_curves
    if math.abs(math.abs(p.z.dot(t.z)) - 1.0) > 1e-12: return meet_march
    let h = p.origin.subtract(t.origin).dot(t.z)
    if math.abs(h) >= t.angle - tol: return meet_curves
    let half = math.sqrt(t.angle * t.angle - h * h)
    let center = t.origin.add(t.z.multiply_scalar(h))
    try out.push(Carrier(1, center, t.x, t.z.cross(t.x), t.radius + half, 0.0, -1))
    try out.push(Carrier(1, center, t.x, t.z.cross(t.x), t.radius - half, 0.0, -1))
    return meet_curves

## Whether cones (or tori) `a` and `b` are one surface: one axis, and the
## same radii along it (a cone's at two heights; a torus's both, at one
## center). Their normals then agree (they point away from the axis).
func same_revolution(a: const Surface*, b: const Surface*, tol: f64) -> bool!:
    if a.z.cross(b.z).length() > 1e-9: return false
    let offset = b.origin.subtract(a.origin)
    if offset.subtract(a.z.multiply_scalar(offset.dot(a.z))).length() > tol: return false
    if a.kind == surface_torus:
        return offset.length() <= tol and math.abs(a.radius - b.radius) <= tol and math.abs(a.angle - b.angle) <= tol
    let scale = math.max(1.0, a.radius + b.radius)
    let heights: f64[2] = [0.0, scale]
    for h in heights:
        let ra = pick(radii_at(a, a.origin, a.z, h), 0)
        let rb = pick(radii_at(b, a.origin, a.z, h), 0)
        if math.abs(ra - rb) > tol: return false
    return true

## The radius of surface of revolution `s` at height `h` along `axis` from
## `base` (sphere and torus: both radii there, the second negative if none).
func radii_at(s: const Surface*, base: Vector3, axis: Vector3, h: f64) -> (f64, f64):
    let own = base.add(axis.multiply_scalar(h)).subtract(s.origin).dot(s.z)
    if s.kind == surface_cylinder: return (s.radius, -1.0)
    if s.kind == surface_cone: return (s.radius + own * math.tan(s.angle), -1.0)
    if s.kind == surface_sphere:
        let d = s.radius * s.radius - own * own
        return ((math.sqrt(d), -1.0) if d >= 0.0 else (-1.0, -1.0))
    let d = s.angle * s.angle - own * own
    if d < 0.0: return (-1.0, -1.0)
    return (s.radius + math.sqrt(d), s.radius - math.sqrt(d))

## Two surfaces of revolution about one axis: the circles where their radii
## agree, found along the axis (sampled, refined by bisection) onto `out`;
## false when their axes differ.
func coaxial(a: const Surface*, b: const Surface*, tol: f64, out: Growing[Carrier]*) -> bool!:
    if a.z.cross(b.z).length() > 1e-9: return false
    let offset = b.origin.subtract(a.origin)
    if offset.subtract(a.z.multiply_scalar(offset.dot(a.z))).length() > tol: return false
    # Heights along a's axis from a's origin where some radius of each agrees.
    let reach = (a.radius + a.angle + b.radius + b.angle + offset.length()) * 4.0 + 1.0
    let steps = 4096
    let step = 2.0 * reach / (f64)steps
    for which_a in 0..<2:
        for which_b in 0..<2:
            var previous = 0.0
            var previous_h = 0.0
            var have = false
            for k in 0..<steps + 1:
                let h = -reach + step * (f64)k
                let value = difference(a, b, h, which_a, which_b)
                if not math.is_finite(value):
                    # A radius ends between the last sample and this one (a
                    # sphere's or torus's top): a crossing just short of the
                    # end falls between no two samples, so the end is looked
                    # at too.
                    if have:
                        let end = range_end(a, b, previous_h, h, which_a, which_b)
                        let at_end = difference(a, b, end, which_a, which_b)
                        if (previous <= 0.0) != (at_end <= 0.0): try push_circle(a, tol, radii_crossing(a, b, previous_h, end, previous, which_a, which_b), which_a, out)
                    have = false
                    continue
                if not have and k > 0:
                    # A radius begins between the last sample and this one.
                    let start = range_end(a, b, h, h - step, which_a, which_b)
                    let at_start = difference(a, b, start, which_a, which_b)
                    if (at_start <= 0.0) != (value <= 0.0): try push_circle(a, tol, radii_crossing(a, b, start, h, at_start, which_a, which_b), which_a, out)
                if have and (previous <= 0.0) != (value <= 0.0): try push_circle(a, tol, radii_crossing(a, b, previous_h, h, previous, which_a, which_b), which_a, out)
                previous = value
                previous_h = h
                have = true
    return true

## Where the radii's difference changes sign between heights `low` (where it
## is `at_low`) and `high`, bisected.
func radii_crossing(a: const Surface*, b: const Surface*, low: f64, high: f64, at_low: f64, which_a: i64, which_b: i64) -> f64:
    var below = low
    var above = high
    for _ in 0..<80:
        let middle = (below + above) * 0.5
        let m = difference(a, b, middle, which_a, which_b)
        if not math.is_finite(m): break
        if (m <= 0.0) == (at_low <= 0.0): below = middle
        else: above = middle
    return (below + above) * 0.5

## The last height from `within` (where both radii exist) toward `beyond`
## (where one does not) where both still do, bisected.
func range_end(a: const Surface*, b: const Surface*, within: f64, beyond: f64, which_a: i64, which_b: i64) -> f64:
    var good = within
    var bad = beyond
    for _ in 0..<80:
        let middle = (good + bad) * 0.5
        if math.is_finite(difference(a, b, middle, which_a, which_b)): good = middle
        else: bad = middle
    return good

## The circle of `a` at height `at` (its radius `which_a`) onto `out`, when
## it is no point.
func push_circle(a: const Surface*, tol: f64, at: f64, which_a: i64, out: Growing[Carrier]*) -> !:
    let r = pick(radii_at(a, a.origin, a.z, at), which_a)
    if r > tol: try out.push(Carrier(curve_circle, a.origin.add(a.z.multiply_scalar(at)), a.x, a.z.cross(a.x), r, 0.0, -1))

func pick(radii: (f64, f64), which: i64) -> f64:
    let (first, second) = radii
    return first if which == 0 else second

## Radius of a (choice which_a) less radius of b (which_b) at height h along
## a's axis; NaN where either has none.
func difference(a: const Surface*, b: const Surface*, h: f64, which_a: i64, which_b: i64) -> f64:
    let ra = pick(radii_at(a, a.origin, a.z, h), which_a)
    let rb = pick(radii_at(b, a.origin, a.z, h), which_b)
    if ra < 0.0 or rb < 0.0: return 0.0 / 0.0
    return ra - rb