Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / modeling / coincide.lucb

## Tolerant coincidence (docs/research/KERNEL-ROBUSTNESS.md, 4.4): before a
## boolean meets its faces, what lies together within the project's
## positional tolerance P is made one, once, as a fact every later step
## reads, the way Parasolid's tolerant modelling does:
##
## - A face of the second solid whose surface is the first's within P (the
##   same kind, the same placement and size to within P, and its whole
##   boundary within P of it) is put on that surface. It is coincident with
##   the first's face from then on, exactly, and its edges and vertices
##   lying off it become tolerant by P (or by how far they lie, where two
##   faces moved at a corner put it further).
## - A vertex of the second solid within P of one of the first's is
##   tolerant by P, so the two merge.
##
## Beyond P nothing is changed: the faces cross, touch or stay apart, and
## the rest of the boolean decides at its own fine tolerance. So two faces
## 0.005 mm apart are one face at P = 0.01 mm, at every model size, and two
## faces 0.011 mm apart are two.

## Samples of each edge the boundary tests take.
let edge_samples: usize = 9

## Put the second solid's faces and vertices lying on the first's within P
## onto them (see above).
func coincide(work: Work*) -> !:
    let w = &work.w
    # Within P, to the resolution: a distance of exactly P computed with
    # rounding is within.
    let p = w.tolerances.positional + w.tolerances.resolution()
    # The faces' boxes, once.
    var lows = Growing[Vector3]()
    defer lows.close()
    var highs = Growing[Vector3]()
    defer highs.close()
    for f in 0..<w.faces.count:
        let (l, h) = try face_box(w, f)
        try lows.push(l)
        try highs.push(h)
    var moved = Growing[bool]()
    defer moved.close()
    try moved.fill(w.faces.count, false)
    for fb in work.faces_a..<w.faces.count:
        let sb = w.surfaces.items[(usize)w.faces.items[fb].surface]
        if sb.kind == surface_spline: continue
        for fa in 0..<work.faces_a:
            let sa_index = w.faces.items[fa].surface
            let sa = w.surfaces.items[(usize)sa_index]
            if sa.kind != sb.kind or sa_index == w.faces.items[fb].surface: continue
            if not boxes_meet((lows.items[fa], highs.items[fa]), (lows.items[fb], highs.items[fb]), p): continue
            if not same_placement(&sa, &sb, p, highs.items[fb].subtract(lows.items[fb]).length()): continue
            if not try boundary_on(w, fb, &sa, p): continue
            # One surface stays, the other's face moves onto it: the body's
            # under a tool; between peers the one whose surface comes first,
            # whichever solid it belongs to, so the result is the same with
            # the operands swapped.
            if work.symmetric and surface_before(&sb, &sa) and not moved.items[fa] and try boundary_on(w, fa, &sb, p):
                try put_on(w, fa, w.faces.items[fb].surface)
                moved.items[fa] = true
            else:
                try put_on(w, fb, sa_index)
                moved.items[fb] = true
            break
    try settle_moved(work, moved.view(), p)
    # Vertices of the second solid within P of the first's.
    let first_points = first_point_count(work)
    for b in first_points..<w.points.count:
        let q = w.points.items[b]
        for a in 0..<first_points:
            let d = w.points.items[a].subtract(q).length()
            if d > p or d <= work.tol * 10.0: continue
            try slacken_point(w, b, p)

## The edges and vertices of the faces put on other surfaces that lie off
## where their faces' surfaces now meet (a point projected onto each of its
## faces' surfaces in turn until it settles) made tolerant by P: the
## decision that made them one was made at P, so whatever is found about
## them later (a crossing, a cut, a merged vertex) is one within P too.
func settle_moved(work: Work*, moved: const bool[], p: f64) -> !:
    let w = &work.w
    # Each edge's faces.
    var sides = Growing[i64]()
    defer sides.close()
    try sides.fill(w.edges.count * 2, -1)
    for f in 0..<w.faces.count:
        for use in w.face_uses(f):
            let e = edge_index(use)
            if sides.items[e * 2] < 0: sides.items[e * 2] = (i64)f
            elif sides.items[e * 2 + 1] < 0 and sides.items[e * 2] != (i64)f: sides.items[e * 2 + 1] = (i64)f
    # Each point's faces (its edges' faces), when one of them moved.
    var around = Growing[i64]()
    defer around.close()
    for f in 0..<w.faces.count:
        if not moved[f]: continue
        for use in w.face_uses(f):
            let e = edge_index(use)
            var faces: i64[2] = [sides.items[e * 2], sides.items[e * 2 + 1]]
            var off = 0.0
            for k in 0..<edge_samples:
                let q = try w.edge_at(e, (f64)k / (f64)(edge_samples - 1))
                off = math.max(off, (try snapped(w, q, faces[..<2])).subtract(q).length())
            if off > work.tol * 10.0: try slacken_edge(w, e, math.max(p, off))
    for f in 0..<w.faces.count:
        if not moved[f]: continue
        for use in w.face_uses(f):
            let edge = w.edges.items[edge_index(use)]
            for v in [edge.start, edge.end]:
                around.clear()
                for e in 0..<w.edges.count:
                    let other = w.edges.items[e]
                    if other.start != v and other.end != v: continue
                    for side in 0..<(usize)2:
                        let g = sides.items[e * 2 + side]
                        if g < 0: continue
                        var known = false
                        for h in around.view(): known = known or h == g
                        if not known: try around.push(g)
                let q = w.points.items[(usize)v]
                let off = (try snapped(w, q, around.view())).subtract(q).length()
                if off > work.tol * 10.0: try slacken_point(w, (usize)v, math.max(p, off))

