Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / modeling / local_blend.lucb

## Fillets built directly, without booleans (FILLET-STUDY.md ยง3.2): for
## straight edges between flat faces, the result's B-rep is made from the
## body's. Each chosen edge becomes a strip (a cylinder, or for G2 and G3
## its section swept straight) between contact lines on its faces. Each
## face touched keeps its plane, its loops rebuilt: a chosen edge replaced
## by its contact line, a sharp edge at a rounded corner shortened, and at
## a corner the curves the corner leaves on the face. Each corner
## (local_corners.lucb) ends the strips there and adds its own faces: a
## sharp end face's cut, a miter, a ball or a setback patch. Every point
## and curve is made once and shared by the faces meeting there, so the
## result is closed by construction; it is still checked (each edge used
## twice, once each way), and faces are turned to agree.
## What it does not cover (curved faces at a corner, a vertex of four or
## more edges not all chosen, chamfers, rims, mixed corners, an
## unsymmetric miter) it
## declines, and the booleans (blend.lucb) take over. Its cost is the
## touched faces', with no intersection, splitting or classification.

## A chosen edge's strip. Its contact line on face `faces[side]` runs
## `origin + along s + intos[side] reach`; `along` is the edge's way from
## its start. Its ends (0 at the edge's start, 1 at its end) are where the
## corners there cut it: `stops[end]` along the edge, the cut's plane
## `planes[end]` (normal, offset), its contacts `contacts[end * 2 + side]`
## (out points) and its section `sections[end]` (a chain from side 0's
## contact to side 1's).
struct Strip:
    var edge: usize
    var faces: usize[2]
    var intos: Vector3[2]
    var along: Vector3
    var origin: Vector3
    var reach: f64
    var convex: bool
    var planes: Vector3[2]
    var offsets: f64[2]
    var contacts: i64[4]
    var sections: i64[2]
    var lines: i64[2]
    var surface: i64
    var sense: bool
    ## Its fillet's radius (one feature's may differ edge by edge).
    var radius: f64

## A run of out edges from point `head` to point `tail`: uses[first..<first
## + count] in the builder's store, signed as they run that way.
struct Chain:
    var head: i64
    var tail: i64
    var first: usize
    var count: usize

## A face the corners add: its surface, sense, name and loop (a chain).
struct Extra:
    var surface: i64
    var sense: bool
    var name: i64
    var first: usize
    var count: usize

## Where a corner leaves a curve on a face (chain `chain`), at vertex
## `vertex` of face `face`.
struct Link:
    var vertex: i64
    var face: usize
    var chain: usize

## Setback corners' patches kept between radii (a FilletPlan's): a
## corner's patch scales with the radius about its vertex (its setbacks,
## contacts and curves all do, and the fit is made at unit size), so each
## is fitted once, at radius 1. Vertex `vertices[k]`'s quads (about the
## vertex) are quads[firsts[k]..], all of knots `knots`.
struct PatchCache:
    var vertices: Growing[i64]
    var firsts: Growing[usize]
    var quads: Growing[Vector3]
    var knots: Growing[f64]

    func close():
        self.vertices.close()
        self.firsts.close()
        self.quads.close()
        self.knots.close()

    ## Vertex `v`'s patch for `radius` (at corner point `p`) onto `quads`
    ## and `knots`; false when it is not kept yet.
    func scaled(v: i64, p: Vector3, radius: f64, quads: Growing[Vector3]*, knots: Growing[f64]*) -> bool!:
        for k in 0..<self.vertices.count:
            if self.vertices.items[k] != v: continue
            let first = self.firsts.items[k]
            let last = self.firsts.items[k + 1] if k + 1 < self.firsts.count else self.quads.count
            for q in self.quads.view()[first..<last]: try quads.push(p.add(q.multiply_scalar(radius)))
            try knots.assign(self.knots.view())
            return true
        return false

    ## Keep vertex `v`'s patch `quads` (made for `radius`, at corner `p`).
    func keep(v: i64, p: Vector3, radius: f64, quads: const Vector3[], knots: const f64[]) -> !:
        try self.vertices.push(v)
        try self.firsts.push(self.quads.count)
        for q in quads: try self.quads.push(q.subtract(p).multiply_scalar(1.0 / radius))
        try self.knots.assign(knots)

