Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / src / cad_edits.lucb

## Editing a set's CAD models through what the viewport picks on. The pick
## mesh is the models' display tessellations joined, each polygon tagged
## with its model (`cad_model`) and B-rep face (`cad_face`), each edge with
## the B-rep edge it lies on (`cad_edge`, -1 inside a face), that edge's
## model (`cad_edge_model`) and, for named models, its reference
## (`cad_edge_reference`); group expressions on it name what a step edits.
## Whole models move and go; faces go (a model losing every face goes with
## them); models are added or replaced (a feature on picked edges).
import interop
import memory
from luce_std import math
from luce_geocore.geocore import Mesh, Vector3, Matrix4, invalid, GeometrySet, Selection
from luce_geocore.core.growing import Growing
from luce_geocore.kernel import ComponentTransform, MeshPart, concatenated, group_bits_of, Domain, TableBuilder, text_attribute, append_text
from model import CadModel
from cad_geometry import set_models, with_models
from modeling import reference_lines, shape_of, CadDirect, CadModeling, found_blends, FoundBlend
from geometry import push_decimal
from luce_std import sort

## Luce's CAD editing operations (Edit CAD).
pub struct CadEdits:
    let reserved: u8 = 0

    ## What Edit CAD's Object, Faces and Edges levels pick on (the models'
    ## kept display tessellations, so nothing is meshed again).
    pub static func pick_mesh(set: interop.Reference[GeometrySet]) -> interop.Reference[Mesh]!:
        let models = set_models(try set.get())
        if models.length == 0: error(invalid, "the geometry has no CAD models")
        var owners = Growing[interop.Reference[Mesh]]()
        defer:
            for owner in owners.view(): owner.release()
            owners.close()
        var parts = Growing[MeshPart]()
        defer parts.close()
        var owning = Growing[f64]()
        defer owning.close()
        for index in 0..<models.length:
            let model = models[index].value()
            let shown = try model.tessellate(16, 0.0, none, model.supports_curvature())
            owners.push(shown) catch failure:
                shown.release()
                error(failure.code, failure.message)
            try parts.push(MeshPart(shown.value(), Matrix4()))
            for face in 0..<shown.value().face_count(): try owning.push((f64)index)
        let joined = try concatenated(parts.view())
        defer joined.release()
        let modeled = try joined.value().with_attribute("cad_model", 2, 1, owning.view(), true)
        defer modeled.release()
        var surfaces = Growing[f64]()
        defer surfaces.close()
        let faces = modeled.value().find_attribute("cad_face", 2)
        for face in 0..<modeled.value().face_count():
            let model = models[(usize)owning.items[(usize)face]].value()
            try surfaces.push((f64)(try model.face_surface_id((i64)(try modeled.value().attribute_value(faces, face)))))
        let tagged = try modeled.value().with_attribute("cad_surface", 2, 1, surfaces.view(), true)
        defer tagged.release()
        var edges = Growing[f64]()
        defer edges.close()
        var edge_models = Growing[i64]()
        defer edge_models.close()
        try edge_owners(tagged.value(), owning.view(), models, &edges, &edge_models)
        let numbered = try tagged.value().with_attribute("cad_edge", 4, 1, edges.view(), true)
        defer numbered.release()
        var owners_of_edges = Growing[f64]()
        defer owners_of_edges.close()
        for model in edge_models.view(): try owners_of_edges.push((f64)model)
        let owned = try numbered.value().with_attribute("cad_edge_model", 4, 1, owners_of_edges.view(), true)
        let chained = try with_chains(owned, models, edges.view(), edge_models.view())
        let referenced = try with_references(chained, models, edges.view(), edge_models.view())
        let named = try with_face_names(referenced, models, owning.view())
        return try with_blend_radii(named, models, owning.view())

    ## Count authored CAD entities, independent of display tessellation density.
    ## Level 0 models, 1 CVs, 2 edges, 3 faces, 5 support patches.
    pub static func selected_entities(pick: interop.Reference[Mesh], selection: interop.Reference[Selection], level: i64) -> i64!:
        let mesh = try pick.get()
        let chosen = try selection.get()
        if level == 1: return chosen.count()
        let domain: i64 = 4 if level == 2 else 2
        if chosen.domain() != domain: return 0
        let owners = mesh.find_attribute("cad_edge_model" if level == 2 else "cad_model", domain)
        let ids = mesh.find_attribute("cad_edge" if level == 2 else ("cad_surface" if level == 5 else "cad_face"), domain)
        if owners < 0 or ids < 0: return 0
        var entities = Growing[i64]()
        defer entities.close()
        var at: i64 = -1
        while true:
            at = chosen.next(at)
            if at < 0: break
            let owner = (i64)(try mesh.attribute_value(owners, at))
            let id = (i64)(try mesh.attribute_value(ids, at)) if level != 0 else 0
            if owner >= 0 and id >= 0: try entities.push(owner * 4294967296 + id)
        sort.sort(entities.items[..<entities.count])
        var count: i64 = 0
        for index in 0..<entities.count:
            if index == 0 or entities.items[index] != entities.items[index - 1]: count += 1
        return count

    ## `set` with the models `group` names on `pick` (whole models only)
    ## moved by Transform Components' numbers: translate, rotate (degrees),
    ## scale, pivot (0 their centroid, 1 the origin, 2 the custom point).
    pub static func transformed_parts(set: interop.Reference[GeometrySet], pick: interop.Reference[Mesh], group: str, numbers: const f64[]) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        var chosen = try Chosen.of(try pick.get(), group, models)
        defer chosen.close()
        for index in 0..<models.length:
            if chosen.faces.items[index] > 0 and chosen.faces.items[index] < chosen.totals.items[index]:
                error(invalid, "only whole CAD models move: pick them at the Object level (faces move with their control vertices)")
        let transform = try ComponentTransform.of(numbers, chosen.centroid)
        let matrix = transform.matrix(transform.translation)
        var result = Growing[interop.Reference[CadModel]]()
        defer:
            for model in result.view(): model.release()
            result.close()
        for index in 0..<models.length:
            let next = (try models[index].value().placed(matrix)) if chosen.faces.items[index] > 0 else models[index].clone()
            result.push(next) catch failure:
                next.release()
                error(failure.code, failure.message)
        return try with_models(source, result.view())

    ## `set` without the faces `group` names on `pick`; a model left with
    ## none goes.
    pub static func without_parts(set: interop.Reference[GeometrySet], pick: interop.Reference[Mesh], group: str) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        let mesh = try pick.get()
        var chosen = try Chosen.of(mesh, group, models)
        defer chosen.close()
        var result = Growing[interop.Reference[CadModel]]()
        defer:
            for model in result.view(): model.release()
            result.close()
        var kept = Growing[i64]()
        defer kept.close()
        for index in 0..<models.length:
            let model = models[index].value()
            if chosen.faces.items[index] == 0:
                try result.push(models[index].clone())
                continue
            kept.clear()
            for face in 0..<model.face_count():
                if not chosen.named(index, face): try kept.push(face)
            if kept.count == 0: continue
            let rest = try model.subset(kept.view())
            result.push(rest) catch failure:
                rest.release()
                error(failure.code, failure.message)
        return try with_models(source, result.view())

    ## The references of the B-rep edges of model `model` that edge group
    ## `group` of `pick` names, apart by `;` ("" when it names none of that
    ## model's): what a feature on picked edges (Fillet) takes.
    pub static func model_edges(pick: interop.Reference[Mesh], group: str, model: i64) -> interop.Owned[str]!:
        let mesh = try pick.get()
        let owner = mesh.find_attribute("cad_edge_model", 4)
        let texts = mesh.find_attribute("cad_edge_reference", 4)
        if owner < 0: error(invalid, "the pick mesh lost its CAD tags")
        if texts < 0: error(invalid, "these edges have no names to keep: they are on a model made without them")
        var bits = try group_bits_of(mesh, group, Domain.edge)
        defer bits.bits.release()
        let words = bits.bits.view()
        var joined = Growing[u8]()
        defer joined.close()
        var seen = Growing[str]()
        defer seen.close()
        for edge in 0..<(try mesh.edge_count()):
            if (words[(usize)edge >> 6] >> (u64)((usize)edge & 63)) & 1 == 0: continue
            if (i64)(try mesh.attribute_value(owner, edge)) != model: continue
            let reference = try mesh.attribute_text(texts, edge)
            if reference == "": continue
            var known = false
            for other in seen.view(): known = known or other == reference
            if known: continue
            try seen.push(reference)
            if joined.count > 0: try append_text(&joined, ";")
            try append_text(&joined, reference)
        return try interop.copy_text((str)joined.view())

    ## The names of the B-rep faces of model `model` that face group `group`
    ## of `pick` names, each once, apart by `;` ("" when it names none of
    ## that model's): what direct modeling's face operations take.
    pub static func model_faces(pick: interop.Reference[Mesh], group: str, model: i64) -> interop.Owned[str]!:
        let mesh = try pick.get()
        let owner = mesh.find_attribute("cad_model", 2)
        let source = mesh.find_attribute("cad_face", 2)
        let texts = mesh.find_attribute("cad_face_name", 2)
        if owner < 0 or source < 0: error(invalid, "the pick mesh lost its CAD tags")
        var bits = try group_bits_of(mesh, group, Domain.face)
        defer bits.bits.release()
        let words = bits.bits.view()
        var joined = Growing[u8]()
        defer joined.close()
        var seen = Growing[i64]()
        defer seen.close()
        for face in 0..<mesh.face_count():
            if (words[(usize)face >> 6] >> (u64)((usize)face & 63)) & 1 == 0: continue
            if (i64)(try mesh.attribute_value(owner, face)) != model: continue
            let brep = (i64)(try mesh.attribute_value(source, face))
            var known = false
            for other in seen.view(): known = known or other == brep
            if known: continue
            try seen.push(brep)
            let name = (try mesh.attribute_text(texts, face)) if texts >= 0 else ""
            if name == "": error(invalid, "a face without a name cannot be referred to: the model's faces have no names")
            if joined.count > 0: try append_text(&joined, ";")
            try append_text(&joined, name)
        return try interop.copy_text((str)joined.view())

    ## How much of model `model` face group `group` of `pick` names: 0
    ## nothing, 1 some of its faces, 2 all of them (the whole model).
    pub static func model_share(pick: interop.Reference[Mesh], group: str, model: i64) -> i64!:
        let mesh = try pick.get()
        let owner = mesh.find_attribute("cad_model", 2)
        if owner < 0: error(invalid, "the pick mesh lost its CAD tags")
        var bits = try group_bits_of(mesh, group, Domain.face)
        defer bits.bits.release()
        let words = bits.bits.view()
        var chosen: i64 = 0
        var total: i64 = 0
        for face in 0..<mesh.face_count():
            if (i64)(try mesh.attribute_value(owner, face)) != model: continue
            total += 1
            if (words[(usize)face >> 6] >> (u64)((usize)face & 63)) & 1 != 0: chosen += 1
        if chosen == 0: return 0
        return 2 if chosen == total else 1

    ## `set` with what face group `group` of `pick` names moved by Transform
    ## Components' numbers (as transformed_parts takes them): a model named
    ## whole is placed, as transformed_parts places it; faces of a model
    ## named in part are turned about the pivot and moved, the faces around
    ## following (CadDirect's Move Face). Faces do not scale: only whole
    ## models do.
    pub static func transformed_faces(set: interop.Reference[GeometrySet], pick: interop.Reference[Mesh], group: str, numbers: const f64[]) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        var chosen = try Chosen.of(try pick.get(), group, models)
        defer chosen.close()
        let transform = try ComponentTransform.of(numbers, chosen.centroid)
        let matrix = transform.matrix(transform.translation)
        let scaled = numbers[6] != 1.0 or numbers[7] != 1.0 or numbers[8] != 1.0
        let (axis, angle) = rotation_of(transform.linear)
        var result = Growing[interop.Reference[CadModel]]()
        defer:
            for model in result.view(): model.release()
            result.close()
        for index in 0..<models.length:
            if chosen.faces.items[index] == 0:
                try result.push(models[index].clone())
                continue
            if chosen.faces.items[index] == chosen.totals.items[index]:
                let placed = try models[index].value().placed(matrix)
                result.push(placed) catch failure:
                    placed.release()
                    error(failure.code, failure.message)
                continue
            if scaled: error(invalid, "faces move and turn, they do not scale: scale whole models at the Object level")
            let names = try CadEdits.model_faces(pick, group, (i64)index)
            defer names.release()
            var moved = models[index].clone()
            if angle > 1e-12:
                let turned = CadDirect.rotated_faces(moved, names.value, transform.pivot, axis, angle) catch failure:
                    moved.release()
                    error(failure.code, failure.message)
                moved.release()
                moved = turned
            if transform.translation.length() > 0.0:
                let shifted = CadDirect.moved_faces(moved, names.value, transform.translation) catch failure:
                    moved.release()
                    error(failure.code, failure.message)
                moved.release()
                moved = shifted
            result.push(moved) catch failure:
                moved.release()
                error(failure.code, failure.message)
        return try with_models(source, result.view())

    ## `set` with every model that has unnamed faces named (CadModeling's
    ## `tagged`, model i's faces `<prefix><i>/f<n>`), so direct modeling
    ## can refer to them; the same set when every face has a name.
    pub static func named_models(set: interop.Reference[GeometrySet], prefix: str) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        var unnamed = false
        for model in models:
            for face in 0..<model.value().face_count():
                if (try model.value().face_name(face)) == "": unnamed = true
        if not unnamed: return set.clone()
        var result = Growing[interop.Reference[CadModel]]()
        defer:
            for model in result.view(): model.release()
            result.close()
        var tag = Growing[u8]()
        defer tag.close()
        for index in 0..<models.length:
            var named = true
            for face in 0..<models[index].value().face_count():
                if (try models[index].value().face_name(face)) == "": named = false
            if named:
                try result.push(models[index].clone())
                continue
            try tag.assign(prefix.bytes)
            try push_decimal(&tag, (i64)index)
            let made = try CadModeling.tagged(models[index], (str)tag.view())
            result.push(made) catch failure:
                made.release()
                error(failure.code, failure.message)
        return try with_models(source, result.view())

    ## The elements of pick mesh `now` that are the B-rep faces (domain 2)
    ## or edges (domain 4) `chosen` selects on pick mesh `before`, as a
    ## group expression of their numbers: a selection carried across a step
    ## that keeps the model's faces and edges but meshes them again (a face
    ## moved). Elements whose B-rep face or edge is gone are left out.
    pub static func carried(before: interop.Reference[Mesh], chosen: interop.Reference[Selection], now: interop.Reference[Mesh]) -> interop.Owned[str]!:
        let prior = try before.get()
        let after = try now.get()
        let selection = try chosen.get()
        let domain = selection.domain()
        if domain != 2 and domain != 4: return try interop.copy_text("")
        let owner_name = "cad_model" if domain == 2 else "cad_edge_model"
        let id_name = "cad_face" if domain == 2 else "cad_edge"
        let old_owner = prior.find_attribute(owner_name, domain)
        let old_id = prior.find_attribute(id_name, domain)
        let new_owner = after.find_attribute(owner_name, domain)
        let new_id = after.find_attribute(id_name, domain)
        if old_owner < 0 or old_id < 0 or new_owner < 0 or new_id < 0: return try interop.copy_text("")
        var keys = Growing[i64]()
        defer keys.close()
        var at: i64 = -1
        while true:
            at = selection.next(at)
            if at < 0: break
            let id = (i64)(try prior.attribute_value(old_id, at))
            if id >= 0: try keys.push((i64)(try prior.attribute_value(old_owner, at)) * 4294967296 + id)
        sort.sort(keys.items[..<keys.count])
        let count = (try after.edge_count()) if domain == 4 else after.face_count()
        var out = Growing[u8]()
        defer out.close()
        var run_start: i64 = -1
        var run_end: i64 = -1
        for element in 0..<count:
            let id = (i64)(try after.attribute_value(new_id, element))
            var taken = false
            if id >= 0:
                let key = (i64)(try after.attribute_value(new_owner, element)) * 4294967296 + id
                var low: usize = 0
                var high = keys.count
                while low < high:
                    let middle = (low + high) // 2
                    if keys.items[middle] < key: low = middle + 1
                    else: high = middle
                taken = low < keys.count and keys.items[low] == key
            if taken and run_end == element - 1 and run_start >= 0:
                run_end = element
                continue
            if run_start >= 0: try push_run(&out, run_start, run_end)
            run_start = element if taken else -1
            run_end = element if taken else -1
        if run_start >= 0: try push_run(&out, run_start, run_end)
        return try interop.copy_text((str)out.view())

    ## `set` with model `index` replaced by `model`.
    pub static func replaced(set: interop.Reference[GeometrySet], index: i64, model: interop.Reference[CadModel]) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        if index < 0 or index >= (i64)models.length: error(invalid, "no such CAD model")
        var all = Growing[interop.Reference[CadModel]]()
        defer all.close()
        for at in 0..<models.length: try all.push(model if (i64)at == index else models[at])
        return try with_models(source, all.view())

    ## `set` with `model` added after its models.
    pub static func with_model(set: interop.Reference[GeometrySet], model: interop.Reference[CadModel]) -> interop.Reference[GeometrySet]!:
        let source = try set.get()
        let models = set_models(source)
        var all = Growing[interop.Reference[CadModel]]()
        defer all.close()
        for existing in models: try all.push(existing)
        try all.push(model)
        return try with_models(source, all.view())