## `q` projected onto each of `faces`' surfaces in turn (-1 skipped) until
## it moves no more: where they meet nearest it.
func snapped(w: const Shape*, q: Vector3, faces: const i64[]) -> Vector3!:
    var at = q
    for _ in 0..<64:
        let before = at
        for f in faces:
            if f >= 0: at = try nearest_on_surface(w, (usize)f, at)
        if at.subtract(before).length() <= w.tolerances.resolution() * 1e-3: break
    return at

## How many of the shape's points are the first solid's: those its faces'
## edges reach (append_shape puts the second's after them).
func first_point_count(work: const Work*) -> usize:
    let w = &work.w
    var most: usize = 0
    for f in 0..<work.faces_a:
        for use in w.face_uses(f):
            let edge = w.edges.items[edge_index(use)]
            if (usize)edge.start + 1 > most: most = (usize)edge.start + 1
            if (usize)edge.end + 1 > most: most = (usize)edge.end + 1
    return most

## Whether surfaces `a` and `b` (one kind, not B-splines) may be one
## surface to within `p` over `extent` (the face's reach): planes by their
## normals turned over the extent (the face's boundary decides), surfaces of
## revolution by their axes, centers and radii.
func same_placement(a: const Surface*, b: const Surface*, p: f64, extent: f64) -> bool:
    let tilt = a.z.cross(b.z).length()
    # A plane: nearly parallel (boundary_on then measures the face itself;
    # turned about its middle it strays half as far as the tilt times its
    # reach).
    if a.kind == surface_plane: return tilt * extent <= p * 4.0
    if a.kind == surface_sphere:
        return b.origin.subtract(a.origin).length() <= p and math.abs(a.radius - b.radius) <= p
    # A cylinder, cone or torus: one axis to within p over the extent.
    if tilt * extent > p: return false
    let offset = b.origin.subtract(a.origin)
    if offset.subtract(a.z.multiply_scalar(offset.dot(a.z))).length() > p: return false
    if a.kind == surface_cylinder: return math.abs(a.radius - b.radius) <= p
    if a.kind == surface_torus:
        return math.abs(offset.dot(a.z)) <= p and math.abs(a.radius - b.radius) <= p and math.abs(a.angle - b.angle) <= p
    # A cone: the same radius where each is placed, and the same slope over
    # the extent.
    let h = offset.dot(a.z)
    let ra = a.radius + h * math.tan(a.angle)
    return math.abs(ra - b.radius) <= p and math.abs(math.tan(a.angle) - math.tan(b.angle)) * extent <= p

## Whether surface `a` comes before `b` (one kind): by origin, x, then y,
## then z, then axis, then radius.
func surface_before(a: const Surface*, b: const Surface*) -> bool:
    let keys_a: f64[8] = [a.origin.x, a.origin.y, a.origin.z, a.z.x, a.z.y, a.z.z, a.radius, a.angle]
    let keys_b: f64[8] = [b.origin.x, b.origin.y, b.origin.z, b.z.x, b.z.y, b.z.z, b.radius, b.angle]
    for k in 0..<(usize)8:
        if keys_a[k] != keys_b[k]: return keys_a[k] < keys_b[k]
    return false

## Whether face `f`'s whole boundary lies within `p` of surface `s`.
func boundary_on(w: const Shape*, f: usize, s: const Surface*, p: f64) -> bool!:
    for use in w.face_uses(f):
        let e = edge_index(use)
        for k in 0..<edge_samples:
            if surface_distance(s, try w.edge_at(e, (f64)k / (f64)(edge_samples - 1))) > p: return false
    return true

## Face `f` put on surface `onto`, facing as it did.
func put_on(w: Shape*, f: usize, onto: i64) -> !:
    let s = &w.surfaces.items[(usize)onto]
    # Its outward normal where it is, before and after.
    let sample = try w.edge_at(edge_index(w.face_uses(f)[0]), 0.5)
    let before = try w.face_normal(f, sample)
    w.faces.items[f].surface = onto
    w.faces.items[f].sense = (try normal_at(s, sample, w.tolerance)).dot(before) > 0.0

func slacken_edge(w: Shape*, e: usize, by: f64) -> !:
    while w.edge_slack.count <= e: try w.edge_slack.push(0.0)
    w.edge_slack.items[e] = math.max(w.edge_slack.items[e], by * 1.01)

func slacken_point(w: Shape*, p: usize, by: f64) -> !:
    while w.point_slack.count <= p: try w.point_slack.push(0.0)
    w.point_slack.items[p] = math.max(w.point_slack.items[p], by * 1.01)