## The builder: the body `w`, the result `out` (its geometry stores begun
## as copies of the body's, so surfaces, carriers and splines keep their
## indices), and what each part of the body became.
struct Local:
    var w: const Shape*
    var out: Shape
    var radius: f64
    var continuity: i64
    var patches: PatchCache*?
    ## Fusion's Tangency weight (fillet_section).
    var blend_shape: BlendShape
    ## Fusion's Setback corner type: three G1 fillets of one kind meet at a
    ## setback corner, not a ball; three of mixed kinds in a vertex blend.
    var setback: bool
    ## Setback corners' least setback (radii), edge shape and fullness.
    var limits: BlendLimits
    ## Each edge's strip, or -1.
    var strip_of: Growing[i64]
    var strips: Growing[Strip]
    ## Each body vertex's out point, made when first used (-1).
    var points: Growing[i64]
    ## Each body edge's out edge, when kept (copied or shortened; -1).
    var kept: Growing[i64]
    ## A sharp edge's new ends at rounded corners (out points; -1: its own).
    var ends: Growing[i64]
    var chains: Growing[Chain]
    var store: Growing[i64]
    var links: Growing[Link]
    var extras: Growing[Extra]
    ## Faces of the result: those of the body first (same order), then the
    ## strips', then the corners'.
    var name: Growing[u8]

    func close():
        self.out.close()
        self.strip_of.close()
        self.strips.close()
        self.points.close()
        self.kept.close()
        self.ends.close()
        self.chains.close()
        self.store.close()
        self.links.close()
        self.extras.close()
        self.name.close()

    ## Body vertex `v`'s out point.
    func point(v: i64) -> i64!:
        if self.points.items[(usize)v] < 0: self.points.items[(usize)v] = try self.out.add_point(self.w.points.items[(usize)v])
        return self.points.items[(usize)v]

    ## A new out point at `p`.
    func new_point(p: Vector3) -> i64!:
        return try self.out.add_point(p)

    func at(id: i64) -> Vector3:
        return self.out.points.items[(usize)id]

    ## A straight out edge from point `a` to `b`.
    func line(a: i64, b: i64) -> i64!:
        let pa = self.at(a)
        let span = self.at(b).subtract(pa)
        let length = span.length()
        if length <= self.w.tolerance: error(invalid, "a direct fillet would make an edge of no length")
        let c = try self.out.add_carrier(Carrier(0, pa, span.multiply_scalar(1.0 / length), Vector3(), 0.0, 0.0, -1))
        return try self.out.add_edge(ShapeEdge(c, 0.0, length, a, b))

    ## The shorter arc from point `a` to `b` of the circle about `center` of
    ## `radius` (in the plane they span with it).
    func arc(a: i64, b: i64, center: Vector3, radius: f64) -> i64!:
        let x = try self.at(a).subtract(center).normalized()
        let to = self.at(b).subtract(center)
        let y = try to.subtract(x.multiply_scalar(to.dot(x))).normalized()
        let sweep = math.atan2(to.dot(y), to.dot(x))
        let c = try self.out.add_carrier(Carrier(1, center, x, y, radius, radius, -1))
        return try self.out.add_edge(ShapeEdge(c, 0.0, sweep, a, b))

    ## The shorter arc from point `a` to `b` of the ellipse about `center`
    ## with semi-axes `major` along `x` and `minor` along `y`.
    func elliptic(a: i64, b: i64, center: Vector3, x: Vector3, y: Vector3, major: f64, minor: f64) -> i64!:
        let pa = self.at(a).subtract(center)
        let pb = self.at(b).subtract(center)
        let ta = math.atan2(pa.dot(y) / minor, pa.dot(x) / major)
        var tb = math.atan2(pb.dot(y) / minor, pb.dot(x) / major)
        while tb - ta > math.pi: tb -= 2.0 * math.pi
        while ta - tb > math.pi: tb += 2.0 * math.pi
        let c = try self.out.add_carrier(Carrier(3, center, x, y, major, minor, -1))
        return try self.out.add_edge(ShapeEdge(c, ta, tb, a, b))

    ## A degree 5 B-spline out edge from point `a` to `b` (its first and
    ## last control points).
    func spline(a: i64, b: i64, net: const Vector3[], knots: const f64[]) -> i64!:
        var weights = Growing[f64]()
        defer weights.close()
        try weights.fill(net.length, 1.0)
        return try self.rational(a, b, net, weights.view(), knots)

    ## The same, rational: `weights` one per control point.
    func rational(a: i64, b: i64, net: const Vector3[], weights: const f64[], knots: const f64[]) -> i64!:
        let index = try self.out.store_spline(net, weights, knots, 5, Matrix4())
        let c = try self.out.add_carrier(Carrier(2, Vector3(), Vector3(), Vector3(), 0.0, 0.0, index))
        return try self.out.add_edge(ShapeEdge(c, knots[5], knots[knots.length - 6], a, b))

    ## A degree 5 B-spline out edge along `net` (`knots`) from `low` to
    ## `high` of its parameter, from point `a` to `b` there.
    func spline_piece(a: i64, b: i64, net: const Vector3[], knots: const f64[], low: f64, high: f64) -> i64!:
        var weights = Growing[f64]()
        defer weights.close()
        try weights.fill(net.length, 1.0)
        let index = try self.out.store_spline(net, weights.view(), knots, 5, Matrix4())
        let c = try self.out.add_carrier(Carrier(2, Vector3(), Vector3(), Vector3(), 0.0, 0.0, index))
        return try self.out.add_edge(ShapeEdge(c, low, high, a, b))

    ## A chain of `uses` from point `head` to `tail`; its index.
    func chain(head: i64, tail: i64, uses: const i64[]) -> usize!:
        try self.chains.push(Chain(head, tail, self.store.count, uses.length))
        for use in uses: try self.store.push(use)
        return self.chains.count - 1

    ## Chain `c`'s uses onto `out`, run from point `start` (its head or tail).
    func walk(c: usize, start: i64, out: Growing[i64]*) -> !:
        let chain = self.chains.items[c]
        if chain.head == start:
            for k in 0..<chain.count: try out.push(self.store.items[chain.first + k])
        elif chain.tail == start:
            var k = chain.count
            while k > 0:
                k -= 1
                try out.push(-self.store.items[chain.first + k])
        else:
            error(invalid, "a direct fillet's curves do not meet")

    ## Chain `c`'s far end from point `start`.
    func other_end(c: usize, start: i64) -> i64:
        let chain = self.chains.items[c]
        return chain.tail if chain.head == start else chain.head