## What a face group names, per model: its polygons' models and B-rep faces.
struct Chosen:
    ## Selected polygons and all polygons, per model.
    var faces: Growing[usize]
    var totals: Growing[usize]
    ## (model, B-rep face) pairs named, as model * 2^32 + face, sorted.
    var named_faces: Growing[i64]
    var centroid: Vector3

    static func of(mesh: const Mesh*, group: str, models: const interop.Reference[CadModel][]) -> Chosen!:
        var result = Chosen(Growing[usize](), Growing[usize](), Growing[i64](), Vector3())
        errdefer result.close()
        try result.faces.fill(models.length, 0)
        try result.totals.fill(models.length, 0)
        let owner = mesh.find_attribute("cad_model", 2)
        let source = mesh.find_attribute("cad_face", 2)
        if owner < 0 or source < 0: error(invalid, "the pick mesh lost its CAD tags")
        var bits = try group_bits_of(mesh, group, Domain.face)
        defer bits.bits.release()
        let words = bits.bits.view()
        var sum = Vector3()
        var count = 0.0
        for face in 0..<mesh.face_count():
            let model = (usize)(try mesh.attribute_value(owner, face))
            if model >= models.length: error(invalid, "the pick mesh does not match its models")
            result.totals.items[model] += 1
            if (words[(usize)face >> 6] >> (u64)((usize)face & 63)) & 1 == 0: continue
            result.faces.items[model] += 1
            try result.named_faces.push((i64)model * 4294967296 + (i64)(try mesh.attribute_value(source, face)))
            sum = sum.add(try mesh.face_center(face))
            count += 1.0
        if count > 0.0: result.centroid = sum.multiply_scalar(1.0 / count)
        sort.sort(result.named_faces.items[..<result.named_faces.count])
        return result

    ## Whether B-rep face `face` of model `model` is named.
    func named(model: usize, face: i64) -> bool:
        let key = (i64)model * 4294967296 + face
        var low: usize = 0
        var high = self.named_faces.count
        while low < high:
            let middle = (low + high) // 2
            if self.named_faces.items[middle] < key: low = middle + 1
            else: high = middle
        return low < self.named_faces.count and self.named_faces.items[low] == key

    func close():
        self.faces.close()
        self.totals.close()
        self.named_faces.close()

