Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / modeling / classify.lucb

## The booleans' classification (step 5): a point well inside each piece,
## and whether it lies inside the other solid, on its coincident face, or
## outside.

## Offsets off the cells' middles (in cells), uneven so a sample does not
## fall on a piece's symmetric features.
let piece_offset_u: f64 = 0.0098765432
let piece_offset_v: f64 = 0.0123456789
## The steps beside a boundary segment, as shares of its length, a point
## inside is looked for at, the farthest first.
let beside_fractions: f64[4] = [0.25, 0.05, 0.01, 0.001]

## A point well inside piece `p` of face `f`: across the middle of its
## chart, the middle of the widest stretch inside it, on the surface.
func piece_point(work: Work*, traced: const Shape*, f: usize, pieces: const Pieces*, p: usize) -> Vector3!:
    let face = work.w.faces.items[f]
    var chart = Growing[Vector3]()
    defer chart.close()
    var starts = Growing[usize]()
    defer starts.close()
    for c in pieces.piece_cycles(p):
        try starts.push(chart.count)
        try loop_chart(traced, face.surface, try face_pole(&work.w, f), pieces.cycle(c), &chart)
    try starts.push(chart.count)
    var low = Vector3(1.0e300, 1.0e300, 0.0)
    var high = Vector3(-1.0e300, -1.0e300, 0.0)
    for q in chart.view():
        low = Vector3(math.min(low.x, q.x), math.min(low.y, q.y), 0.0)
        high = Vector3(math.max(high.x, q.x), math.max(high.y, q.y), 0.0)
    # Angles count by the radius, so clearances compare like lengths.
    let s = &work.w.surfaces.items[(usize)face.surface]
    let wraps = periodic(s)
    let scale = 1.0 if s.kind == surface_plane or s.kind == surface_spline else math.max(s.radius, nonzero)
    # The chart with angles scaled, for clearances.
    var scaled = Growing[Vector3]()
    defer scaled.close()
    for q in chart.view(): try scaled.push(Vector3(q.x * scale, q.y, 0.0))
    var best_u = 0.0
    var best_v = 0.0
    var best = -1.0
    # First a few candidates: a point a quarter of the piece's narrower
    # extent from every boundary segment is well inside already (a disk
    # cut from a face by a hole is found at once).
    let enough = 0.25 * math.min((high.x - low.x) * scale, high.y - low.y)
    for row in 0..<3:
        for column in 0..<5:
            let u = low.x + (high.x - low.x) * ((f64)column + 0.5 + piece_offset_u) / 5.0
            let v = low.y + (high.y - low.y) * ((f64)row + 0.5 + piece_offset_v) / 3.0
            if chart_winding(chart.view(), starts.view(), u, v, wraps, s.kind == surface_torus) == 0: continue
            let clearance = nearest_segment(scaled.view(), starts.view(), u * scale, v, best)
            if clearance > best:
                best = clearance
                best_u = u
                best_v = v
    if enough > 0.0 and best >= enough: return try surface_point(work.w.surfaces.items[(usize)face.surface], Vector3(best_u, best_v, 0.0))
    best = -1.0
    # A coarse grid of candidates off the vertices (an irrational step); of
    # those inside, the one farthest from every boundary segment; then
    # finer grids about the best so far.
    var cell_u = (high.x - low.x) / 24.0
    var cell_v = (high.y - low.y) / 12.0
    var from_u = low.x + cell_u * (0.5 + piece_offset_u)
    var from_v = low.y + cell_v * (0.5 + piece_offset_v)
    var columns = 24
    var rows = 12
    for round in 0..<4:
        for row in 0..<rows:
            let v = from_v + cell_v * (f64)row
            for column in 0..<columns:
                let u = from_u + cell_u * (f64)column
                if chart_winding(chart.view(), starts.view(), u, v, wraps, s.kind == surface_torus) == 0: continue
                let clearance = nearest_segment(scaled.view(), starts.view(), u * scale, v, best)
                if clearance > best:
                    best = clearance
                    best_u = u
                    best_v = v
        if best < 0.0 and round == 0:
            # A piece thinner than the grid's cells (a thin wall's ring
            # round a hole): beside the middle of each boundary segment,
            # stepping in, on whichever side is inside.
            let (u, v, clearance) = beside_boundary(chart.view(), scaled.view(), starts.view(), scale, wraps, s.kind == surface_torus)
            if clearance > 0.0:
                best = clearance
                best_u = u
                best_v = v
                cell_u = clearance / math.max(scale, nonzero) * 3.5
                cell_v = clearance * 3.5
        if best < 0.0: break
        # Next: a 7 x 7 grid over the cells about the best.
        cell_u = cell_u * 2.0 / 7.0
        cell_v = cell_v * 2.0 / 7.0
        from_u = best_u - cell_u * 3.0
        from_v = best_v - cell_v * 3.0
        columns = 7
        rows = 7
        _ = round
    if best < 0.0: error(invalid, "a face piece has no inside to classify")
    return try surface_point(work.w.surfaces.items[(usize)face.surface], Vector3(best_u, best_v, 0.0))

