Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / modeling / boolean_result.lucb

## A boolean's result (boolean.lucb steps 6 and 7): the pieces the
## operation keeps, merged where they lie on one surface, written as a new
## B-rep; an edge not used exactly twice, once each way, is an error.

## Classify each connected block by its piece with the fewest boundary
## uses first: a point well inside a piece costs in its boundary, and one
## piece's class serves the block (a plate's face with a hundred holes is
## then never the one asked).
func classify_smallest(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], others: Others*) -> !:
    let count = pieces.piece_count()
    var smallest = Growing[i64]()
    defer smallest.close()
    var sizes = Growing[usize]()
    defer sizes.close()
    try smallest.fill(count, -1)
    try sizes.fill(count, 0)
    for p in 0..<count:
        var size: usize = 0
        for c in pieces.piece_cycles(p): size += pieces.cycle(c).length
        sizes.items[p] = size
        let root = union_root(others.block.items, p)
        let best = smallest.items[root]
        if best < 0 or size < sizes.items[(usize)best]: smallest.items[root] = (i64)p
    for root in 0..<count:
        let p = smallest.items[root]
        if p >= 0: _ = try classify(work, traced, piece_face[(usize)p], pieces, (usize)p, others)

## The refusal of a result whose edges are not each used twice.
let not_closed = "the result is not a closed solid (some edges are not shared by two faces); this operation is not supported for these shapes yet"

## The refusal of a result that is not a manifold solid.
let non_manifold = "the result would be non-manifold: the bodies touch along an edge or a face, where four faces meet; non-manifold bodies are not supported yet"

## Steps 4 to 7: split, classify, select and write.
func assemble(work: Work*, op: i64, others: Others*) -> interop.Reference[CadModel]!:
    let w = &work.w
    var traced = try final_shape(work)
    defer traced.close()
    var pieces = try new_pieces()
    defer pieces.close()
    var piece_face = Growing[usize]()
    defer piece_face.close()
    # Each piece's name: its face's, or merged faces' names together.
    var piece_name = Growing[i64]()
    defer piece_name.close()
    try face_pieces(work, &traced, w.faces.count, &pieces, &piece_face, &piece_name)
    # Classify and select.
    try find_blocks(work, &traced, &pieces, piece_face.view(), others)
    try classify_smallest(work, &traced, &pieces, piece_face.view(), others)
    var keep = Growing[bool]()
    defer keep.close()
    var turn = Growing[bool]()
    defer turn.close()
    for p in 0..<pieces.piece_count():
        let f = piece_face.items[p]
        let class = try classify(work, &traced, f, &pieces, p, others)
        let first = work.is_a(f)
        var take = false
        var flip = false
        if op == op_union:
            take = class == class_out or (class == class_same and first)
        elif op == op_subtract:
            if first: take = class == class_out or class == class_opposite
            else:
                take = class == class_in
                flip = true
        else:
            take = class == class_in or (class == class_same and first)
        try keep.push(take)
        try turn.push(flip)
    # Faces touching along a line no section follows (contact.lucb), both
    # kept: the bodies would be pinched together along it.
    for touch in work.contacts.view():
        var kept_a = false
        var kept_b = false
        for p in 0..<pieces.piece_count():
            if not keep.items[p]: continue
            kept_a = kept_a or piece_face.items[p] == touch.fa
            kept_b = kept_b or piece_face.items[p] == touch.fb
        if kept_a and kept_b: error(invalid, non_manifold)
    try merge_pieces(work, &traced, &pieces, &piece_face, &piece_name, &keep, &turn)
    # Every edge used twice, but a face passing through one of them (before
    # the zones' seams, which the traced shape does not hold).
    if (try pieces_closed(work, &pieces, keep.view(), turn.view())) and (try touches_itself(work, &traced, &pieces, piece_face.view(), keep.view())): error(invalid, non_manifold)
    # Faces touching along a section (from outside, joined; one inside the
    # other at its face, subtracted) whose kept pieces both reach it: the
    # merged faces no longer share the section's edge, and the result
    # closes, but it is pinched to nothing along it.
    if try pinched(work, &traced, &pieces, piece_face.view(), keep.view(), op): error(invalid, non_manifold)
    try seam_zones(work, &traced, &pieces, piece_face.view(), keep.view())
    # A result that does not close where the bodies touch along a curve
    # (from outside, joined; one inside the other at its face, subtracted)
    # leaves edges four faces meet at: named so. (A fillet's tool touches
    # the body the same way and closes.)
    var touching = false
    for touch in work.tangencies.view():
        touching = touching or (op == op_union and not touch.same) or (op == op_subtract and touch.same)
    return write_result(work, &pieces, piece_face.view(), piece_name.view(), keep.view(), turn.view()) catch failure:
        if touching and failure.code == invalid and failure.message.compare(not_closed) == 0: error(invalid, non_manifold)
        error(failure.code, failure.message)