## The B-rep edge under every edge of `mesh` (-1 inside a face or on a
## seam): an edge between polygons of two B-rep faces lies on the B-rep edge
## those faces share, the nearest one when they share several. `owning` is
## each polygon's model.
func edge_owners(mesh: const Mesh*, owning: const f64[], models: const interop.Reference[CadModel][], out: Growing[f64]*, out_models: Growing[i64]*) -> !:
    let ends = try mesh.edge_span()
    let edges = ends.length // 2
    try out.fill(edges, -1.0)
    try out_models.fill(edges, -1)
    let source = mesh.find_attribute("cad_face", 2)
    if source < 0: return
    let faces = try mesh.attribute_entry(source)
    let offsets = mesh.offset_span()
    let corner_edges = try mesh.corner_edge_span()
    # The two polygons of each mesh edge.
    let sides = try new i64[edges * 2] --- in memory.heap
    defer free(sides) in memory.heap
    for at in 0..<sides.length: sides[at] = -1
    for face in 0..<offsets.length - 1:
        for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
            let edge = (usize)corner_edges[corner]
            if sides[edge * 2] < 0: sides[edge * 2] = (i64)face
            elif sides[edge * 2 + 1] < 0: sides[edge * 2 + 1] = (i64)face
    var pairs = Growing[FacePairs]()
    defer:
        for at in 0..<pairs.count: pairs.items[at].close()
        pairs.close()
    for model in models: try pairs.push(try FacePairs.of(model.value()))
    let points = mesh.point_span()
    let origin = mesh.position_origin()
    # Consecutive mesh edges follow one B-rep edge: the last pair's answer.
    var last_key: i64 = -1
    var last_edge: i64 = -1
    for edge in 0..<edges:
        let p = sides[edge * 2]
        let q = sides[edge * 2 + 1]
        if p < 0: continue
        let model = (usize)owning[(usize)p]
        if model >= models.length: continue
        if q >= 0 and model != (usize)owning[(usize)q]: continue
        let a = (i64)faces.number((usize)p, 0)
        let b = (i64)faces.number((usize)q, 0) if q >= 0 else -1
        if a == b: continue
        let key = (i64)model * 1099511627776 + (a if a < b else b) * 1048576 + (b if a < b else a)
        let index = &pairs.items[model]
        out_models.items[edge] = (i64)model
        if key == last_key and index.single(a, b):
            out.items[edge] = (f64)last_edge
            continue
        let middle = points[(usize)ends[edge * 2]].vector().add(points[(usize)ends[edge * 2 + 1]].vector()).multiply_scalar(0.5).add(origin)
        last_key = key
        last_edge = try index.nearest(models[model].value(), a, b, middle)
        out.items[edge] = (f64)last_edge