## Edges `chosen` of `w` filleted to `radius` (`continuity`), built
## directly; none when the body or the edges are beyond what this builds
## (the booleans then do it). `patches` keeps setback patches between
## radii, when given. With `setback` (Fusion's Setback corner type) corners
## of three are setback corners, mixed kinds too.
pub func local_blend(w: const Shape*, chosen: const usize[], radius: f64, continuity: i64, tag: str, patches: PatchCache*? = none, blend_shape: BlendShape = plain_blend, radii: (const f64[])? = none, setback: bool = false, limits: BlendLimits = no_limits) -> interop.Reference[CadModel]?!:
    var made = try new_local(w, radius, continuity, patches, blend_shape, setback, limits)
    defer made.close()
    let b = &made
    if not try eligible(b, chosen): return none
    # Each edge its own radius (`radii`, one per chosen edge), or `radius`.
    for at in 0..<chosen.length:
        var own = radius
        if let given = radii: own = given[at]
        try begin_strip(b, chosen[at], own)
    # Each corner: where its strips stop, then the strip surfaces (their
    # extent known), then the corner's curves and faces.
    var corners = Growing[i64]()
    defer corners.close()
    for strip in b.strips.view():
        let edge = w.edges.items[strip.edge]
        let ends: i64[2] = [edge.start, edge.end]
        for v in ends:
            var known = false
            for c in corners.view():
                if c == v: known = true
            if not known: try corners.push(v)
    var plans = Growing[CornerPlan]()
    defer:
        for plan in plans.view():
            var owned = plan
            owned.close()
        plans.close()
    for v in corners.view():
        let plan = plan_corner(b, v) catch failure:
            if failure.code != invalid: error(failure.code, failure.message)
            return none
        try plans.push(plan)
    for s in 0..<b.strips.count:
        strip_surface(b, s) catch failure:
            if failure.code != invalid: error(failure.code, failure.message)
            return none
    for plan in plans.view():
        # A Y corner is only built here: its own reason stands.
        make_corner(b, &plan, tag) catch failure:
            if failure.code != invalid or plan.kind == 5: error(failure.code, failure.message)
            return none
    let result = local_result(b, tag) catch failure:
        if failure.code != invalid: error(failure.code, failure.message)
        return none
    return result