## Step 4: the first `faces` faces of the work shape split along the new
## edges into `pieces` on `traced`, each piece's face and name noted.
func face_pieces(work: Work*, traced: const Shape*, faces: usize, pieces: Pieces*, piece_face: Growing[usize]*, piece_name: Growing[i64]*) -> !:
    let w = &work.w
    var halves = Growing[HalfEdge]()
    defer halves.close()
    # The faces no new edge crosses and no cut splits keep their loops as
    # they are: one piece each, with no tracing (drilling the hundredth
    # hole in a plate leaves the other ninety-nine holes' walls whole).
    var touched = Growing[bool]()
    defer touched.close()
    try touched.fill(faces, false)
    for section in work.sections.view():
        if section.fa >= 0 and (usize)section.fa < faces: touched.items[(usize)section.fa] = true
        if section.fb >= 0 and (usize)section.fb < faces: touched.items[(usize)section.fb] = true
    for mark in work.imprints.view():
        if mark.face < faces: touched.items[mark.face] = true
    for f in 0..<faces:
        if not touched.items[f] and not (try split_edges(work, f)):
            try whole_piece(work, f, pieces)
            try piece_face.push(f)
            try piece_name.push(w.faces.items[f].name)
            continue
        halves.clear()
        # The boundary, piece by piece, the way the face uses each edge.
        for use in w.face_uses(f):
            let e = edge_index(use)
            let first = work.piece_starts.items[e]
            let last = work.piece_starts.items[e + 1]
            for k in 0..<last - first:
                let id = work.piece_ids.items[first + k if use > 0 else last - 1 - k]
                let forward = (id > 0) == (use > 0)
                try halves.push(HalfEdge((id if id > 0 else -id) - 1, forward))
        let boundary = halves.count
        # New edges across it, both ways, unless already on its boundary.
        for at in 0..<work.sections.count:
            let section = work.sections.items[at]
            if section.fa != (i64)f and section.fb != (i64)f: continue
            try add_both(&halves, boundary, work.section_ids.items[at])
        for mark in work.imprints.view():
            if mark.face != f: continue
            let first = work.piece_starts.items[mark.edge]
            let last = work.piece_starts.items[mark.edge + 1]
            for k in first..<last:
                let id = work.piece_ids.items[k]
                let final = work.finals.items[edge_index(id)]
                let middle = try w.at(final.carrier, (final.t0 + final.t1) * 0.5)
                if try face_contains(w, f, middle, work.tol) == inside_face: try add_both(&halves, boundary, id)
        let before = pieces.piece_count()
        try split_face(traced, f, halves.view(), try face_pole(w, f), pieces)
        for _ in before..<pieces.piece_count():
            try piece_face.push(f)
            try piece_name.push(w.faces.items[f].name)

## Whether a cut splits one of face `f`'s edges into pieces.
func split_edges(work: const Work*, f: usize) -> bool!:
    for use in work.w.face_uses(f):
        let e = edge_index(use)
        if work.piece_starts.items[e + 1] - work.piece_starts.items[e] != 1: return true
    return false