## Takes `mesh`: with each edge's B-rep edge reference (modeling's names:
## the edge's faces and where it is) in text attribute
## `cad_edge_reference`, when a model has names. That is what a feature
## keeps of picked edges, since their numbers change with anything upstream.
func with_references(mesh: interop.Reference[Mesh], models: const interop.Reference[CadModel][], edges: const f64[], edge_models: const i64[]) -> interop.Reference[Mesh]!:
    var strings = TableBuilder()
    defer strings.close()
    # Each model's B-rep edge's string (-1 none), after the earlier models'.
    var ids = Growing[i32]()
    defer ids.close()
    var firsts = Growing[usize]()
    defer firsts.close()
    var lines = Growing[u8]()
    defer lines.close()
    var any = false
    for model in models:
        try firsts.push(ids.count)
        try reference_lines(model.value(), &lines)
        let bytes = lines.view()
        var start: usize = 0
        var line: i64 = 0
        let count = model.value().edge_count()
        for at in 0..<bytes.length + 1:
            if at < bytes.length and bytes[at] != 10: continue
            if line < count:
                let text = (str)bytes[start..<at]
                try ids.push((try strings.intern(text)) if text != "" else -1)
                any = any or text != ""
            line += 1
            start = at + 1
        while (i64)(ids.count - firsts.items[firsts.count - 1]) < count: try ids.push(-1)
    if not any: return mesh
    defer mesh.release()
    let values = try new i32[edges.length] --- in memory.heap
    defer free(values) in memory.heap
    for at in 0..<edges.length:
        let model = edge_models[at]
        values[at] = ids.items[firsts.items[(usize)model] + (usize)edges[at]] if model >= 0 and edges[at] >= 0.0 else -1
    return try mesh.value().with_attribute_entry(try text_attribute("cad_edge_reference", Domain.edge, edges.length, &strings, values))