func new_local(w: const Shape*, radius: f64, continuity: i64, patches: PatchCache*?, blend_shape: BlendShape, setback: bool, limits: BlendLimits) -> Local!:
    var out = empty_shape(w.tolerances, w.tolerance)
    out.display = w.display
    errdefer out.close()
    for c in w.carriers.view(): try out.carriers.push(c)
    for sp in w.splines.view(): try out.splines.push(sp)
    for p in w.spline_points.view(): try out.spline_points.push(p)
    for x in w.spline_weights.view(): try out.spline_weights.push(x)
    for k in w.spline_knots.view(): try out.spline_knots.push(k)
    for s in w.surfaces.view():
        try out.surfaces.push(try Surface(s.kind, s.origin, s.x, s.z, s.radius, s.angle, s.points, s.weights, s.ku, s.kv, s.nu, s.nv, s.du, s.dv))
    var made = Local(w, out, radius, continuity, patches, blend_shape, setback, limits, Growing[i64](), Growing[Strip](), Growing[i64](), Growing[i64](), Growing[i64](),
                     Growing[Chain](), Growing[i64](), Growing[Link](), Growing[Extra](), Growing[u8]())
    errdefer made.close()
    # Every edge used exactly twice (its faces: faces_of).
    var seen = Growing[i64]()
    defer seen.close()
    try seen.fill(w.edges.count, 0)
    for use in w.uses.view(): seen.items[edge_index(use)] += 1
    for e in 0..<w.edges.count:
        if seen.items[e] != 2: error(invalid, "an edge must lie between two faces")
    try made.strip_of.fill(w.edges.count, -1)
    try made.points.fill(w.points.count, -1)
    try made.kept.fill(w.edges.count, -1)
    try made.ends.fill(w.edges.count * 2, -1)
    return made

## Edge `e`'s two faces (one face twice for a seam), from the body's
## sides (Shape.index_sides).
func faces_of(b: const Local*, e: usize) -> (usize, usize):
    let first = b.w.sides.items[e * 2]
    let second = b.w.sides.items[e * 2 + 1]
    return ((usize)first, (usize)(second if second >= 0 else first))

## Whether this builds `chosen`: straight edges between two planes, and at
## each of their ends three edges and three flat faces, or four to eight
## edges, all chosen, between as many flat faces (a setback corner, or a
## ball where one touches every face).
func eligible(b: Local*, chosen: const usize[]) -> bool!:
    let w = b.w
    for e in chosen:
        if w.carriers.items[(usize)w.edges.items[e].carrier].kind != curve_line: return false
        let (fa, fb) = faces_of(b, e)
        if fa == fb: return false
        if w.surfaces.items[(usize)w.faces.items[fa].surface].kind != surface_plane or w.surfaces.items[(usize)w.faces.items[fb].surface].kind != surface_plane: return false
        if b.strip_of.items[e] >= 0: return false
        b.strip_of.items[e] = 0
    defer:
        for e in chosen: b.strip_of.items[e] = -1
    var faces = Growing[usize]()
    defer faces.close()
    for e in chosen:
        let edge = w.edges.items[e]
        let ends: i64[2] = [edge.start, edge.end]
        for v in ends:
            let degree = edge_degree(w, v)
            if degree < 3 or degree > (i64)most_setback_edges: return false
            if degree > 3:
                for other in 0..<w.edges.count:
                    let o = w.edges.items[other]
                    if (o.start == v or o.end == v) and b.strip_of.items[other] < 0: return false
            try corner_faces(b, v, &faces)
            if (i64)faces.count != degree: return false
            for f in faces.view():
                if w.surfaces.items[(usize)w.faces.items[f].surface].kind != surface_plane: return false
    return true