## Face `f`, whose edges are each one piece, as one piece of its loops in
## their order (its outer loop first).
func whole_piece(work: const Work*, f: usize, pieces: Pieces*) -> !:
    let w = &work.w
    let uses = w.face_uses(f)
    var at: usize = 0
    for size in w.face_sizes(f):
        for k in 0..<(usize)size:
            let use = uses[at + k]
            let id = work.piece_ids.items[work.piece_starts.items[edge_index(use)]]
            let forward = (id > 0) == (use > 0)
            let edge = (id if id > 0 else -id) - 1
            try pieces.uses.push((edge + 1) * (1 if forward else -1))
        try pieces.pieces.push(pieces.cycle_starts.count - 1)
        try pieces.cycle_starts.push(pieces.uses.count)
        at += (usize)size
    try pieces.piece_starts.push(pieces.pieces.count)

## Add final edge `id` (signed) to `halves` both ways, unless one of the
## first `boundary` halves is it.
func add_both(halves: Growing[HalfEdge]*, boundary: usize, id: i64) -> !:
    let edge = (id if id > 0 else -id) - 1
    for at in 0..<boundary:
        if halves.items[at].edge == edge: return
    for at in boundary..<halves.count:
        if halves.items[at].edge == edge: return
    try halves.push(HalfEdge(edge, true))
    try halves.push(HalfEdge(edge, false))

## The shape faces are split in: the final edges over the merged
## vertices, with the work shape's carriers, surfaces and faces (their
## surfaces and senses; their loops are what is being split).
func final_shape(work: Work*) -> Shape!:
    var s = empty_shape(work.w.tolerances, work.tol)
    errdefer s.close()
    for p in work.vertices.view(): try s.points.push(p)
    for c in work.w.carriers.view(): try s.carriers.push(c)
    for sp in work.w.splines.view(): try s.splines.push(sp)
    for p in work.w.spline_points.view(): try s.spline_points.push(p)
    for x in work.w.spline_weights.view(): try s.spline_weights.push(x)
    for k in work.w.spline_knots.view(): try s.spline_knots.push(k)
    for e in work.finals.view(): try s.edges.push(e)
    for su in work.w.surfaces.view():
        try s.surfaces.push(try Surface(su.kind, su.origin, su.x, su.z, su.radius, su.angle, su.points, su.weights, su.ku, su.kv, su.nu, su.nv, su.du, su.dv))
    for face in work.w.faces.view():
        try s.faces.push(ShapeFace(face.surface, face.sense, 0, 0, 0, 0))
    return s

## Step 7: the kept pieces as a new B-rep, which must be closed.
## A final edge cut from a tolerant edge (Stitch's) keeps its precision.
func write_result(work: Work*, pieces: const Pieces*, piece_face: const usize[], piece_name: const i64[], keep: const bool[], turn: const bool[]) -> interop.Reference[CadModel]!:
    var slack = Growing[f64]()
    defer slack.close()
    try slack.fill(work.finals.count, 0.0)
    for e in 0..<work.w.edges.count:
        let precision = work.w.edge_slack_of(e)
        if precision <= 0.0 or e + 1 >= work.piece_starts.count: continue
        for at in work.piece_starts.items[e]..<work.piece_starts.items[e + 1]:
            let id = (usize)(edge_index(work.piece_ids.items[at]))
            slack.items[id] = math.max(slack.items[id], precision)
    # A traced section's edge keeps the distance it was measured to stray
    # from its faces (write_pieces records it when over the tolerance).
    for at in 0..<work.sections.count:
        let section = work.sections.items[at]
        if section.precision <= 0.0: continue
        let id = (usize)edge_index(work.section_ids.items[at])
        slack.items[id] = math.max(slack.items[id], section.precision * 1.01)
    return try write_pieces(work, pieces, piece_face, piece_name, keep, turn, true, 0.0, 0.0, slack.view())