## Takes `mesh`: with each polygon's B-rep face name (modeling's: what made
## it) in text attribute `cad_face_name`, when a model has names: what a
## sketch on a picked face keeps, as its number changes with anything
## upstream. `owning` is each polygon's model.
func with_face_names(mesh: interop.Reference[Mesh], models: const interop.Reference[CadModel][], owning: const f64[]) -> interop.Reference[Mesh]!:
    let source = mesh.value().find_attribute("cad_face", 2)
    if source < 0: return mesh
    var strings = TableBuilder()
    defer strings.close()
    # Each model's B-rep face's string (-1 none), after the earlier models'.
    var ids = Growing[i32]()
    defer ids.close()
    var firsts = Growing[usize]()
    defer firsts.close()
    var any = false
    for model in models:
        try firsts.push(ids.count)
        for face in 0..<model.value().face_count():
            let name = try model.value().face_name(face)
            try ids.push((try strings.intern(name)) if name != "" else -1)
            any = any or name != ""
    if not any: return mesh
    defer mesh.release()
    let faces = try mesh.value().attribute_entry(source)
    let count = (usize)mesh.value().face_count()
    let values = try new i32[count] --- in memory.heap
    defer free(values) in memory.heap
    for at in 0..<count:
        let model = (usize)owning[at]
        let face = (usize)faces.number(at, 0)
        values[at] = ids.items[firsts.items[model] + face] if model < models.length and firsts.items[model] + face < ids.count else -1
    return try mesh.value().with_attribute_entry(try text_attribute("cad_face_name", Domain.face, count, &strings, values))