## The faces at vertex `v` onto `faces` (cleared first), each once.
func corner_faces(b: const Local*, v: i64, faces: Growing[usize]*) -> !:
    faces.clear()
    let w = b.w
    for e in 0..<w.edges.count:
        let edge = w.edges.items[e]
        if edge.start != v and edge.end != v: continue
        let (fa, fb) = faces_of(b, e)
        let sides: usize[2] = [fa, fb]
        for f in sides:
            var known = false
            for g in faces.view():
                if g == f: known = true
            if not known: try faces.push(f)

## The three faces at vertex `v` (of three edges).
func vertex_faces(b: const Local*, v: i64) -> usize[3]!:
    var faces = Growing[usize]()
    defer faces.close()
    try corner_faces(b, v, &faces)
    if faces.count != 3: error(invalid, "a corner needs three faces")
    return [faces.items[0], faces.items[1], faces.items[2]]

## Edge `e`'s strip of `radius`: its frame, its ends still open.
func begin_strip(b: Local*, e: usize, radius: f64) -> !:
    let w = b.w
    let (fa, fb) = faces_of(b, e)
    let edge = w.edges.items[e]
    let origin = w.points.items[(usize)edge.start]
    let along = try w.points.items[(usize)edge.end].subtract(origin).normalized()
    let ua = try into_face(w, fa, e, along)
    let ub = try into_face(w, fb, e, along)
    let angle = math.acos(math.clamp(ua.dot(ub), -1.0, 1.0))
    let strip = Strip(e, [fa, fb], [ua, ub], along, origin, radius / math.tan(angle * 0.5), try convex(w, e),
                      [Vector3(), Vector3()], [0.0, 0.0], [-1, -1, -1, -1], [-1, -1], [-1, -1], -1, true, radius)
    b.strip_of.items[e] = (i64)b.strips.count
    try b.strips.push(strip)

## Where strip `s`'s contact line on `side` meets the plane of normal `n`
## and offset `h` (its parameter along the edge).
func contact_stop(strip: const Strip*, side: usize, n: Vector3, h: f64) -> f64!:
    let start = strip.origin.add(strip.intos[side].multiply_scalar(strip.reach))
    let crossing = n.dot(strip.along)
    if math.abs(crossing) < 1e-9: error(invalid, "a fillet's end runs along its contact line")
    return (h - n.dot(start)) / crossing

## The point at `s` along strip `strip`'s contact line on `side`.
func contact_at(strip: const Strip*, side: usize, s: f64) -> Vector3:
    return strip.origin.add(strip.along.multiply_scalar(s)).add(strip.intos[side].multiply_scalar(strip.reach))