## A point inside the loops of `chart` (from `starts`; `scaled`, the same
## with u times `scale`) beside the middle of a boundary segment, stepped
## in from it by a fraction of the segment, the one farthest from every
## segment: its u, v and that clearance (-1: none found).
func beside_boundary(chart: const Vector3[], scaled: const Vector3[], starts: const usize[], scale: f64, wraps: bool, torus: bool) -> (f64, f64, f64):
    var best = -1.0
    var best_u = 0.0
    var best_v = 0.0
    for loop in 0..<starts.length - 1:
        let first = starts[loop]
        let last = starts[loop + 1]
        for k in first..<last:
            let a = scaled[k]
            let b = scaled[first if k + 1 == last else k + 1]
            let dx = b.x - a.x
            let dy = b.y - a.y
            let length = math.sqrt(dx * dx + dy * dy)
            if length <= 0.0: continue
            for fraction in beside_fractions:
                for side in [-1.0, 1.0]:
                    let step = length * fraction * side
                    let u = ((a.x + b.x) * 0.5 - dy / length * step) / scale
                    let v = (a.y + b.y) * 0.5 + dx / length * step
                    if chart_winding(chart, starts, u, v, wraps, torus) == 0: continue
                    let clearance = nearest_segment(scaled, starts, u * scale, v, best)
                    if clearance > best:
                        best = clearance
                        best_u = u
                        best_v = v
    return (best_u, best_v, best)

## The distance from (`u`, `v`) to the nearest segment of the loops of
## `points` (from `starts`), or a smaller one as soon as it is below
## `enough` (the candidate cannot win).
func nearest_segment(points: const Vector3[], starts: const usize[], u: f64, v: f64, enough: f64) -> f64:
    var nearest = 1.0e300
    let floor = enough * enough if enough > 0.0 else -1.0
    for loop in 0..<starts.length - 1:
        let first = starts[loop]
        let last = starts[loop + 1]
        for k in first..<last:
            let a = points[k]
            let b = points[first if k + 1 == last else k + 1]
            let dx = b.x - a.x
            let dy = b.y - a.y
            let length = dx * dx + dy * dy
            var t = 0.0
            if length > 0.0: t = math.clamp(((u - a.x) * dx + (v - a.y) * dy) / length, 0.0, 1.0)
            let ex = a.x + dx * t - u
            let ey = a.y + dy * t - v
            let d = ex * ex + ey * ey
            if d < nearest:
                nearest = d
                if nearest <= floor: return math.sqrt(nearest)
    return math.sqrt(nearest)

## What pieces are classified against: both solids' faces (their charts,
## for exact rays, and boxes), B-spline surfaces' Bezier patches, and
## each block's class once a ray found it.
struct Others:
    var charts: Charts
    var nets: Nets
    ## Where a ray's hit lies against an analytic face (face_lookup.lucb).
    var lookup: Lookup
    var lows: Growing[Vector3]
    var highs: Growing[Vector3]
    ## Each solid's box: [0] the first's, [1] the second's.
    var solid_low: Vector3[2]
    var solid_high: Vector3[2]
    ## Each solid's widest edge slack (a tolerant face lies that far off).
    var solid_slack: f64[2]
    ## Each piece's block, and each block's class (-1 not yet known).
    var block: Growing[usize]
    var block_class: Growing[i64]

    func close():
        self.charts.close()
        self.nets.close()
        self.lookup.close()
        self.lows.close()
        self.highs.close()
        self.block.close()
        self.block_class.close()

func new_others(work: const Work*) -> Others!:
    let w = &work.w
    var made = Others(try new_charts(w.faces.count), try new_nets(w.surfaces.count), try new_lookup(w), Growing[Vector3](), Growing[Vector3](),
                      [Vector3(1.0e300, 1.0e300, 1.0e300), Vector3(1.0e300, 1.0e300, 1.0e300)],
                      [Vector3(-1.0e300, -1.0e300, -1.0e300), Vector3(-1.0e300, -1.0e300, -1.0e300)], [0.0, 0.0], Growing[usize](), Growing[i64]())
    errdefer made.close()
    for f in 0..<w.faces.count:
        let (l, h) = try face_box(w, f)
        try made.lows.push(l)
        try made.highs.push(h)
        let k: usize = 0 if work.is_a(f) else 1
        let sl = made.solid_low[k]
        let sh = made.solid_high[k]
        made.solid_low[k] = Vector3(math.min(sl.x, l.x), math.min(sl.y, l.y), math.min(sl.z, l.z))
        made.solid_high[k] = Vector3(math.max(sh.x, h.x), math.max(sh.y, h.y), math.max(sh.z, h.z))
        for use in w.face_uses(f): made.solid_slack[k] = math.max(made.solid_slack[k], w.edge_slack_of(edge_index(use)))
    return made