## Takes `mesh`: with each polygon's B-rep face's blend radius in attribute
## `cad_blend_radius` (modeling's identify blends; 0 for a face that is no
## constant rolling-ball blend), so the editor tells fillets apart (Select
## blends, Press Pull on them a Reblend) without the B-rep at hand.
## `owning` is each polygon's model.
func with_blend_radii(mesh: interop.Reference[Mesh], models: const interop.Reference[CadModel][], owning: const f64[]) -> interop.Reference[Mesh]!:
    let source = mesh.value().find_attribute("cad_face", 2)
    if source < 0: return mesh
    defer mesh.release()
    # Each model's faces' radii, after the earlier models'.
    var radii = Growing[f64]()
    defer radii.close()
    var firsts = Growing[usize]()
    defer firsts.close()
    var found = Growing[FoundBlend]()
    defer found.close()
    for model in models:
        try firsts.push(radii.count)
        let first = radii.count
        for _ in 0..<model.value().face_count(): try radii.push(0.0)
        if model.value().brep() == none or model.value().independent_faces() > 0: continue
        var w = try shape_of(model.value())
        defer w.close()
        found.clear()
        try found_blends(&w, &found)
        # The shape's faces are the model's, in order.
        for blend in found.view():
            if first + blend.face < radii.count: radii.items[first + blend.face] = blend.radius
    let faces = try mesh.value().attribute_entry(source)
    let count = (usize)mesh.value().face_count()
    var values = Growing[f64]()
    defer values.close()
    for at in 0..<count:
        let model = (usize)owning[at]
        let face = (usize)faces.number(at, 0)
        let index = firsts.items[model] + face if model < models.length else radii.count
        try values.push(radii.items[index] if index < radii.count else 0.0)
    return try mesh.value().with_attribute("cad_blend_radius", 2, 1, values.view(), false)