## Strip `s`'s surface, over its ends: a cylinder (G1) about the line the
## ball rolls along, or its section swept straight (G2, G3). Outward is
## away from the material: off the cylinder's axis at an outside edge,
## toward it at an inside one.
func strip_surface(b: Local*, s: usize) -> !:
    let strip = b.strips.items[s]
    let ua = strip.intos[0]
    let ub = strip.intos[1]
    let angle = math.acos(math.clamp(ua.dot(ub), -1.0, 1.0))
    let bisector = try ua.add(ub).normalized()
    var empty_points: Vector3[]
    var empty_numbers: f64[]
    # The span the ends reach along the edge (their planes may lean).
    var low = 1.0e300
    var high = -1.0e300
    for end in 0..<(usize)2:
        for side in 0..<(usize)2:
            let at = try contact_stop(&strip, side, strip.planes[end], strip.offsets[end])
            low = math.min(low, at)
            high = math.max(high, at)
    if b.continuity == 1:
        let axis = strip.origin.add(bisector.multiply_scalar(strip.radius / math.sin(angle * 0.5)))
        let x = try contact_at(&strip, 0, 0.0).subtract(axis).normalized()
        try b.out.surfaces.push(try Surface(1, axis, x, strip.along, strip.radius, 0.0, empty_points, empty_numbers, empty_numbers, empty_numbers, 0, 0, 0, 0))
        b.strips.items[s].surface = (i64)b.out.surfaces.count - 1
        b.strips.items[s].sense = strip.convex
        return
    # The section at `low`, swept to `high` (a little past each, so the
    # surface's own edges stay off the face's).
    let margin = (high - low) * 0.01 + strip.reach * 0.01
    let start = strip.origin.add(strip.along.multiply_scalar(low - margin))
    var section = Growing[Vector3]()
    defer section.close()
    var knots = Growing[f64]()
    defer knots.close()
    try fillet_section(start.add(ua.multiply_scalar(strip.reach)), start.add(ub.multiply_scalar(strip.reach)), start, b.continuity, &section, &knots, b.blend_shape)
    let sweep = strip.along.multiply_scalar(high - low + margin * 2.0)
    var net = Growing[Vector3]()
    defer net.close()
    for q in section.view():
        try net.push(q)
        try net.push(q.add(sweep))
    var weights = Growing[f64]()
    defer weights.close()
    try weights.fill(net.count, 1.0)
    let kv: f64[4] = [0.0, 0.0, 1.0, 1.0]
    try b.out.surfaces.push(try Surface(3, Vector3(), Vector3(), Vector3(), 0.0, 0.0, net.view(), weights.view(), knots.view(), kv[..<4], (i64)section.count, 2, 5, 1))
    b.strips.items[s].surface = (i64)b.out.surfaces.count - 1
    # du x dv at the section's middle against outward (toward the edge at
    # an outside edge, away from it inside).
    let du = section.items[section.count // 2].subtract(section.items[section.count // 2 - 1])
    let outward = bisector.multiply_scalar(-1.0 if strip.convex else 1.0)
    b.strips.items[s].sense = du.cross(sweep).dot(outward) > 0.0

## Strip `strip`'s section where plane (`n`, `h`) cuts it, from point `a`
## (side 0's contact) to `z` (side 1's): an arc of a circle when the plane
## is square to the edge, else of an ellipse (G1); the section moved along
## the edge onto the plane, an affine copy (G2, G3). Its chain.
func plane_section(b: Local*, strip: const Strip*, n: Vector3, h: f64, a: i64, z: i64) -> usize!:
    let ua = strip.intos[0]
    let ub = strip.intos[1]
    let angle = math.acos(math.clamp(ua.dot(ub), -1.0, 1.0))
    let bisector = try ua.add(ub).normalized()
    let crossing = n.dot(strip.along)
    if b.continuity == 1:
        let axis = strip.origin.add(bisector.multiply_scalar(strip.radius / math.sin(angle * 0.5)))
        let center = axis.add(strip.along.multiply_scalar((h - n.dot(axis)) / crossing))
        var id: i64 = 0
        if math.abs(math.abs(crossing) - 1.0) < 1e-12:
            id = try b.arc(a, z, center, strip.radius)
        else:
            # The minor axis lies in the plane across the edge; the major
            # along the plane's steepest way, longer by 1 / |cos|.
            let minor = try n.cross(strip.along).normalized()
            let major = try minor.cross(n).normalized()
            id = try b.elliptic(a, z, center, major, minor, strip.radius / math.abs(crossing), strip.radius)
        let uses: i64[1] = [id + 1]
        return try b.chain(a, z, uses[..<1])
    var section = Growing[Vector3]()
    defer section.close()
    var knots = Growing[f64]()
    defer knots.close()
    # The section through the plane's point on the edge line, then each
    # control point moved along the edge onto the plane.
    let foot = strip.origin.add(strip.along.multiply_scalar((h - n.dot(strip.origin)) / crossing))
    try fillet_section(foot.add(ua.multiply_scalar(strip.reach)), foot.add(ub.multiply_scalar(strip.reach)), foot, b.continuity, &section, &knots, b.blend_shape)
    for k in 0..<section.count:
        let q = section.items[k]
        section.items[k] = q.add(strip.along.multiply_scalar((h - n.dot(q)) / crossing))
    let id = try b.spline(a, z, section.view(), knots.view())
    let uses: i64[1] = [id + 1]
    return try b.chain(a, z, uses[..<1])