## The kept pieces as a new B-rep: with `closed`, every edge must be used
## twice, once each way (a solid); without, an edge used once is an open
## body's boundary (Trim's sheets). Its tolerance takes in `precision`
## (how far new edges may lie off their faces); with `exact` > 0 it is that
## instead, and each vertex lying off its edges' ends by more is tolerant
## by as much (Stitch's merged vertices).
func write_pieces(work: Work*, pieces: const Pieces*, piece_face: const usize[], piece_name: const i64[], keep: const bool[], turn: const bool[], closed: bool, precision: f64, exact: f64,
                  edge_slack: const f64[]) -> interop.Reference[CadModel]!:
    let w = &work.w
    var uses_count = Growing[i64]()
    defer uses_count.close()
    var direction = Growing[i64]()
    defer direction.close()
    for _ in 0..<work.finals.count:
        try uses_count.push(0)
        try direction.push(0)
    for p in 0..<pieces.piece_count():
        if not keep[p]: continue
        for c in pieces.piece_cycles(p):
            for use in pieces.cycle(c):
                let e = edge_index(use)
                uses_count.items[e] += 1
                direction.items[e] += (1 if use > 0 else -1) * (-1 if turn[p] else 1)
    var open_edges = 0
    # Edges four (six, …) faces meet at, as many each way: the bodies touch
    # along them, and the answer is a non-manifold body.
    var crowded = 0
    for e in 0..<work.finals.count:
        let used = uses_count.items[e]
        if closed and used != 0 and (used != 2 or direction.items[e] != 0):
            open_edges += 1
            if used >= 4 and used % 2 == 0 and direction.items[e] == 0: crowded += 1
        # Open, an edge is a boundary (once) or shared each way (twice).
        if not closed and used > 1 and (used != 2 or direction.items[e] != 0): open_edges += 1
    if open_edges > 0:
        if closed and crowded == open_edges: error(invalid, non_manifold)
        if closed: error(invalid, not_closed)
        error(invalid, "the result's faces do not meet edge to edge")
    # Merged vertices sit within ten tolerances of their curves.
    # The result's own tolerance (what it is meshed to and its edges are
    # checked against when written): two millionths of the work's size,
    # or wider where its edges' precision is.
    let tolerance = exact if exact > 0.0 else math.min(1.0, math.max(math.max(work.size * 2e-6, precision * 2.0), least_tolerance))
    let output = try BrepModel.held(work.w.tolerances, math.max(tolerance, least_tolerance))
    defer output.release()
    let b = output.value()
    var vertex_ids = Growing[i64]()
    defer vertex_ids.close()
    for _ in work.vertices.view(): try vertex_ids.push(-1)
    var slack = Growing[f64]()
    defer slack.close()
    try slack.fill(work.vertices.count, 0.0)
    # How far each vertex is from its edges' ends: with an exact
    # tolerance (Stitch's merged vertices), or without one only where a
    # tolerant edge's precision merged it.
    for e in 0..<work.finals.count:
        if uses_count.items[e] == 0: continue
        let edge = work.finals.items[e]
        let a = (try w.at(edge.carrier, edge.t0)).subtract(work.placed(edge.start)).length()
        let z = (try w.at(edge.carrier, edge.t1)).subtract(work.placed(edge.end)).length()
        # A vertex's zone holds its edges' (a tolerant edge's precision).
        let own = edge_slack[e] if e < edge_slack.length else 0.0
        slack.items[(usize)edge.start] = math.max(slack.items[(usize)edge.start], math.max(a * 1.01, own))
        slack.items[(usize)edge.end] = math.max(slack.items[(usize)edge.end], math.max(z * 1.01, own))
    # The order everything is written in (canonical.lucb): between peers
    # one of the result's own geometry.
    var layout = try layout_of(work, pieces, piece_face, keep, turn)
    defer layout.close()
    var edge_ids = Growing[i64]()
    defer edge_ids.close()
    try edge_ids.fill(work.finals.count, -1)
    for e in layout.edges.view():
        if uses_count.items[e] == 0: continue
        let edge = work.finals.items[e]
        let flip = layout.flipped.items[e]
        let first = edge.end if flip else edge.start
        let last = edge.start if flip else edge.end
        for v in [first, last]:
            if vertex_ids.items[(usize)v] >= 0: continue
            vertex_ids.items[(usize)v] = try b.add_vertex(work.placed(v))
            if slack.items[(usize)v] > tolerance: try b.set_vertex_precision(vertex_ids.items[(usize)v], slack.items[(usize)v])
        let start = vertex_ids.items[(usize)first]
        let end = vertex_ids.items[(usize)last]
        let c = w.carriers.items[(usize)edge.carrier]
        var forward = (edge.t1 > edge.t0) != flip
        var id: i64 = -1
        if c.kind == curve_line: id = try b.add_line(start, end)
        elif c.kind == curve_circle or c.kind == curve_ellipse:
            var axis = c.x.cross(c.y)
            # Between peers: the axis up the first axis it leans along, and
            # a circle's reference through its first vertex (a closed one's
            # seam stays where its vertex is).
            var reference = c.x
            if work.symmetric:
                let (turned, sign_flipped) = canonical_axis(axis)
                axis = turned
                if sign_flipped: forward = not forward
                if c.kind == curve_circle:
                    let toward = work.placed(first).subtract(c.origin)
                    reference = toward.subtract(axis.multiply_scalar(toward.dot(axis)))
                else:
                    let (major, _) = canonical_axis(c.x)
                    reference = major
            id = (try b.add_circle(start, end, c.origin, axis, reference, c.a, forward)) if c.kind == curve_circle else (try b.add_ellipse(start, end, c.origin, axis, reference, c.a, c.b, forward))
        else:
            let (points, weights, knots, degree) = w.spline_net(c.spline)
            id = try b.add_spline_edge(start, end, points, weights, degree, knots, forward)
        # A joined edge's precision: how far apart the edges it joined lay.
        if e < edge_slack.length and edge_slack[e] > tolerance: try b.set_edge_precision(id, edge_slack[e])
        edge_ids.items[e] = id
    var surface_ids = Growing[i64]()
    defer surface_ids.close()
    for _ in w.surfaces.view(): try surface_ids.push(-1)
    var uses = Growing[i64]()
    defer uses.close()
    var sizes = Growing[i64]()
    defer sizes.close()
    for k in 0..<layout.order.count:
        let p = layout.order.items[k]
        let face = w.faces.items[piece_face[p]]
        let si = (usize)face.surface
        if surface_ids.items[si] < 0:
            let s = w.surfaces.items[si]
            surface_ids.items[si] = (try b.add_spline_surface(s.points, s.weights, s.nu, s.nv, s.du, s.dv, s.ku, s.kv)) if s.kind == surface_spline else (try b.add_surface(s.kind, s.origin, s.z, s.x, s.radius, s.angle))
        uses.clear()
        sizes.clear()
        for loop in 0..<layout.loop_count(k):
            let cycle = layout.piece_uses(k, loop)
            for use in cycle:
                let e = edge_index(use)
                let runs = (use > 0) != layout.flipped.items[e]
                try uses.push((edge_ids.items[e] + 1) * (1 if runs else -1))
            try sizes.push((i64)cycle.length)
        let made = try b.add_face(surface_ids.items[si], uses.view(), sizes.view(), face.sense != turn[p])
        try b.set_face_name(made, w.name(piece_name[p]))
    return try CadModel.of_brep(output)