## Pieces in blocks: pieces of one solid sharing an edge that keeps clear of
## the other solid's surfaces are on the same side of it, so one ray serves
## the block (OpenCASCADE's connexity blocks).
func find_blocks(work: const Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], others: Others*) -> !:
    let count = pieces.piece_count()
    others.block.clear()
    others.block_class.clear()
    for p in 0..<count:
        try others.block.push(p)
        try others.block_class.push(-1)
    # The first piece found using each final edge, per solid.
    let edges = traced.edges.count
    var seen = Growing[i64]()
    defer seen.close()
    for _ in 0..<edges * 2: try seen.push(-1)
    var clear = Growing[i64]()
    defer clear.close()
    for _ in 0..<edges: try clear.push(-1)
    for p in 0..<count:
        let solid: usize = 0 if work.is_a(piece_face[p]) else 1
        for c in pieces.piece_cycles(p):
            for use in pieces.cycle(c):
                let e = edge_index(use)
                if clear.items[e] < 0: clear.items[e] = 1 if try keeps_clear(work, traced, e, solid) else 0
                if clear.items[e] == 0: continue
                let other = seen.items[e * 2 + solid]
                if other < 0:
                    seen.items[e * 2 + solid] = (i64)p
                    continue
                let ra = union_root(others.block.items, p)
                let rb = union_root(others.block.items, (usize)other)
                if ra < rb: others.block.items[rb] = ra
                elif rb < ra: others.block.items[ra] = rb

## Whether final edge `e`'s middle is well clear of every surface of the
## solid other than `solid` (B-spline surfaces: never assumed).
func keeps_clear(work: const Work*, traced: const Shape*, e: usize, solid: usize) -> bool!:
    let edge = traced.edges.items[e]
    let middle = try traced.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
    let w = &work.w
    let first = work.faces_a if solid == 0 else 0
    let last = w.faces.count if solid == 0 else work.faces_a
    for f in first..<last:
        let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
        if s.kind == surface_spline: return false
        if surface_distance(s, middle) <= work.tol * 1000.0: return false
    return true

## Piece `p` of face `f` against the other solid.
func classify(work: Work*, traced: const Shape*, f: usize, pieces: const Pieces*, p: usize, others: Others*) -> i64!:
    # A face whose box misses the other solid's lies outside it.
    let other: usize = 1 if work.is_a(f) else 0
    # Tolerant faces (coincide.lucb) are as far apart as they may lie.
    let pad = math.max(work.tol * 10.0, math.max(others.solid_slack[0], others.solid_slack[1]))
    let l = others.lows.items[f]
    let h = others.highs.items[f]
    let ol = others.solid_low[other]
    let oh = others.solid_high[other]
    # Its block's, once known, unless its face lies on one of the other's
    # (then the piece itself decides). A point inside a piece of a face
    # with many holes is the costliest step here: found only when needed.
    let block = union_root(others.block.items, p)
    if l.x > oh.x + pad or l.y > oh.y + pad or l.z > oh.z + pad or ol.x > h.x + pad or ol.y > h.y + pad or ol.z > h.z + pad:
        # So is its block (pieces of a block lie on one side).
        others.block_class.items[block] = class_out
        return class_out
    var paired = false
    for pair in work.coincident.view(): paired = paired or pair.fa == f or pair.fb == f
    if not paired and others.block_class.items[block] >= 0: return others.block_class.items[block]
    let point = try piece_point(work, traced, f, pieces, p)
    for pair in work.coincident.view():
        let partner = pair.fb if pair.fa == f else (pair.fa if pair.fb == f else f)
        if partner == f: continue
        if try face_contains(&work.w, partner, point, work.tol) != outside:
            return class_same if pair.same else class_opposite
    if others.block_class.items[block] >= 0: return others.block_class.items[block]
    let class = try ray_class(work, f, point, others)
    others.block_class.items[block] = class
    return class

## Inside or outside the other solid at `point` (on face `f`), by rays.
func ray_class(work: Work*, f: usize, point: Vector3, others: Others*) -> i64!:
    # The other solid's faces.
    let first = work.faces_a if work.is_a(f) else 0
    let last = work.w.faces.count if work.is_a(f) else work.faces_a
    return class_in if try inside_faces(&work.w, &others.charts, &others.nets, first, last, point, work.size, &others.lookup) else class_out