## A model's B-rep edges by the pair of faces using them: sorted keys
## (low face * 2^20 + high face) and their edges.
struct FacePairs:
    var keys: Growing[i64]

    static func of(model: const CadModel*) -> FacePairs!:
        var result = FacePairs(Growing[i64]())
        errdefer result.close()
        let edges = (usize)model.edge_count()
        var counts = Growing[i64]()
        defer counts.close()
        try counts.fill(edges, 0)
        let first = try new i64[edges] --- in memory.heap
        defer free(first) in memory.heap
        for at in 0..<edges: first[at] = -1
        for face in 0..<model.face_count():
            for use in 0..<(try model.face_edge_count(face)):
                let id = try model.face_edge_id(face, use)
                if id < 0 or (usize)id >= edges: continue
                counts.items[(usize)id] += 1
                let other = first[(usize)id]
                if other < 0:
                    first[(usize)id] = face
                elif other != face and (try model.face_surface_id(other)) != (try model.face_surface_id(face)):
                    # (Two faces of one surface meet at a seam: no edge to
                    # pick, as Fusion's periodic faces have none.)
                    let low = other if other < face else face
                    let high = face if other < face else other
                    # Key in the high bits, edge in the low 24.
                    try result.keys.push((low * 1048576 + high) * 16777216 + id)
        for id in 0..<edges:
            if counts.items[id] == 1:
                try result.keys.push((-1048576 + first[id]) * 16777216 + (i64)id)
        sort.sort(result.keys.items[..<result.keys.count])
        return result

    ## The range of entries for faces `a` and `b`.
    func range(a: i64, b: i64) -> (usize, usize):
        let pair = (a if a < b else b) * 1048576 + (b if a < b else a)
        var low: usize = 0
        var high = self.keys.count
        while low < high:
            let middle = (low + high) // 2
            if self.keys.items[middle] >> 24 < pair: low = middle + 1
            else: high = middle
        var end = low
        while end < self.keys.count and self.keys.items[end] >> 24 == pair: end += 1
        return (low, end)

    ## Whether faces `a` and `b` share exactly one edge.
    func single(a: i64, b: i64) -> bool:
        let (low, end) = self.range(a, b)
        return end == low + 1

    ## The edge faces `a` and `b` share nearest to `point` (-1: none).
    func nearest(model: const CadModel*, a: i64, b: i64, point: Vector3) -> i64!:
        let (low, end) = self.range(a, b)
        if end == low: return -1
        if end == low + 1: return self.keys.items[low] & 16777215
        var found: i64 = -1
        var best = 1e300
        for at in low..<end:
            let id = self.keys.items[at] & 16777215
            for use in 0..<(try model.face_edge_count(a)):
                if (try model.face_edge_id(a, use)) != id: continue
                var distance = 1e300
                for step in 0..<17:
                    distance = math.min(distance, (try model.face_edge_point(a, use, (f64)step / 16.0)).subtract(point).length())
                if distance < best:
                    best = distance
                    found = id
        return found

    func close():
        self.keys.close()