## Whether every edge of the kept pieces is used twice, once each way.
func pieces_closed(work: Work*, pieces: const Pieces*, keep: const bool[], turn: const bool[]) -> bool!:
    var uses_count = Growing[i64]()
    defer uses_count.close()
    var direction = Growing[i64]()
    defer direction.close()
    try uses_count.fill(work.finals.count, 0)
    try direction.fill(work.finals.count, 0)
    for p in 0..<pieces.piece_count():
        if not keep[p]: continue
        for c in pieces.piece_cycles(p):
            for use in pieces.cycle(c):
                let e = edge_index(use)
                uses_count.items[e] += 1
                direction.items[e] += (1 if use > 0 else -1) * (-1 if turn[p] else 1)
    for e in 0..<work.finals.count:
        if uses_count.items[e] != 0 and (uses_count.items[e] != 2 or direction.items[e] != 0): return false
    return true

## Whether an edge of the kept pieces lies inside another kept piece's face
## (a hole's wall tangent to a face from inside: the face passes through
## the edge, the solid has no thickness there). Analytic faces whose
## surface the edge lies on, at a quarter, half and three quarters of its
## length, are checked (an edge touching a face at one point, as a ball
## touching a box, is no such edge).
func touches_itself(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[]) -> bool!:
    let w = &work.w
    var used = Growing[bool]()
    defer used.close()
    try used.fill(work.finals.count, false)
    for p in 0..<pieces.piece_count():
        if not keep[p]: continue
        for c in pieces.piece_cycles(p):
            for use in pieces.cycle(c): used.items[edge_index(use)] = true
    for e in 0..<work.finals.count:
        if not used.items[e]: continue
        let edge = work.finals.items[e]
        let middle = try w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
        let quarter = try w.at(edge.carrier, edge.t0 * 0.75 + edge.t1 * 0.25)
        let three = try w.at(edge.carrier, edge.t0 * 0.25 + edge.t1 * 0.75)
        for q in 0..<pieces.piece_count():
            if not keep[q]: continue
            let f = piece_face[q]
            let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
            if s.kind == surface_spline: continue
            if surface_distance(s, middle) > work.tol * 10.0 or surface_distance(s, quarter) > work.tol * 10.0 or surface_distance(s, three) > work.tol * 10.0: continue
            # Not one of its own edges.
            var bounds = false
            for c in pieces.piece_cycles(q):
                for use in pieces.cycle(c):
                    if edge_index(use) == e: bounds = true
            if bounds: continue
            if (try piece_holds(work, traced, f, pieces, q, middle)) and (try piece_holds(work, traced, f, pieces, q, quarter)) and (try piece_holds(work, traced, f, pieces, q, three)): return true
    return false

