Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.1

0.9.1 / src / trim_crossings.lucb

## Exact CAD-edge/grid-line crossings for layout reconciliation, and the
## parallel speculative pass that computes them ahead of the serial pass.
import memory
from luce_std import math
from luce_geocore.geocore import Vector3, invalid
from brep_types import Surface, Curve, BrepFace
from layout_types import Stations, GridLayout
from patch_sides import edge_index
from mapped_patch import parameter
from trim_chains import refreshed
from trim_memo import TrimMemo, memo_parameter, bits
from face_errors import FaceErrors
from luce_geocore.core import parallel

## Parameter on `edge` in [ta, tb] whose support chart coordinate `axis`
## equals `value`, by safeguarded bisection on inverse projections. Pure in
## its inputs, so `memo` may return an earlier identical call's result.
pub func intersection(s: Surface, edge: Curve, ta: f64, tb: f64, pa: Vector3, pb: Vector3, axis: usize, value: f64, tolerance: f64, epsilon: f64, memo: TrimMemo*? = none, edge_id: usize = 0) -> f64!:
    let table = memo else return try bisect(s, edge, ta, tb, pa, pb, axis, value, tolerance, epsilon)
    var key: u64[11]
    key[0] = 2
    key[1] = (u64)edge_id
    key[2] = bits(ta)
    key[3] = bits(tb)
    key[4] = bits(pa.x)
    key[5] = bits(pa.y)
    key[6] = bits(pb.x)
    key[7] = bits(pb.y)
    key[8] = (u64)axis
    key[9] = bits(value)
    key[10] = bits(pa.z) ^ (bits(pb.z) << 1)
    var failed = false
    if let found = table.find(key[..<11], &failed):
        if failed: error(invalid, "CAD edge/grid intersection did not converge")
        return found.x
    let t = bisect(s, edge, ta, tb, pa, pb, axis, value, tolerance, epsilon) catch failure:
        if failure.code == invalid: try table.put(key[..<11], Vector3(), true)
        error(failure.code, failure.message)
    try table.put(key[..<11], Vector3(t, 0.0, 0.0), false)
    return t

func bisect(s: Surface, edge: Curve, ta: f64, tb: f64, pa: Vector3, pb: Vector3, axis: usize, value: f64, tolerance: f64, epsilon: f64) -> f64!:
    var low = ta
    var high = tb
    var a = pa.x if axis == 0 else pa.y
    var b = pb.x if axis == 0 else pb.y
    let chord = (try edge.at(tb)).subtract(try edge.at(ta)).length()
    # Parameter error must also fit the physical snap budget. A short curved
    # trim with a tight CAD tolerance cannot use the same UV residual as a
    # metre-scale support with a loose modelling tolerance.
    let target = epsilon * 1e-5 if s.kind == 0 else math.min(epsilon * 0.1, tolerance * 0.01 * math.abs(b - a) / math.max(tolerance, chord))
    var seed = pa.add(pb).multiply_scalar(0.5)
    for step in 0..<32:
        let fraction = 0.5 if step % 4 == 3 else math.clamp((value - a) / (b - a), 0.05, 0.95)
        let t = low + (high - low) * fraction
        seed = try parameter(s, try edge.at(t), seed, tolerance)
        let p = seed.x if axis == 0 else seed.y
        if math.abs(p - value) < target: return t
        if (p < value) == (a < value):
            low = t
            a = p
        else:
            high = t
            b = p
    error(invalid, "CAD edge/grid intersection did not converge")

## Crossings of every trim segment with every interior grid line of `plan`,
## as reconcile enumerates them. With `speculative`, chains are previewed
## without being stored and results only fill `memo`.
pub func crossings_of(plan: const GridLayout*, face: BrepFace, s: Surface, vertices: const Vector3[], edges: const Curve[], cuts: const Stations[], tolerance: f64, memo: TrimMemo*) -> !:
    for use in 0..<face.uses.length:
        let index = edge_index(face.uses[use])
        let edge = edges[index]
        let chain = plan.chains[use]
        var owned = false
        var uv = chain.points
        if chain.points.length != cuts[index].count:
            let fresh = try refreshed(chain, s, vertices, edge, cuts[index], tolerance, memo = memo)
            free(fresh.times) in memory.heap
            uv = fresh.points
            owned = true
        defer:
            if owned: free(uv) in memory.heap
        let times = cuts[index].values
        let incidence = math.max(1e-13, plan.epsilon * 1e-5)
        for axis in 0..<(usize)2:
            let lines = plan.u if axis == 0 else plan.v
            let last = lines.count - 1
            for segment in 0..<uv.length - 1:
                let a = uv[segment].x if axis == 0 else uv[segment].y
                let b = uv[segment + 1].x if axis == 0 else uv[segment + 1].y
                let low = math.min(a, b) + incidence
                let high = math.max(a, b) - incidence
                var line = first_above(lines, low, last)
                while line < last:
                    let value = lines.values[line]
                    line += 1
                    if value >= high: break
                    _ = intersection(s, edge, times[segment], times[segment + 1], uv[segment], uv[segment + 1], axis, value, tolerance, plan.epsilon, memo, index) catch failure:
                        if failure.code != invalid: error(failure.code, failure.message)
                        recover 0.0

struct Speculation:
    let vertices: const Vector3[]
    let edges: const Curve[]
    let surfaces: const Surface[]
    let faces: const BrepFace[]
    let cuts: const Stations[]
    let plans: const GridLayout[]
    let memos: TrimMemo[]
    let wanted: const usize[]
    let tolerance: f64
    let errors: FaceErrors*

func speculate_item(raw: void*?, item: usize):
    let job = (Speculation*)(raw else return)
    let at = job.wanted[item]
    let face = job.faces[at]
    crossings_of(&job.plans[at], face, job.surfaces[(usize)face.surface], job.vertices, job.edges, job.cuts, job.tolerance, &job.memos[at]) catch failure:
        # A speculative failure is only a missing memo entry, except that an
        # exhausted allocator must not be ignored.
        if failure.code != invalid: job.errors.record(at, failure.code, failure.message)

## Fill each pending face's memo in parallel from the current shared cuts,
## before the serial reconcile pass that consumes it.
pub func speculate(vertices: const Vector3[], edges: const Curve[], surfaces: const Surface[], faces: const BrepFace[], cuts: const Stations[], plans: const GridLayout[], memos: TrimMemo[], tolerance: f64) -> !:
    let wanted = try new usize[faces.length] --- in memory.heap
    defer free(wanted) in memory.heap
    var count: usize = 0
    for at in 0..<faces.length:
        if not plans[at].valid: continue
        var revision: usize = 0
        for use in faces[at].uses: revision += cuts[edge_index(use)].count
        if revision == plans[at].seen: continue
        wanted[count] = at
        count += 1
    if count < 2: return
    var errors = try FaceErrors(faces.length)
    defer errors.close()
    var job = Speculation(vertices = vertices, edges = edges, surfaces = surfaces, faces = faces, cuts = cuts, plans = plans, memos = memos, wanted = wanted[..<count], tolerance = tolerance, errors = &errors)
    parallel.run(count, speculate_item, (void*)&job)
    try errors.raise()

## First index in 1..<last whose line lies strictly above `low` (else `last`).
pub func first_above(lines: Stations, low: f64, last: usize) -> usize:
    var lower: usize = 1
    var upper = last if last > 1 else 1
    while lower < upper:
        let middle = (lower + upper) // 2
        if lines.values[middle] > low: upper = middle
        else: lower = middle + 1
    return lower