## Takes the mesh. Connected tangent edges share a model-local chain ID;
## corners and ambiguous branches stop a chain. Failures leave single edges.
func with_chains(mesh: interop.Reference[Mesh], models: const interop.Reference[CadModel][], edges: const f64[], edge_models: const i64[]) -> interop.Reference[Mesh]!:
    defer mesh.release()
    var ids = Growing[i64]()
    defer ids.close()
    var firsts = Growing[usize]()
    defer firsts.close()
    for model in models:
        try firsts.push(ids.count)
        var chains = Growing[i64]()
        defer chains.close()
        for edge in 0..<model.value().edge_count(): try chains.push(edge)
        tangent_ids(model.value(), &chains) catch failure:
            for edge in 0..<chains.count: chains.items[edge] = (i64)edge
        for id in chains.view(): try ids.push(id)
    var values = Growing[f64]()
    defer values.close()
    for at in 0..<edges.length:
        let model = edge_models[at]
        try values.push((f64)ids.items[firsts.items[(usize)model] + (usize)edges[at]] if model >= 0 and edges[at] >= 0.0 else -1.0)
    return try mesh.value().with_attribute("cad_edge_chain", 4, 1, values.view(), true)

func tangent_ids(model: const CadModel*, ids: Growing[i64]*) -> !:
    if ids.count == 0: return
    var shape = try shape_of(model)
    defer shape.close()
    for e in 0..<shape.edges.count:
        for end in 0..<2:
            let edge = shape.edges.items[e]
            let vertex = edge.start if end == 0 else edge.end
            let arriving = (try shape.leaving(e, (i64)end)).multiply_scalar(-1.0)
            var candidate: i64 = -1
            var count: usize = 0
            for f in 0..<shape.edges.count:
                if f == e: continue
                let other = shape.edges.items[f]
                if other.start != vertex and other.end != vertex: continue
                let leaving = try shape.leaving(f, 0 if other.start == vertex else 1)
                let alignment = leaving.dot(arriving)
                if math.abs(alignment) < 1.0 - 1e-6: continue
                count += 1
                if alignment > 0.0: candidate = (i64)f
            if count != 1 or candidate < 0: continue
            let a = ids.items[e]
            let b = ids.items[(usize)candidate]
            if a == b: continue
            let keep = a if a < b else b
            for at in 0..<ids.count:
                if ids.items[at] == a or ids.items[at] == b: ids.items[at] = keep

## The axis and angle (radians, 0..π) of rotation matrix `linear`'s turn.
func rotation_of(linear: Matrix4) -> (Vector3, f64):
    let x = linear.x
    let y = linear.y
    let z = linear.z
    let cosine = math.max(-1.0, math.min(1.0, (x.x + y.y + z.z - 1.0) * 0.5))
    let angle = math.acos(cosine)
    if angle < 1e-12: return (Vector3(0.0, 0.0, 1.0), 0.0)
    let skew = Vector3(y.z - z.y, z.x - x.z, x.y - y.x)
    if skew.length() > 1e-9: return (skew.multiply_scalar(1.0 / skew.length()), angle)
    # A half turn: the axis from the diagonal, R = 2aaᵀ - I.
    var axis = Vector3(math.sqrt(math.max(0.0, (x.x + 1.0) * 0.5)), math.sqrt(math.max(0.0, (y.y + 1.0) * 0.5)), math.sqrt(math.max(0.0, (z.z + 1.0) * 0.5)))
    if axis.x >= axis.y and axis.x >= axis.z:
        axis = Vector3(axis.x, x.y / (2.0 * axis.x), x.z / (2.0 * axis.x))
    elif axis.y >= axis.z:
        axis = Vector3(y.x / (2.0 * axis.y), axis.y, y.z / (2.0 * axis.y))
    else:
        axis = Vector3(z.x / (2.0 * axis.z), z.y / (2.0 * axis.z), axis.z)
    return (axis.multiply_scalar(1.0 / axis.length()), angle)

## A run of element numbers `first`..`last` onto group text `out` ("3",
## "3-9"), apart from what is there by a space.
func push_run(out: Growing[u8]*, first: i64, last: i64) -> !:
    if out.count > 0: try out.push(32)
    try push_decimal(out, first)
    if last > first:
        try out.push(45)
        try push_decimal(out, last)