## Whether faces the tangencies note touch along a section where the
## operation keeps material on neither side between them, and a kept piece
## of each face reaches that section (bounded by it or holding it).
func pinched(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[], op: i64) -> bool!:
    let w = &work.w
    for touch in work.tangencies.view():
        if not ((op == op_union and not touch.same) or (op == op_subtract and touch.same)): continue
        for at in 0..<work.sections.count:
            let section = work.sections.items[at]
            let pair = (section.fa == (i64)touch.fa and section.fb == (i64)touch.fb) or (section.fa == (i64)touch.fb and section.fb == (i64)touch.fa)
            if not pair: continue
            let id = work.section_ids.items[at]
            let e = edge_index(id)
            let edge = work.finals.items[e]
            let middle = try w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
            if (try kept_reaches(work, traced, pieces, piece_face, keep, touch.fa, e, middle)) and (try kept_reaches(work, traced, pieces, piece_face, keep, touch.fb, e, middle)): return true
    return false

## Whether a kept piece of face `f` has final edge `e` on its boundary or
## holds `p` (on it).
func kept_reaches(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[], f: usize, e: usize, p: Vector3) -> bool!:
    for q in 0..<pieces.piece_count():
        if not keep[q] or piece_face[q] != f: continue
        for c in pieces.piece_cycles(q):
            for use in pieces.cycle(c):
                if edge_index(use) == e: return true
        if try piece_holds(work, traced, f, pieces, q, p): return true
    return false